A fast way to compute the Expected Number of Coin Tosses until you reach H h\ eads AND T tails By Shalosh B. Ekhad Theorem: You toss a coin whose probabilty of Heads is p and probability of T\ ails is 1-p and stop as soon as you have reached your goal of having at least h Heads and t tails. Let L(h,t) be the expected number of to\ sses. Then F(h,t) satisfy the following pure recurrences (h p + p t - h - 2 p - 3 t + 4) L(h, t - 1) L(h, t) = - ------------------------------------------- t - 1 (2 h p + 2 p t - 2 h - 4 p - 3 t + 5) L(h, t - 2) + ------------------------------------------------- t - 1 (-1 + p) (t - 2 + h) L(h, t - 3) - -------------------------------- t - 1 (h p + p t + 2 h - 2 p - 2) L(h - 1, t) L(h, t) = --------------------------------------- h - 1 (2 h p + 2 p t + h - 4 p - 1) L(h - 2, t) p (t - 2 + h) L(h - 3, t) - ----------------------------------------- + ------------------------- h - 1 h - 1 subject to the initial condisions 2 3 2 p - p + 1 p - 3 p + p - 1 L(1, 1) = - ----------, L(1, 2) = -----------------, p (-1 + p) p (-1 + p) 4 3 2 3 p - 4 p + 6 p - p + 1 p - 2 p + 2 L(1, 3) = - ------------------------, L(2, 1) = - ------------, p (-1 + p) p (-1 + p) 4 3 5 4 3 2 (p - 2 p + p - 1) 3 p - 10 p + 10 p - 2 p + 2 L(2, 2) = ---------------------, L(2, 3) = - ------------------------------, p (-1 + p) p (-1 + p) 4 5 4 p - 3 p + 3 3 p - 5 p + 3 p - 3 L(3, 1) = - ------------, L(3, 2) = ---------------------, p (-1 + p) p (-1 + p) 6 5 4 3 (2 p - 6 p + 5 p - p + 1) L(3, 3) = - ------------------------------ p (-1 + p) and in Maple notation L(h,t) = -(h*p+p*t-h-2*p-3*t+4)/(t-1)*L(h,t-1)+(2*h*p+2*p*t-2*h-4*p-3*t+5)/(t-1 )*L(h,t-2)-(-1+p)*(t-2+h)/(t-1)*L(h,t-3) L(h,t) = (h*p+p*t+2*h-2*p-2)/(h-1)*L(h-1,t)-(2*h*p+2*p*t+h-4*p-1)/(h-1)*L(h-2,t )+p*(t-2+h)/(h-1)*L(h-3,t) 2 3 2 p - p + 1 p - 3 p + p - 1 L(1, 1) = - ----------, L(1, 2) = -----------------, p (-1 + p) p (-1 + p) 4 3 2 3 p - 4 p + 6 p - p + 1 p - 2 p + 2 L(1, 3) = - ------------------------, L(2, 1) = - ------------, p (-1 + p) p (-1 + p) 4 3 5 4 3 2 (p - 2 p + p - 1) 3 p - 10 p + 10 p - 2 p + 2 L(2, 2) = ---------------------, L(2, 3) = - ------------------------------, p (-1 + p) p (-1 + p) 4 5 4 p - 3 p + 3 3 p - 5 p + 3 p - 3 L(3, 1) = - ------------, L(3, 2) = ---------------------, p (-1 + p) p (-1 + p) 6 5 4 3 (2 p - 6 p + 5 p - p + 1) L(3, 3) = - ------------------------------ p (-1 + p) These recurrences enable very fast compuations of the expected number of coi\ n tosses until reahing the desired goal For a fair coin, L(h,h)/h for multiples of 50 from 1 to , 500, are 1/50 L(50, 50) = 2.159178475, 1/100 L(100, 100) = 2.112696958, 1/150 L(150, 150) = 2.092055029, 1/200 L(200, 200) = 2.079738604, 1/250 L(250, 250) = 2.071329291, 1/300 L(300, 300) = 2.065119863, 1/350 L(350, 350) = 2.060292867, 1/400 L(400, 400) = 2.056401330, 1/450 L(450, 450) = 2.053177530, 1/500 L(500, 500) = 2.050450036 If the prob. of a Head is 1/3 then, L(20*i,30*i)/(20*i) for i from 1 to, 10, are: 1/20 L(20, 40) = 3.326175219, 1/40 L(40, 80) = 3.231201900, 1/60 L(60, 120) = 3.188928559, 1/80 L(80, 160) = 3.163683224, 1/100 L(100, 200) = 3.146438314, 1/120 L(120, 240) = 3.133700943, 1/140 L(140, 280) = 3.123797347, 1/160 L(160, 320) = 3.115811868, 1/180 L(180, 360) = 3.109195848, 1/200 L(200, 400) = 3.103597873 If the prob. of a Head is 2/5 then, L(20*i,30*i)/(20*i) for i from 1 to, 10, are: 1/20 L(20, 30) = 2.786396382, 1/40 L(40, 60) = 2.703047862, 1/60 L(60, 90) = 2.665933775, 1/80 L(80, 120) = 2.643766080, 1/100 L(100, 150) = 2.628622228, 1/120 L(120, 180) = 2.617436151, 1/140 L(140, 210) = 2.608738412, 1/160 L(160, 240) = 2.601725058, 1/180 L(180, 270) = 2.595914335, 1/200 L(200, 300) = 2.590997663 ------------------------------- This ends this article that took, 1.326, seconds to produce