Exponential Distribution & Poisson: Example 5.10 Suppose that customers are in line to receive service

Solution 1:

Denote $E_n$ as the event that the $n^{\text{th}}$ customer in line gets served and $X\sim \text{Exponential}(\mu)$ as the service time of the individual who is initially being served. We consider $\mathbb{P}(E_n|X=x)$ for $x\geq 0$ fixed.

If $N_x$ indicates the number of individuals ahead of the $n^{\text{th}}$ customer who left the line while the initial customer was being served on $[0,x)$, then $N_x\sim \text{Binomial}(n-1,1-e^{-\theta x})$ and $$\mathbb{P}(E_n|X=x)=\sum_{k=0}^{n-1}\mathbb{P}(E_n|X=x,N_x=k)\mathbb{P}(N_x=k|X=x)$$ Since the exponential distribution is memoryless we can say $$ \mathbb{P}(E_n|X=x,N_x=k)=e^{-\theta x}P_{n-k-1} \text{ for } k\in \{0,1,...,n-2\} \\ \mathbb{P}(E_n|X=x,N_x=n-1)=e^{-\theta x} $$ By prescribing $P_0 = 1 $ we can condense the aforementioned equations into one relationship. $$\mathbb{P}(E_n|X=x,N_x=k)=e^{-\theta x}P_{n-k-1}$$ Therefore $$\begin{eqnarray*}\mathbb{P}(E_n|X=x)&=&\sum_{k=0}^{n-1}e^{-\theta x}P_{n-k-1}\cdot {n-1 \choose k}(1-e^{-\theta x})^k(e^{-\theta x})^{n-k-1} \\ &=& \sum_{k=0}^{n-1}P_{n-k-1}{n-1 \choose k}(1-e^{-\theta x})^k(e^{-\theta x})^{n-k}\end{eqnarray*}$$ From total law of probability, $$\begin{eqnarray*} P_n&=&\mathbb{P}(E_n) \\ &=& \int_0^{\infty}\mathbb{P}(E_n|X=x)f_{X}(x)\mathrm{d}x \\ &=& \sum_{k=0}^{n-1} \mu P _{n-k-1} {n-1 \choose k} \int_0^{\infty} (1-e^{-\theta x})^k (e^{-\theta x})^{n-k}e^{-\mu x}\mathrm{d}x\end{eqnarray*}$$ Enforce $x \mapsto e^{-\theta x}$ to see how $$\begin{eqnarray*}\int_0^{\infty} (1-e^{-\theta x})^k (e^{-\theta x})^{n-k}e^{-\mu x}\mathrm{d}x &=& \frac{1}{\theta} \int_0^1 x^{n-k+\frac{\mu}{\theta}-1}(1-x)^k \mathrm{d}x \\ &=& \frac{\Gamma(n-k+\mu / \theta) \Gamma(k+1)}{\theta \Gamma(n+\mu / \theta+1)} \\ &=& \frac{(n-k+\mu / \theta-1)! k!}{\theta (n + \mu / \theta)!} \end{eqnarray*} $$ So now we can write $$P_n=\frac{\mu}{\theta}\cdot \sum_{k=0}^{n-1} {n-1 \choose k}\frac{(n-k+\mu / \theta-1)! k!}{ (n + \mu / \theta)!}P_{n-k-1}$$ Shift the index and do a bit of algebra to get $$P_n=\frac{\mu}{n\theta + \mu }\cdot \sum_{k=0}^{n-1}{n-1 \choose k}\frac{(n-k-1)!(k+\mu / \theta)!}{(n+ \mu / \theta-1)!}P_k$$ Let's apply this recursive formula to establish a formula for $P_n$. Plugging in $n=1$ yields $$P_1=\frac{\mu}{\theta+\mu} P_0 = \frac{\mu}{\theta +\mu}$$ Plug in $n=2$ to obtain $P_2:$ $$\begin{eqnarray*}P_2 &=& \frac{\mu}{2\theta + \mu} \cdot \sum_{k=0}^1 {1 \choose k}\frac{(1-k)!(k+\mu / \theta)!}{(\mu / \theta+1)!}P_k \\ &=& \frac{\mu}{2 \theta + \mu} \Bigg[\frac{(\mu/\theta)!}{(1+\mu/\theta)!}P_0+P_1\Bigg] \\ &=& \frac{\mu}{2\theta + \mu}\cdot \Bigg[\frac{1}{1+\mu/\theta}+ \frac{\mu}{\theta + \mu}\Bigg] \\ &=& \frac{\mu}{2\theta + \mu}\end{eqnarray*}$$ Now take $n=3$ to see $$\begin{eqnarray*}P_3 &=& \frac{\mu}{3\theta + \mu}\sum_{k=0}^2{2 \choose k}\frac{(2-k)!(k+\mu / \theta)!}{(2+\mu / \theta)!}P_k\\ &=& \frac{\mu}{3\theta + \mu}\Bigg[\frac{2!(\mu/\theta)!}{(2+\mu/\theta)!}P_0+{2 \choose 1}\frac{(1+\mu/\theta)!}{(2+\mu/\theta)!}P_1 + P_2\Bigg] \\ &=& \frac{\mu}{3\theta + \mu}\cdot \Bigg[\frac{2}{(\mu/\theta +2)(\mu/\theta +1)} + \frac{2\mu}{(\mu + \theta)(2+\mu/\theta)}+\frac{\mu}{2\theta + \mu}\Bigg] \\ &=& \frac{\mu}{3\theta + \mu}\end{eqnarray*}$$ You should now see how $P_n=\frac{\mu}{n\theta + \mu}$.

