Expected sum of exponential variables until two of them sum to a threshold

Solution 1:

To apply one-step analysis, we need to keep track of the value $X$ last added, that is, we need to set up an equation for $E[S\mid X=x]$, where $S$ is the expected sum of the terms yet to come.

The next value makes an expected contribution $\frac1\lambda$ to the sum. Then with density $\lambda\mathrm e^{-\lambda r}$ for $0\le r\le\tau-x$ we add another expected $E[S\mid X=r]$. Thus

$$ E[S\mid X=x]=\frac1\lambda+\int_0^{\tau-x}\lambda\mathrm e^{-\lambda r}E[S\mid X=r]\mathrm dr\;. $$

Differentiating with respect to $x$ yields (with the prime denoting differentiation with respect to $x$)

$$ E'[S\mid X=x]=-\lambda\mathrm e^{-\lambda(\tau-x)}E[S\mid X=\tau-x]\;. $$

After a lot of fiddling around with exponential trial functions, the solution of this equation is found to be

$$ E[S\mid X=x]=\frac1N\left(\frac1{\sqrt{\mu_+}}\mathrm e^{\mu_+\left(x-\frac\tau2\right)}-\frac1{\sqrt{\mu_-}}\mathrm e^{\mu_-\left(x-\frac\tau2\right)}\right)\;, $$

where

$$ \mu_\pm=\frac\lambda2\left(1\pm\sqrt{1-4\mathrm e^{-\lambda\tau}}\right) $$

and the normalisation factor $N$ is determined by the boundary condition $E[S\mid X=\tau]=\frac1\lambda$ to be

$$ N=\lambda\left(\frac1{\sqrt{\mu_+}}\mathrm e^{\mu_+\frac\tau2}-\frac1{\sqrt{\mu_-}}\mathrm e^{\mu_-\frac\tau2}\right)\;. $$

Since we add a second term even if the first one is greater than $\tau$ (with probability $\mathrm e^{-\lambda\tau}$), the desired expected value $E[S]$ of the sum is given by

$$ E[S]=E[S\mid X=0]+\frac{\mathrm e^{-\lambda\tau}}\lambda\;. $$

Substituting $x=0$ and simplifying leads to

$$ E[S]=\frac{\mathrm e^{-\lambda\tau}}\lambda\left(\frac{\xi\mathrm e^{\frac{\lambda\tau}2}+2\sin\frac{\xi\lambda\tau}2}{\xi\cos\frac{\xi\lambda\tau}2-\sin\frac{\xi\lambda\tau}2}+1\right)\;, $$

where $\xi=\sqrt{4\mathrm e^{-\lambda\tau}-1}$, in the case $\mathrm e^{\lambda\tau}\lt4$, and

$$ E[S]=\frac{\mathrm e^{-\lambda\tau}}\lambda\left(\frac{\zeta\mathrm e^{\frac{\lambda\tau}2}+2\sinh\frac{\zeta\lambda\tau}2}{\zeta\cosh\frac{\zeta\lambda\tau}2-\sinh\frac{\zeta\lambda\tau}2}+1\right)\;, $$

where $\zeta=\sqrt{1-4\mathrm e^{-\lambda\tau}}$, in the case $\mathrm e^{\lambda\tau}\gt4$. In the boundary case $\mathrm e^{\lambda\tau}=4$, applying L'Hôpital to either expression yields

$$ E[S]=\frac1{4\lambda}\frac{3+\log2}{1-\log2}\;. $$

Here's a plot of $\lambda E[S]$ as a function of $\lambda\tau$, with the boundary case $\mathrm e^{\lambda\tau}=4$ halfway along the horizontal axis:

Here's the code I used to draw the graph and to check the result by simulation.

Two limiting cases: For small $\lambda\tau$,

$$ E[S]=\frac1\lambda\left(2+\frac12(\lambda\tau)^2+O\left((\lambda\tau)^3\right)\right)\;, $$

in agreement with the fact that we always add at least two terms and the probability for adding a third term is approximately $\frac12(\lambda\tau)^2$.

And for large $\lambda\tau$,

$$ E[S]=\frac1\lambda\left(\frac{\mathrm e^{\lambda\tau}}{\lambda\tau-1}+O(1)\right)\;, $$

which should be compared to the estimate

$$ E[S]\approx\frac1\lambda\left(\frac{\mathrm e^{\lambda\tau}}{\lambda\tau+1}\right) $$

that results from estimating the expected number of terms by the reciprocal of the probability of a given pair of terms terminating the process; the correlations between adjacent pairs lead to the actual result being slightly higher (with $-1$ instead of $+1$ in the denominator).

Here's a plot up to $\lambda\tau=6$ with these two approximations shown in green: