On the Probabilities of the First Player Winning in a Two-Player Pile game   where the winner is the first to accumulate n dollars



                              By Shalosh B. Ekhad



                Consider the following simple 2-Player Pile game



Players take turn tossing a die with, 2,

    faces marked as follows, with the given probabilities



              A face marked with , 1, dots , with probability, 1/2

              A face marked with , 2, dots , with probability, 1/2

             and they get the number of chips indicated by the die

   The player to be the FIRST to accumulate n chips is declared the winner.



            Theorem: The probability of the FIRST player winning is



                                 1/2 + 1/2 a(n)



      where a(n) is a squence of numbers satisfying the linear recurrence



                                                  2
           (3 n - 1) (n - 3) a(n - 1)        (21 n  - 67 n + 62) a(n - 2)
a(n) = 1/2 -------------------------- + 1/16 ----------------------------
                  n (3 n - 7)                        n (3 n - 7)

                2
            (6 n  - 17 n + 2) a(n - 3)        (n - 4) (3 n - 4) a(n - 4)
     + 1/16 -------------------------- - 1/16 --------------------------
                   n (3 n - 7)                       n (3 n - 7)



                       Subject to the initial conditions



                                                           15
                  a(1) = 1, a(2) = 1/2, a(3) = 5/8, a(4) = --
                                                           32



                             and in Maple notation



a(n) = 1/2*(3*n-1)*(n-3)/n/(3*n-7)*a(n-1)+1/16*(21*n^2-67*n+62)/n/(3*n-7)*a(n-2
)+1/16*(6*n^2-17*n+2)/n/(3*n-7)*a(n-3)-1/16*(n-4)*(3*n-4)/n/(3*n-7)*a(n-4)




a(1) = 1, a(2) = 1/2, a(3) = 5/8, a(4) = 15/32


Just for kicks, a(1000), equals , 4703025243733041245335180218650942764448856\
    444605768897659990219445020141284929026052521191573282233326318855259872\
    552922579333002745672824909918402769023624502287064946531767873542382066\
    449193520452604040205655122135402146292411862426909600341428682982963475\
    605264084427536007774814301596045620789466531629834098430299193799736313\
    988658592807338277347843459537298749887359135316144812507093968210527416\
    519420537400321012195393888578364129869363322809672454902076372772889698\
    412021463820937173920753812452022073989538643698657893785692457379938431\

                                                            /
    82416227511715178615164461382028011183895978368827703  /  14351633690928\
                                                          /
    181552910415014721024800278971276108690005970534210322078267404628923208\
    243578956328373980574557987343284668088987010788191642824141952083164817\
    391248643164035000086097393530005608928615873757935780597701932955798545\
    493414628255058294246363124569770299851118078700702913956192020527746291\
    585168021113623057313200297435600989257362616847062553625339588328228815\
    251016529535161470158485414650824874424552265877722482300505269981647906\
    442611179237761490069369722948709004895010244652078822844422553197965751\
    941043598302429006813614409472985328146929441100102855346352245681720273\
    106393628672



Hence the probability of the first player winning if the goal is to reach, 1000,

    chips is



1482193621530148567744393303658611907672385692056926689573653323226658028153\
    312182581349569811365659731320644351333053996034692031106275892531513379\
    236006717984147734965868817687345163173665052828066113416195634610991547\
    317042778667965731921509243711466142091733082625956083230148039538635162\
    508982523823833100452346608723258027106699985511664335067479733797129331\
    820321755116454814401641217955530646739247681647829229797894202168936310\
    639463484277489214648325169770664701191855020704139233836947089822566775\
    540536470580541346409180757605935240331616774437444115627871801980773427\

                             /
    3692904169084762456375  /  287032673818563631058208300294420496005579425\
                           /
    522173800119410684206441565348092578464164871579126567479611491159746865\
    693361779740215763832856482839041663296347824972863280700001721947870600\
    112178572317475158715611954038659115970909868292565101165884927262491395\
    405997022361574014058279123840410554925831703360422272461146264005948712\
    019785147252336941251072506791766564576305020330590703229403169708293016\
    497488491045317554449646010105399632958128852223584755229801387394458974\
    180097900204893041576456888451063959315038820871966048580136272288189459\
    70656293858882200205710692704491363440546212787257344



                           that, in floating point is

                                  0.5163849822



                            -----------------------



         This ends this article that took, 0.139, seconds to produce.