Expected number of parallel tosses of $N$ unfair coins until all coins landed head at least once

Question

I am trying to understand this answer, but it doesn't work when I plug in the numbers. Given the recurrence relation

\begin{align*} E_n &= \dfrac{\displaystyle 1+\sum_{k=1}^{n-1}q^kp^{n-k}E_{k}}{1-q^n} \\ E_1 &= \frac{1}{p} \end{align*}

and assuming $p = q = 1/2$, we can compute $E_5$ as:

\begin{align} E_1 &= 2\\ E_2 &= \frac{1 + (1/2)(1/2)2}{1-(1/4)} = \frac{6}{3} = 2\\ E_3 &= \frac{1 + (1/2)(1/4)2 + (1/4)(1/2)2}{1-(1/8)} = \frac{12}{7} \approx 1.714\\ E_4 &= \frac{1 + (1/2)(1/8)2 + (1/4)(1/4)2 + (1/8)(1/2)(12/7)}{1-(1/16)} = \frac{152}{105} \approx 1.448\\ E_5 &= \frac{1 + (1/2)(1/16)2 + (1/4)(1/8)2 + (1/8)(1/4)(12/7) + (1/16)(1/2)(152/105)}{1-(1/32)} = \frac{4112}{3255} \approx 1.263, \end{align}

which does not match the author's answer of $E_5 = 2470/651 \approx 3.79416282642$.

I have no experience with absorbing Markov chains so I have no idea where the mistake is. Am I doing something wrong or is the answer wrong?

(Apologies if this is not the right place. I would have posted this as a comment to the answer, but my reputation is not high enough to do that...)

Answer 1

The recurrence relation given by @saulspatz in the comments is correct. Solved for $E_n$, it is:

$$ E_n = \dfrac{1+\sum\limits_{k=1}^{n-1}\binom{n}{k}p^{n-k}q^{k}E_k}{1 - q^n} $$

with $ E_1 = \frac{1}{p} $. This form correctly predicts $ E_2 = \frac{8}{3} $ and $ E_3 = \frac{22}{7} $, as well as $ E_5 = \frac{2470}{651}$.

Answer 2

Note that the probability of needing $m$ parallel rolls is given by

$$\mathrm{P}[T=m] = \sum_{k=1}^n {n\choose k} (1-q^{m-1})^{n-k} q^{(m-1)k} (1-q)^k.$$

Here we choose the $k$ coins that have not landed a head yet and which see their first head on the $m$th roll. Check if this is a probability distribution:

$$\sum_{m\ge 1} \sum_{k=1}^n {n\choose k} (1-q^{m-1})^{n-k} q^{(m-1)k} (1-q)^k \\ = \sum_{m\ge 1} \left(-(1-q^{m-1})^n + (q^{m-1}(1-q) + 1 - q^{m-1})^n\right) \\ = \sum_{m\ge 1} \left(-(1-q^{m-1})^n + (1 - q^m)^n\right).$$

The partial sums to an upper limit of $m'$ are $(1-q^{m'})^n$ so the series converges to a value of one, confirming the sanity check. We then have for the expectation

