Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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.

share|improve this question
    
I cannot parse the formula. –  Igor Rivin Feb 16 '11 at 15:17
    
something's wrong. I'll fix this. –  Pradipta Feb 16 '11 at 15:18
    
I think its working now. –  Pradipta Feb 16 '11 at 15:24
    
Are you sure $f(n)$ appears on both sides of the first equation? –  Emil Jeřábek Feb 16 '11 at 15:30
    
yeah. with probability $\frac{1}{2^n}$ no coin succeeds in round 1, thus you are back where you started. –  Pradipta Feb 16 '11 at 15:33
show 5 more comments

5 Answers

up vote 11 down vote accepted

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

share|improve this answer
    
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$$. –  Emil Jeřábek Feb 16 '11 at 16:15
    
@Emil: right, corrected, thanks. –  Did Feb 16 '11 at 16:27
1  
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)$. –  Emil Jeřábek Feb 16 '11 at 16:33
    
That should have been $k\le\log_2n$, of course. –  Emil Jeřábek Feb 16 '11 at 16:34
    
In fact, $\sum_{k\le\log_2n}(1-2^{-k})^n$ is bounded, hence $f(n)=\log_2n+O(1)$. –  Emil Jeřábek Feb 16 '11 at 16:53
add comment

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

share|improve this answer
2  
@Louigi: The maximum of $n$ standard (independent) exponentials is again distributed as an exponential... Sure about this? –  Did Feb 16 '11 at 17:52
    
Oh, you're right Didier, that step was nonsense. I'll fix my answer. –  Louigi Addario-Berry Feb 16 '11 at 18:48
    
@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.) –  Did Feb 17 '11 at 7:37
    
@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.) –  Louigi Addario-Berry Feb 17 '11 at 10:12
    
@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. –  Louigi Addario-Berry Feb 17 '11 at 10:20
show 1 more comment

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.

share|improve this answer
    
Very useful comment, Mike. –  Pradipta Feb 17 '11 at 15:37
add comment

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.

share|improve this answer
add comment

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

share|improve this answer
1  
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)$. –  Douglas Zare Feb 17 '11 at 1:01
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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