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, 3, faces marked as follows, with the given probabilities A face marked with , 1, dots , with probability, 1/3 A face marked with , 2, dots , with probability, 1/3 A face marked with , 3, dots , with probability, 1/3 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 6 a(n) = -1/18 (2320739396307106544860239396 n 5 4 - 59745221751240077413439161239 n + 585645231978178735566301292978 n 3 2 - 2751436997792475095198452589591 n + 6440957257471339487034060221353 n - 7057348112065221205818286257031 n + 2832587668834497767770112539104) 6 a(n - 1)/(n (2 n - 1) %1) + 1/162 (8371496018470994722645021788 n 5 4 - 211149839505129264070956259065 n + 2021061372086633637936209999833 n 3 2 - 9354176212784723004626472270782 n + 21657682088760718627853812935077 n - 23151748011626175945133679982577 n + 8704844317293871610764818192012) 6 a(n - 2)/(n (2 n - 1) %1) + 1/486 (33711538044766050519295679904 n 5 4 - 873168089019405338058967081224 n + 8714347721036577656392058558920 n 3 - 42918414661043144673461141940887 n 2 + 109927860021175616407939849139027 n - 138135233440656617412182530076416 n + 65646008170081811260211558239890) 6 a(n - 3)/(n (2 n - 1) %1) + 1/1458 (53249697214730833309207165872 n 5 4 - 1444205689930222102992819529692 n + 15340452167642703148200508083706 n 3 - 81873638463301030916810963697557 n 2 + 231950366015432222653360883919101 n - 329335179473509404247901848127818 n + 180825155805691068048387560336874) 6 a(n - 4)/(n (2 n - 1) %1) + 1/1458 (5947019126576957437829108856 n 5 4 - 166571108415035171680144918986 n + 1837622253737390851216865968290 n 3 - 10215543583183392289532703749939 n 2 + 30424721562381157709384496085269 n - 46642631288027827149359278517074 n + 28853046991527090040451937174450) a(n - 5)/(n (2 n - 1) %1) - 1/1458 ( 6 5 9590805885841719309839778264 n - 272583848790278625058993673946 n 4 3 + 3016189958396060061650563671618 n - 16437514713890468822450188952941 n 2 + 45608239869471985246712399397345 n - 59294862641493940477960088365640 n + 27210851426228319251769077209530) a(n - 6)/(n (2 n - 1) %1) - 1/1458 ( 6 5 6508844546017172554445016960 n - 190314758937136749553900802880 n 4 3 + 2176628094840761022980066529308 n - 12324560276244805994527120238561 n 2 + 35981015782583222255392525437577 n - 50793893498175689217885904461928 n + 26622397396994113119728438749158) a(n - 7)/(n (2 n - 1) %1) + 1/1458 ( 5 4 984258603465365076252949728 n - 26168777317574961988263864660 n 3 2 + 263574277095558968862541968203 n - 1229856046452686831857959473529 n + 2588842300199101455038479613320 n - 1950208307779100734811539356234) 5 a(n - 8)/(n (2 n - 1) %1) + 1/1458 (n - 9) (32748356849818135379084172 n 4 3 - 803620519585225913690922681 n + 6330879740471440815459189267 n 2 - 18065047592772380796947099221 n + 6693858045986109727904255655 n + 15086226080426239106218549330) a(n - 9)/(n (2 n - 1) %1) + 1/1458 4 (n - 9) (n - 10) (203401392063036642326406780 n 3 2 - 2846704350568400439501415005 n + 12875538467842979827894759126 n - 22494747481022966463790701755 n + 12627553174048080248946343731) a(n - 10)/(n (2 n - 1) %1) 4 3 %1 := 10916118949939378459694724 n - 210989161457335802247866691 n 2 + 1307885461388499210577571345 n - 3319576951107553202550221822 n + 3381670186995330668234774949 Subject to the initial conditions 35 389 2615 22427 a(1) = 1, a(2) = 5/9, a(3) = --, a(4) = ---, a(5) = ----, a(6) = -----, 81 729 6561 59049 191855 1606181 13665941 116959979 a(7) = ------, a(8) = -------, a(9) = --------, a(10) = --------- 531441 4782969 43046721 387420489 and in Maple notation a(n) = -1/18*(2320739396307106544860239396*n^6-59745221751240077413439161239*n^ 5+585645231978178735566301292978*n^4-2751436997792475095198452589591*n^3+ 6440957257471339487034060221353*n^2-7057348112065221205818286257031*n+ 2832587668834497767770112539104)/n/(2*n-1)/(10916118949939378459694724*n^4-\ 210989161457335802247866691*n^3+1307885461388499210577571345*n^2-\ 3319576951107553202550221822*n+3381670186995330668234774949)*a(n-1)+1/162*( 8371496018470994722645021788*n^6-211149839505129264070956259065*n^5+ 2021061372086633637936209999833*n^4-9354176212784723004626472270782*n^3+ 21657682088760718627853812935077*n^2-23151748011626175945133679982577*n+ 8704844317293871610764818192012)/n/(2*n-1)/(10916118949939378459694724*n^4-\ 210989161457335802247866691*n^3+1307885461388499210577571345*n^2-\ 3319576951107553202550221822*n+3381670186995330668234774949)*a(n-2)+1/486*( 33711538044766050519295679904*n^6-873168089019405338058967081224*n^5+ 8714347721036577656392058558920*n^4-42918414661043144673461141940887*n^3+ 109927860021175616407939849139027*n^2-138135233440656617412182530076416*n+ 65646008170081811260211558239890)/n/(2*n-1)/(10916118949939378459694724*n^4-\ 210989161457335802247866691*n^3+1307885461388499210577571345*n^2-\ 3319576951107553202550221822*n+3381670186995330668234774949)*a(n-3)+1/1458*( 53249697214730833309207165872*n^6-1444205689930222102992819529692*n^5+ 15340452167642703148200508083706*n^4-81873638463301030916810963697557*n^3+ 231950366015432222653360883919101*n^2-329335179473509404247901848127818*n+ 180825155805691068048387560336874)/n/(2*n-1)/(10916118949939378459694724*n^4-\ 210989161457335802247866691*n^3+1307885461388499210577571345*n^2-\ 3319576951107553202550221822*n+3381670186995330668234774949)*a(n-4)+1/1458*( 5947019126576957437829108856*n^6-166571108415035171680144918986*n^5+ 1837622253737390851216865968290*n^4-10215543583183392289532703749939*n^3+ 30424721562381157709384496085269*n^2-46642631288027827149359278517074*n+ 28853046991527090040451937174450)/n/(2*n-1)/(10916118949939378459694724*n^4-\ 210989161457335802247866691*n^3+1307885461388499210577571345*n^2-\ 3319576951107553202550221822*n+3381670186995330668234774949)*a(n-5)-1/1458*( 9590805885841719309839778264*n^6-272583848790278625058993673946*n^5+ 3016189958396060061650563671618*n^4-16437514713890468822450188952941*n^3+ 45608239869471985246712399397345*n^2-59294862641493940477960088365640*n+ 27210851426228319251769077209530)/n/(2*n-1)/(10916118949939378459694724*n^4-\ 210989161457335802247866691*n^3+1307885461388499210577571345*n^2-\ 3319576951107553202550221822*n+3381670186995330668234774949)*a(n-6)-1/1458*( 6508844546017172554445016960*n^6-190314758937136749553900802880*n^5+ 2176628094840761022980066529308*n^4-12324560276244805994527120238561*n^3+ 35981015782583222255392525437577*n^2-50793893498175689217885904461928*n+ 26622397396994113119728438749158)/n/(2*n-1)/(10916118949939378459694724*n^4-\ 210989161457335802247866691*n^3+1307885461388499210577571345*n^2-\ 3319576951107553202550221822*n+3381670186995330668234774949)*a(n-7)+1/1458*( 984258603465365076252949728*n^5-26168777317574961988263864660*n^4+ 263574277095558968862541968203*n^3-1229856046452686831857959473529*n^2+ 2588842300199101455038479613320*n-1950208307779100734811539356234)/n/(2*n-1)/( 10916118949939378459694724*n^4-210989161457335802247866691*n^3+ 1307885461388499210577571345*n^2-3319576951107553202550221822*n+ 3381670186995330668234774949)*a(n-8)+1/1458*(n-9)*(32748356849818135379084172*n ^5-803620519585225913690922681*n^4+6330879740471440815459189267*n^3-\ 18065047592772380796947099221*n^2+6693858045986109727904255655*n+ 15086226080426239106218549330)/n/(2*n-1)/(10916118949939378459694724*n^4-\ 210989161457335802247866691*n^3+1307885461388499210577571345*n^2-\ 3319576951107553202550221822*n+3381670186995330668234774949)*a(n-9)+1/1458*(n-9 )*(n-10)*(203401392063036642326406780*n^4-2846704350568400439501415005*n^3+ 12875538467842979827894759126*n^2-22494747481022966463790701755*n+ 12627553174048080248946343731)/n/(2*n-1)/(10916118949939378459694724*n^4-\ 210989161457335802247866691*n^3+1307885461388499210577571345*n^2-\ 3319576951107553202550221822*n+3381670186995330668234774949)*a(n-10) a(1) = 1, a(2) = 5/9, a(3) = 35/81, a(4) = 389/729, a(5) = 2615/6561, a(6) = 22427/59049, a(7) = 191855/531441, a(8) = 1606181/4782969, a(9) = 13665941/ 43046721, a(10) = 116959979/387420489 Just for kicks, a(1000), equals , 6000149715760823165151887453781875384291062\ 382446130030277884973009695822340704993874876396303899376423536511771559\ 846588606710470123159598145736776577074959942965358650114362333237127135\ 470309948667066960731380292609314421421119330572329711074135538634101732\ 626091415191631278567929905970673438495446688565344676133359299881845116\ 457481565356861289262163813025868231043132718608718036461361462778832851\ 454668273822097329586454601448162506176101134845495431823341079895659360\ 977152812016050169958287275487918893382918518558060361449799041243224930\ 785996671415802529021202047827897528164947408255429020697344127646615125\ 792647167908917979216179759958933325340560202476059194713270990523179982\ 820765454475510346005454560266558766382824580556877516117835999349088557\ 478973978348335146818659854813278220635743168330048062812434366195727969\ 723622369674322897680309205908952524448509754642348882022049250257129011\ / 749607315262592031461736209700418862228406523 / 1942079168580724010733\ / 305132405178411698958319372431686457653346456318073585861654768318299849\ 645678972898834106828085098634853817639454052793793557881820535414347088\ 988863532646144031642578359465910158535004915621567655793889445164237706\ 465473002117114006093442375507754853945584250266012576271108796137418938\ 632958476273785044817364417032910293605644167189847180526767894938263728\ 113495723861497878617033503632297703435221644321210916278713106186087340\ 441084071730159708507807867114711086397628107607488993013753239745040104\ 692986721231136937932425586624982678976071599463161364402150245855349726\ 018647307172785906748613317082273405102829773381278597564793890760755286\ 729895498621384854049351279847931205862892884240456605730666380086241798\ 790667983506224534190829762177066532766879925988850301417114586583813608\ 848077417680717892395937727083825325209928941157259486136819934789656482\ 16640862698897925988931145600683858128653568049999074868783790048889 Hence the probability of the first player winning if the goal is to reach, 1000, chips is 1001040332869166121192412003471498582770934471598446493380216098093207515904\ 634352353533531906342336368567099612271841782260460461170342824387625462\ 823795642506888371287682338134738201456966531282698414602306114712246874\ 469051828178771714881291871736250173555384318210953385129184964782536141\ 502746875302152296039859904933391931634264495924281931109268394413988719\ 604539163132724907646930168738062833472774025157517962204258754433612698\ 951887433598717897697701152570479332550708819321415623449663845240121936\ 101343534465112842648300609610774685090866723295848418500680905741819821\ 688715947664716140154427140307031186449935621776976247141310967589439093\ 449023648181390023660921315665645042924589743751237980483176469393029635\ 659165104166023683782914580933109012538202275958425008059174056293699217\ 099660472007748454664352771012189924837817481653761034219452872124659287\ 831032209943601452827614423740740915589714476039995603603425148931043876\ / 43823009227706 / 19420791685807240107333051324051784116989583193724316\ / 864576533464563180735858616547683182998496456789728988341068280850986348\ 538176394540527937935578818205354143470889888635326461440316425783594659\ 101585350049156215676557938894451642377064654730021171140060934423755077\ 548539455842502660125762711087961374189386329584762737850448173644170329\ 102936056441671898471805267678949382637281134957238614978786170335036322\ 977034352216443212109162787131061860873404410840717301597085078078671147\ 110863976281076074889930137532397450401046929867212311369379324255866249\ 826789760715994631613644021502458553497260186473071727859067486133170822\ 734051028297733812785975647938907607552867298954986213848540493512798479\ 312058628928842404566057306663800862417987906679835062245341908297621770\ 665327668799259888503014171145865838136088480774176807178923959377270838\ 253252099289411572594861368199347896564821664086269889792598893114560068\ 3858128653568049999074868783790048889 that, in floating point is 0.5154477475 ----------------------- This ends this article that took, 5.351, seconds to produce.