2
$\begingroup$

Play 2*t rounds of the same coin-tossing game, please express P(t rounds show head and the other t rounds show tail, and at any time point between 0 and 2t, the number of coin landing head is no less than that of tail). If possible, please also show that when t goes to infinity, this probability becomes/does not become 0. Please give details even if this is too simple to you This event can also be framed as a random walk: starting at the origin of a vertical axis, in each step, go up (+) and down (-) by 1, never reaching any place that has a negative coordinate (never go downer than the origin), and goes back to origin in the long run. If this probability goes to zero at infinity, please advise on similar events that happen with a positive probability when t goes to infinity.

$\endgroup$
  • 1
    $\begingroup$ You may want to stipulate that the number of rounds is always even. Also, consider using "probability" instead of "possibility". $\endgroup$ – Keep these mind Mar 7 '13 at 10:25
  • $\begingroup$ I do not understand "Taking the infinite limit of the possibility of such thing happens". Already P(never negative before t) goes to zero when t goes to infinity. $\endgroup$ – Did Mar 7 '13 at 10:34
  • $\begingroup$ Let me rephrase. Play 2*t rounds of the same coin-tossing game, please express P(t rounds show head and the other t rounds show tail, and at any time point between 0 and 2t, the number of coin landing head is no less than that of tail). If possible, please also show that when t goes to infinity, this probability becomes/does not become 0. Please give details even if this is too simple to you $\endgroup$ – Xin Mar 7 '13 at 11:31
  • 1
    $\begingroup$ About version 2: already P(exactly t rounds show heads during the 2t first rounds) goes to zero. $\endgroup$ – Did Mar 7 '13 at 16:09
  • $\begingroup$ Out of 4t rounds, what is P(the number of rounds show head is between t and 2t) when t goes to infinity? $\endgroup$ – Xin Mar 8 '13 at 5:36
0
$\begingroup$

The probability you seek is $C_t/4^t$, where $C_t$ is the $t$th Catalan number. From the exact formula for $C_t$ you should be able to prove that this probability tends to $0$.

$\endgroup$
  • $\begingroup$ Which 'exact formula' were you referring to? The link is for Catalan number's wiki page which contains many formulas. I assume you meant the asymptotically growth formula of the Catalan number derived using Stirling's approximation of n!. Is this right? $\endgroup$ – Xin Mar 8 '13 at 1:21
  • $\begingroup$ @Xin The exact formula on the Wikipedia page is $C_t={1\over t+1}\,{2t\choose t}$. $\endgroup$ – user940 Mar 8 '13 at 18:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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