3
$\begingroup$

Context

(Major edits) I am dealing with an expected value problem for a function

$$ g_s(D)=\textrm{max}\left\{0,D-y\right\} $$

of a discrete random variable $D$, where $y$ is a given (integer) scalar and $D$ follows a Negative Binomial distribution with known probability mass function (p.m.f):

$$ \begin{align} D \approx \textrm{Neg.Bin.}(\gamma,\alpha)\equiv\textrm{Pr}(D=d) &=\frac{(d+\gamma-1)!}{d!(\gamma-1)!}\alpha^d(1-\alpha)^\gamma \\ &=f_\gamma(d) \end{align} $$

For reasons that will become clearer later, I have highlighted the parameter $\gamma$ in the concise notation $f_{\gamma}(\cdot)$ for the p.m.f.; and will denote the corresponding Cumulative Density Function (CDF) as $F_\gamma(y)=\sum_{d=0}^y f_{\gamma}(d)$.

The expression of interest is the expected value of $g_s(D)$:

$$ E\left[g_s(D)\right]=\sum_{d=y+1}^\infty(d-y)f_\gamma(d) \tag{1}\label{lossfun} $$

Eq.\eqref{lossfun} is commonly referred to as "loss function" in the context of inventory control. (The sum in Eq.\eqref{lossfun} starts at $y+1$ because the case $y - D \geq 0$ is accounted for in a complementary expression for the "overage" or excess inventory, which I do not consider here).

Issue

I seem unable to obtain a correct expression for Eq.\eqref{lossfun} "from scratch" which can be reconciled with the solutions provided by the following references (both of which omit the detailed derivation):

  • Alternative 1: Eq. 36 in this reference suggests the following solution: $$ E\left[g_s(D)\right]=E[D]\left[1-F_{\gamma+1}(y-2)\right]-y\left[1-F_\gamma(y-1)\right]$$
  • Alternative 2: This other reference (Section C.2.3.6, p.452) gives the following expression, which is also mentioned in a different post: $$ E\left[g_s(D)\right]=-\left(y-\gamma\frac{\alpha}{1-\alpha}\right) \left[1-F_\gamma(y)\right]+(y+\gamma)\frac{\alpha}{1-\alpha}f_\gamma(y) $$

My derivation is shown next. Grateful for any help in understanding what's wrong with it, if anything (especially compared with Alternative 2)

Detailed derivation of loss function

Below, I develop Eq.\eqref{lossfun} to the best of my understanding:

$$\begin{align} E\left[g_s(D)\right] &= \sum_{d=y+1}^\infty df_\gamma(d)- y\sum_{d=y+1}^\infty f_\gamma(d) \tag{2}\label{e2}\\ &= \sum_{d=0}^\infty d\frac{(d+\gamma-1)!}{d!(\gamma-1)!}\alpha^{d}(1-\alpha)^\gamma - \sum_{d=1}^{y} d\frac{(d+\gamma-1)!}{d(d-1)!}\frac{\gamma}{\gamma!}\alpha\alpha^{d-1}(1-\alpha)^\gamma - y\left[1-F_\gamma(y)\right] \tag{3}\label{e3}\\ &= E\left[D\right] - \gamma\alpha \sum_{d=1}^y \frac{(d+\gamma-1)!}{(d-1)!\gamma!}\alpha^{d-1}(1-\alpha)^\gamma - y\left[1-F_\gamma(y)\right] \tag{4}\label{e4}\\ & = E\left[D\right] - E\left[D\right](1-\alpha)\sum_{z=\gamma}^{y+\gamma-1}\frac{z!}{(z-\gamma)!\gamma!}\alpha^{z-\gamma}(1-\alpha)^\gamma - y\left[1-F_\gamma(y)\right] \tag{5}\label{e5}\\ & = E\left[D\right]\left\{1-\sum_{z=\gamma+1}^{y+\gamma}\frac{(z-1)!}{\left[z-(\gamma+1)\right]!\gamma!}\alpha^{z-(\gamma+1)}(1-\alpha)^{\gamma+1}\right\}- y\left[1-F_\gamma(y)\right] \tag{6}\label{e6} \\ & = E\left[D\right]\left\{1-\sum_{z=\theta}^{y+\theta-1}\frac{(z-1)!}{(z-\theta)!(\theta-1)!}\alpha^{z-\theta}(1-\alpha)^{\theta}\right\}- y\left[1-F_\gamma(y)\right] \tag{7}\label{e7} \\ & = E\left[D\right]\left\{1-\sum_{d=0}^{y-1}\binom{d+\theta-1}{\theta-1}\alpha^{d}(1-\alpha)^{\theta}\right\}-y\left[1-F_\gamma(y)\right] \tag{8}\label{e8}\\ & = E\left[D\right]\left\{1-F_{\gamma+1}(y-1)\right\}-y\left[1-F_\gamma(y)\right] \tag{9}\label{e9} \end{align}$$

