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:

P(Ak)=[s2k]pksk(1ps)(1s+(1p)pksk+1)(1s)=[s2k]Gk,p(s)P(Ak)=[s2k]pksk(1−ps)(1−s+(1−p)pksk+1)(1−s)=[s2k]Gk,p(s)
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:
s=1+(1p)pk1(k+1)(1p)pk+o(pk)>1s∗=1+(1−p)pk1−(k+1)(1−p)pk+o(pk)>1
Thus in the vicinity of s=1s=1 the Gk,p(s)Gk,p(s) behaves as
Gk,p(s)pksk(1ps)(ss)(1s)=m=ksmpk1smk+1p(1skm)s1Gk,p(s)≈pksk(1−ps)(s∗−s)(1−s)=∑m=k∞smpk1−s∗m−k+1−p(1−s∗k−m)s∗−1
and thus since for large kk the root ss∗ is very close to 11 giving
[s2k]Gk,p(s)1(1pk1k(1p)pk)sk2k1exp(λk)[s2k]Gk,p(s)≈1−(1−pk1−k(1−p)pk)s∗k−2k≈1−exp⁡(−λk)
where
λk=(2kk)(s1)=(2kk)(1p)pk1(k+1)(1p)pkλk=(2k−k)(s∗−1)=(2k−k)(1−p)pk1−(k+1)(1−p)pk
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

λk=(2kk)2k11(k+1)2k1k12λk=(2k−k)2−k−11−(k+1)2−k−1→k→∞12
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


Comments