In 100 consecutive coin flips, what is the probability that the sequence H H T T will not appear? Outline a computationally feasible algorithm to solve this. If the number of coin flips is raised to 1 billion will your algorithm complete in a reasonable amount of time?

for n coins, denote such probability p(n). the recurrence relation is p(n+4) = p(n+3) - p(n)/16, with p(0)=p(1)=p(2)=p(3)=1.the characteristic equation: x^4-x^3+1/16=0 has 2 real roots: x_1~0.92 and x_2=1/2; it also has two complex conjugate roots x_3 and x_4 (both with norm of ~0.37).p(n) can thus be written as a1*(x1^n)+a2*(x2^n)+a3*(x3^n)+a4*(x4^n), where a's are determined by the initial conditions. one can get a_i=1+(3/4)/(4*x_i^3-1) by inverting a Vandermonde matrix.when n is sufficiently large, one just needs the root with the largest norm, so the probability is ~1.4*(0.92)^n.the exact expression of x_1 and a_1 are:for n=10^2, via mathematica, the exact recursion gives 3.1e-4, which agrees with a1*(x1^100) extremely well;for n=10^9, one essentially needs to calculate 10^9*log10(x_1)+log10(a_1) to two digits after the decimal point to get two significant figures for the answer: ~ 9.0e-36380553----- ----- ----- ----- -----another approach is to use the generating function: (1 - x + x^4/16)^(-1). by using the negative multinomial coefficients, one gets----- ----- ----- ----- -----a slightly harder question is to calculate the prob for an "overlapping pattern" (in the sense that if the pattern appears more than once in the sequence, they could overlap), e.g., "H T H".the generating function is slightly more complicated: (1 + x^2/4)/(1 - x + x^2/4 - x^3/8), which results the recurrence relation: p(n+3) = p(n+2) - p(n+1)/4 + p(n)/8, with p(0)=p(1)=p(2)=1. then same technique as above applies.

Hi all(sorry for digging up old threads) but quick question for wileyswhow did you come up with your recurrence relation? Easy to prove manually that it works fine for small n; but I have issues proving it for a general "n"Best,Hotone

1/2 of the time the last letter is H so the sequence is ok if there were no HHTT's there before, the other 1/2 it's a T, so for the sequence to be ok the previous 3 letters have to be anything but HHT (happens 1/8 of the time).So p(n+4) = 1/2 p(n+3) + 1/2 (p(n+3) - p(n)*1/8)

i have nothing more to add for the non-overlapping patterns. but to illustrate why overlapping pattern is tricky, consider the prob that "HTH" does not appear within n+3 tosses. similarly by conditioning on the last toss, the recurrence seems to be: p(n+3) = p(n+2) - p(n)/8.however, this actually over-subtracts the possibility that the first n tosses with no "HTH" appearing but ending up with "HT". by appending "HTH" to this kind of sequence which gives "...HTHTH", "HTH" would have appeared within n+1 tosses, hence not being included in p(n+3).easy to see, the probability of this happening is simply [p(n)-p(n+1)]*(1/4), where 1/4 is the prob of the last "TH". so the correct recurrence is:p(n+3) = p(n+2) - p(n)/8 + [p(n)-p(n+1)]/4 = p(n+2) - p(n+1)/4 + p(n)/8

Hi All,I have a basic question up to the non overlapping patterns :I don't understand why in the case where the sequence ends with T, the probability that we don't get HHT before it is equal to : p(n+3)-p(n)/8Best,ReaVer

One way to see it is via a counting argument:let A be p(n+3) * 2^(n+3), i.e. the total # of length n+3 flip sequences that don't contain HHTT.We want to exclude from these the sequences that end in HHT. There are p(n) * 2^n of them, so we have A - p(n) * 2^n.Now the probability is (A - p(n) * 2^n) / 2^(n+3), which simplifies to p(n+3) - p(n) / 8.I'm sure there's a better way to do this but my brain is currently fried...