# Discrepancy between heads and tails

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.

-

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] = 2\Pr[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.

-
After we've proven $E[H_{i}] = \Theta ( \sqrt{i} )$ , couldn't we say that for $i=n$ we have the second result, i.e. no $E[H_{i}]$ is greater than $\Theta ( \sqrt{n} )$. –  chazisop Dec 26 '12 at 11:08
If the $H_i$ were independent, then the conclusion won't be true, since you actually expect some of these values to be somewhat larger than the expectation. It's not true in general that $E[\max(A,B)] = \max(E[A],E[B])$. –  Yuval Filmus Dec 27 '12 at 3:10
The law of the iterated logarithm doesn't apply here, since $n$ is fixed and we're not normalizing by $i$. The answer for $\mathrm{E} \max_{i\leq n} H_i$ is $\theta(\sqrt{n})$. –  Peter Shor Dec 28 '12 at 5:45
+1 for the first part. but I honestly dont understand the second part (can you elaborate more plz). This does not mean that it is not correct though. –  AJed Dec 30 '12 at 5:15
@AJed I added some more explanation to the second part, though the real trick, the reflection principle, is described in the link. –  Yuval Filmus Dec 30 '12 at 12:09

You can use the half-normal distribution to prove the answer.

The half-normal distribution states that if $X$ is a normal distribution with mean 0 and variance $\sigma^2$, then $|X|$ follows a half distribution with mean $\sigma \sqrt{\frac{2}{\pi}}$, and variance $\sigma^2 (1-2/\pi)$. This gives the required answer, since the variance $\sigma^2$ of the normal walk is $n$, and you can approximate the distribution of $X$ to a normal distribution using the central limit theorem.

$X$ is the sum of the random walk as Yuval Filmus mentioned.

-
I dont prefer this that I posted.. . although it gives the lower bound, nothing can be told about the upper bound. I tried to use a maximum distribution argument to solve it, it turned out to be an ugly integration. But it is good to know all these distributions. –  AJed Jan 1 '13 at 20:00