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)$?
Is it a coincidence or is there an explanation for this?
4
$\begingroup$
probability
-
0There 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