where $F_{\gamma+1}(\cdot)$ denotes the CDF of the Negative Binomial distribution having parameter $\gamma+1$.

More details on each step:

  • Eq.\eqref{e3}: the first sum is split as described here; also, $\sum_{d=y+1}^\infty f_\gamma(d)=1-F_\gamma(y)$ is the complementary CDF.
  • Eq.\eqref{e5}: I leverage the fact that the mean of the distribution can be expressed as $\frac{\gamma\alpha}{1-\alpha}$. Also, I make the substitution $z=d+\gamma-1$, after this example
  • Eq.\eqref{e6}: The sum index is shifted as described here
  • Eq.\eqref{e7}: I make the substitution $\theta=\gamma+1$
  • Eq.\eqref{e8}: I make the substitution $d = z-\theta$, after this example. This is meant to save space: in reality I should set $t=z-\theta=d-2$ and then apply the index shift rule again (add $-2$ to each bound), which yields the same result.

Next I compare my result with the selected references.

Comparative insights

My stab at a obtaining an expression for Eq.\eqref{lossfun} "from scratch" fails to replicate either reference exactly.

  • Eq.\eqref{e9} is comparable with, but not identical to Eq. 36 in this reference. However, I am satisfied I can see how Alternative 1 comes about, also thanks to personal communications with the author of the paper cited (this post has been refined several times in the absence of an answer).
  • I am genuinely struggling to reconcile my result with the second (quite authoritative) source, Their equation is not directly comparable with Eq.\eqref{e9}, and features one neat parameterisation of the p.m.f.- not two. This issue is discussed next.

To ease comparison with Eq.\eqref{e9} I further develop the expression in Alternative 2 as follows: $$ \begin{align} E\left[g_s(D)\right] &= -\left(y-\gamma\frac{\alpha}{1-\alpha}\right)\left[1-F_\gamma(y)\right]+(y+\gamma)\frac{\alpha}{1-\alpha}f_\gamma(y) \\ & = -\left(y-E\left[D\right]\right)\left[1-F_\gamma(y)\right]+\left[y\frac{\alpha}{1-\alpha}f_\gamma(y)+E[D]f_\gamma(y)\right] \\ &=E\left[D\right]\left\{1-\left[F_\gamma(y)-f_\gamma(y)\right]\right\}-y\left[1-F_\gamma(y)\right]+\frac{E\left[D\right]}{\gamma}yf_\gamma(y) \\ & = E\left[D\right]\left\{ 1 - \left[F_\gamma(y-1)-\frac{yf_\gamma(y)}{\gamma}\right]\right\}-y\left[1-F_\gamma(y-1)\right] \end{align} $$

Unless I have made a mistake somewhere, comparing the above with Eq.\eqref{e9} might suggest that: $$ F_{\gamma+1}(y-1)=\left[F_\gamma(y-1)-\frac{yf_\gamma(y)}{\gamma}\right] $$

which doesn't seem correct since:

