`` Recurrences for the Probability of being broke after 2n steps using a fair die By Shalosh B. Ekhad Cosider a random walker who walks on the discrete line, and decides where to go next by rolling a fair die with, 2, faces , marked with -1, 1 Let , a(n), be its probability of visiting the origin after 2n steps Then a(n) satisfies the linear recurrence equation (2 n + 1) a(n) + (-2 n - 2) a(n + 1) = 0 subject to the initial conditions a[1] = 1/2 Proof: Use the Almkvist-Zeilberger algorithm Using this recurrence, it follows that the asymptotic behavior of a(n) is / 1 1 5 \ 0.56418958354776 |1 - --- + ------ + -------| | 8 n 2 3| \ 128 n 1024 n / --------------------------------------------- 1/2 n Caveat: the constant in front is a non-rigorous estimate, everything else is rigorous Cosider a random walker who walks on the discrete line, and decides where to go next by rolling a fair die with, 4, faces , marked with -3, -1, 1, 3 Let , a(n), be its probability of visiting the origin after 2n steps Then a(n) satisfies the linear recurrence equation (2 n + 3) (2 n + 1) (5 n + 9) (n + 1) a(n) 3 2 - (2 n + 3) (145 n + 551 n + 665 n + 256) a(n + 1) + 6 (3 n + 5) (3 n + 4) (5 n + 4) (n + 2) a(n + 2) = 0 subject to the initial conditions 11 a[1] = 1/4, a[2] = -- 64 Proof: Use the Almkvist-Zeilberger algorithm Using this recurrence, it follows that the asymptotic behavior of a(n) is / 17 19 4913 \ 0.252313252202016 |1 - ----- - -------- + ----------| | 200 n 2 3| \ 16000 n 3200000 n / ----------------------------------------------------- 1/2 n Caveat: the constant in front is a non-rigorous estimate, everything else is rigorous Cosider a random walker who walks on the discrete line, and decides where to go next by rolling a fair die with, 6, faces , marked with -5, -3, -1, 1, 3, 5 Let , a(n), be its probability of visiting the origin after 2n steps Then a(n) satisfies the linear recurrence equation -4 (2 n + 5) (2 n + 3) (2 n + 1) (7 n + 19) (5 n + 11) (7 n + 20) (7 n + 13) (n + 2) (n + 1) a(n) + 4 (7 n + 20) (2 n + 5) (2 n + 3) (n + 2) 5 4 3 2 (25480 n + 223496 n + 755066 n + 1223233 n + 946889 n + 279936) 6 5 a(n + 1) - (5 n + 6) (2 n + 5) (7 n + 6) (499359 n + 6777015 n 4 3 2 + 38079431 n + 113390385 n + 188723986 n + 166469280 n + 60800544) a(n + 2) + 30 (5 n + 14) (5 n + 13) (5 n + 12) (7 n + 12) (5 n + 11) (5 n + 6) (7 n + 13) (7 n + 6) (3 + n) a(3 + n) = 0 subject to the initial conditions 73 361 a[1] = 1/6, a[2] = ---, a[3] = ---- 648 3888 Proof: Use the Almkvist-Zeilberger algorithm Using this recurrence, it follows that the asymptotic behavior of a(n) is / 111 12037 1367631 \ 0.165177796722318 |1 - ------ - ---------- + -------------| | 1400 n 2 3| \ 5488000 n 1097600000 n / ----------------------------------------------------------- 1/2 n Caveat: the constant in front is a non-rigorous estimate, everything else is rigorous Cosider a random walker who walks on the discrete line, and decides where to go next by rolling a fair die with, 8, faces , marked with -7, -5, -3, -1, 1, 3, 5, 7 Let , a(n), be its probability of visiting the origin after 2n steps Then a(n) satisfies the linear recurrence equation 2 (9 n + 35) (9 n + 26) (9 n + 17) (22 + 7 n) (7 n + 15) (9 n + 34) (9 n + 25) (7 n + 23) (3 n + 11) (2 n + 7) (2 n + 5) (2 n + 3) (2 n + 1) (3 + n) (n + 2) (n + 1) a(n) - 2 (22 + 7 n) (9 n + 35) (9 n + 26) (2 n + 7) 7 6 (2 n + 5) (2 n + 3) (9 n + 34) (3 + n) (n + 2) (2988657 n + 47106927 n 5 4 3 2 + 308299233 n + 1082677961 n + 2195925623 n + 2563099333 n + 1588693387 n + 402653184) a(n + 1) + 3 (9 n + 8) (2 n + 7) (2 n + 5) 10 9 (7 n + 8) (3 + n) (9 n + 35) (1381866885 n + 38056175325 n 8 7 6 + 468385432416 n + 3392266350552 n + 16008364902577 n 5 4 3 + 51428276217181 n + 113895957376388 n + 171686882573408 n 2 + 168572639572488 n + 97347661631664 n + 25107146735616) a(n + 2) - (7 n + 16) (2 n + 7) (7 n + 15) (7 n + 8) (9 n + 16) (9 n + 17) (9 n + 8) ( 9 8 7 6 218437803 n + 6407508888 n + 83369869683 n + 631518621781 n 5 4 3 + 3069147801342 n + 9924269285287 n + 21351530132832 n 2 + 29472429925984 n + 23684436468600 n + 8442532454400) a(3 + n) + 14 (22 + 7 n) (7 n + 15) (7 n + 8) (7 n + 23) (7 n + 16) (3 n + 8) (7 n + 24) (9 n + 26) (9 n + 17) (9 n + 8) (7 n + 25) (7 n + 26) (7 n + 27) (9 n + 25) (9 n + 16) (n + 4) a(n + 4) = 0 subject to the initial conditions 43 2269 126583 a[1] = 1/8, a[2] = ---, a[3] = -----, a[4] = ------- 512 32768 2097152 Proof: Use the Almkvist-Zeilberger algorithm Using this recurrence, it follows that the asymptotic behavior of a(n) is / 13 331 10985 \ 0.123116260614915 |1 - ----- - --------- + ----------| | 168 n 2 3| \ 131712 n 9483264 n / ------------------------------------------------------ 1/2 n Caveat: the constant in front is a non-rigorous estimate, everything else is rigorous Cosider a random walker who walks on the discrete line, and decides where to go next by rolling a fair die with, 10, faces , marked with -9, -7, -5, -3, -1, 1, 3, 5, 7, 9 Let , a(n), be its probability of visiting the origin after 2n steps Then a(n) satisfies the linear recurrence equation 16 (11 n + 52) (11 n + 41) (11 n + 54) (11 n + 43) (11 n + 32) (11 n + 21) (11 n + 51) (2 n + 9) (2 n + 7) (2 n + 5) (2 n + 3) (2 n + 1) (3 n + 13) (11 n + 53) (11 n + 42) (31 + 11 n) (9 n + 38) (9 n + 29) (9 n + 37) (9 n + 28) (9 n + 19) (n + 4) (3 + n) (n + 2) (n + 1) a(n) - 16 (11 n + 52) (11 n + 54) (11 n + 43) (11 n + 32) (2 n + 9) (2 n + 7) (2 n + 5) (2 n + 3) (11 n + 53) (11 n + 42) (9 n + 38) (9 n + 37) (9 n + 28) (n + 4) (3 + n) 9 8 7 (n + 2) (1757534922 n + 43512303978 n + 466044956652 n 6 5 4 + 2827914734458 n + 10686167297738 n + 26004703880212 n 3 2 + 40623957448628 n + 39150643367527 n + 21050693640983 n + 4800000000000 ) a(n + 1) + 12 (11 n + 54) (11 n + 43) (11 n + 10) (2 n + 9) (2 n + 7) (2 n + 5) (11 n + 53) (9 n + 37) (9 n + 10) (n + 4) (3 + n) ( 14 13 12 437912250396489 n + 19936065783201777 n + 418449454496246151 n 11 10 + 5366568621447712833 n + 46974780909181660205 n 9 8 + 296832126591855350903 n + 1396173491688708125697 n 7 6 + 4965141748146074138043 n + 13413661131078364168050 n 5 4 + 27391639643208730814100 n + 41615471821042114599112 n 3 2 + 45608780787272641706944 n + 34082705548223637017472 n + 15543580179724299288576 n + 3263699655216000000000) a(n + 2) - 4 (11 n + 54) (11 n + 21) (11 n + 10) (11 n + 20) (2 n + 9) (2 n + 7) 15 (9 n + 20) (9 n + 19) (9 n + 10) (n + 4) (10045020643309080 n 14 13 + 565565101674796080 n + 14824121313670530510 n 12 11 + 239949884589574989445 n + 2682292497149078857296 n 10 9 + 21934210497949657931375 n + 135546143646597494371650 n 8 7 + 644563927321844275461075 n + 2378008670176332274869852 n 6 5 + 6806518205843212732312361 n + 14991216521954746019700060 n 4 3 + 24950300788170205143562480 n + 30374837038835646905498832 n 2 + 25535622849825247151683824 n + 13255496539602971064399360 n + 3202901831731876560000000) a(3 + n) + (11 n + 32) (11 n + 21) (11 n + 10) (31 + 11 n) (11 n + 20) (2 n + 9) (11 n + 30) (3 n + 10) 12 (9 n + 29) (9 n + 20) (9 n + 28) (9 n + 19) (9 n + 10) (31015667237005 n 11 10 9 + 1584618635199710 n + 37074568500450305 n + 525254310112369090 n 8 7 + 5018719638888905859 n + 34070592201981921066 n 6 5 + 168507492076764038147 n + 611774266511024059150 n 4 3 + 1618140199206066577036 n + 3040919030591316603944 n 2 + 3854107703553818706528 n + 2957914753254564721920 n + 1039575322802016000000) a(n + 4) - 810 (9 n + 37) (9 n + 28) (9 n + 19) (9 n + 10) (11 n + 43) (11 n + 32) (11 n + 21) (11 n + 10) (9 n + 38) (9 n + 29) (9 n + 20) (3 n + 13) (3 n + 10) (11 n + 42) (31 + 11 n) (11 n + 20) (9 n + 40) (11 n + 41) (11 n + 30) (9 n + 41) (3 n + 14) (11 n + 40) (9 n + 43) (9 n + 44) (5 + n) a(5 + n) = 0 subject to the initial conditions 67 13813 481603 10811441 a[1] = 1/10, a[2] = ----, a[3] = ------, a[4] = --------, a[5] = --------- 1000 250000 10000000 250000000 Proof: Use the Almkvist-Zeilberger algorithm Using this recurrence, it follows that the asymptotic behavior of a(n) is / 101 617 1030301 \ 0.0982128002186148 |1 - ------ - --------- + ------------| | 1320 n 2 3| \ 232320 n 919987200 n / ---------------------------------------------------------- 1/2 n Caveat: the constant in front is a non-rigorous estimate, everything else is rigorous This took, 148.777, seconds