$$\sum_{m=1}^{m'} m \left(-(1-q^{m-1})^n + (1 - q^m)^n\right) \\ = - \sum_{m=0}^{m'-1} (m+1) (1-q^{m})^n + \sum_{m=1}^{m'} m (1 - q^m)^n \\ = m'(1-q^{m'})^n - \sum_{m=0}^{m'-1} (1-q^{m})^n.$$

The sum is (the term for $m=0$ is zero and simplifies the computation):

$$\sum_{m=0}^{m'-1} \sum_{k=0}^n {n\choose k} (-1)^k q^{km} \\ = m' + \sum_{m=0}^{m'-1} \sum_{k=1}^n {n\choose k} (-1)^k q^{km} = m' + \sum_{k=1}^n {n\choose k} (-1)^k \sum_{m=0}^{m'-1} q^{km} \\ = m' + \sum_{k=1}^n {n\choose k} (-1)^k \frac{1-q^{km'}}{1-q^k}.$$

Computing the limit we thus have

$$\bbox[5px,border:2px solid #00A000]{ \mathrm{E}[T] = \sum_{k=1}^n {n\choose k} (-1)^{k+1} \frac{1}{1-q^k}.}$$

This yields for a fair coin the sequence

$$2,8/3,{\frac {22}{7}},{\frac {368}{105}}, {\frac {2470}{651}},{\frac {7880}{1953}}, {\frac {150266}{35433}},\;\ldots$$

and for a coin that lands heads with probability $3/4$ so that $q=1/4:$

$$3/2,{\frac {15}{8}},{\frac {225}{104}},{\frac {2487}{1040}}, {\frac {64839}{25168}},{\frac {36999}{13552}}, {\frac {78709677}{27508624}},\;\ldots$$

These values match the data from the recurrence.

Addendum, next day. We may prove the closed form using the recurrence and strong induction. For $n=1$ we get $1/(1-q)$ which is correct. In the induction step we find

$$\frac{1}{1-q^n} + \frac{1}{1-q^n} \sum_{k=1}^{n-1} {n\choose k} p^{n-k} q^k \sum_{\ell = 1}^k {k\choose \ell} (-1)^{\ell+1} \frac{1}{1-q^\ell} \\ = \frac{1}{1-q^n} + \frac{1}{1-q^n} \sum_{\ell = 1}^{n-1} (-1)^{\ell+1} \frac{1}{1-q^\ell} \sum_{k=\ell}^{n-1} {n\choose k} p^{n-k} q^k {k\choose \ell}.$$

Working with the sum we observe that

$${n\choose k} {k\choose \ell} = \frac{n!}{(n-k)! \times \ell! \times (k-\ell)!} = {n\choose \ell} {n-\ell\choose n-k}$$

and we obtain

$$\frac{1}{1-q^n} \sum_{\ell = 1}^{n-1} {n\choose \ell} (-1)^{\ell+1} \frac{1}{1-q^\ell} \sum_{k=\ell}^{n-1} {n-\ell\choose n-k} p^{n-k} q^k \\ = \frac{1}{1-q^n} \sum_{\ell = 1}^{n-1} {n\choose \ell} (-1)^{\ell+1} \frac{1}{1-q^\ell} \sum_{k=0}^{n-\ell-1} {n-\ell\choose n-k-\ell} p^{n-k-\ell} q^{k+\ell} \\ = \frac{1}{1-q^n} \sum_{\ell = 1}^{n-1} {n\choose \ell} (-1)^{\ell+1} \frac{q^\ell}{1-q^\ell} \sum_{k=0}^{n-\ell-1} {n-\ell\choose k} p^{n-\ell-k} q^{k} \\ = \frac{1}{1-q^n} \sum_{\ell = 1}^{n-1} {n\choose \ell} (-1)^{\ell+1} \frac{q^\ell}{1-q^\ell} ((p+q)^{n-\ell} - q^{n-\ell}) \\ = \frac{1}{1-q^n} \sum_{\ell = 1}^{n-1} {n\choose \ell} (-1)^{\ell+1} \frac{q^\ell-1+1-q^n}{1-q^\ell} \\ = \frac{1}{1-q^n} \sum_{\ell = 1}^{n-1} {n\choose \ell} (-1)^{\ell} + \frac{1}{1-q^n} \sum_{\ell = 1}^{n-1} {n\choose \ell} (-1)^{\ell+1} \frac{1-q^n}{1-q^\ell} \\ = \frac{1}{1-q^n} (0-1-(-1)^n) + \sum_{\ell = 1}^{n-1} {n\choose \ell} (-1)^{\ell+1} \frac{1}{1-q^\ell}.$$

We now restore the term in front that did not participate to find

$$\frac{1}{1-q^n} + \frac{1}{1-q^n} (-1+(-1)^{n+1}) + \sum_{\ell = 1}^{n-1} {n\choose \ell} (-1)^{\ell+1} \frac{1}{1-q^\ell} \\ = \sum_{\ell = 1}^{n} {n\choose \ell} (-1)^{\ell+1} \frac{1}{1-q^\ell}.$$

This concludes the proof.