$$ \begin{align} F_{\gamma+1}(y-1) & = \sum_{d=0}^{y-1}\binom{d+\theta-1}{\theta-1}\alpha^d(1-\alpha)^{\theta} \\ & = \sum_{d=0}^{y-1}\frac{(d+(\gamma+1)-1)!}{d!(\gamma+1)-1)!}\alpha^d(1-\alpha)^{\gamma+1} \\ & = \frac{1-\alpha}{\alpha}\sum_{d=0}^{y-1}\frac{(d+1)\left((d+1)+\gamma-1\right)!}{\gamma(d+1)!(\gamma-1)!}\alpha^{d+1}(1-\alpha)^{\gamma} \\ & = \frac{1-\alpha}{\gamma\alpha}\sum_{d=0}^{y-1}(d+1)f_\gamma(d+1) \\ & =\frac{1-\alpha}{\gamma}\sum_{d=0}^{y-1}(d+\gamma)f_\gamma(d) \\ & = (1-\alpha)\left[F_\gamma(y-1)+\frac{1}{\gamma}\sum_{d=0}^{y-1}df_\gamma(d)\right] \\ & =(1-\alpha)\left[F_\gamma(y-1)-\frac{yf_\gamma(y)}{\gamma}+\frac{1}{\gamma}\sum_{d=0}^{y}df_\gamma(d)\right] \end{align} $$

This is as far as I get, but would be nice to be able to reconcile the last result, or at least figure out what I am doing wrong.

$\endgroup$
4
  • 1
    $\begingroup$ You seem to be using what Wikipedia calls alternative formulation 4 for the negative binomial. It looks as if the linked paper may also be doing this. Would its expression and yours be the same if $y=r-2$? $\endgroup$ Commented Jun 13 at 1:37
  • $\begingroup$ @Henry I've thought a bit more about what you wrote and I now realise I forgot that, after my subtitutions, I was no longer working in the variable $d$ but $t=d-2$ hence the two CDFs in my last equation were in fact underpinned by different indexes. $\endgroup$ Commented Jun 16 at 9:40
  • 1
    $\begingroup$ @DrEti. Would the derivtion work if you start the summation from $d=y$? $\endgroup$ Commented Jun 17 at 9:03
  • $\begingroup$ @bob Indeed it should, and that's the only reason for discrepancy left I can think of. The post has been updated few times (in the absence of a formal "fix" to the initial issue), and the discrepancy now might appear trivial $\endgroup$ Commented Jun 17 at 14:05

3 Answers 3

Reset to default
1
+50
$\begingroup$

I added a proof for $$ F_{\gamma+1}(y-1)=\left[F_\gamma(y-1)-\frac{yf_\gamma(y)}{\gamma}\right] $$ since I think this is what you want to prove.

You've got $$E\left[g_s(D)\right]=E\left[D\right]\left\{1-F_{\gamma+1}(y-1)\right\}-y\left[1-F_\gamma(y)\right]$$

I think this is correct.

You wrote "I need to know what I am doing wrong", so I'm going to add an explanation about this.

I don't think you are wrong.

You wrote

$$ F_{\gamma+1}(y-1)=\left[F_\gamma(y-1)-\frac{yf_\gamma(y)}{\gamma}\right] $$

This is correct.

So, what you want to know should be how to prove this.

In the following, let us prove this by using the idea of telescoping sum.

Proof :

