Statistical Analysis of the duration of the number of coin tosses until you have n dollars if at each round the probability of winning a dollar is p and losing a dollar is 1-p By Shalosh B. Ekhad Suppose that at each round, you win a dollar with probability p and lose a \ dollar with probability 1-p and you quit as soon as you reach n dollars. If p>1/2, then, of course, sooner or later \ you will reach your goal, how long should it take? The probability generating function is given explicity / 2 1/2\n |1 - (1 - 4 p (1 - p) t ) | |---------------------------| \ 2 (1 - p) t / and in Maple format (1/2*(1-(1-4*p*(1-p)*t^2)^(1/2))/(1-p)/t)^n The expected duration is n -------- -1 + 2 p and in Maple format n/(-1+2*p) The variance is 4 n p (-1 + p) - -------------- 3 (-1 + 2 p) and in Maple format -4*n*p*(-1+p)/(-1+2*p)^3 The scaled , 3, -th moment about the mean is 2 -2 p + 2 p + 1 ------------------------------- 2 / n p (-1 + p)\1/2 (-1 + 2 p) |- ------------| | 3 | \ (-1 + 2 p) / and in Maple format (-2*p^2+2*p+1)/(-1+2*p)^2/(-n*p*(-1+p)/(-1+2*p)^3)^(1/2) The scaled , 4, -th moment about the mean is 4 3 2 -4 p + (6 n + 8) p + (-9 n + 6) p + (3 n - 10) p - 1 ------------------------------------------------------- n p (-1 + p) (-1 + 2 p) and in Maple format (-4*p^4+(6*n+8)*p^3+(-9*n+6)*p^2+(3*n-10)*p-1)/n/p/(-1+p)/(-1+2*p) The scaled , 5, -th moment about the mean is 6 5 4 3 (-1 + 8 p + (-40 n - 24) p + (100 n - 48) p + (-60 n + 136) p 2 / // n p (-1 + p)\1/2 + (-10 n - 42) p + (10 n - 30) p) / ||- ------------| n p (-1 + p) / || 3 | \\ (-1 + 2 p) / 3\ (-1 + 2 p) | | / and in Maple format (-1+8*p^6+(-40*n-24)*p^5+(100*n-48)*p^4+(-60*n+136)*p^3+(-10*n-42)*p^2+(10*n-30 )*p)/(-n*p*(-1+p)/(-1+2*p)^3)^(1/2)/n/p/(-1+p)/(-1+2*p)^3 The scaled , 6, -th moment about the mean is 8 7 2 6 (16 p + (-200 n - 64) p + (60 n + 700 n - 368) p 2 5 2 4 + (-180 n - 520 n + 1328) p + (195 n - 450 n - 860) p 2 3 2 2 + (-90 n + 610 n - 568) p + (15 n - 115 n + 442) p + (-25 n + 74) p / 2 2 2 2 + 1) / (n p (-1 + p) (-1 + 2 p) ) / and in Maple format (16*p^8+(-200*n-64)*p^7+(60*n^2+700*n-368)*p^6+(-180*n^2-520*n+1328)*p^5+(195*n ^2-450*n-860)*p^4+(-90*n^2+610*n-568)*p^3+(15*n^2-115*n+442)*p^2+(-25*n+74)*p+1 )/n^2/p^2/(-1+p)^2/(-1+2*p)^2 The scaled , 7, -th moment about the mean is / 10 | 4 p / 16 n\ 9 / 106 2 \ 8 - 840 |- 1/840 + ----- + |- 4/21 - ----| p + |- --- + n + 24/5 n| p \ 105 \ 15 / \ 35 / /464 2 44 \ 7 / 417 2 182 \ 6 + |--- - 4 n - -- n| p + |- --- + 23/4 n - --- n| p \35 15 / \ 35 15 / / 401 2 \ 5 / 2 433 \ 4 + |- --- - 13/4 n + 39/2 n| p + |130/7 + 1/8 n - --- n| p \ 35 / \ 60 / / 2 31 \ 3 / 403 2 21 \ 2 + |- 11/5 + 1/2 n - -- n| p + |- --- - 1/8 n + -- n| p \ 15 / \ 140 20 / \ / 83 n \ | / // n p (-1 + p)\1/2 2 2 2 4\ + |- --- + ----| p| / ||- ------------| n p (-1 + p) (-1 + 2 p) | \ 420 15 / / / || 3 | | \\ (-1 + 2 p) / / and in Maple format -840/(-n*p*(-1+p)/(-1+2*p)^3)^(1/2)*(-1/840+4/105*p^10+(-4/21-16/15*n)*p^9+(-\ 106/35+n^2+24/5*n)*p^8+(464/35-4*n^2-44/15*n)*p^7+(-417/35+23/4*n^2-182/15*n)*p ^6+(-401/35-13/4*n^2+39/2*n)*p^5+(130/7+1/8*n^2-433/60*n)*p^4+(-11/5+1/2*n^2-31 /15*n)*p^3+(-403/140-1/8*n^2+21/20*n)*p^2+(-83/420+1/15*n)*p)/n^2/p^2/(-1+p)^2/ (-1+2*p)^4 The scaled , 8, -th moment about the mean is 12 11 2 10 (-64 p + (3808 n + 384) p + (-7840 n - 20944 n + 16416) p 3 2 9 + (840 n + 39200 n - 1008 n - 85600) p 3 2 8 + (-3780 n - 67480 n + 161616 n + 88320) p 3 2 7 + (6930 n + 34720 n - 299544 n + 164544) p 3 2 6 + (-6615 n + 27580 n + 147588 n - 355824) p 3 2 5 + (3465 n - 39620 n + 77532 n + 127824) p 3 2 4 + (-945 n + 14210 n - 80976 n + 97500) p 3 2 3 2 2 + (105 n - 280 n + 7602 n - 42760) p + (-490 n + 4207 n - 10386) p / 3 3 3 3 + (119 n - 354) p - 1) / (n p (-1 + p) (-1 + 2 p) ) / and in Maple format (-64*p^12+(3808*n+384)*p^11+(-7840*n^2-20944*n+16416)*p^10+(840*n^3+39200*n^2-\ 1008*n-85600)*p^9+(-3780*n^3-67480*n^2+161616*n+88320)*p^8+(6930*n^3+34720*n^2-\ 299544*n+164544)*p^7+(-6615*n^3+27580*n^2+147588*n-355824)*p^6+(3465*n^3-39620* n^2+77532*n+127824)*p^5+(-945*n^3+14210*n^2-80976*n+97500)*p^4+(105*n^3-280*n^2 +7602*n-42760)*p^3+(-490*n^2+4207*n-10386)*p^2+(119*n-354)*p-1)/n^3/p^3/(-1+p)^ 3/(-1+2*p)^3 The scaled , 9, -th moment about the mean is / 14 | 2 p / 82 n\ 13 /1594 137 2 533 \ 12 - 20160 |1/20160 - ----- + |2/45 + ----| p + |---- - --- n - --- n| p \ 315 \ 105 / \315 45 105 / / 9746 3 274 2 907 \ 11 + |- ---- + n + --- n - --- n| p \ 315 15 105 / /9641 3 1237 2 21703 \ 10 + |---- - 11/2 n - ---- n + ----- n| p \315 36 210 / /41467 3 157 2 15123 \ 9 + |----- + 49/4 n + --- n - ----- n| p \ 315 36 70 / / 68741 3 2917 2 7933 \ 8 + |- ----- - 111/8 n + ---- n + ---- n| p \ 210 45 70 / /18622 3 7607 2 1417 \ 7 + |----- + 63/8 n - ---- n + ---- n| p \ 105 90 10 / /16903 21 3 26689 2 26559 \ 6 + |----- - -- n + ----- n - ----- n| p \ 120 16 720 140 / / 373393 13 3 289 2 1651 \ 5 + |- ------ - -- n + --- n + ---- n| p \ 2520 16 144 35 / /683 3 1589 2 17033 \ 4 + |---- + 7/16 n - ---- n + ----- n| p \1260 288 840 / /46283 3 33 2 10589 \ 3 /19637 137 2 2777 \ 2 + |----- - 1/16 n + -- n - ----- n| p + |----- + ---- n - ---- n| p \2520 40 1680 / \10080 1440 3360 / \ / 367 41 n\ | / // n p (-1 + p)\1/2 3 3 3 5\ + |----- - ----| p| / ||- ------------| n p (-1 + p) (-1 + 2 p) | \10080 3360/ / / || 3 | | \\ (-1 + 2 p) / / and in Maple format -20160/(-n*p*(-1+p)/(-1+2*p)^3)^(1/2)*(1/20160-2/315*p^14+(2/45+82/105*n)*p^13+ (1594/315-137/45*n^2-533/105*n)*p^12+(-9746/315+n^3+274/15*n^2-907/105*n)*p^11+ (9641/315-11/2*n^3-1237/36*n^2+21703/210*n)*p^10+(41467/315+49/4*n^3+157/36*n^2 -15123/70*n)*p^9+(-68741/210-111/8*n^3+2917/45*n^2+7933/70*n)*p^8+(18622/105+63 /8*n^3-7607/90*n^2+1417/10*n)*p^7+(16903/120-21/16*n^3+26689/720*n^2-26559/140* n)*p^6+(-373393/2520-13/16*n^3+289/144*n^2+1651/35*n)*p^5+(683/1260+7/16*n^3-\ 1589/288*n^2+17033/840*n)*p^4+(46283/2520-1/16*n^3+33/40*n^2-10589/1680*n)*p^3+ (19637/10080+137/1440*n^2-2777/3360*n)*p^2+(367/10080-41/3360*n)*p)/n^3/p^3/(-1 +p)^3/(-1+2*p)^5 The scaled , 10, -th moment about the mean is 16 15 2 14 (256 p + (-64128 n - 2048) p + (436800 n + 480960 n - 622080) p 3 2 13 + (-302400 n - 3057600 n + 2512128 n + 4390400) p 4 3 2 12 + (15120 n + 1965600 n + 5606160 n - 23623392 n - 2972800) p 4 3 2 11 + (-90720 n - 5065200 n + 6111840 n + 54224064 n - 39331584) p 4 3 2 10 + (234360 n + 6237000 n - 35416080 n - 22327008 n + 107136832) p 4 3 2 9 + (-340200 n - 2797200 n + 48182400 n - 85605408 n - 70262720) p 4 3 2 8 + (303345 n - 1757700 n - 22310820 n + 128502288 n - 78328080) p 4 3 2 7 + (-170100 n + 2853900 n - 7696080 n - 46958760 n + 122422720) p 4 3 2 6 + (58590 n - 1370250 n + 11305980 n - 23752020 n - 25169648) p 4 3 2 5 + (-11340 n + 217350 n - 3016860 n + 17958816 n - 26612496) p 4 3 2 4 + (945 n + 28350 n - 299775 n - 302046 n + 6809060) p 3 2 3 + (-9450 n + 147210 n - 985206 n + 2403080) p 2 2 / 4 4 + (6825 n - 59787 n + 137610) p + (-501 n + 1498) p + 1) / (n p / 4 4 (-1 + p) (-1 + 2 p) ) and in Maple format (256*p^16+(-64128*n-2048)*p^15+(436800*n^2+480960*n-622080)*p^14+(-302400*n^3-\ 3057600*n^2+2512128*n+4390400)*p^13+(15120*n^4+1965600*n^3+5606160*n^2-23623392 *n-2972800)*p^12+(-90720*n^4-5065200*n^3+6111840*n^2+54224064*n-39331584)*p^11+ (234360*n^4+6237000*n^3-35416080*n^2-22327008*n+107136832)*p^10+(-340200*n^4-\ 2797200*n^3+48182400*n^2-85605408*n-70262720)*p^9+(303345*n^4-1757700*n^3-\ 22310820*n^2+128502288*n-78328080)*p^8+(-170100*n^4+2853900*n^3-7696080*n^2-\ 46958760*n+122422720)*p^7+(58590*n^4-1370250*n^3+11305980*n^2-23752020*n-\ 25169648)*p^6+(-11340*n^4+217350*n^3-3016860*n^2+17958816*n-26612496)*p^5+(945* n^4+28350*n^3-299775*n^2-302046*n+6809060)*p^4+(-9450*n^3+147210*n^2-985206*n+ 2403080)*p^3+(6825*n^2-59787*n+137610)*p^2+(-501*n+1498)*p+1)/n^4/p^4/(-1+p)^4/ (-1+2*p)^4 Let's check it against numerical computations for p=, 2/3, and n= , 3 The exact value for these values is [9., 72., 3.064129385, 18.38888889, 138.6060237, 1312.873457, 14956.58369, 7 8 199489.9539, 0.3051547231 10 , 0.5268462159 10 ] Let's see what happened after, 500, rounds The probability of ending in <=, 500, rounds is , 1.000000000 The approximate values for the average, variance, and higher scaled-moments \ about the mean are [9.000000000, 72.00000000, 3.064129384, 18.38888888, 138.6060231, 1312.873420, 7 8 14956.58148, 199489.8208, 0.3051539192 10 , 0.5268413528 10 ] compared to the exact values [9., 72., 3.064129385, 18.38888889, 138.6060237, 1312.873457, 14956.58369, 7 8 199489.9539, 0.3051547231 10 , 0.5268462159 10 ] Now let's run a simulation with, 2000, times (where you quit after, 500, rounds) The fraction of games that ended in <=, 500, rounds is 1. the statistical data for the simulation turned out to be [9.374000000, 82.39212400, 2.869423413, 15.28380584, 94.59385295, 673.4699180, 7 5209.723567, 42463.10856, 357781.2051, 0.3081041463 10 ] Of course, this changes each time, but it is not too far off. recall that the exact value is [9., 72., 3.064129385, 18.38888889, 138.6060237, 1312.873457, 14956.58369, 7 8 199489.9539, 0.3051547231 10 , 0.5268462159 10 ] This ends this article that took, 2.359, seconds to generate.