Problem Detail: Consider a sequence of $n$ flips of an unbiased coin. Let $H_i$ denote the absolute value of the excess of the number of heads over tails seen in the first $i$ flips. Define $H=text{max}_i H_i$. Show that $E[H_i]=Theta ( sqrt{i} )$ and $E[H]=Theta( sqrt{n} )$. This problem appears in the first chapter of `Randomized algorithms’ by Raghavan and Motwani, so perhaps there is an elementary proof of the above statement. I’m unable to solve it, so I would appreciate any help.
Asked By : Plummer
Answered By : Yuval Filmus
Your coin flips form a one-dimensional random walk $X_0,X_1,ldots$ starting at $X_0 = 0$, with $X_{i+1} = X_i pm 1$, each of the options with probability $1/2$. Now $H_i = |X_i|$ and so $H_i^2 = X_i^2$. It is easy to calculate $E[X_i^2] = i$ (this is just the variance), and so $E[H_i] leq sqrt{E[H_i^2]} = sqrt{i}$ from convexity. We also know that $X_i$ is distributed roughly normal with zero mean and variance $i$, and so you can calculate $E[H_i] approx sqrt{(2/pi)i}$. As for $E[max_{i leq n} H_i]$, we have the law of the iterated logarithm, which (perhaps) leads us to expect something slightly larger than $sqrt{n}$. If you are good with an upper bound of $tilde{O}(sqrt{n})$, you can use a large deviation bound for each $X_i$ and then the union bound, though that ignores the fact that the $X_i$ are related. Edit: As it happens, $Pr[max_{i leq n} X_i = k] = Pr[X_n = k] + Pr[X_n = k+1]$ due to the reflection principle, see this question. So $$ begin{align*} E[max_{i leq n} X_i] &= sum_{k geq 0} k(Pr[X_n = k] + Pr[X_n = k+1]) &= sum_{k geq 1} (2k-1) Pr[X_n = k] &= sum_{k geq 1} 2k Pr[X_n = k] – frac{1}{2} + frac{1}{2}Pr[X_n = 0] &= E[H_n] + Theta(1), end{align*} $$ since $Pr[H_n = k] = Pr[X_n = k] + Pr[X_n = -k] = 2Pr[X_n = k]$. Now $$ frac{max_{i leq n} X_i + max_{i leq n} (-X_i)}{2} leq max_{i leq n} H_i leq max_{i leq n} X_i + max_{i leq n} (-X_i), $$ and therefore $E[max_{i leq n} H_i] leq 2E[H_n] + Theta(1) = O(sqrt{n})$. The other direction is similar.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/7600