We have $$\begin{align}&F_{\gamma+1}(y-1)-F_\gamma(y-1) \\\\&=\sum_{d=0}^{y-1}\binom{d+\gamma}{d}\alpha^d(1-\alpha)^{\gamma +1}-\sum_{d=0}^{y-1}\binom{d+\gamma-1}{d}\alpha^d(1-\alpha)^{\gamma} \\\\&=\sum_{d=\color{red}1}^{y-1}\binom{d+\gamma}{d}\alpha^d(1-\alpha)^{\gamma +1}-\sum_{d=\color{red}1}^{y-1}\binom{d+\gamma-1}{d}\alpha^d(1-\alpha)^{\gamma}+(1-\alpha)^{\gamma+1}-(1-\alpha)^{\gamma} \\\\&=\sum_{d=1}^{y-1}\bigg[\binom{d+\gamma}{d}\alpha^d(1-\alpha)^{\gamma}-\binom{d+\gamma-1}{d}\alpha^d(1-\alpha)^{\gamma}-\binom{d+\gamma}{d}\alpha^{d+1}(1-\alpha)^{\gamma}\bigg]+(1-\alpha)^{\gamma+1}-(1-\alpha)^{\gamma} \\\\&=\sum_{d=1}^{y-1}\bigg[\binom{d+\gamma-1}{d-1}\alpha^d(1-\alpha)^{\gamma}-\binom{d+\gamma}{d}\alpha^{d+1}(1-\alpha)^{\gamma}\bigg]+(1-\alpha)^{\gamma+1}-(1-\alpha)^{\gamma} \\\\&=\sum_{d=1}^{y-1}\bigg(G(d)-G(d+1)\bigg)+(1-\alpha)^{\gamma+1}-(1-\alpha)^{\gamma}\end{align}$$ where $$G(d):=\binom{d+\gamma-1}{d-1}\alpha^d(1-\alpha)^{\gamma}$$

So, using the idea of telescoping sum, we get $$\begin{align}&\sum_{d=1}^{y-1}\bigg(G(d)-G(d+1)\bigg)+(1-\alpha)^{\gamma+1}-(1-\alpha)^{\gamma} \\\\&=G(1)-G(y)+(1-\alpha)^{\gamma+1}-(1-\alpha)^{\gamma} \\\\&=\binom{\gamma}{0}\alpha(1-\alpha)^{\gamma}-\binom{y+\gamma-1}{y-1}\alpha^y(1-\alpha)^{\gamma}+(1-\alpha)^{\gamma+1}-(1-\alpha)^{\gamma} \\\\&=-\binom{y+\gamma-1}{y-1}\alpha^y(1-\alpha)^{\gamma} \\\\&=-\frac{yf_\gamma(y)}{\gamma}.\ \blacksquare\end{align}$$

In the following, let us prove by induction on $y$ that what you got is equal to the the expression written in Alternative 2 : $$E\left[D\right]\left\{1-F_{\gamma+1}(y-1)\right\}-y\left[1-F_\gamma(y)\right]=-\left(y-\gamma\frac{\alpha}{1-\alpha}\right) \left[1-F_\gamma(y)\right]+(y+\gamma)\frac{\alpha}{1-\alpha}f_\gamma(y)\tag{10}$$

Here, $(10)$ is equivalent to

$$F_{\gamma+1}(y-1)-F_\gamma(y)+\frac{y+\gamma}{\gamma}f_\gamma(y)=0$$

i.e.

$$\sum_{d=0}^{y-1}\binom{d+\gamma}{d} \alpha^d(1-\alpha)^{\gamma+1}-\sum_{d=0}^y\binom{d+\gamma-1}{d} \alpha^d(1-\alpha)^\gamma+\frac{y+\gamma}{\gamma}\binom{y+\gamma-1}{y}\alpha^y(1-\alpha)^\gamma=0$$

i.e.

$$\underbrace{\sum_{d=0}^{y-1}\binom{d+\gamma}{d} \alpha^d(1-\alpha)}_{A(y)}-\underbrace{\sum_{d=0}^y\binom{d+\gamma-1}{d} \alpha^d}_{B(y)}+\underbrace{\binom{y+\gamma}{y}\alpha^y}_{C(y)}=0\tag{11}$$

We see that $(10)$ is equivalent to $(11)$, so, in the following, let us prove $(11)$ by induction on $y$.

For $y=1$, $(11)$ holds.

Suppose that $(11)$ holds for $y$.

