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

0

There are combinatorial proofs, but they’re a bit involved and not so enlightening as some. You’ll find some references in this answer and the following comments. My answer here includes what is essentially an expansion and clarification of the one in Phira’s Sved reference.