The Relative Probablity of Winning a Daniel Litt style game when rolling a f\ air, 2, sides die marked with, {1, 2}, of number of occurrences of, [1, 1, 1], Versus the number of occurences of all, 3, letter words in, {1, 2} By Shalosh B. Ekhad ----------------------------------------------------------------------------\ ----------------------- Question Mumber, 1, : If Alice bets that there are more occurrences of consec\ utive substrings in, {[1, 2, 1]}, than in, {[1, 1, 1]}, and Bob, bets vice versa, who is more likely to win? Answer: Alice is more likely to win. Let's be more quantitative. We need the following two lemmas Lemma , 1.1, : Let a(n) be the number of words of length n in the alphabet , {1, 2}, with more occurences of, {[1, 2, 1]}, then , {[1, 1, 1]} a(n) satisfies the following linear recurrence equation with polynomial coef\ ficients of order, 22 (2 n + 3) (n + 2) (n + 1) a(n) -32/3 ------------------------------ (n + 20) (n + 19) (n + 22) (2 n + 5) (11 n + 39) (n + 2) a(n + 1) + 16/3 -------------------------------------- (n + 20) (n + 19) (n + 22) 2 (n + 4) (74 n + 592 n + 1113) a(n + 2) - 32/3 --------------------------------------- (n + 20) (n + 19) (n + 22) 2 (n + 4) (605 n + 6517 n + 18204) a(n + 3) + 8/3 ------------------------------------------ (n + 20) (n + 19) (n + 22) 3 2 (785 n + 9393 n + 35968 n + 42324) a(n + 4) - 4/3 --------------------------------------------- (n + 20) (n + 19) (n + 22) 3 2 (487 n - 1470 n - 66871 n - 244986) a(n + 5) + 4/3 ---------------------------------------------- (n + 20) (n + 19) (n + 22) 3 2 (13 n + 5430 n + 69449 n + 226692) a(n + 6) + 8/3 --------------------------------------------- (n + 20) (n + 19) (n + 22) 3 2 (3607 n + 83943 n + 645776 n + 1646496) a(n + 7) - 2/3 -------------------------------------------------- (n + 20) (n + 19) (n + 22) 3 2 (8291 n + 155757 n + 808042 n + 682824) a(n + 8) + 1/3 -------------------------------------------------- (n + 20) (n + 19) (n + 22) 3 2 (1271 n + 13023 n - 101176 n - 1050116) a(n + 9) - -------------------------------------------------- (n + 20) (n + 19) (n + 22) 3 2 (71 n + 21021 n + 368761 n + 1620366) a(n + 10) - 2/3 ------------------------------------------------- (n + 20) (n + 19) (n + 22) 3 2 (5003 n + 179013 n + 1996948 n + 6880668) a(n + 11) + 1/3 ----------------------------------------------------- (n + 20) (n + 19) (n + 22) 3 2 (365 n + 12378 n + 134602 n + 462372) a(n + 12) - 14/3 ------------------------------------------------- (n + 20) (n + 19) (n + 22) 3 2 (221 n - 3948 n - 212273 n - 1595466) a(n + 13) + 2/3 ------------------------------------------------- (n + 20) (n + 19) (n + 22) 3 2 (1543 n + 79827 n + 1297454 n + 6734064) a(n + 14) + 1/3 ---------------------------------------------------- (n + 20) (n + 19) (n + 22) 3 2 (277 n + 12144 n + 172946 n + 796302) a(n + 15) - 4/3 ------------------------------------------------- (n + 20) (n + 19) (n + 22) 3 2 (835 n + 33273 n + 425978 n + 1723464) a(n + 16) + 1/3 -------------------------------------------------- (n + 20) (n + 19) (n + 22) 3 2 (421 n + 18033 n + 255380 n + 1200876) a(n + 17) - 1/3 -------------------------------------------------- (n + 20) (n + 19) (n + 22) 2 (n + 18) (14 n + 540 n + 6349) a(n + 18) + 2/3 ----------------------------------------- (n + 20) (n + 19) (n + 22) 3 2 (7 n - 135 n - 12412 n - 138948) a(n + 19) + 1/3 -------------------------------------------- (n + 20) (n + 19) (n + 22) 3 2 2 (6 n + 367 n + 7452 n + 50244) a(n + 20) + -------------------------------------------- (n + 20) (n + 19) (n + 22) (5 n + 106) (2 n + 39) a(n + 21) - 2/3 -------------------------------- + a(n + 22) = 0 (n + 22) (n + 20) Subject to the initial conditions a(1) = 0, a(2) = 0, a(3) = 1, a(4) = 4, a(5) = 9, a(6) = 19, a(7) = 44, a(8) = 97, a(9) = 198, a(10) = 407, a(11) = 853, a(12) = 1747, a(13) = 3516, a(14) = 7139, a(15) = 14528, a(16) = 29252, a(17) = 58739, a(18) = 118464, a(19) = 238553, a(20) = 478396, a(21) = 959870, a(22) = 1928605 Lemma , 1.2, : Let b(n) be the number of words of length n in the alphabet , {1, 2}, with more occurences of, {[1, 1, 1]}, then , {[1, 2, 1]} b(n) satisfies the following linear recurrence equation with polynomial coef\ ficients of order, 15 2 (2 n + 3) (n + 2) (n + 1) b(n) (n + 2) (14 n + 65 n + 87) b(n + 1) 32/3 ------------------------------ - 16/3 ------------------------------------ (n + 15) (n + 14) (n + 12) (n + 15) (n + 14) (n + 12) 3 2 (14 n + 144 n + 511 n + 612) b(n + 2) + 32/3 --------------------------------------- (n + 15) (n + 14) (n + 12) 3 2 (65 n + 879 n + 3946 n + 5868) b(n + 3) - 8/3 ----------------------------------------- (n + 15) (n + 14) (n + 12) 3 2 (59 n + 1335 n + 9532 n + 21612) b(n + 4) - 4/3 ------------------------------------------- (n + 15) (n + 14) (n + 12) 3 2 (265 n + 5178 n + 33347 n + 70818) b(n + 5) + 4/3 --------------------------------------------- (n + 15) (n + 14) (n + 12) 3 2 (113 n + 1503 n + 3694 n - 8892) b(n + 6) - 4/3 ------------------------------------------- (n + 15) (n + 14) (n + 12) 3 2 (265 n + 9195 n + 95450 n + 310884) b(n + 7) - 2/3 ---------------------------------------------- (n + 15) (n + 14) (n + 12) 3 2 (533 n + 17103 n + 172786 n + 560088) b(n + 8) + 1/3 ------------------------------------------------ (n + 15) (n + 14) (n + 12) 3 2 (39 n + 819 n + 3732 n - 5020) b(n + 9) - ----------------------------------------- (n + 15) (n + 14) (n + 12) 3 2 (43 n + 2065 n + 29248 n + 129204) b(n + 10) - ---------------------------------------------- (n + 15) (n + 14) (n + 12) 3 2 (227 n + 8667 n + 108202 n + 443568) b(n + 11) + 1/3 ------------------------------------------------ (n + 15) (n + 14) (n + 12) 3 2 (67 n + 2429 n + 29250 n + 116976) b(n + 12) - ---------------------------------------------- (n + 15) (n + 14) (n + 12) 3 2 (101 n + 3753 n + 46360 n + 190308) b(n + 13) + 1/3 ----------------------------------------------- (n + 15) (n + 14) (n + 12) 2 3 (3 n + 75 n + 466) b(n + 14) - ------------------------------- + b(n + 15) = 0 (n + 15) (n + 12) Subject to the initial conditions b(1) = 0, b(2) = 0, b(3) = 1, b(4) = 3, b(5) = 6, b(6) = 14, b(7) = 34, b(8) = 72, b(9) = 147, b(10) = 315, b(11) = 667, b(12) = 1357, b(13) = 2769, b(14) = 5727, b(15) = 11701 This enables us to compute the first, 20000, terms of these sequences The probability of Alice winning the bet, as n grows larger is approximately 0.16288 1/2 - ------- 1/2 n The probability of Bob winning the bet, as n grows larger is approximately 0.4886 1/2 - ------ 1/2 n You can see that indeed Alice has a better chance, but not significantly so. ----------------------------------------- This took, 32.039, seconds to generate ----------------------------------------------------------------------------\ ----------------------- Question Mumber, 2, : If Alice bets that there are more occurrences of consec\ utive substrings in, {[2, 1, 2]}, than in, {[1, 1, 1]}, and Bob, bets vice versa, who is more likely to win? Answer: Alice is more likely to win. Let's be more quantitative. We need the following two lemmas Lemma , 2.1, : Let a(n) be the number of words of length n in the alphabet , {1, 2}, with more occurences of, {[2, 1, 2]}, then , {[1, 1, 1]} a(n) satisfies the following linear recurrence equation with polynomial coef\ ficients of order, 15 2 128 (n - 1) (n - 2) (n + 1) a(n) 64 (n - 1) (11 n + 16 n - 8) a(n + 1) -------------------------------- - -------------------------------------- (n + 15) (n + 13) (n + 12) (n + 15) (n + 13) (n + 12) 3 2 (68 n + 165 n - 47 n + 12) a(n + 2) + 64/3 ------------------------------------- (n + 15) (n + 13) (n + 12) 3 2 (293 n + 1230 n + 679 n + 54) a(n + 3) - 16/3 ---------------------------------------- (n + 15) (n + 13) (n + 12) 3 2 8 (166 n + 1129 n + 1955 n + 1026) a(n + 4) + --------------------------------------------- (n + 15) (n + 13) (n + 12) 3 2 (958 n + 9615 n + 28613 n + 26130) a(n + 5) - 4/3 --------------------------------------------- (n + 15) (n + 13) (n + 12) 3 2 (1465 n + 18123 n + 67688 n + 75600) a(n + 6) + 2/3 ----------------------------------------------- (n + 15) (n + 13) (n + 12) 3 2 (377 n + 5661 n + 26329 n + 36885) a(n + 7) - 4/3 --------------------------------------------- (n + 15) (n + 13) (n + 12) 3 2 (851 n + 16035 n + 95314 n + 173160) a(n + 8) + 1/3 ----------------------------------------------- (n + 15) (n + 13) (n + 12) 3 2 (455 n + 9054 n + 54919 n + 94740) a(n + 9) - 1/3 --------------------------------------------- (n + 15) (n + 13) (n + 12) 3 2 (71 n + 693 n - 4676 n - 43968) a(n + 10) + 1/3 ------------------------------------------- (n + 15) (n + 13) (n + 12) 3 2 (11 n + 448 n + 5561 n + 21508) a(n + 11) + ------------------------------------------- (n + 15) (n + 13) (n + 12) 3 2 3 (3 n + 119 n + 1538 n + 6496) a(n + 12) - ------------------------------------------- (n + 15) (n + 13) (n + 12) 3 2 (31 n + 1206 n + 15563 n + 66624) a(n + 13) + 1/3 --------------------------------------------- (n + 15) (n + 13) (n + 12) 2 (17 n + 459 n + 3088) a(n + 14) - 1/3 -------------------------------- + a(n + 15) = 0 (n + 13) (n + 15) Subject to the initial conditions a(1) = 0, a(2) = 0, a(3) = 1, a(4) = 4, a(5) = 11, a(6) = 25, a(7) = 53, a(8) = 110, a(9) = 225, a(10) = 456, a(11) = 921, a(12) = 1856, a(13) = 3733, a(14) = 7501, a(15) = 15063 Lemma , 2.2, : Let b(n) be the number of words of length n in the alphabet , {1, 2}, with more occurences of, {[1, 1, 1]}, then , {[2, 1, 2]} b(n) satisfies the following linear recurrence equation with polynomial coef\ ficients of order, 13 2 128 (n - 1) (n - 2) (n + 1) b(n) 64 (n - 1) (7 n + 10 n - 4) b(n + 1) - -------------------------------- + ------------------------------------- (n + 10) (n + 13) (n + 12) (n + 10) (n + 13) (n + 12) 2 n (14 n + 36 n + 1) b(n + 2) - 128/3 ----------------------------- (n + 10) (n + 13) (n + 12) (5 n + 7) (23 n + 78) (n + 1) b(n + 3) + 16/3 -------------------------------------- (n + 10) (n + 13) (n + 12) 3 2 8 (76 n + 621 n + 1453 n + 934) b(n + 4) - ------------------------------------------ (n + 10) (n + 13) (n + 12) 3 2 4 (114 n + 1201 n + 3911 n + 4034) b(n + 5) + --------------------------------------------- (n + 10) (n + 13) (n + 12) 3 2 (481 n + 6867 n + 31676 n + 47148) b(n + 6) - 2/3 --------------------------------------------- (n + 10) (n + 13) (n + 12) 3 2 (311 n + 5421 n + 30520 n + 54744) b(n + 7) + 2/3 --------------------------------------------- (n + 10) (n + 13) (n + 12) 3 2 (167 n + 3537 n + 24526 n + 55092) b(n + 8) - 2/3 --------------------------------------------- (n + 10) (n + 13) (n + 12) 3 2 2 (31 n + 776 n + 6353 n + 16874) b(n + 9) + -------------------------------------------- (n + 10) (n + 13) (n + 12) 3 2 (89 n + 2439 n + 21976 n + 64836) b(n + 10) - 1/3 --------------------------------------------- (n + 10) (n + 13) (n + 12) 3 2 (37 n + 1143 n + 11732 n + 39984) b(n + 11) + 1/3 --------------------------------------------- (n + 10) (n + 13) (n + 12) (n + 12) (5 n + 49) b(n + 12) - ----------------------------- + b(n + 13) = 0 (n + 13) (n + 10) Subject to the initial conditions b(1) = 0, b(2) = 0, b(3) = 1, b(4) = 3, b(5) = 8, b(6) = 18, b(7) = 39, b(8) = 83, b(9) = 173, b(10) = 357, b(11) = 733, b(12) = 1497, b(13) = 3046 This enables us to compute the first, 20000, terms of these sequences The probability of Alice winning the bet, as n grows larger is approximately 0.14106 1/2 - ------- 1/2 n The probability of Bob winning the bet, as n grows larger is approximately 0.4232 1/2 - ------ 1/2 n You can see that indeed Alice has a better chance, but not significantly so. ----------------------------------------- This took, 24.353, seconds to generate ----------------------------------------------------------------------------\ ----------------------- Question Mumber, 3, : If Alice bets that there are more occurrences of consec\ utive substrings in, {[2, 2, 2]}, than in, {[1, 1, 1]}, and Bob, bets vice versa, who is more likely to win? Answer: They are equally likely to win ----------------------------------------------------------------------------\ ----------------------- Question Mumber, 4, : If Alice bets that there are more occurrences of consec\ utive substrings in, {[1, 1, 2]}, than in, {[1, 1, 1]}, and Bob, bets vice versa, who is more likely to win? Answer: Alice is more likely to win. Let's be more quantitative. We need the following two lemmas Lemma , 4.1, : Let a(n) be the number of words of length n in the alphabet , {1, 2}, with more occurences of, {[1, 1, 2]}, then , {[1, 1, 1]} a(n) satisfies the following linear recurrence equation with polynomial coef\ ficients of order, 19 (n + 1) (n + 2) (n + 3) a(n) (2 n + 5) (n + 3) (n + 2) a(n + 1) -64/3 ---------------------------- - 64/3 ---------------------------------- (n + 19) (n + 17) (n + 16) (n + 19) (n + 17) (n + 16) 2 (n + 3) (n - 6 n - 31) a(n + 2) + 32/3 -------------------------------- (n + 19) (n + 17) (n + 16) 2 16 (n + 4) (4 n + 41 n + 119) a(n + 3) + --------------------------------------- (n + 19) (n + 17) (n + 16) 3 2 4 (17 n + 368 n + 2799 n + 6888) a(n + 4) - ------------------------------------------- (n + 19) (n + 17) (n + 16) 3 2 (227 n + 5448 n + 41155 n + 100218) a(n + 5) - 4/3 ---------------------------------------------- (n + 19) (n + 17) (n + 16) 3 2 (371 n + 10374 n + 93319 n + 272880) a(n + 6) + 2/3 ----------------------------------------------- (n + 19) (n + 17) (n + 16) 3 2 (1625 n + 45084 n + 408091 n + 1214016) a(n + 7) + 1/3 -------------------------------------------------- (n + 19) (n + 17) (n + 16) 3 2 (587 n + 16936 n + 161921 n + 514380) a(n + 8) - ------------------------------------------------ (n + 19) (n + 17) (n + 16) 3 2 (26 n + 3213 n + 54346 n + 248871) a(n + 9) - 2/3 --------------------------------------------- (n + 19) (n + 17) (n + 16) 3 2 (397 n + 12898 n + 137591 n + 482434) a(n + 10) + ------------------------------------------------- (n + 19) (n + 17) (n + 16) 3 2 2 (236 n + 7115 n + 69690 n + 219335) a(n + 11) - ------------------------------------------------- (n + 19) (n + 17) (n + 16) 3 2 (265 n + 8430 n + 87941 n + 298560) a(n + 12) + 2/3 ----------------------------------------------- (n + 19) (n + 17) (n + 16) 3 2 (385 n + 12024 n + 117347 n + 341364) a(n + 13) + 1/3 ------------------------------------------------- (n + 19) (n + 17) (n + 16) 3 2 (103 n + 3194 n + 29685 n + 72578) a(n + 14) - ---------------------------------------------- (n + 19) (n + 17) (n + 16) 3 2 (17 n - 288 n - 18809 n - 159864) a(n + 15) + 1/3 --------------------------------------------- (n + 19) (n + 17) (n + 16) 2 (n + 15) (17 n + 477 n + 3268) a(n + 16) - 1/3 ----------------------------------------- (n + 19) (n + 17) (n + 16) 3 2 (49 n + 2382 n + 38531 n + 207414) a(n + 17) + 1/3 ---------------------------------------------- (n + 19) (n + 17) (n + 16) 2 (11 n + 376 n + 3201) a(n + 18) - 2/3 -------------------------------- + a(n + 19) = 0 (n + 17) (n + 19) Subject to the initial conditions a(1) = 0, a(2) = 0, a(3) = 1, a(4) = 3, a(5) = 8, a(6) = 18, a(7) = 41, a(8) = 89, a(9) = 191, a(10) = 400, a(11) = 833, a(12) = 1717, a(13) = 3523, a(14) = 7184, a(15) = 14604, a(16) = 29588, a(17) = 59822, a(18) = 120695, a(19) = 243166 Lemma , 4.2, : Let b(n) be the number of words of length n in the alphabet , {1, 2}, with more occurences of, {[1, 1, 1]}, then , {[1, 1, 2]} b(n) satisfies the following linear recurrence equation with polynomial coef\ ficients of order, 10 (n + 3) (n + 1) b(n) n (n + 1) b(n + 1) -32/3 -------------------- - 8/3 ------------------ (n + 10) (n + 7) (n + 10) (n + 7) 2 2 (17 n + 119 n + 210) b(n + 2) (25 n + 217 n + 456) b(n + 3) + 4/3 ------------------------------ - 2/3 ------------------------------ (n + 10) (n + 7) (n + 10) (n + 7) 2 (19 n + 331 n + 1188) b(n + 4) - 1/3 ------------------------------- (n + 10) (n + 7) 2 2 (59 n + 711 n + 2088) b(n + 5) (13 n + 150 n + 423) b(n + 6) + 1/3 ------------------------------- - 4/3 ------------------------------ (n + 10) (n + 7) (n + 10) (n + 7) 2 2 (11 n + 145 n + 504) b(n + 7) (10 n + 143 n + 486) b(n + 8) + 1/3 ------------------------------ + 2/3 ------------------------------ (n + 10) (n + 7) (n + 10) (n + 7) 2 (5 n + 79 n + 302) b(n + 9) - ---------------------------- + b(n + 10) = 0 (n + 10) (n + 7) Subject to the initial conditions b(1) = 0, b(2) = 0, b(3) = 1, b(4) = 2, b(5) = 5, b(6) = 11, b(7) = 26, b(8) = 56, b(9) = 121, b(10) = 255 This enables us to compute the first, 20000, terms of these sequences The probability of Alice winning the bet, as n grows larger is approximately 0.099744 1/2 - -------- 1/2 n The probability of Bob winning the bet, as n grows larger is approximately 0.6982 1/2 - ------ 1/2 n You can see that indeed Alice has a better chance, but not significantly so. ----------------------------------------- This took, 25.318, seconds to generate ----------------------------------------------------------------------------\ ----------------------- Question Mumber, 5, : If Alice bets that there are more occurrences of consec\ utive substrings in, {[1, 2, 2]}, than in, {[1, 1, 1]}, and Bob, bets vice versa, who is more likely to win? Answer: Alice is more likely to win. Let's be more quantitative. We need the following two lemmas Lemma , 5.1, : Let a(n) be the number of words of length n in the alphabet , {1, 2}, with more occurences of, {[1, 2, 2]}, then , {[1, 1, 1]} a(n) satisfies the following linear recurrence equation with polynomial coef\ ficients of order, 18 (n + 1) (n + 2) (n + 3) a(n) (n - 5) (n + 3) (n + 2) a(n + 1) 64/3 ---------------------------- - 64/3 -------------------------------- (n + 15) (n + 18) (n + 16) (n + 15) (n + 18) (n + 16) 2 (n + 3) (11 n + 111 n + 340) a(n + 2) + 16/3 -------------------------------------- (n + 15) (n + 18) (n + 16) 3 2 (115 n + 1902 n + 9869 n + 16362) a(n + 3) - 8/3 -------------------------------------------- (n + 15) (n + 18) (n + 16) 3 2 (163 n + 2610 n + 12989 n + 20178) a(n + 4) + 8/3 --------------------------------------------- (n + 15) (n + 18) (n + 16) 3 2 (119 n + 6564 n + 68821 n + 201120) a(n + 5) + 2/3 ---------------------------------------------- (n + 15) (n + 18) (n + 16) 3 2 (1211 n + 30528 n + 243901 n + 627600) a(n + 6) - 2/3 ------------------------------------------------- (n + 15) (n + 18) (n + 16) 3 2 (811 n + 20548 n + 170149 n + 463244) a(n + 7) + ------------------------------------------------ (n + 15) (n + 18) (n + 16) 3 2 (220 n + 8475 n + 98015 n + 356742) a(n + 8) - 2/3 ---------------------------------------------- (n + 15) (n + 18) (n + 16) 3 2 (367 n + 6288 n + 23348 n - 30027) a(n + 9) - 2/3 --------------------------------------------- (n + 15) (n + 18) (n + 16) 3 2 (149 n + 2601 n + 19018 n + 85008) a(n + 10) + 1/3 ---------------------------------------------- (n + 15) (n + 18) (n + 16) 3 2 (485 n + 10920 n + 56857 n - 50826) a(n + 11) + 1/3 ----------------------------------------------- (n + 15) (n + 18) (n + 16) 3 2 (202 n + 4956 n + 32423 n + 25110) a(n + 12) - 2/3 ---------------------------------------------- (n + 15) (n + 18) (n + 16) 3 2 (127 n + 4257 n + 47159 n + 172773) a(n + 13) + 2/3 ----------------------------------------------- (n + 15) (n + 18) (n + 16) 2 (n + 13) (167 n + 4396 n + 28728) a(n + 14) - 1/3 -------------------------------------------- (n + 15) (n + 18) (n + 16) 3 2 (29 n + 1014 n + 11041 n + 35400) a(n + 15) + 1/3 --------------------------------------------- (n + 15) (n + 18) (n + 16) 3 2 2 (6 n + 287 n + 4562 n + 24100) a(n + 16) + -------------------------------------------- (n + 15) (n + 18) (n + 16) (5 n + 86) (2 n + 31) a(n + 17) - 2/3 ------------------------------- + a(n + 18) = 0 (n + 18) (n + 16) Subject to the initial conditions a(1) = 0, a(2) = 0, a(3) = 1, a(4) = 4, a(5) = 11, a(6) = 26, a(7) = 56, a(8) = 117, a(9) = 239, a(10) = 484, a(11) = 975, a(12) = 1957, a(13) = 3924, a(14) = 7859, a(15) = 15737, a(16) = 31505, a(17) = 63065, a(18) = 126238 Lemma , 5.2, : Let b(n) be the number of words of length n in the alphabet , {1, 2}, with more occurences of, {[1, 1, 1]}, then , {[1, 2, 2]} b(n) satisfies the following linear recurrence equation with polynomial coef\ ficients of order, 11 (n + 1) (n + 2) b(n) (n + 2) (n - 3) b(n + 1) -16/3 -------------------- + 8/3 ------------------------ (n + 11) (n + 8) (n + 11) (n + 8) 2 2 (13 n + 117 n + 230) b(n + 2) (43 n + 395 n + 870) b(n + 3) + 4/3 ------------------------------ - 2/3 ------------------------------ (n + 11) (n + 8) (n + 11) (n + 8) 2 2 (5 n + 25 n - 3) b(n + 4) (59 n + 737 n + 2262) b(n + 5) + 4/3 -------------------------- + 1/3 ------------------------------- (n + 11) (n + 8) (n + 11) (n + 8) 2 2 (43 n + 559 n + 1834) b(n + 6) (13 n + 160 n + 447) b(n + 7) - 1/3 ------------------------------- - 2/3 ------------------------------ (n + 11) (n + 8) (n + 11) (n + 8) 2 (37 n + 515 n + 1708) b(n + 8) 2 (5 n + 43) b(n + 9) + 1/3 ------------------------------- + --------------------- (n + 11) (n + 8) (n + 11) (n + 8) 2 (11 n + 203 n + 918) b(n + 10) - 1/3 ------------------------------- + b(n + 11) = 0 (n + 11) (n + 8) Subject to the initial conditions b(1) = 0, b(2) = 0, b(3) = 1, b(4) = 3, b(5) = 7, b(6) = 16, b(7) = 34, b(8) = 73, b(9) = 153, b(10) = 318, b(11) = 657 This enables us to compute the first, 20000, terms of these sequences The probability of Alice winning the bet, as n grows larger is approximately 0.0814340 1/2 - --------- 1/2 n The probability of Bob winning the bet, as n grows larger is approximately 0.57005 1/2 - ------- 1/2 n You can see that indeed Alice has a better chance, but not significantly so. ----------------------------------------- This took, 25.549, seconds to generate The best bet against, [1, 1, 1], is a member of, {[1, 1, 2], [2, 1, 1]}, 0.598456 and then your edge, if you have n rolls, is approximately, -------- 1/2 n The next best bet is a member of, {[1, 2, 2], [2, 2, 1]}, 0.4886160 and then your edge is approximately, --------- 1/2 n The next best bet is a member of, {[1, 2, 1]}, 0.32572 and then your edge is approximately, ------- 1/2 n The next best bet is a member of, {[2, 1, 2]}, 0.28214 and then your edge is approximately, ------- 1/2 n The next best bet is a member of, {[2, 2, 2]}, and then your edge is exactly 0 ----------------------- This ends this chapter that took, 107.584, seconds to generate.