Then, we have $$\begin{align}&A(y+1)-B(y+1)+C(y+1) \\\\&=A(y+1)-B(y+1)+C(y+1)-(A(y)-B(y)+C(y)) \\\\&=(A(y+1)-A(y))-(B(y+1)-B(y))+(C(y+1)-C(y)) \\\\&=\color{red}{\binom{y+\gamma}{y}\alpha^y(1-\alpha)}-\binom{y+1+\gamma-1}{y+1}\alpha^{y+1}+\binom{y+1+\gamma}{y+1}\alpha^{y+1}\color{red}{-\binom{y+\gamma}{y}\alpha^y} \\\\&=\color{red}{-\binom{y+\gamma}{y}\alpha^{y+1}}-\binom{y+\gamma}{y+1}\alpha^{y+1}+\binom{y+\gamma+1}{y+1}\alpha^{y+1} \\\\&=\alpha^{y+1}\bigg(-\binom{y+\gamma}{y}-\binom{y+\gamma}{y+1}+\binom{y+\gamma+1}{y+1}\bigg) \\\\&=0.\ \blacksquare\end{align}$$

$\endgroup$
2
  • 1
    $\begingroup$ Thank you @mathlove for the thorough and insightful answer, I do appreciate. Introducing the notion of telescopic sum, in particular, was indeed very helpful. $\endgroup$ Commented Jun 21 at 15:11
  • $\begingroup$ @Ettore S : You are welcome. I am glad to hear that. $\endgroup$ Commented Jun 21 at 15:24
1
$\begingroup$

So you got

$$ E\left[D\right]\left\{1-F_{\gamma+1}(y-1)\right\}-y\left[1-F_\gamma(y)\right]$$

which IS identical to eq. 36 in your first reference:

$$E\left[D\right]\left\{1-F_{\gamma+1}(y-1)\right\}-y\left[1-F_\gamma(y)\right] $$ $$= E\left[D\right]\left\{1-F_{\gamma+1}(y-1)\right\}-y\left[1-F_\gamma(y-1)\right] + yf_\gamma\left(y\right)$$ $$ = E\left[D\right]\left\{1-F_{\gamma+1}(y-1)\right\}-y\left[1-F_\gamma(y-1)\right] + \frac{\left(y+\gamma-1\right)!}{\left(\gamma-1\right)!\left(y-1\right)!}(1-\alpha)^\gamma \alpha^y$$

Dividing the third term with $\frac{\gamma\alpha}{1-\alpha}\left(=E\left[D\right]\right)$ leads to

$$=\frac{\left(y+\gamma-1\right)!}{\gamma!\left(y-1\right)!}(1-\alpha)^{\gamma+1} \alpha^{y-1}$$ $$ =\binom{y-1+\gamma}{\gamma}(1-\alpha)^{\gamma+1} \alpha^{y-1} $$ $$ = f_{\gamma+1}(y-1).$$

You can thus rewrite your equation as eq.36 from the first reference:

$$ E\left[D\right]\left\{1-F_{\gamma+1}(y-2)\right\}-y\left[1-F_\gamma(y-1)\right].$$

Then to link the expression of yours to the second reference, you can use induction or calculate directly. The left hand term of your expression is

$$\frac{\gamma\alpha}{(1-\alpha)}\left[1-F_{\gamma+1}(y-1)\right]$$ We can manipulate this (also using the proof of mathlove):

$$ = \frac{\gamma\alpha}{(1-\alpha)}\left[1-\left(F_{\gamma}(y-1)-\frac{y}{\gamma}f_\gamma(y)\right)\right]$$ $$ = \frac{\gamma\alpha}{(1-\alpha)}\left[1-F_{\gamma}(y)+f_{\gamma}(y)+\frac{y}{\gamma}f_\gamma(y)\right]$$ $$ = \frac{\gamma\alpha}{(1-\alpha)} - \frac{\gamma\alpha}{(1-\alpha)}F_{\gamma}(y) +\frac{\gamma\alpha}{(1-\alpha)}f_{\gamma}(y) + \frac{y\alpha}{(1-\alpha)}f_{\gamma}(y),$$

ending up with: $$=\frac{\gamma\alpha}{(1-\alpha)}\left(1-F_{\gamma}(y)\right) + f_{\gamma}(y)\frac{\alpha}{(1-\alpha)}\left(\gamma + y\right).$$

taking the right hand term of your expression in, you end up with

