Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
    
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. –  EuYu Oct 27 '12 at 6:42
    
@EuYu: Note that the second event is "$H_{2i}\ne T_{2i}$ for all $i\le k$". –  Voldemort Oct 27 '12 at 6:43
    
@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. –  André Nicolas Oct 27 '12 at 6:59
2  
@André: The Wikipedia article on 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! :-) –  joriki Oct 27 '12 at 7:54
add comment

1 Answer 1

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.