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)$?

  • 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.