4
$\begingroup$

Tossing a fair coin $2n$ times. After the $i$-th toss, the number of heads is $H_{i}$ and the number of tails is $T_{i}$. Is this a mere coincidence that the probability of $H_{2k}=T_{2k}$ equals to the probability that $H_{2i}\ne T_{2i}$ for all $i\le k$? How do I understand this more easily? Is there a way to devise a one-to-one correspondence of any case that $H_{2k}=T_{2k}$ to a case that $H_{2i}\ne T_{2i}(i\le k)$?

  • 0
    There seems to be something missing. $\Pr(T_4 = H_4) = \frac{3}{8}$ while $\Pr(T_2 \neq H_2) = \frac{1}{2}$. The equality you claim doesn't seem to hold.2012-10-27
  • 0
    @EuYu: Note that the second event is "$H_{2i}\ne T_{2i}$ **for all** $i\le k$".2012-10-27
  • 0
    @Voldemort: A proper intuitive explanation requires pictures. The general idea is called a Reflection Principle for random walks. First used I think for the ballot problem. One takes a path to $(k,k)$ and reflects the bits that go above the diagonal. Sorry not to have a standard reference.2012-10-27
  • 2
    @André: The Wikipedia article on [Bertrand's ballot theorem](http://en.wikipedia.org/wiki/Bertrand's_ballot_theorem) says "A variation of his method is popularly known as André's reflection method, although André did not use any reflections." Apparently you do! :-)2012-10-27

1 Answers 1