$$\frac{\gamma\alpha}{(1-\alpha)}\left(1-F_{\gamma}(y)\right) + f_{\gamma}(y)\frac{\alpha}{(1-\alpha)}\left(\gamma + y\right)-y\left(1-F_{\gamma}(y)\right)$$ $$=-\left(y-\frac{\gamma\alpha}{(1-\alpha)}\right)\left(1-F_{\gamma}(y)\right) + f_{\gamma}(y)\frac{\alpha}{(1-\alpha)}\left(\gamma + y\right),$$

which is the expression from your second reference.

$\endgroup$
1
  • 1
    $\begingroup$ Many thanks @Steven01123581321 as you know I am already indebted to you for the great feedback and help. I really like how you addressed the reconciliation with the first reference, that's incredibly helpful. For the second reference I do agree with you that's how Zipkin's equation comes about - yet my issue was that I couldn't see how $F_\gamma(y-1)-\frac{yf(y)}{\gamma}=F_{\gamma+1}(y-1)$, which is where the other comment really helped. I wish I had made one post for each reference: you perfectly answered my earlier query about reference 1. It's a pity I expanded it. $\endgroup$ Commented Jun 21 at 15:34
0
$\begingroup$

Following the excellent answers already received, I thought I'd add my two pennies' worth as some sort of "lesson learned" from them. (Posting as an answer to avoid further edits to my own post).

What the answers received made me realise is that I stopped too early when trying to satisfy myself that, as the answers pointed out, it is indeed the case that:

$$ F_{\gamma+1}(y-1)=\left[F_\gamma(y-1)-\frac{yf_\gamma(y)}{\gamma}\right] $$

Specifically, in the original post I got this far:

\begin{align} F_{\gamma+1}(y-1) & =(1-\alpha)\left[F_\gamma(y-1)-\frac{yf_\gamma(y)}{\gamma}+\frac{1}{\gamma}\sum_{d=0}^{y}df_\gamma(d)\right] \end{align}

and mistakenly assumed something went wrong because this intermediate solution happened to contain the solution I was seeking. Had I not given up I would have obtained:

\begin{align} F_{\gamma+1}(y-1) & =(1-\alpha)\left[F_\gamma(y-1)-\frac{yf_\gamma(y)}{\gamma}+\sum_{d=0}^{y}\frac{df_\gamma(d)}{\gamma}\right] \\ & = F_\gamma(y-1)-\alpha F_\gamma(y-1)+\left[\sum_{d=0}^{y-1}\frac{df_\gamma(d)}{\gamma}\right]-\alpha\left[\sum_{d=0}^{y-1}\frac{df_\gamma(d)}{\gamma}\right] \\ & = F_\gamma(y-1) - \sum_{d=0}^{y-1}\frac{d+1}{d+\gamma}f_\gamma(d+1)+\sum_{d=0}^{y-1}\frac{d}{\gamma}f_\gamma(d)-\sum_{d=0}^{y-1}\frac{d(d+1)}{\gamma(d+\gamma)}f_\gamma(d+1) \\ & = F_\gamma(y-1) +\sum_{d=0}^{y-1}\frac{d}{\gamma}f_\gamma(d) - \sum_{d=1}^{y}\left[\frac{1}{(\gamma+d-1)}+\frac{(d-1)}{\gamma(\gamma+d-1)}\right]df_\gamma(d) \\ & = F_\gamma(y-1) + \left[\sum_{d=0}^{y-1}\frac{d}{\gamma}f_\gamma(d) - \sum_{d=1}^{y} \frac{d}{\gamma}f_\gamma(d) \right] \\ & = F_\gamma(y-1) + \left[ \sum_{d=1}^{y-1} \frac{d}{\gamma}f_\gamma(d) + \frac{0}{\gamma}f_\gamma(0) - \sum_{d=1}^{y-1} \frac{d}{\gamma}f_\gamma(d) - \frac{y}{\gamma}f_\gamma(y)\right] \\ & = F_\gamma(y-1) - \frac{y}{\gamma}f_\gamma(y) \end{align}

where the notion of telescopic sum mentioned in one of the previous answeres comes indeed handy towards the end.

$\endgroup$

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.