I am presented with a problem as follows:

A listener is receiving messages with a wait time in between two consecutive messages that is exponentially distributed with a mean of 1 time unit. After any given message, there is a 1/2 chance that no further messages will be received. What is the mean and variance of the time until the final message is received?

Before considering the chance of no further messages arriving, the time taken until the nth message arrives seems to be modeled by a Gamma distribution with

$k=n, \theta=1$

This would mean the mean time until the nth message is $n$, and the variance is also $n$. But then there's the issue of the 1/2 chance of a message being the final message. This makes a geometric distribution for which message will be the final message, with a mean of $2$, and a variance of $(1-1/2)/(1/2)^2 = 2$, if I am not mistaken. The mean time until this final message would then be expected to be $n$ where $n=2$, ergo $2$, but how do I go about finding the variance in a situation like this?


One method is to find the distribution.

Let $N$ be the number of messages, which (as you have determined) has a geometric distribution with

$$\Pr(N=n) = 2^{-n},\ n=1, 2, 3, \ldots.$$

Conditional on $N$, you also have determined the distribution of the time $T$ to message $N:$ it is Gamma with parameter $N,$ given by

$$\Pr(T \le t\mid N=n) = \frac{1}{\Gamma(n)}\int_0^t x^{n-1}e^{-x}\mathrm{d}x$$

for $t\ge 0$ and $n=1, 2, 3, \ldots.$

Simply invoke the law of total probability by decomposing the event $T\le t$ into the union of disjoint events $T\le t, N=n:$

$$\eqalign{ \Pr(T\le t) &= \sum_{n=1}^\infty \Pr(T\le t\mid N=n)\Pr(N=n) \\ &= \sum_{n=1}^\infty 2^{-n} \frac{1}{\Gamma(n)}\int_0^t x^{n-1}e^{-x}\mathrm{d}x \\ &= \frac{1}{2}\int_0^t \left(\sum_{n=1}^\infty \frac{1}{(n-1)!} \left(\frac{x}{2}\right)^{n-1}\right)e^{-x}\mathrm{d}x \\ &= \int_0^t e^{x/2} e^{-x}\mathrm{d}\left(\frac{x}{2}\right) \\ &= 1 - e^{-t/2}. }$$

Now that the probability law of $T$ has been obtained, you may (easily) compute its mean and variance (or simply recognize it as a $\chi^2(2)$ variable and look up its properties).

As a quick check, here is an R simulation of $T$ involving a million independent messages (and therefore around half a million realizations of $T$). Its output is a histogram of the simulation on which the PDF $f(t) = \mathrm{d}/\mathrm{d}t(1-\exp(-t/2)) = \exp(-t/2)/2$ is graphed. The agreement between the two is excellent.

n <- 1e6
wait <- c(0, rexp(n))
terminate <- c(TRUE, runif(n) <= 1/2)
times <- diff(cumsum(wait)[terminate])

hist(times, freq=FALSE, breaks=200)
curve(exp(-x/2)/2, add=TRUE, lwd=2)

Figure of output

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.