At time $t = 0$, I place $N$ coins on a table heads-up. For each coin $c_i$ I randomly sample a value $x_i$ from an exponential distribution with rate $\lambda$, and let this be the time before the coin is flipped to be tails-up (a permanent state). If I'm not mistaken, the probability distribution for the time until all coins are tails up should be Erlang distributed (with parameters $k = N$ and $\lambda$).

Now, I sample a single value $r_k$ from a uniform distribution for all times $t = [0, T]$, where $T$ is the first time at which all coins are tails-up. I then reset the entire system by turning the time to $t = 0$ and flipping all of the coins to the heads-up state.

If I repeat the above procedure an arbitrarily large number of times, what probability distribution do I have for values of $r_k$?

NOTE - I am mistaken about the Erlang distribution. "heropup" makes the comment, which I agree with now, that the time until all the coins are "tails-up" is going to be $max(x_i)$ (i.e. the maximum value of the $N$ iid exponentially distributed variables) rather than the sum of $N$ iid exponentially distributed variables (which is given be the Erlang distribution).

The question now reduces to the following:

If we randomly sample a value $v_i$ from the PDF for $T$ (given by heropup as: $f_T(t) = n \lambda e^{-\lambda t} (1-e^{-\lambda t})^{n-1}, \quad t \ge 0$), and then sample a single value $r_i$ from a uniform distribution $r_i \in [0, v]$, then repeat this process for an arbitrary number of pairs of $v_i$ and $r_i$, what PDF do we have for the $r_i$? Note again that we only ever sample one $r_i$ for some $v_i$ sampled from the PDF for $T$.

  • $\begingroup$ Are you sure about your Erlang claim? While the sum of exponentials is gamma distributed, you are dealing with the maximum of exponentials... $\endgroup$ – soakley Feb 26 '14 at 18:43

I do not agree with your interpretation for the first part. The distribution for the time until all coins are tails up is the distribution of the maximum order statistic, because the process of coin flipping is not serial, but parallel. That is to say, if $T$ is the random time until the last coin is flipped, then $T = \max_i x_i$, not $T = \sum_{i=1}^n x_i$, unless you mean to say that the time until the next coin $c_i$ is flipped tails is measured from the point where the previous coin $c_{i-1}$ was flipped.

If we go with your statement of the question as it is posed, then the distribution of $T$ has PDF $$ f_T(t) = n \lambda e^{-\lambda t} (1-e^{-\lambda t})^{n-1}, \quad t \ge 0.$$

The distribution of $R \mid T \sim {\rm Uniform}(0,T)$, so it follows that $$f_R(r) = \int_{t=r}^\infty f_{R \mid T}(r) f_T(t) \, dt,$$ where $f_{R \mid T}(r) = \frac{1}{T}$, and $f_T(t)$ was found previously. Hence $$f_R(r) = n\lambda \int_{t=r}^\infty \frac{e^{-\lambda t}}{t} (1-e^{-\lambda t})^{n-1} \, dt.$$ As far as I am aware, this integral does not have an elementary closed-form solution. We can calculate $${\rm E}[R] = {\rm E}[{\rm E}[R \mid T]] = {\rm E}[T/2] = \frac{H_n}{2\lambda},$$ where $H_n$ is the $n^{\rm th}$ harmonic number. We can also calculate $$\begin{align*} {\rm Var}[R] &= {\rm Var}[{\rm E}[R \mid T]] + {\rm E}[{\rm Var}[R \mid T]] \\ &= {\rm Var}[T/2] + {\rm E}[T^2/12] \\ &= {\rm E}[T^2/4] - ({\rm E}[T/2])^2 + {\rm E}[T^2/12] \\ &= \frac{{\rm E}[T^2]}{3} - \frac{H_n^2}{4\lambda^2} \\ &= (6\lambda)^{-2} (2\pi^2 + 3 H_n^2 - 12 \psi'(n+1)), \end{align*}$$ where $$\psi'(z) = \int_{t=0}^\infty \frac{t e^{-zt}}{1-e^{-t}} \, dt = \sum_{k=0}^\infty \frac{1}{(z+k)^2}$$ is the polygamma (trigamma in this case) function.

  • $\begingroup$ Thanks! Is there a name for this distribution? $\endgroup$ – user131681 Feb 26 '14 at 18:49
  • $\begingroup$ Also, see my update for the original posting. I have noted my error. $\endgroup$ – user131681 Feb 26 '14 at 18:50
  • $\begingroup$ If there is, I don't know it: I would just call it the maximum order statistic of $n$ IID exponential($\lambda$) random variables. $\endgroup$ – heropup Feb 26 '14 at 18:50
  • $\begingroup$ Ok, I've isolated my confusion. Why are we computing $f_R(r) = n\lambda \int_{t=r}^\infty \frac{e^{-\lambda t}}{t} (1-e^{-\lambda t})^{n-1} \, dt$ instead of a simple product $f_{R \mid T}(r) \times f_T(t)$? Shouldn't the simple product yield the joint density function? $\endgroup$ – user131681 Feb 27 '14 at 3:03
  • $\begingroup$ The reason why we don't want the joint density is because that is what you stipulated in the question: you want the marginal (unconditional) distribution of $R$. So, the density of $R$ at some value $R = r$ is given by the integral of the joint density on $t \in [r, \infty)$. $\endgroup$ – heropup Feb 27 '14 at 4:49

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.