A fast way to compute the Probability Generating Function for the Number of \ Coin Tosses until you reach n heads OR n tails and A fast way to compute the Probability Generating Function for the Number of \ Coin Tosses until you reach n heads AND n tails and By Shalosh B. Ekhad Theorem: You toss a coin whose probabilty of Heads is p and probability of T\ ails is 1-p Let L1(n,t) be the probability generating function of the random variable: N\ umber of coin tosses until you either get n heads or n tails Let L2(n,t) be the probability generating function of the random variable: N\ umber of coin tosses until you either get n heads AND n tails Then surpisingly both these sequences of functions (the first polynomial, th\ e second rational function), satisfies the SAME third-order recurrence 2 4 2 2 p t (p - 1) (2 n + 1) 2 2 2 2 2 2 (4 n p t - 4 n p t + 6 p t - 6 p t + 2 n t - n + 3 t - 2) L1(n, t)/( 2 2 4 4 (n + 2) %1 (p t - 1) (p t - t + 1)) - p t (p - 1) (32 n p t 2 3 4 4 4 2 2 4 3 4 4 4 - 64 n p t + 64 n p t + 48 n p t - 128 n p t + 24 p t 2 4 2 4 3 4 2 2 2 4 2 4 - 16 n p t + 96 n p t - 48 p t - 12 n p t - 32 n p t + 36 p t 2 2 2 3 2 2 4 2 2 2 + 12 n p t + 8 n t - 30 n p t - 12 p t - 12 n t + 30 n p t 3 2 2 2 2 2 3 2 + 16 n t - 12 p t + 2 n t - 26 n t + 12 p t + 6 t + n + 5 n t 2 - 10 t + 3 n + 2 t + 2) L1(n, t + 1)/((n + 2) %1 (p t - 1) (p t - t + 1)) 2 6 5 2 5 5 6 5 2 4 5 5 5 + t (16 n p t - 48 n p t + 32 n p t + 48 n p t - 96 n p t 6 5 2 4 4 2 3 5 4 5 5 5 + 12 p t + 24 n p t - 16 n p t + 96 n p t - 36 p t 2 4 3 2 3 4 4 4 3 5 4 5 - 28 n p t - 48 n p t + 48 n p t - 32 n p t + 36 p t 2 3 3 2 2 4 4 3 3 4 4 4 + 56 n p t + 24 n p t - 62 n p t - 96 n p t + 18 p t 3 5 2 2 3 3 3 2 4 4 3 3 4 - 12 p t - 24 n p t + 124 n p t + 48 n p t - 24 p t - 36 p t 2 2 2 2 3 2 3 3 3 2 4 2 2 - 12 n p t - 4 n p t - 56 n p t + 48 p t + 18 p t + 6 n p t 2 2 2 2 3 2 3 2 2 2 + 12 n p t - 26 n p t - 6 n p t - 22 p t - 6 n p t - 2 n t 2 2 2 2 3 2 2 + 16 n p t + 26 n p t - 10 p t - 2 p t + 3 n t - 16 n p t - 5 n t 2 2 2 2 + 8 p t + 10 p t - n + 8 n t - 8 p t - 2 t - 3 n + 4 t - 2) L1(n, t + 2)/((n + 2) %1 (p t - 1) (p t - t + 1)) + L1(n, t + 3) = 0 2 2 2 2 2 2 %1 := 4 n p t - 4 n p t + 2 p t - 2 p t + 2 n t - n + t - 1 2 4 2 2 p t (p - 1) (2 n + 1) 2 2 2 2 2 2 (4 n p t - 4 n p t + 6 p t - 6 p t + 2 n t - n + 3 t - 2) L2(n, t)/( 2 2 4 4 (n + 2) %1 (p t - 1) (p t - t + 1)) - p t (p - 1) (32 n p t 2 3 4 4 4 2 2 4 3 4 4 4 - 64 n p t + 64 n p t + 48 n p t - 128 n p t + 24 p t 2 4 2 4 3 4 2 2 2 4 2 4 - 16 n p t + 96 n p t - 48 p t - 12 n p t - 32 n p t + 36 p t 2 2 2 3 2 2 4 2 2 2 + 12 n p t + 8 n t - 30 n p t - 12 p t - 12 n t + 30 n p t 3 2 2 2 2 2 3 2 + 16 n t - 12 p t + 2 n t - 26 n t + 12 p t + 6 t + n + 5 n t 2 - 10 t + 3 n + 2 t + 2) L2(n, t + 1)/((n + 2) %1 (p t - 1) (p t - t + 1)) 2 6 5 2 5 5 6 5 2 4 5 5 5 + t (16 n p t - 48 n p t + 32 n p t + 48 n p t - 96 n p t 6 5 2 4 4 2 3 5 4 5 5 5 + 12 p t + 24 n p t - 16 n p t + 96 n p t - 36 p t 2 4 3 2 3 4 4 4 3 5 4 5 - 28 n p t - 48 n p t + 48 n p t - 32 n p t + 36 p t 2 3 3 2 2 4 4 3 3 4 4 4 + 56 n p t + 24 n p t - 62 n p t - 96 n p t + 18 p t 3 5 2 2 3 3 3 2 4 4 3 3 4 - 12 p t - 24 n p t + 124 n p t + 48 n p t - 24 p t - 36 p t 2 2 2 2 3 2 3 3 3 2 4 2 2 - 12 n p t - 4 n p t - 56 n p t + 48 p t + 18 p t + 6 n p t 2 2 2 2 3 2 3 2 2 2 + 12 n p t - 26 n p t - 6 n p t - 22 p t - 6 n p t - 2 n t 2 2 2 2 3 2 2 + 16 n p t + 26 n p t - 10 p t - 2 p t + 3 n t - 16 n p t - 5 n t 2 2 2 2 + 8 p t + 10 p t - n + 8 n t - 8 p t - 2 t - 3 n + 4 t - 2) L2(n, t + 2)/((n + 2) %1 (p t - 1) (p t - t + 1)) + L2(n, t + 3) = 0 2 2 2 2 2 2 %1 := 4 n p t - 4 n p t + 2 p t - 2 p t + 2 n t - n + t - 1 but with different initial conditions, of course. 2 3 2 2 3 2 2 L1(1, t) = t, L1(2, t) = -2 p t + 2 p t + 2 p t - 2 p t + t , L1(3, t) = 4 5 4 4 3 5 3 4 2 5 2 4 2 3 6 p t - 6 p t - 12 p t + 12 p t + 6 p t - 9 p t + 3 p t 4 3 3 + 3 p t - 3 p t + t 2 p t (p - 1) (t - 2) L2(1, t) = - -----------------------, L2(2, t) = (p t - t + 1) (p t - 1) 2 4 2 2 3 2 2 3 2 2 p t (p - 1) (2 p t - 2 p t - 2 p t + 2 p t + 3 t - 8 t + 6) ---------------------------------------------------------------------, 2 2 (p t - t + 1) (p t - 1) 3 6 3 4 5 4 4 3 5 3 4 L2(3, t) = - p t (p - 1) (6 p t - 6 p t - 12 p t + 12 p t 2 5 2 4 2 3 4 2 2 3 2 + 6 p t + 9 p t - 33 p t - 15 p t + 18 p t + 33 p t - 18 p t 3 2 / 3 3 + 10 t - 36 t + 45 t - 20) / ((p t - t + 1) (p t - 1) ) / In Maple notation: 2*p^2*t^4*(p-1)^2*(2*n+1)*(4*n*p^2*t^2-4*n*p*t^2+6*p^2*t^2-6*p*t^2+2*n*t-n+3*t-\ 2)/(n+2)/(4*n*p^2*t^2-4*n*p*t^2+2*p^2*t^2-2*p*t^2+2*n*t-n+t-1)/(p*t-1)/(p*t-t+1 )*L1(n,t)-p*t^2*(p-1)*(32*n^2*p^4*t^4-64*n^2*p^3*t^4+64*n*p^4*t^4+48*n^2*p^2*t^ 4-128*n*p^3*t^4+24*p^4*t^4-16*n^2*p*t^4+96*n*p^2*t^4-48*p^3*t^4-12*n^2*p^2*t^2-\ 32*n*p*t^4+36*p^2*t^4+12*n^2*p*t^2+8*n^2*t^3-30*n*p^2*t^2-12*p*t^4-12*n^2*t^2+ 30*n*p*t^2+16*n*t^3-12*p^2*t^2+2*n^2*t-26*n*t^2+12*p*t^2+6*t^3+n^2+5*n*t-10*t^2 +3*n+2*t+2)/(n+2)/(4*n*p^2*t^2-4*n*p*t^2+2*p^2*t^2-2*p*t^2+2*n*t-n+t-1)/(p*t-1) /(p*t-t+1)*L1(n,t+1)+t*(16*n^2*p^6*t^5-48*n^2*p^5*t^5+32*n*p^6*t^5+48*n^2*p^4*t ^5-96*n*p^5*t^5+12*p^6*t^5+24*n^2*p^4*t^4-16*n^2*p^3*t^5+96*n*p^4*t^5-36*p^5*t^ 5-28*n^2*p^4*t^3-48*n^2*p^3*t^4+48*n*p^4*t^4-32*n*p^3*t^5+36*p^4*t^5+56*n^2*p^3 *t^3+24*n^2*p^2*t^4-62*n*p^4*t^3-96*n*p^3*t^4+18*p^4*t^4-12*p^3*t^5-24*n^2*p^2* t^3+124*n*p^3*t^3+48*n*p^2*t^4-24*p^4*t^3-36*p^3*t^4-12*n^2*p^2*t^2-4*n^2*p*t^3 -56*n*p^2*t^3+48*p^3*t^3+18*p^2*t^4+6*n^2*p^2*t+12*n^2*p*t^2-26*n*p^2*t^2-6*n*p *t^3-22*p^2*t^3-6*n^2*p*t-2*n^2*t^2+16*n*p^2*t+26*n*p*t^2-10*p^2*t^2-2*p*t^3+3* n^2*t-16*n*p*t-5*n*t^2+8*p^2*t+10*p*t^2-n^2+8*n*t-8*p*t-2*t^2-3*n+4*t-2)/(n+2)/ (4*n*p^2*t^2-4*n*p*t^2+2*p^2*t^2-2*p*t^2+2*n*t-n+t-1)/(p*t-1)/(p*t-t+1)*L1(n,t+ 2)+L1(n,t+3) = 0 2*p^2*t^4*(p-1)^2*(2*n+1)*(4*n*p^2*t^2-4*n*p*t^2+6*p^2*t^2-6*p*t^2+2*n*t-n+3*t-\ 2)/(n+2)/(4*n*p^2*t^2-4*n*p*t^2+2*p^2*t^2-2*p*t^2+2*n*t-n+t-1)/(p*t-1)/(p*t-t+1 )*L2(n,t)-p*t^2*(p-1)*(32*n^2*p^4*t^4-64*n^2*p^3*t^4+64*n*p^4*t^4+48*n^2*p^2*t^ 4-128*n*p^3*t^4+24*p^4*t^4-16*n^2*p*t^4+96*n*p^2*t^4-48*p^3*t^4-12*n^2*p^2*t^2-\ 32*n*p*t^4+36*p^2*t^4+12*n^2*p*t^2+8*n^2*t^3-30*n*p^2*t^2-12*p*t^4-12*n^2*t^2+ 30*n*p*t^2+16*n*t^3-12*p^2*t^2+2*n^2*t-26*n*t^2+12*p*t^2+6*t^3+n^2+5*n*t-10*t^2 +3*n+2*t+2)/(n+2)/(4*n*p^2*t^2-4*n*p*t^2+2*p^2*t^2-2*p*t^2+2*n*t-n+t-1)/(p*t-1) /(p*t-t+1)*L2(n,t+1)+t*(16*n^2*p^6*t^5-48*n^2*p^5*t^5+32*n*p^6*t^5+48*n^2*p^4*t ^5-96*n*p^5*t^5+12*p^6*t^5+24*n^2*p^4*t^4-16*n^2*p^3*t^5+96*n*p^4*t^5-36*p^5*t^ 5-28*n^2*p^4*t^3-48*n^2*p^3*t^4+48*n*p^4*t^4-32*n*p^3*t^5+36*p^4*t^5+56*n^2*p^3 *t^3+24*n^2*p^2*t^4-62*n*p^4*t^3-96*n*p^3*t^4+18*p^4*t^4-12*p^3*t^5-24*n^2*p^2* t^3+124*n*p^3*t^3+48*n*p^2*t^4-24*p^4*t^3-36*p^3*t^4-12*n^2*p^2*t^2-4*n^2*p*t^3 -56*n*p^2*t^3+48*p^3*t^3+18*p^2*t^4+6*n^2*p^2*t+12*n^2*p*t^2-26*n*p^2*t^2-6*n*p *t^3-22*p^2*t^3-6*n^2*p*t-2*n^2*t^2+16*n*p^2*t+26*n*p*t^2-10*p^2*t^2-2*p*t^3+3* n^2*t-16*n*p*t-5*n*t^2+8*p^2*t+10*p*t^2-n^2+8*n*t-8*p*t-2*t^2-3*n+4*t-2)/(n+2)/ (4*n*p^2*t^2-4*n*p*t^2+2*p^2*t^2-2*p*t^2+2*n*t-n+t-1)/(p*t-1)/(p*t-t+1)*L2(n,t+ 2)+L2(n,t+3) = 0 L1(1,t) = t, L1(2,t) = -2*p^2*t^3+2*p^2*t^2+2*p*t^3-2*p*t^2+t^2, L1(3,t) = 6*p^ 4*t^5-6*p^4*t^4-12*p^3*t^5+12*p^3*t^4+6*p^2*t^5-9*p^2*t^4+3*p^2*t^3+3*p*t^4-3*p *t^3+t^3 L2(1,t) = -p*t^2*(p-1)*(t-2)/(p*t-t+1)/(p*t-1), L2(2,t) = p^2*t^4*(p-1)^2*(2*p^ 2*t^3-2*p^2*t^2-2*p*t^3+2*p*t^2+3*t^2-8*t+6)/(p*t-t+1)^2/(p*t-1)^2, L2(3,t) = - p^3*t^6*(p-1)^3*(6*p^4*t^5-6*p^4*t^4-12*p^3*t^5+12*p^3*t^4+6*p^2*t^5+9*p^2*t^4-\ 33*p^2*t^3-15*p*t^4+18*p^2*t^2+33*p*t^3-18*p*t^2+10*t^3-36*t^2+45*t-20)/(p*t-t+ 1)^3/(p*t-1)^3 These recurrences enable very fast compuations of these probabiltiy generati\ ng function, that enable us to compute expectation, variance and higher \ scaled moments. Let's assume a fair cooin. ----------------------------------------------------- If your goal is, 100, heads OR , 100, tails then the expected duration, variance, up to the, 4, scaled-moments are [188.7303042, 7.856478900, -0.8733679760, 3.450887406] If your goal is, 100, heads AND , 100, tails then the expected duration, variance, up to the, 4, scaled-moments are [211.2696958, 9.179523536, 1.113756362, 4.311938320] ----------------------------------------------------- If your goal is, 200, heads OR , 200, tails then the expected duration, variance, up to the, 4, scaled-moments are [384.0522792, 11.38957774, -0.9094549977, 3.570854483] If your goal is, 200, heads AND , 200, tails then the expected duration, variance, up to the, 4, scaled-moments are [415.9477208, 12.71290378, 1.079378443, 4.179747092] ----------------------------------------------------- If your goal is, 300, heads OR , 300, tails then the expected duration, variance, up to the, 4, scaled-moments are [580.4640412, 14.10001259, -0.9253384202, 3.624675829] If your goal is, 300, heads AND , 300, tails then the expected duration, variance, up to the, 4, scaled-moments are [619.5359588, 15.42343258, 1.064064926, 4.121845899] ----------------------------------------------------- If your goal is, 400, heads OR , 400, tails then the expected duration, variance, up to the, 4, scaled-moments are [777.4394679, 16.38480578, -0.9347771617, 3.656956936] If your goal is, 400, heads AND , 400, tails then the expected duration, variance, up to the, 4, scaled-moments are [822.5605321, 17.70827277, 1.054911179, 4.087523932] ----------------------------------------------------- If your goal is, 500, heads OR , 500, tails then the expected duration, variance, up to the, 4, scaled-moments are [974.7749818, 18.39764767, -0.9412058958, 3.679071224] If your goal is, 500, heads AND , 500, tails then the expected duration, variance, up to the, 4, scaled-moments are [1025.225018, 19.72114287, 1.048653454, 4.064184831] ----------------------------------------------------- If your goal is, 600, heads OR , 600, tails then the expected duration, variance, up to the, 4, scaled-moments are [1172.366226, 20.21733767, -0.9459448914, 3.695439332] If your goal is, 600, heads AND , 600, tails then the expected duration, variance, up to the, 4, scaled-moments are [1227.633774, 21.54085168, 1.044028471, 4.047000058] ----------------------------------------------------- If your goal is, 700, heads OR , 700, tails then the expected duration, variance, up to the, 4, scaled-moments are [1370.151224, 21.89067828, -0.9496242448, 3.708186436] If your goal is, 700, heads AND , 700, tails then the expected duration, variance, up to the, 4, scaled-moments are [1429.848776, 23.21420573, 1.040430558, 4.033669562] ----------------------------------------------------- If your goal is, 800, heads OR , 800, tails then the expected duration, variance, up to the, 4, scaled-moments are [1568.089604, 23.44816045, -0.9525876820, 3.718478016] If your goal is, 800, heads AND , 800, tails then the expected duration, variance, up to the, 4, scaled-moments are [1631.910396, 24.77169797, 1.037528202, 4.022940406] ----------------------------------------------------- If your goal is, 900, heads OR , 900, tails then the expected duration, variance, up to the, 4, scaled-moments are [1766.153326, 24.91096147, -0.9550407210, 3.727013790] If your goal is, 900, heads AND , 900, tails then the expected duration, variance, up to the, 4, scaled-moments are [1833.846674, 26.23450684, 1.035122673, 4.014064276] ----------------------------------------------------- If your goal is, 1000, heads OR , 1000, tails then the expected duration, variance, up to the, 4, scaled-moments are [1964.321978, 26.29449949, -0.9571147759, 3.734242658] If your goal is, 1000, heads AND , 1000, tails then the expected duration, variance, up to the, 4, scaled-moments are [2035.678022, 27.61805113, 1.033086625, 4.006563110] ----------------------------------------------------- If your goal is, 1100, heads OR , 1100, tails then the expected duration, variance, up to the, 4, scaled-moments are [2162.580149, 27.61041332, -0.9588983093, 3.740467628] If your goal is, 1100, heads AND , 1100, tails then the expected duration, variance, up to the, 4, scaled-moments are [2237.419851, 28.93397009, 1.031334189, 4.000115344] ----------------------------------------------------- If your goal is, 1200, heads OR , 1200, tails then the expected duration, variance, up to the, 4, scaled-moments are [2360.915871, 28.86774487, -0.9604533442, 3.745901629] If your goal is, 1200, heads AND , 1200, tails then the expected duration, variance, up to the, 4, scaled-moments are