For part $(b)$ take $T_n$ as the time the $n^{\text{th}}$ customer waits in line. Similar to $(a)$, we'll first consider $\mathbb{E}(T_n|E_n,X=x)$. We get $$\mathbb{E}(T_n|E_n,X=x)=\sum_{k=0}^{n-1}\mathbb{E}(T_n|E_n,X=x,N_x=k)\mathbb{P}(N_x=k|E_n,X=x)$$ Since the exponential distribution is memoryless, $$\mathbb{E}(T_n|E_n,X=x,N_x=k)=x+W_{n-k-1}$$ where $W_j=\mathbb{E}(T_j|E_j)$ with $W_0=0$. Therefore, $$\begin{eqnarray*}\mathbb{E}(T_n|E_n,X=x)&=&\sum_{k=0}^{n-1}\big(W_{n-k-1}+x\big)\mathbb{P}(N_x=k|E_n,X=x) \\ &=& \sum_{k=0}^{n-1}x\mathbb{P}(N_x=k|E_n,X=x)+\sum_{k=0}^{n-1}W_{n-k-1}\mathbb{P}(N_x=k|E_n,X=x) \\ &=& x+ \sum_{k=0}^{n-1} {n-1 \choose k}\big(1-e^{-\theta x}\big)^k\big(e^{-\theta x}\big)^{n-k-1}W_{n-k-1} \\ &=& x+\sum_{k=0}^{n-1}{n-1 \choose k}\big(e^{-\theta x}\big)^k\big(1-e^{-\theta x}\big)^{n-k-1}W_k \end{eqnarray*}$$ Using total law of expectation, $$\begin{eqnarray*}W_n &=& \int_0^{\infty}\mathbb{E}(T_n|E_n,X=x)f_{X}(x)\mathrm{d}x \\ &=& \int_0^{\infty}xf_{X}(x)\mathrm{d}x +\mu \sum_{k=0}^{n-1}{n-1 \choose k}W_k \int_0^{\infty}\big(e^{-\theta x}\big)^k\big(1-e^{-\theta x}\big)^{n-k-1}e^{-\mu x}\mathrm{d}x \\ &=& \frac{1}{\mu}+\frac{\mu}{\theta}\sum_{k=0}^{n-1} \frac{(k+\mu/\theta -1)! (n-k-1)!}{(n+\mu/\theta-1)!}{n-1 \choose k}W_k\end{eqnarray*}$$ After computing a few terms you will be able to deduce that $$W_n=\frac{1}{\mu}+\frac{1}{\mu + \theta}+ \dots + \frac{1}{\mu + (n-1)\theta}$$