7

Let $H_n$ be the number of heads in $n$ coin flips.
Let $T_n$ be the number of tails in $n$ coins flips.

Is there a good way to calculate $E_n = E[|H-T|]$ that isn't brute force computation, i.e. directly evaluating $$E[|H-T|] = \frac{1}{2^n} \sum {n \choose r} |n-2r|. $$

I don't see any approach that can simplify this calculation.

Calvin Lin
  • 68,864
  • 4
    This seems equivalent to calculating the expected distance from the origin of a 1D random walk. See eg http://mathworld.wolfram.com/RandomWalk1-Dimensional.html – leonbloy May 13 '13 at 19:04

1 Answers1

6

$$\sum_r \dbinom{n}r \vert n-2r \vert = \sum_{r < n/2} \dbinom{n}r (n-2r) + \sum_{r>n/2} \dbinom{n}r (2r-n) = 2\sum_{r>n/2} \dbinom{n}r r - \sum_{r<n/2}\dbinom{n}r r$$ I trust you can take it from here. You may need to use the identities $$r \binom{n}r = n\dbinom{n-1}{r-1}$$ $$\sum_{r=0}^{k-1} \dbinom{2k}r = \dfrac{4^k - \dbinom{2k}k}2$$ $$\sum_{r=0}^{k} \dbinom{2k+1}r = 2^{2k}$$