Trang chủ‎ > ‎IT‎ > ‎Programming‎ > ‎Algorithms Design‎ > ‎

Some probability of toss coin problems

1. k consecutive heads with a biased coin?

You toss a coin repeatedly and independently. The probability to get a head is pp, tail is 1p1−p. Let AkAkbe the following event: kk or more consecutive heads occur amongst the tosses numbered 2k,...,2k+112k,...,2k+1−1. Prove that P(Aki.o.)=1P(Aki.o.)=1 if p12p≥1200 otherwise.

Per Borel-Cantelli theorem you need to determine convergence of k1P(Ak)∑k⩾1P(Ak). Per section 14.1 of the "Problems and snapshots from the world of probability" by Blom, Holst and Sandell the probability than amongst 2k2k throws considered in AkAk a run of heads of length k⩾k will occur can be extracted from the probability generating function:

Because n=2kn=2k grows much faster than kk, we can use asymptotic techniques to find cn=[sn]Gk,p(s)cn=[sn]Gk,p(s). The large nn behavior of cncn is determined by smallest positive roots of the denominator of Gk,p(s)Gk,p(s). The smallest in absolute value root of equation 1s+(1p)pksk+11−s+(1−p)pksk+1 is close to s=1s=1, specifically:
Thus in the vicinity of s=1s=1 the Gk,p(s)Gk,p(s) behaves as
and thus since for large kk the root ss∗ is very close to 11 giving
Clearly limkλk=0limk→∞λk=0 and thus limkP(Ak)=0limk→∞P(Ak)=0 exponentially for 2p<12p<1, and thus k1P(Ak)∑k⩾1P(Ak) convergence, hence P(Ak i.o)=0P(Ak i.o)=0 by Borel-Cantelli theorem.

Furthermore limkλk=limk→∞λk=∞ for 2p>12p>1 implying P(Ak i.o)=1P(Ak i.o)=1.

When p=12p=12 we have

therefore P(Ak)1exp(1/2)P(Ak)→1−exp⁡(−1/2) and the sum k1P(Ak)∑k⩾1P(Ak) diverges, implying P(Ak i.o)=1P(Ak i.o)=1.

Nice question! Being a homework, I am sure there must be a simpler solution, and I am very keen to see it now.

2. Probability of tossing a fair coin with at least kk consecutive heads