Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

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.

share|improve this question

2 Answers 2

up vote 8 down vote accepted

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.

share|improve this answer
    
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
1  
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
1  
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.

share|improve this answer
    
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

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.