Coin flipping and a recurrence relation

Question

How can one solve the following recurrence relation?

$f(n) = 1 + \frac{1}{2^n} \sum_{k = 0}^n {{n}\choose{k}} f(k)$

$f(0) = 0$

As it happens, I can show $f(n) = \Theta(\log n)$ through other means (see below). But I'd like to know how to solve the recurrence "directly".

The recurrence relation comes from the following coin flipping problem. There are $n$ independent, unbiased coins, and we toss all of then for a number of rounds. Let $T(n)$ be the first round when each coin has got head at least once (ie, $T(n) = \text{arg} \min_t \text{s.t.} H_t(i) \geq 1; \forall i \in [n]$, where $H_t(i)$ is the number of heads the $i^{th}$ coin has got in the first $t$ rounds). Then one can see that $E(T(n))$ fulfills the recurrence relation mentioned above.

To see that $E(T(n)) = O(\log n)$, note that we reduce the number of coins who haven't gotten head yet by a factor of 2, in expectation. The $\log n$ bound follows routinely from that. On the other direction (ie, $E(T(n)) = \Omega(\log n)$), let $S = \log n/20$. Then at time $S$ with high probability, a large number of coins will still be "headless", from which the lower bound follows.

Answer 1

The exponential generating function of the sequence $(f(n))$ is $$ \sum_{n\ge0}f(n)\frac{s^n}{n!}=\mathrm{e}^{s}\sum_{k\ge0}(1-\mathrm{e}^{-s/2^k}). $$ Not sure that this formula helps to recover the asymptotic behaviour of $f(n)$ when $n\to\infty$, though, even if it yields a few equivalent expressions of every $f(n)$, such as $$ f(n)=\sum_{k\ge0}(1-(1-2^{-k})^n), $$ or $$ f(n)=\sum_{i=1}^n(-1)^{i+1}\frac{2^i}{2^i-1}{n\choose i}. $$

---

Edit (Most of the following was explained in comments by Emil Jeřábek. It is presented to show how far one can go using the expressions of $f(n)$ written above.)

Fix $n\ge2$ and recall the first expression of $f(n)$, as a sum over $k$ of $$x_k=1-(1-2^{-k})^n. $$ Since the sequence $(x_k)$ is nonincreasing, $f(n)\ge ix_i$ for every fixed $i$. On the other hand, $x_k\le1$ and $x_k\le n2^{-k}$ for every $k$, hence $f(n)\le i+n2^{-i}$.

Choose $i\ge1$ such that $i\le\log_2n < i+1$. Then $n/2 < 2^i\le n$ hence $x_i\ge1-(1-1/n)^n>1-1/\mathrm{e}$.

Finally, $f(1)=2$ hence, for every $n\ge1$, $$ (1-1/\mathrm{e})(\log_2(n)-1) < f(n)\le\log_2(n)+2. $$ These estimates can be upgraded to a precise asymptotics as follows. Fix $a<1$ and choose $i$ as close as possible to $a\log_2n$. Then $(1-n^{-a})^n\to0$ hence $x_i\to1$ and $f(n)\ge ix_i\ge a\log_2(n)(1+o(1))$.

This proves that $f(n)=\log_2(n)+o(\log_2(n))$ when $n\to+\infty$.

Answer 2

I think you can get the precise value (well, within an additive error of one) by a sort of limiting argument. Rather than a sequence of coins, for each $i=1,\ldots,n$ let $P_i$ be a Poisson process with rate $\ln(2)$ so that the probability there is at least one point in an interval of length $1$ is $1-e^{-\ln(2)} = 1/2$. Now let $T$ be the first time $t$ that in each of the Poisson processes, at least one point has fallen. then $\lceil T \rceil$ has the same distribution as the time you are looking for.

Furthermore, $T$ is distributed as the maximum of $n$ exponential random variables with mean $1/\ln(2)$, or in other words as $1/\ln(2)$ times the maximum of $n$ standard exponentials. Next, note that you can find such a maximum by first considering the minimum, which is exponentially distributed with mean $1/n$, then considering the maximum remaining time for the remaining $n-1$ exponentials and using the memoryless property. It follows that $T$ is distributed as a sum $E_1+\ldots+E_n$, where the $E_i$ are independent and $E_i$ has mean $1/i$.

It follows that $T$ is has mean $H_n/\ln 2$, and so $f(n) = \mathbb{E}(\lceil T\rceil)$ has mean in $[H_n/\ln(2),H_n/\ln(2)+1]$.

Answer 3

Sums like

$f_n = \sum_{k \ge 0} (1 - (1-2^{-k})^n)$

(and even much more terribly looking ones) have been considered at many places in the literature. There are methods for evaluating them asymptotically at arbitrary precision (i.e. up to any error of order $n^{-c}$). One such method is the Mellin Transform, see

http://algo.inria.fr/flajolet/Publications/mellin-harm.pdf

for an excellent survey by Flajolet et al. There, $f_n$ serves as one of several "running examples", and the authors show that

$f_n \sim \log_2 n + \gamma/\ln 2 + 1/2 + Q(\log_2 n) + O(n^{-1/2})$

where $Q$ is an explicitly given Fourier series. Interestingly, this series remains bounded, but oscillates forever.

Answer 4

This is exactly the problem of finding the expected maximum of $n$ iid geometric (1/2) random variables. This is because the geometric distribution models the time until the first success in independent Bernoulli trials, and each coin flip can be considered an independent Bernoulli trial.

The question of finding the expected maximum of $n$ iid geometric random variables was asked a few months ago on MO. You can see from the accepted answer there that the expected value can be expressed as

$$\sum_{i=1}^n \binom{n}{i} (-1)^{i+1} \frac{1}{1-\frac{1}{2^i}},$$
which is the last expression in Didier Piau's answer in a slightly different form.

The other answer cites a paper by Bennett Eisenberg that claims that "There is no... simple expression for... the expected value of the maximum of $n$ IID geometric random variables." However, the paper itself proves that $E[T(n)] - \sum_{k=1}^n \frac{1}{\lambda k}$ "is very close to 1/2 not only for moderate values of $\lambda$, but also for relatively small values of $n$ and that this difference is logarithmically summable to 1/2 for all values of $\lambda$." In your case, $\lambda = \ln 2$. Thus $E[T(n)]$ is very close to $\frac{H_n}{\ln 2} + \frac{1}{2}$, right in the middle of the range given by Louigi Addario-Berry's answer.

Answer 5

You can express $f(n)$ explicitly as an infinite sum. After $k$ tosses, the probability that at least one coin didn't get 'heads', is $g_k(n) = 1 - (1-\frac{1}{2^k})^n$. Therefore, $P_k(n) \equiv Prob(T(n) = k) = g_{k-1}(n) - g_{k}(n) = (1-\frac{1}{2^{k}})^n - (1-\frac{1}{2^{k-1}})^n$. From this, the expectation is $f(n) = \sum_{k=1}^{\infty} k [(1-\frac{1}{2^{k}})^n - (1-\frac{1}{2^{k-1}})^n]$.