11
$\begingroup$

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.

$\endgroup$
10
  • $\begingroup$ I cannot parse the formula. $\endgroup$
    – Igor Rivin
    Feb 16, 2011 at 15:17
  • $\begingroup$ something's wrong. I'll fix this. $\endgroup$
    – Pradipta
    Feb 16, 2011 at 15:18
  • $\begingroup$ I think its working now. $\endgroup$
    – Pradipta
    Feb 16, 2011 at 15:24
  • $\begingroup$ Are you sure $f(n)$ appears on both sides of the first equation? $\endgroup$ Feb 16, 2011 at 15:30
  • $\begingroup$ yeah. with probability $\frac{1}{2^n}$ no coin succeeds in round 1, thus you are back where you started. $\endgroup$
    – Pradipta
    Feb 16, 2011 at 15:33

5 Answers 5

11
$\begingroup$

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$.

$\endgroup$
4
  • $\begingroup$ I think the last expression should read either $$1+\sum_{i=1}^n\frac{(-1)^{i+1}}{2^i-1}\binom ni$$ or $$\sum_{i=1}^n\frac{(-1)^{i+1}2^i}{2^i-1}\binom ni$$. $\endgroup$ Feb 16, 2011 at 16:15
  • 1
    $\begingroup$ Also, the expression $f(n)=\sum_k(1-(1-2^{-k})^n)$ easily gives the logarithmic asymptotic behaviour. We have $1\ge 1-(1-2^{-k})^n\ge1-e^{-1}$ for $n\le\log_2n$, hence $\log_2n\ge\sum_{k\le\log_2n}(1-(1-2^{-k})^n)\ge(1-e^{-1})\log_2n$. On the other hand, for $k>\log_2n$ we have $1-(1-2^{-k})^n=1-\exp(-n2^{-k}+O(n2^{-2k}))=O(n2^{-k})$, hence $\sum_{k>\log_2n}(1-(1-2^{-k})^n)=O(1)$. $\endgroup$ Feb 16, 2011 at 16:33
  • $\begingroup$ That should have been $k\le\log_2n$, of course. $\endgroup$ Feb 16, 2011 at 16:34
  • $\begingroup$ In fact, $\sum_{k\le\log_2n}(1-2^{-k})^n$ is bounded, hence $f(n)=\log_2n+O(1)$. $\endgroup$ Feb 16, 2011 at 16:53
7
$\begingroup$

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]$.

$\endgroup$
5
  • 2
    $\begingroup$ @Louigi: The maximum of $n$ standard (independent) exponentials is again distributed as an exponential... Sure about this? $\endgroup$
    – Did
    Feb 16, 2011 at 17:52
  • $\begingroup$ Oh, you're right Didier, that step was nonsense. I'll fix my answer. $\endgroup$ Feb 16, 2011 at 18:48
  • $\begingroup$ @Louigi Minor point: first line of second paragraph, cancel the upper part sign around $T$. Re $H_n$, I find this modified version of your post a bit mysterious, since your parenthesis seems to give a stronger result than what you write before the parenthesis, thus the reader is led to wonder whether this stronger result holds or not... No reason to be shy here! Indeed, $T$ IS a sum of exponentials in the sense that $T=X_1/1+X_2/2+\cdots+X_n/n$ where $(X_i)$ is an i.i.d. sequence of standard exponential random variables. (Nice post, by the way.) $\endgroup$
    – Did
    Feb 17, 2011 at 7:37
  • $\begingroup$ @Didier, yes, T is a sum of exponentials, and its renormalized distribution is the Gumbel distribution. (In fact, if I recall correctly this is Gumbel's original example.) $\endgroup$ Feb 17, 2011 at 10:12
  • $\begingroup$ @Didier PS though I wasn't being shy (not one of my strong points), I have followed your suggestion and made the argument of the second paragraph more explicit. $\endgroup$ Feb 17, 2011 at 10:20
6
$\begingroup$

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.

$\endgroup$
0
5
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ Very useful comment, Mike. $\endgroup$
    – Pradipta
    Feb 17, 2011 at 15:37
3
$\begingroup$

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]$.

$\endgroup$
1
  • 1
    $\begingroup$ You can simplify the final expression to the second equation in Didier Piau's answer. The expected value is the sum of the probabilities that the value is at least $k$, $\sum g_k(n)$. $\endgroup$ Feb 17, 2011 at 1:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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