How to bet against any given, 3, -letter word in the David Litt game with a fair die with, 2, faces By Shalosh B. Ekhad ----------------------------------------------------------------- ----------------------------------------------------------------- Chapter Number, 1 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, 31.377, 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.804, 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, 28.284, 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.603, 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, 110.453, seconds to generate. ----------------------------------------------------------------- Chapter Number, 2 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, 2], 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, 1, 1]}, than in, {[1, 1, 2]}, and Bob, bets vice versa, who is more likely to win? Answer: Bob 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, 1, 1]}, then , {[1, 1, 2]} a(n) satisfies the following linear recurrence equation with polynomial coef\ ficients of order, 10 (n + 3) (n + 1) a(n) n (n + 1) a(n + 1) -32/3 -------------------- - 8/3 ------------------ (n + 10) (n + 7) (n + 10) (n + 7) 2 2 (17 n + 119 n + 210) a(n + 2) (25 n + 217 n + 456) a(n + 3) + 4/3 ------------------------------ - 2/3 ------------------------------ (n + 10) (n + 7) (n + 10) (n + 7) 2 (19 n + 331 n + 1188) a(n + 4) - 1/3 ------------------------------- (n + 10) (n + 7) 2 2 (59 n + 711 n + 2088) a(n + 5) (13 n + 150 n + 423) a(n + 6) + 1/3 ------------------------------- - 4/3 ------------------------------ (n + 10) (n + 7) (n + 10) (n + 7) 2 2 (11 n + 145 n + 504) a(n + 7) (10 n + 143 n + 486) a(n + 8) + 1/3 ------------------------------ + 2/3 ------------------------------ (n + 10) (n + 7) (n + 10) (n + 7) 2 (5 n + 79 n + 302) a(n + 9) - ---------------------------- + a(n + 10) = 0 (n + 10) (n + 7) Subject to the initial conditions a(1) = 0, a(2) = 0, a(3) = 1, a(4) = 2, a(5) = 5, a(6) = 11, a(7) = 26, a(8) = 56, a(9) = 121, a(10) = 255 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, 2]}, then , {[1, 1, 1]} b(n) satisfies the following linear recurrence equation with polynomial coef\ ficients of order, 19 (n + 1) (n + 2) (n + 3) b(n) (2 n + 5) (n + 3) (n + 2) b(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) b(n + 2) + 32/3 -------------------------------- (n + 19) (n + 17) (n + 16) 2 16 (n + 4) (4 n + 41 n + 119) b(n + 3) + --------------------------------------- (n + 19) (n + 17) (n + 16) 3 2 4 (17 n + 368 n + 2799 n + 6888) b(n + 4) - ------------------------------------------- (n + 19) (n + 17) (n + 16) 3 2 (227 n + 5448 n + 41155 n + 100218) b(n + 5) - 4/3 ---------------------------------------------- (n + 19) (n + 17) (n + 16) 3 2 (371 n + 10374 n + 93319 n + 272880) b(n + 6) + 2/3 ----------------------------------------------- (n + 19) (n + 17) (n + 16) 3 2 (1625 n + 45084 n + 408091 n + 1214016) b(n + 7) + 1/3 -------------------------------------------------- (n + 19) (n + 17) (n + 16) 3 2 (587 n + 16936 n + 161921 n + 514380) b(n + 8) - ------------------------------------------------ (n + 19) (n + 17) (n + 16) 3 2 (26 n + 3213 n + 54346 n + 248871) b(n + 9) - 2/3 --------------------------------------------- (n + 19) (n + 17) (n + 16) 3 2 (397 n + 12898 n + 137591 n + 482434) b(n + 10) + ------------------------------------------------- (n + 19) (n + 17) (n + 16) 3 2 2 (236 n + 7115 n + 69690 n + 219335) b(n + 11) - ------------------------------------------------- (n + 19) (n + 17) (n + 16) 3 2 (265 n + 8430 n + 87941 n + 298560) b(n + 12) + 2/3 ----------------------------------------------- (n + 19) (n + 17) (n + 16) 3 2 (385 n + 12024 n + 117347 n + 341364) b(n + 13) + 1/3 ------------------------------------------------- (n + 19) (n + 17) (n + 16) 3 2 (103 n + 3194 n + 29685 n + 72578) b(n + 14) - ---------------------------------------------- (n + 19) (n + 17) (n + 16) 3 2 (17 n - 288 n - 18809 n - 159864) b(n + 15) + 1/3 --------------------------------------------- (n + 19) (n + 17) (n + 16) 2 (n + 15) (17 n + 477 n + 3268) b(n + 16) - 1/3 ----------------------------------------- (n + 19) (n + 17) (n + 16) 3 2 (49 n + 2382 n + 38531 n + 207414) b(n + 17) + 1/3 ---------------------------------------------- (n + 19) (n + 17) (n + 16) 2 (11 n + 376 n + 3201) b(n + 18) - 2/3 -------------------------------- + b(n + 19) = 0 (n + 17) (n + 19) 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) = 41, b(8) = 89, b(9) = 191, b(10) = 400, b(11) = 833, b(12) = 1717, b(13) = 3523, b(14) = 7184, b(15) = 14604, b(16) = 29588, b(17) = 59822, b(18) = 120695, b(19) = 243166 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.6982 1/2 - ------ 1/2 n The probability of Bob winning the bet, as n grows larger is approximately 0.099744 1/2 - -------- 1/2 n You can see that indeed Bob has a better chance, but not significantly so. ----------------------------------------- This took, 26.312, seconds to generate ----------------------------------------------------------------------------\ ----------------------- Question Mumber, 2, : If Alice bets that there are more occurrences of consec\ utive substrings in, {[1, 2, 1]}, than in, {[1, 1, 2]}, and Bob, bets vice versa, who is more likely to win? Answer: Bob 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, {[1, 2, 1]}, then , {[1, 1, 2]} a(n) satisfies the following linear recurrence equation with polynomial coef\ ficients of order, 9 (n + 1) (n + 2) (n + 3) a(n) (11 n + 35) (n + 3) (n + 2) a(n + 1) 32/3 ---------------------------- - 8/3 ------------------------------------ (n + 10) (n + 9) (n + 6) (n + 10) (n + 9) (n + 6) 2 4 (n + 3) (9 n + 69 n + 134) a(n + 2) + -------------------------------------- (n + 10) (n + 9) (n + 6) 2 2 (n + 4) (9 n + 38 n - 31) a(n + 3) - ------------------------------------- (n + 10) (n + 9) (n + 6) 2 (n + 5) (13 n + 661 n + 3252) a(n + 4) - 1/3 --------------------------------------- (n + 10) (n + 9) (n + 6) 2 2 (7 n + 213 n + 1034) a(n + 5) (n + 7) (7 n + 135 n + 570) a(n + 6) + ------------------------------ - ------------------------------------- (n + 9) (n + 10) (n + 10) (n + 9) (n + 6) 2 (n + 8) (28 n + 403 n + 1389) a(n + 7) + 1/3 --------------------------------------- (n + 10) (n + 9) (n + 6) 2 (16 n + 231 n + 800) a(n + 8) - 1/3 ------------------------------ + a(n + 9) = 0 (n + 10) (n + 6) Subject to the initial conditions a(1) = 0, a(2) = 0, a(3) = 1, a(4) = 3, a(5) = 6, a(6) = 14, a(7) = 32, a(8) = 66, a(9) = 138 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, 2]}, then , {[1, 2, 1]} b(n) satisfies the following linear recurrence equation with polynomial coef\ ficients of order, 10 2 16 (n + 4) (n + 2) (n + 1) b(n) 24 (n + 2) (n + 3 n - 2) b(n + 1) - ------------------------------- + ---------------------------------- (n + 10) (n + 9) (n + 7) (n + 10) (n + 9) (n + 7) 3 2 4 (9 n + 163 n + 768 n + 1076) b(n + 2) + ----------------------------------------- (n + 10) (n + 9) (n + 7) 3 2 2 (59 n + 965 n + 4876 n + 7864) b(n + 3) - ------------------------------------------- (n + 10) (n + 9) (n + 7) 3 2 2 (72 n + 1303 n + 7481 n + 13884) b(n + 4) + --------------------------------------------- (n + 10) (n + 9) (n + 7) 3 2 2 (63 n + 1202 n + 7429 n + 14996) b(n + 5) - --------------------------------------------- (n + 10) (n + 9) (n + 7) 3 2 (95 n + 1827 n + 11574 n + 24148) b(n + 6) + -------------------------------------------- (n + 10) (n + 9) (n + 7) 3 2 (60 n + 1209 n + 8051 n + 17676) b(n + 7) - ------------------------------------------- (n + 10) (n + 9) (n + 7) 3 2 (28 n + 617 n + 4497 n + 10820) b(n + 8) + ------------------------------------------ (n + 10) (n + 9) (n + 7) 2 (8 n + 121 n + 450) 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) = 3, b(5) = 7, b(6) = 17, b(7) = 38, b(8) = 80, b(9) = 169, b(10) = 353 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.70522 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 Bob has a better chance, but not significantly so. ----------------------------------------- This took, 19.116, seconds to generate ----------------------------------------------------------------------------\ ----------------------- Question Mumber, 3, : If Alice bets that there are more occurrences of consec\ utive substrings in, {[1, 2, 2]}, than in, {[1, 1, 2]}, 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, {[2, 1, 1]}, than in, {[1, 1, 2]}, and Bob, bets vice versa, who is more likely to win? Answer: They are equally likely to win ----------------------------------------------------------------------------\ ----------------------- Question Mumber, 5, : If Alice bets that there are more occurrences of consec\ utive substrings in, {[2, 1, 2]}, than in, {[1, 1, 2]}, and Bob, bets vice versa, who is more likely to win? Answer: Bob 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, {[2, 1, 2]}, then , {[1, 1, 2]} a(n) satisfies the following linear recurrence equation with polynomial coef\ ficients of order, 10 2 (n + 3) (n + 1) a(n) (7 n + 35 n + 40) a(n + 1) -32/3 -------------------- + 8/3 --------------------------- (n + 10) (n + 7) (n + 10) (n + 7) 2 2 (n - 25 n - 86) a(n + 2) (15 n + 287 n + 884) a(n + 3) - 4/3 ------------------------- - 2/3 ------------------------------ (n + 10) (n + 7) (n + 10) (n + 7) 2 2 (13 n - 295 n - 1664) a(n + 4) (9 n - 76 n - 699) a(n + 5) - 1/3 ------------------------------- + 2/3 ---------------------------- (n + 10) (n + 7) (n + 10) (n + 7) 2 (53 n + 857 n + 3302) a(n + 6) + 1/3 ------------------------------- (n + 10) (n + 7) 2 (47 n + 672 n + 2379) a(n + 7) - 2/3 ------------------------------- (n + 10) (n + 7) 2 2 (65 n + 969 n + 3544) a(n + 8) (11 n + 175 n + 678) a(n + 9) + 1/3 ------------------------------- - 2/3 ------------------------------ (n + 10) (n + 7) (n + 10) (n + 7) + a(n + 10) = 0 Subject to the initial conditions a(1) = 0, a(2) = 0, a(3) = 1, a(4) = 4, a(5) = 10, a(6) = 21, a(7) = 41, a(8) = 80, a(9) = 162, a(10) = 338 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, 2]}, then , {[2, 1, 2]} b(n) satisfies the following linear recurrence equation with polynomial coef\ ficients of order, 17 (n + 1) (n + 2) (n + 3) b(n) (5 n + 17) (n + 3) (n + 2) b(n + 1) 64/3 ---------------------------- - 64/3 ----------------------------------- (n + 14) (n + 17) (n + 16) (n + 14) (n + 17) (n + 16) 2 32 (n + 3) (8 n + 65 n + 131) b(n + 2) + --------------------------------------- (n + 14) (n + 17) (n + 16) 3 2 16 (23 n + 303 n + 1310 n + 1866) b(n + 3) - -------------------------------------------- (n + 14) (n + 17) (n + 16) 3 2 (199 n + 1992 n + 4037 n - 4644) b(n + 4) + 4/3 ------------------------------------------- (n + 14) (n + 17) (n + 16) 3 2 (56 n + 4755 n + 51823 n + 151896) b(n + 5) + 4/3 --------------------------------------------- (n + 14) (n + 17) (n + 16) 3 2 (308 n + 12771 n + 131827 n + 403488) b(n + 6) - 4/3 ------------------------------------------------ (n + 14) (n + 17) (n + 16) 3 2 (997 n + 37422 n + 397841 n + 1302192) b(n + 7) + 2/3 ------------------------------------------------- (n + 14) (n + 17) (n + 16) 3 2 2 (531 n + 17315 n + 178968 n + 596920) b(n + 8) - -------------------------------------------------- (n + 14) (n + 17) (n + 16) 3 2 2 (785 n + 23822 n + 238893 n + 792784) b(n + 9) + -------------------------------------------------- (n + 14) (n + 17) (n + 16) 3 2 2 (901 n + 27681 n + 282638 n + 958806) b(n + 10) - --------------------------------------------------- (n + 14) (n + 17) (n + 16) 3 2 (4703 n + 152736 n + 1649533 n + 5921568) b(n + 11) + 1/3 ----------------------------------------------------- (n + 14) (n + 17) (n + 16) 3 2 (3178 n + 111081 n + 1292411 n + 5004132) b(n + 12) - 1/3 ----------------------------------------------------- (n + 14) (n + 17) (n + 16) 3 2 (1687 n + 63585 n + 798158 n + 3336264) b(n + 13) + 1/3 --------------------------------------------------- (n + 14) (n + 17) (n + 16) 3 2 (343 n + 13833 n + 185750 n + 830382) b(n + 14) - 2/3 ------------------------------------------------- (n + 14) (n + 17) (n + 16) 3 2 (199 n + 8502 n + 120875 n + 571788) b(n + 15) + 1/3 ------------------------------------------------ (n + 14) (n + 17) (n + 16) 2 (12 n + 347 n + 2499) b(n + 16) - -------------------------------- + b(n + 17) = 0 (n + 17) (n + 14) Subject to the initial conditions b(1) = 0, b(2) = 0, b(3) = 1, b(4) = 4, b(5) = 11, b(6) = 25, b(7) = 51, b(8) = 100, b(9) = 197, b(10) = 397, b(11) = 814, b(12) = 1673, b(13) = 3411, b(14) = 6885, b(15) = 13809, b(16) = 27660, b(17) = 55509 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.49868 1/2 - ------- 1/2 n The probability of Bob winning the bet, as n grows larger is approximately 0.29922 1/2 - ------- 1/2 n You can see that indeed Bob has a better chance, but not significantly so. ----------------------------------------- This took, 24.050, seconds to generate ----------------------------------------------------------------------------\ ----------------------- Question Mumber, 6, : If Alice bets that there are more occurrences of consec\ utive substrings in, {[2, 2, 1]}, than in, {[1, 1, 2]}, and Bob, bets vice versa, who is more likely to win? Answer: They are equally likely to win ----------------------------------------------------------------------------\ ----------------------- Question Mumber, 7, : If Alice bets that there are more occurrences of consec\ utive substrings in, {[2, 2, 2]}, than in, {[1, 1, 2]}, and Bob, bets vice versa, who is more likely to win? Answer: Bob is more likely to win. Let's be more quantitative. We need the following two lemmas Lemma , 7.1, : Let a(n) be the number of words of length n in the alphabet , {1, 2}, with more occurences of, {[2, 2, 2]}, then , {[1, 1, 2]} a(n) satisfies the following linear recurrence equation with polynomial coef\ ficients of order, 11 (n + 1) (n + 2) a(n) (n + 2) (n - 3) a(n + 1) -16/3 -------------------- + 8/3 ------------------------ (n + 11) (n + 8) (n + 11) (n + 8) 2 2 (13 n + 117 n + 230) a(n + 2) (43 n + 395 n + 870) a(n + 3) + 4/3 ------------------------------ - 2/3 ------------------------------ (n + 11) (n + 8) (n + 11) (n + 8) 2 2 (5 n + 25 n - 3) a(n + 4) (59 n + 737 n + 2262) a(n + 5) + 4/3 -------------------------- + 1/3 ------------------------------- (n + 11) (n + 8) (n + 11) (n + 8) 2 2 (43 n + 559 n + 1834) a(n + 6) (13 n + 160 n + 447) a(n + 7) - 1/3 ------------------------------- - 2/3 ------------------------------ (n + 11) (n + 8) (n + 11) (n + 8) 2 (37 n + 515 n + 1708) a(n + 8) 2 (5 n + 43) a(n + 9) + 1/3 ------------------------------- + --------------------- (n + 11) (n + 8) (n + 11) (n + 8) 2 (11 n + 203 n + 918) a(n + 10) - 1/3 ------------------------------- + a(n + 11) = 0 (n + 11) (n + 8) Subject to the initial conditions a(1) = 0, a(2) = 0, a(3) = 1, a(4) = 3, a(5) = 7, a(6) = 16, a(7) = 34, a(8) = 73, a(9) = 153, a(10) = 318, a(11) = 657 Lemma , 7.2, : Let b(n) be the number of words of length n in the alphabet , {1, 2}, with more occurences of, {[1, 1, 2]}, then , {[2, 2, 2]} b(n) satisfies the following linear recurrence equation with polynomial coef\ ficients of order, 18 (n + 1) (n + 2) (n + 3) b(n) (n - 5) (n + 3) (n + 2) b(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) b(n + 2) + 16/3 -------------------------------------- (n + 15) (n + 18) (n + 16) 3 2 (115 n + 1902 n + 9869 n + 16362) b(n + 3) - 8/3 -------------------------------------------- (n + 15) (n + 18) (n + 16) 3 2 (163 n + 2610 n + 12989 n + 20178) b(n + 4) + 8/3 --------------------------------------------- (n + 15) (n + 18) (n + 16) 3 2 (119 n + 6564 n + 68821 n + 201120) b(n + 5) + 2/3 ---------------------------------------------- (n + 15) (n + 18) (n + 16) 3 2 (1211 n + 30528 n + 243901 n + 627600) b(n + 6) - 2/3 ------------------------------------------------- (n + 15) (n + 18) (n + 16) 3 2 (811 n + 20548 n + 170149 n + 463244) b(n + 7) + ------------------------------------------------ (n + 15) (n + 18) (n + 16) 3 2 (220 n + 8475 n + 98015 n + 356742) b(n + 8) - 2/3 ---------------------------------------------- (n + 15) (n + 18) (n + 16) 3 2 (367 n + 6288 n + 23348 n - 30027) b(n + 9) - 2/3 --------------------------------------------- (n + 15) (n + 18) (n + 16) 3 2 (149 n + 2601 n + 19018 n + 85008) b(n + 10) + 1/3 ---------------------------------------------- (n + 15) (n + 18) (n + 16) 3 2 (485 n + 10920 n + 56857 n - 50826) b(n + 11) + 1/3 ----------------------------------------------- (n + 15) (n + 18) (n + 16) 3 2 (202 n + 4956 n + 32423 n + 25110) b(n + 12) - 2/3 ---------------------------------------------- (n + 15) (n + 18) (n + 16) 3 2 (127 n + 4257 n + 47159 n + 172773) b(n + 13) + 2/3 ----------------------------------------------- (n + 15) (n + 18) (n + 16) 2 (n + 13) (167 n + 4396 n + 28728) b(n + 14) - 1/3 -------------------------------------------- (n + 15) (n + 18) (n + 16) 3 2 (29 n + 1014 n + 11041 n + 35400) b(n + 15) + 1/3 --------------------------------------------- (n + 15) (n + 18) (n + 16) 3 2 2 (6 n + 287 n + 4562 n + 24100) b(n + 16) + -------------------------------------------- (n + 15) (n + 18) (n + 16) (5 n + 86) (2 n + 31) b(n + 17) - 2/3 ------------------------------- + b(n + 18) = 0 (n + 18) (n + 16) Subject to the initial conditions b(1) = 0, b(2) = 0, b(3) = 1, b(4) = 4, b(5) = 11, b(6) = 26, b(7) = 56, b(8) = 117, b(9) = 239, b(10) = 484, b(11) = 975, b(12) = 1957, b(13) = 3924, b(14) = 7859, b(15) = 15737, b(16) = 31505, b(17) = 63065, b(18) = 126238 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.57005 1/2 - ------- 1/2 n The probability of Bob winning the bet, as n grows larger is approximately 0.0814340 1/2 - --------- 1/2 n You can see that indeed Bob has a better chance, but not significantly so. ----------------------------------------- This took, 26.256, seconds to generate The best bet against, [1, 1, 2], is a member of, {[1, 2, 2], [2, 1, 1], [2, 2, 1]}, and then your edge, if you have n rolls, is exactly 0 The next best bet is a member of, {[2, 1, 2]}, 0.19946 and then your edge is approximately, - ------- 1/2 n The next best bet is a member of, {[1, 2, 1]}, 0.28202 and then your edge is approximately, - ------- 1/2 n The next best bet is a member of, {[2, 2, 2]}, 0.4886160 and then your edge is approximately, - --------- 1/2 n The next best bet is a member of, {[1, 1, 1]}, 0.598456 and then your edge is approximately, - -------- 1/2 n ----------------------- This ends this chapter that took, 95.971, seconds to generate. ----------------------------------------------------------------- Chapter Number, 3 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, 2, 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, 1, 1]}, than in, {[1, 2, 1]}, and Bob, bets vice versa, who is more likely to win? Answer: Bob 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, 1, 1]}, then , {[1, 2, 1]} a(n) satisfies the following linear recurrence equation with polynomial coef\ ficients of order, 15 2 (2 n + 3) (n + 2) (n + 1) a(n) (n + 2) (14 n + 65 n + 87) a(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) a(n + 2) + 32/3 --------------------------------------- (n + 15) (n + 14) (n + 12) 3 2 (65 n + 879 n + 3946 n + 5868) a(n + 3) - 8/3 ----------------------------------------- (n + 15) (n + 14) (n + 12) 3 2 (59 n + 1335 n + 9532 n + 21612) a(n + 4) - 4/3 ------------------------------------------- (n + 15) (n + 14) (n + 12) 3 2 (265 n + 5178 n + 33347 n + 70818) a(n + 5) + 4/3 --------------------------------------------- (n + 15) (n + 14) (n + 12) 3 2 (113 n + 1503 n + 3694 n - 8892) a(n + 6) - 4/3 ------------------------------------------- (n + 15) (n + 14) (n + 12) 3 2 (265 n + 9195 n + 95450 n + 310884) a(n + 7) - 2/3 ---------------------------------------------- (n + 15) (n + 14) (n + 12) 3 2 (533 n + 17103 n + 172786 n + 560088) a(n + 8) + 1/3 ------------------------------------------------ (n + 15) (n + 14) (n + 12) 3 2 (39 n + 819 n + 3732 n - 5020) a(n + 9) - ----------------------------------------- (n + 15) (n + 14) (n + 12) 3 2 (43 n + 2065 n + 29248 n + 129204) a(n + 10) - ---------------------------------------------- (n + 15) (n + 14) (n + 12) 3 2 (227 n + 8667 n + 108202 n + 443568) a(n + 11) + 1/3 ------------------------------------------------ (n + 15) (n + 14) (n + 12) 3 2 (67 n + 2429 n + 29250 n + 116976) a(n + 12) - ---------------------------------------------- (n + 15) (n + 14) (n + 12) 3 2 (101 n + 3753 n + 46360 n + 190308) a(n + 13) + 1/3 ----------------------------------------------- (n + 15) (n + 14) (n + 12) 2 3 (3 n + 75 n + 466) a(n + 14) - ------------------------------- + a(n + 15) = 0 (n + 15) (n + 12) Subject to the initial conditions a(1) = 0, a(2) = 0, a(3) = 1, a(4) = 3, a(5) = 6, a(6) = 14, a(7) = 34, a(8) = 72, a(9) = 147, a(10) = 315, a(11) = 667, a(12) = 1357, a(13) = 2769, a(14) = 5727, a(15) = 11701 Lemma , 1.2, : Let b(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]} b(n) satisfies the following linear recurrence equation with polynomial coef\ ficients of order, 22 (2 n + 3) (n + 2) (n + 1) b(n) -32/3 ------------------------------ (n + 20) (n + 19) (n + 22) (2 n + 5) (11 n + 39) (n + 2) b(n + 1) + 16/3 -------------------------------------- (n + 20) (n + 19) (n + 22) 2 (n + 4) (74 n + 592 n + 1113) b(n + 2) - 32/3 --------------------------------------- (n + 20) (n + 19) (n + 22) 2 (n + 4) (605 n + 6517 n + 18204) b(n + 3) + 8/3 ------------------------------------------ (n + 20) (n + 19) (n + 22) 3 2 (785 n + 9393 n + 35968 n + 42324) b(n + 4) - 4/3 --------------------------------------------- (n + 20) (n + 19) (n + 22) 3 2 (487 n - 1470 n - 66871 n - 244986) b(n + 5) + 4/3 ---------------------------------------------- (n + 20) (n + 19) (n + 22) 3 2 (13 n + 5430 n + 69449 n + 226692) b(n + 6) + 8/3 --------------------------------------------- (n + 20) (n + 19) (n + 22) 3 2 (3607 n + 83943 n + 645776 n + 1646496) b(n + 7) - 2/3 -------------------------------------------------- (n + 20) (n + 19) (n + 22) 3 2 (8291 n + 155757 n + 808042 n + 682824) b(n + 8) + 1/3 -------------------------------------------------- (n + 20) (n + 19) (n + 22) 3 2 (1271 n + 13023 n - 101176 n - 1050116) b(n + 9) - -------------------------------------------------- (n + 20) (n + 19) (n + 22) 3 2 (71 n + 21021 n + 368761 n + 1620366) b(n + 10) - 2/3 ------------------------------------------------- (n + 20) (n + 19) (n + 22) 3 2 (5003 n + 179013 n + 1996948 n + 6880668) b(n + 11) + 1/3 ----------------------------------------------------- (n + 20) (n + 19) (n + 22) 3 2 (365 n + 12378 n + 134602 n + 462372) b(n + 12) - 14/3 ------------------------------------------------- (n + 20) (n + 19) (n + 22) 3 2 (221 n - 3948 n - 212273 n - 1595466) b(n + 13) + 2/3 ------------------------------------------------- (n + 20) (n + 19) (n + 22) 3 2 (1543 n + 79827 n + 1297454 n + 6734064) b(n + 14) + 1/3 ---------------------------------------------------- (n + 20) (n + 19) (n + 22) 3 2 (277 n + 12144 n + 172946 n + 796302) b(n + 15) - 4/3 ------------------------------------------------- (n + 20) (n + 19) (n + 22) 3 2 (835 n + 33273 n + 425978 n + 1723464) b(n + 16) + 1/3 -------------------------------------------------- (n + 20) (n + 19) (n + 22) 3 2 (421 n + 18033 n + 255380 n + 1200876) b(n + 17) - 1/3 -------------------------------------------------- (n + 20) (n + 19) (n + 22) 2 (n + 18) (14 n + 540 n + 6349) b(n + 18) + 2/3 ----------------------------------------- (n + 20) (n + 19) (n + 22) 3 2 (7 n - 135 n - 12412 n - 138948) b(n + 19) + 1/3 -------------------------------------------- (n + 20) (n + 19) (n + 22) 3 2 2 (6 n + 367 n + 7452 n + 50244) b(n + 20) + -------------------------------------------- (n + 20) (n + 19) (n + 22) (5 n + 106) (2 n + 39) b(n + 21) - 2/3 -------------------------------- + b(n + 22) = 0 (n + 22) (n + 20) Subject to the initial conditions b(1) = 0, b(2) = 0, b(3) = 1, b(4) = 4, b(5) = 9, b(6) = 19, b(7) = 44, b(8) = 97, b(9) = 198, b(10) = 407, b(11) = 853, b(12) = 1747, b(13) = 3516, b(14) = 7139, b(15) = 14528, b(16) = 29252, b(17) = 58739, b(18) = 118464, b(19) = 238553, b(20) = 478396, b(21) = 959870, b(22) = 1928605 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.4886 1/2 - ------ 1/2 n The probability of Bob winning the bet, as n grows larger is approximately 0.16288 1/2 - ------- 1/2 n You can see that indeed Bob has a better chance, but not significantly so. ----------------------------------------- This took, 35.904, 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, 2, 1]}, and Bob, bets vice versa, who is more likely to win? Answer: They are equally likely to win ----------------------------------------------------------------------------\ ----------------------- Question Mumber, 3, : If Alice bets that there are more occurrences of consec\ utive substrings in, {[2, 2, 2]}, than in, {[1, 2, 1]}, and Bob, bets vice versa, who is more likely to win? Answer: Bob is more likely to win. Let's be more quantitative. We need the following two lemmas Lemma , 3.1, : Let a(n) be the number of words of length n in the alphabet , {1, 2}, with more occurences of, {[2, 2, 2]}, then , {[1, 2, 1]} a(n) satisfies the following linear recurrence equation with polynomial coef\ ficients of order, 13 2 128 (n - 1) (n - 2) (n + 1) a(n) 64 (n - 1) (7 n + 10 n - 4) a(n + 1) - -------------------------------- + ------------------------------------- (n + 10) (n + 13) (n + 12) (n + 10) (n + 13) (n + 12) 2 n (14 n + 36 n + 1) a(n + 2) - 128/3 ----------------------------- (n + 10) (n + 13) (n + 12) (5 n + 7) (23 n + 78) (n + 1) a(n + 3) + 16/3 -------------------------------------- (n + 10) (n + 13) (n + 12) 3 2 8 (76 n + 621 n + 1453 n + 934) a(n + 4) - ------------------------------------------ (n + 10) (n + 13) (n + 12) 3 2 4 (114 n + 1201 n + 3911 n + 4034) a(n + 5) + --------------------------------------------- (n + 10) (n + 13) (n + 12) 3 2 (481 n + 6867 n + 31676 n + 47148) a(n + 6) - 2/3 --------------------------------------------- (n + 10) (n + 13) (n + 12) 3 2 (311 n + 5421 n + 30520 n + 54744) a(n + 7) + 2/3 --------------------------------------------- (n + 10) (n + 13) (n + 12) 3 2 (167 n + 3537 n + 24526 n + 55092) a(n + 8) - 2/3 --------------------------------------------- (n + 10) (n + 13) (n + 12) 3 2 2 (31 n + 776 n + 6353 n + 16874) a(n + 9) + -------------------------------------------- (n + 10) (n + 13) (n + 12) 3 2 (89 n + 2439 n + 21976 n + 64836) a(n + 10) - 1/3 --------------------------------------------- (n + 10) (n + 13) (n + 12) 3 2 (37 n + 1143 n + 11732 n + 39984) a(n + 11) + 1/3 --------------------------------------------- (n + 10) (n + 13) (n + 12) (n + 12) (5 n + 49) a(n + 12) - ----------------------------- + a(n + 13) = 0 (n + 13) (n + 10) 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) = 39, a(8) = 83, a(9) = 173, a(10) = 357, a(11) = 733, a(12) = 1497, a(13) = 3046 Lemma , 3.2, : Let b(n) be the number of words of length n in the alphabet , {1, 2}, with more occurences of, {[1, 2, 1]}, then , {[2, 2, 2]} b(n) satisfies the following linear recurrence equation with polynomial coef\ ficients of order, 15 2 128 (n - 1) (n - 2) (n + 1) b(n) 64 (n - 1) (11 n + 16 n - 8) b(n + 1) -------------------------------- - -------------------------------------- (n + 15) (n + 13) (n + 12) (n + 15) (n + 13) (n + 12) 3 2 (68 n + 165 n - 47 n + 12) b(n + 2) + 64/3 ------------------------------------- (n + 15) (n + 13) (n + 12) 3 2 (293 n + 1230 n + 679 n + 54) b(n + 3) - 16/3 ---------------------------------------- (n + 15) (n + 13) (n + 12) 3 2 8 (166 n + 1129 n + 1955 n + 1026) b(n + 4) + --------------------------------------------- (n + 15) (n + 13) (n + 12) 3 2 (958 n + 9615 n + 28613 n + 26130) b(n + 5) - 4/3 --------------------------------------------- (n + 15) (n + 13) (n + 12) 3 2 (1465 n + 18123 n + 67688 n + 75600) b(n + 6) + 2/3 ----------------------------------------------- (n + 15) (n + 13) (n + 12) 3 2 (377 n + 5661 n + 26329 n + 36885) b(n + 7) - 4/3 --------------------------------------------- (n + 15) (n + 13) (n + 12) 3 2 (851 n + 16035 n + 95314 n + 173160) b(n + 8) + 1/3 ----------------------------------------------- (n + 15) (n + 13) (n + 12) 3 2 (455 n + 9054 n + 54919 n + 94740) b(n + 9) - 1/3 --------------------------------------------- (n + 15) (n + 13) (n + 12) 3 2 (71 n + 693 n - 4676 n - 43968) b(n + 10) + 1/3 ------------------------------------------- (n + 15) (n + 13) (n + 12) 3 2 (11 n + 448 n + 5561 n + 21508) b(n + 11) + ------------------------------------------- (n + 15) (n + 13) (n + 12) 3 2 3 (3 n + 119 n + 1538 n + 6496) b(n + 12) - ------------------------------------------- (n + 15) (n + 13) (n + 12) 3 2 (31 n + 1206 n + 15563 n + 66624) b(n + 13) + 1/3 --------------------------------------------- (n + 15) (n + 13) (n + 12) 2 (17 n + 459 n + 3088) b(n + 14) - 1/3 -------------------------------- + b(n + 15) = 0 (n + 13) (n + 15) Subject to the initial conditions b(1) = 0, b(2) = 0, b(3) = 1, b(4) = 4, b(5) = 11, b(6) = 25, b(7) = 53, b(8) = 110, b(9) = 225, b(10) = 456, b(11) = 921, b(12) = 1856, b(13) = 3733, b(14) = 7501, b(15) = 15063 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.4232 1/2 - ------ 1/2 n The probability of Bob winning the bet, as n grows larger is approximately 0.14106 1/2 - ------- 1/2 n You can see that indeed Bob has a better chance, but not significantly so. ----------------------------------------- This took, 26.449, seconds to generate ----------------------------------------------------------------------------\ ----------------------- Question Mumber, 4, : If Alice bets that there are more occurrences of consec\ utive substrings in, {[1, 1, 2]}, than in, {[1, 2, 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, 2, 1]} a(n) satisfies the following linear recurrence equation with polynomial coef\ ficients of order, 10 2 16 (n + 4) (n + 2) (n + 1) a(n) 24 (n + 2) (n + 3 n - 2) a(n + 1) - ------------------------------- + ---------------------------------- (n + 10) (n + 9) (n + 7) (n + 10) (n + 9) (n + 7) 3 2 4 (9 n + 163 n + 768 n + 1076) a(n + 2) + ----------------------------------------- (n + 10) (n + 9) (n + 7) 3 2 2 (59 n + 965 n + 4876 n + 7864) a(n + 3) - ------------------------------------------- (n + 10) (n + 9) (n + 7) 3 2 2 (72 n + 1303 n + 7481 n + 13884) a(n + 4) + --------------------------------------------- (n + 10) (n + 9) (n + 7) 3 2 2 (63 n + 1202 n + 7429 n + 14996) a(n + 5) - --------------------------------------------- (n + 10) (n + 9) (n + 7) 3 2 (95 n + 1827 n + 11574 n + 24148) a(n + 6) + -------------------------------------------- (n + 10) (n + 9) (n + 7) 3 2 (60 n + 1209 n + 8051 n + 17676) a(n + 7) - ------------------------------------------- (n + 10) (n + 9) (n + 7) 3 2 (28 n + 617 n + 4497 n + 10820) a(n + 8) + ------------------------------------------ (n + 10) (n + 9) (n + 7) 2 (8 n + 121 n + 450) a(n + 9) - ----------------------------- + a(n + 10) = 0 (n + 10) (n + 7) Subject to the initial conditions a(1) = 0, a(2) = 0, a(3) = 1, a(4) = 3, a(5) = 7, a(6) = 17, a(7) = 38, a(8) = 80, a(9) = 169, a(10) = 353 Lemma , 4.2, : Let b(n) be the number of words of length n in the alphabet , {1, 2}, with more occurences of, {[1, 2, 1]}, then , {[1, 1, 2]} b(n) satisfies the following linear recurrence equation with polynomial coef\ ficients of order, 9 (n + 1) (n + 2) (n + 3) b(n) (11 n + 35) (n + 3) (n + 2) b(n + 1) 32/3 ---------------------------- - 8/3 ------------------------------------ (n + 10) (n + 9) (n + 6) (n + 10) (n + 9) (n + 6) 2 4 (n + 3) (9 n + 69 n + 134) b(n + 2) + -------------------------------------- (n + 10) (n + 9) (n + 6) 2 2 (n + 4) (9 n + 38 n - 31) b(n + 3) - ------------------------------------- (n + 10) (n + 9) (n + 6) 2 (n + 5) (13 n + 661 n + 3252) b(n + 4) - 1/3 --------------------------------------- (n + 10) (n + 9) (n + 6) 2 2 (7 n + 213 n + 1034) b(n + 5) (n + 7) (7 n + 135 n + 570) b(n + 6) + ------------------------------ - ------------------------------------- (n + 9) (n + 10) (n + 10) (n + 9) (n + 6) 2 (n + 8) (28 n + 403 n + 1389) b(n + 7) + 1/3 --------------------------------------- (n + 10) (n + 9) (n + 6) 2 (16 n + 231 n + 800) b(n + 8) - 1/3 ------------------------------ + b(n + 9) = 0 (n + 10) (n + 6) 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) = 32, b(8) = 66, b(9) = 138 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.4232 1/2 - ------ 1/2 n The probability of Bob winning the bet, as n grows larger is approximately 0.70522 1/2 - ------- 1/2 n You can see that indeed Alice has a better chance, but not significantly so. ----------------------------------------- This took, 19.267, 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, 2, 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, 2, 1]} a(n) satisfies the following linear recurrence equation with polynomial coef\ ficients of order, 17 (n + 1) (n + 2) (n + 3) a(n) (5 n + 17) (n + 3) (n + 2) a(n + 1) 64/3 ---------------------------- - 64/3 ----------------------------------- (n + 14) (n + 17) (n + 16) (n + 14) (n + 17) (n + 16) 2 32 (n + 3) (8 n + 65 n + 131) a(n + 2) + --------------------------------------- (n + 14) (n + 17) (n + 16) 3 2 16 (23 n + 303 n + 1310 n + 1866) a(n + 3) - -------------------------------------------- (n + 14) (n + 17) (n + 16) 3 2 (199 n + 1992 n + 4037 n - 4644) a(n + 4) + 4/3 ------------------------------------------- (n + 14) (n + 17) (n + 16) 3 2 (56 n + 4755 n + 51823 n + 151896) a(n + 5) + 4/3 --------------------------------------------- (n + 14) (n + 17) (n + 16) 3 2 (308 n + 12771 n + 131827 n + 403488) a(n + 6) - 4/3 ------------------------------------------------ (n + 14) (n + 17) (n + 16) 3 2 (997 n + 37422 n + 397841 n + 1302192) a(n + 7) + 2/3 ------------------------------------------------- (n + 14) (n + 17) (n + 16) 3 2 2 (531 n + 17315 n + 178968 n + 596920) a(n + 8) - -------------------------------------------------- (n + 14) (n + 17) (n + 16) 3 2 2 (785 n + 23822 n + 238893 n + 792784) a(n + 9) + -------------------------------------------------- (n + 14) (n + 17) (n + 16) 3 2 2 (901 n + 27681 n + 282638 n + 958806) a(n + 10) - --------------------------------------------------- (n + 14) (n + 17) (n + 16) 3 2 (4703 n + 152736 n + 1649533 n + 5921568) a(n + 11) + 1/3 ----------------------------------------------------- (n + 14) (n + 17) (n + 16) 3 2 (3178 n + 111081 n + 1292411 n + 5004132) a(n + 12) - 1/3 ----------------------------------------------------- (n + 14) (n + 17) (n + 16) 3 2 (1687 n + 63585 n + 798158 n + 3336264) a(n + 13) + 1/3 --------------------------------------------------- (n + 14) (n + 17) (n + 16) 3 2 (343 n + 13833 n + 185750 n + 830382) a(n + 14) - 2/3 ------------------------------------------------- (n + 14) (n + 17) (n + 16) 3 2 (199 n + 8502 n + 120875 n + 571788) a(n + 15) + 1/3 ------------------------------------------------ (n + 14) (n + 17) (n + 16) 2 (12 n + 347 n + 2499) a(n + 16) - -------------------------------- + a(n + 17) = 0 (n + 17) (n + 14) 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) = 51, a(8) = 100, a(9) = 197, a(10) = 397, a(11) = 814, a(12) = 1673, a(13) = 3411, a(14) = 6885, a(15) = 13809, a(16) = 27660, a(17) = 55509 Lemma , 5.2, : Let b(n) be the number of words of length n in the alphabet , {1, 2}, with more occurences of, {[1, 2, 1]}, then , {[1, 2, 2]} b(n) satisfies the following linear recurrence equation with polynomial coef\ ficients of order, 10 2 (n + 3) (n + 1) b(n) (7 n + 35 n + 40) b(n + 1) -32/3 -------------------- + 8/3 --------------------------- (n + 10) (n + 7) (n + 10) (n + 7) 2 2 (n - 25 n - 86) b(n + 2) (15 n + 287 n + 884) b(n + 3) - 4/3 ------------------------- - 2/3 ------------------------------ (n + 10) (n + 7) (n + 10) (n + 7) 2 2 (13 n - 295 n - 1664) b(n + 4) (9 n - 76 n - 699) b(n + 5) - 1/3 ------------------------------- + 2/3 ---------------------------- (n + 10) (n + 7) (n + 10) (n + 7) 2 (53 n + 857 n + 3302) b(n + 6) + 1/3 ------------------------------- (n + 10) (n + 7) 2 (47 n + 672 n + 2379) b(n + 7) - 2/3 ------------------------------- (n + 10) (n + 7) 2 2 (65 n + 969 n + 3544) b(n + 8) (11 n + 175 n + 678) b(n + 9) + 1/3 ------------------------------- - 2/3 ------------------------------ (n + 10) (n + 7) (n + 10) (n + 7) + b(n + 10) = 0 Subject to the initial conditions b(1) = 0, b(2) = 0, b(3) = 1, b(4) = 4, b(5) = 10, b(6) = 21, b(7) = 41, b(8) = 80, b(9) = 162, b(10) = 338 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.29922 1/2 - ------- 1/2 n The probability of Bob winning the bet, as n grows larger is approximately 0.49868 1/2 - ------- 1/2 n You can see that indeed Alice has a better chance, but not significantly so. ----------------------------------------- This took, 24.032, seconds to generate The best bet against, [1, 2, 1], is a member of, {[1, 1, 2], [2, 1, 1]}, 0.28202 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.19946 and then your edge is approximately, ------- 1/2 n The next best bet is a member of, {[2, 1, 2]}, and then your edge is exactly 0 The next best bet is a member of, {[2, 2, 2]}, 0.28214 and then your edge is approximately, - ------- 1/2 n The next best bet is a member of, {[1, 1, 1]}, 0.32572 and then your edge is approximately, - ------- 1/2 n ----------------------- This ends this chapter that took, 105.852, seconds to generate. ----------------------------------------------------------------- Chapter Number, 4 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, 2, 2], 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, 1, 1]}, than in, {[1, 2, 2]}, and Bob, bets vice versa, who is more likely to win? Answer: Bob 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, 1, 1]}, then , {[1, 2, 2]} a(n) satisfies the following linear recurrence equation with polynomial coef\ ficients of order, 11 (n + 1) (n + 2) a(n) (n + 2) (n - 3) a(n + 1) -16/3 -------------------- + 8/3 ------------------------ (n + 11) (n + 8) (n + 11) (n + 8) 2 2 (13 n + 117 n + 230) a(n + 2) (43 n + 395 n + 870) a(n + 3) + 4/3 ------------------------------ - 2/3 ------------------------------ (n + 11) (n + 8) (n + 11) (n + 8) 2 2 (5 n + 25 n - 3) a(n + 4) (59 n + 737 n + 2262) a(n + 5) + 4/3 -------------------------- + 1/3 ------------------------------- (n + 11) (n + 8) (n + 11) (n + 8) 2 2 (43 n + 559 n + 1834) a(n + 6) (13 n + 160 n + 447) a(n + 7) - 1/3 ------------------------------- - 2/3 ------------------------------ (n + 11) (n + 8) (n + 11) (n + 8) 2 (37 n + 515 n + 1708) a(n + 8) 2 (5 n + 43) a(n + 9) + 1/3 ------------------------------- + --------------------- (n + 11) (n + 8) (n + 11) (n + 8) 2 (11 n + 203 n + 918) a(n + 10) - 1/3 ------------------------------- + a(n + 11) = 0 (n + 11) (n + 8) Subject to the initial conditions a(1) = 0, a(2) = 0, a(3) = 1, a(4) = 3, a(5) = 7, a(6) = 16, a(7) = 34, a(8) = 73, a(9) = 153, a(10) = 318, a(11) = 657 Lemma , 1.2, : Let b(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]} b(n) satisfies the following linear recurrence equation with polynomial coef\ ficients of order, 18 (n + 1) (n + 2) (n + 3) b(n) (n - 5) (n + 3) (n + 2) b(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) b(n + 2) + 16/3 -------------------------------------- (n + 15) (n + 18) (n + 16) 3 2 (115 n + 1902 n + 9869 n + 16362) b(n + 3) - 8/3 -------------------------------------------- (n + 15) (n + 18) (n + 16) 3 2 (163 n + 2610 n + 12989 n + 20178) b(n + 4) + 8/3 --------------------------------------------- (n + 15) (n + 18) (n + 16) 3 2 (119 n + 6564 n + 68821 n + 201120) b(n + 5) + 2/3 ---------------------------------------------- (n + 15) (n + 18) (n + 16) 3 2 (1211 n + 30528 n + 243901 n + 627600) b(n + 6) - 2/3 ------------------------------------------------- (n + 15) (n + 18) (n + 16) 3 2 (811 n + 20548 n + 170149 n + 463244) b(n + 7) + ------------------------------------------------ (n + 15) (n + 18) (n + 16) 3 2 (220 n + 8475 n + 98015 n + 356742) b(n + 8) - 2/3 ---------------------------------------------- (n + 15) (n + 18) (n + 16) 3 2 (367 n + 6288 n + 23348 n - 30027) b(n + 9) - 2/3 --------------------------------------------- (n + 15) (n + 18) (n + 16) 3 2 (149 n + 2601 n + 19018 n + 85008) b(n + 10) + 1/3 ---------------------------------------------- (n + 15) (n + 18) (n + 16) 3 2 (485 n + 10920 n + 56857 n - 50826) b(n + 11) + 1/3 ----------------------------------------------- (n + 15) (n + 18) (n + 16) 3 2 (202 n + 4956 n + 32423 n + 25110) b(n + 12) - 2/3 ---------------------------------------------- (n + 15) (n + 18) (n + 16) 3 2 (127 n + 4257 n + 47159 n + 172773) b(n + 13) + 2/3 ----------------------------------------------- (n + 15) (n + 18) (n + 16) 2 (n + 13) (167 n + 4396 n + 28728) b(n + 14) - 1/3 -------------------------------------------- (n + 15) (n + 18) (n + 16) 3 2 (29 n + 1014 n + 11041 n + 35400) b(n + 15) + 1/3 --------------------------------------------- (n + 15) (n + 18) (n + 16) 3 2 2 (6 n + 287 n + 4562 n + 24100) b(n + 16) + -------------------------------------------- (n + 15) (n + 18) (n + 16) (5 n + 86) (2 n + 31) b(n + 17) - 2/3 ------------------------------- + b(n + 18) = 0 (n + 18) (n + 16) Subject to the initial conditions b(1) = 0, b(2) = 0, b(3) = 1, b(4) = 4, b(5) = 11, b(6) = 26, b(7) = 56, b(8) = 117, b(9) = 239, b(10) = 484, b(11) = 975, b(12) = 1957, b(13) = 3924, b(14) = 7859, b(15) = 15737, b(16) = 31505, b(17) = 63065, b(18) = 126238 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.57005 1/2 - ------- 1/2 n The probability of Bob winning the bet, as n grows larger is approximately 0.0814340 1/2 - --------- 1/2 n You can see that indeed Bob has a better chance, but not significantly so. ----------------------------------------- This took, 26.478, seconds to generate ----------------------------------------------------------------------------\ ----------------------- Question Mumber, 2, : If Alice bets that there are more occurrences of consec\ utive substrings in, {[1, 1, 2]}, than in, {[1, 2, 2]}, and Bob, bets vice versa, who is more likely to win? Answer: They are equally likely to win ----------------------------------------------------------------------------\ ----------------------- Question Mumber, 3, : If Alice bets that there are more occurrences of consec\ utive substrings in, {[1, 2, 1]}, than in, {[1, 2, 2]}, and Bob, bets vice versa, who is more likely to win? Answer: Bob is more likely to win. Let's be more quantitative. We need the following two lemmas Lemma , 3.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, 2, 2]} a(n) satisfies the following linear recurrence equation with polynomial coef\ ficients of order, 10 2 (n + 3) (n + 1) a(n) (7 n + 35 n + 40) a(n + 1) -32/3 -------------------- + 8/3 --------------------------- (n + 10) (n + 7) (n + 10) (n + 7) 2 2 (n - 25 n - 86) a(n + 2) (15 n + 287 n + 884) a(n + 3) - 4/3 ------------------------- - 2/3 ------------------------------ (n + 10) (n + 7) (n + 10) (n + 7) 2 2 (13 n - 295 n - 1664) a(n + 4) (9 n - 76 n - 699) a(n + 5) - 1/3 ------------------------------- + 2/3 ---------------------------- (n + 10) (n + 7) (n + 10) (n + 7) 2 (53 n + 857 n + 3302) a(n + 6) + 1/3 ------------------------------- (n + 10) (n + 7) 2 (47 n + 672 n + 2379) a(n + 7) - 2/3 ------------------------------- (n + 10) (n + 7) 2 2 (65 n + 969 n + 3544) a(n + 8) (11 n + 175 n + 678) a(n + 9) + 1/3 ------------------------------- - 2/3 ------------------------------ (n + 10) (n + 7) (n + 10) (n + 7) + a(n + 10) = 0 Subject to the initial conditions a(1) = 0, a(2) = 0, a(3) = 1, a(4) = 4, a(5) = 10, a(6) = 21, a(7) = 41, a(8) = 80, a(9) = 162, a(10) = 338 Lemma , 3.2, : Let b(n) be the number of words of length n in the alphabet , {1, 2}, with more occurences of, {[1, 2, 2]}, then , {[1, 2, 1]} b(n) satisfies the following linear recurrence equation with polynomial coef\ ficients of order, 17 (n + 1) (n + 2) (n + 3) b(n) (5 n + 17) (n + 3) (n + 2) b(n + 1) 64/3 ---------------------------- - 64/3 ----------------------------------- (n + 14) (n + 17) (n + 16) (n + 14) (n + 17) (n + 16) 2 32 (n + 3) (8 n + 65 n + 131) b(n + 2) + --------------------------------------- (n + 14) (n + 17) (n + 16) 3 2 16 (23 n + 303 n + 1310 n + 1866) b(n + 3) - -------------------------------------------- (n + 14) (n + 17) (n + 16) 3 2 (199 n + 1992 n + 4037 n - 4644) b(n + 4) + 4/3 ------------------------------------------- (n + 14) (n + 17) (n + 16) 3 2 (56 n + 4755 n + 51823 n + 151896) b(n + 5) + 4/3 --------------------------------------------- (n + 14) (n + 17) (n + 16) 3 2 (308 n + 12771 n + 131827 n + 403488) b(n + 6) - 4/3 ------------------------------------------------ (n + 14) (n + 17) (n + 16) 3 2 (997 n + 37422 n + 397841 n + 1302192) b(n + 7) + 2/3 ------------------------------------------------- (n + 14) (n + 17) (n + 16) 3 2 2 (531 n + 17315 n + 178968 n + 596920) b(n + 8) - -------------------------------------------------- (n + 14) (n + 17) (n + 16) 3 2 2 (785 n + 23822 n + 238893 n + 792784) b(n + 9) + -------------------------------------------------- (n + 14) (n + 17) (n + 16) 3 2 2 (901 n + 27681 n + 282638 n + 958806) b(n + 10) - --------------------------------------------------- (n + 14) (n + 17) (n + 16) 3 2 (4703 n + 152736 n + 1649533 n + 5921568) b(n + 11) + 1/3 ----------------------------------------------------- (n + 14) (n + 17) (n + 16) 3 2 (3178 n + 111081 n + 1292411 n + 5004132) b(n + 12) - 1/3 ----------------------------------------------------- (n + 14) (n + 17) (n + 16) 3 2 (1687 n + 63585 n + 798158 n + 3336264) b(n + 13) + 1/3 --------------------------------------------------- (n + 14) (n + 17) (n + 16) 3 2 (343 n + 13833 n + 185750 n + 830382) b(n + 14) - 2/3 ------------------------------------------------- (n + 14) (n + 17) (n + 16) 3 2 (199 n + 8502 n + 120875 n + 571788) b(n + 15) + 1/3 ------------------------------------------------ (n + 14) (n + 17) (n + 16) 2 (12 n + 347 n + 2499) b(n + 16) - -------------------------------- + b(n + 17) = 0 (n + 17) (n + 14) Subject to the initial conditions b(1) = 0, b(2) = 0, b(3) = 1, b(4) = 4, b(5) = 11, b(6) = 25, b(7) = 51, b(8) = 100, b(9) = 197, b(10) = 397, b(11) = 814, b(12) = 1673, b(13) = 3411, b(14) = 6885, b(15) = 13809, b(16) = 27660, b(17) = 55509 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.49868 1/2 - ------- 1/2 n The probability of Bob winning the bet, as n grows larger is approximately 0.29922 1/2 - ------- 1/2 n You can see that indeed Bob has a better chance, but not significantly so. ----------------------------------------- This took, 24.308, seconds to generate ----------------------------------------------------------------------------\ ----------------------- Question Mumber, 4, : If Alice bets that there are more occurrences of consec\ utive substrings in, {[2, 1, 1]}, than in, {[1, 2, 2]}, and Bob, bets vice versa, who is more likely to win? Answer: They are equally likely to win ----------------------------------------------------------------------------\ ----------------------- Question Mumber, 5, : If Alice bets that there are more occurrences of consec\ utive substrings in, {[2, 1, 2]}, than in, {[1, 2, 2]}, and Bob, bets vice versa, who is more likely to win? Answer: Bob 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, {[2, 1, 2]}, then , {[1, 2, 2]} a(n) satisfies the following linear recurrence equation with polynomial coef\ ficients of order, 9 (n + 1) (n + 2) (n + 3) a(n) (11 n + 35) (n + 3) (n + 2) a(n + 1) 32/3 ---------------------------- - 8/3 ------------------------------------ (n + 10) (n + 9) (n + 6) (n + 10) (n + 9) (n + 6) 2 4 (n + 3) (9 n + 69 n + 134) a(n + 2) + -------------------------------------- (n + 10) (n + 9) (n + 6) 2 2 (n + 4) (9 n + 38 n - 31) a(n + 3) - ------------------------------------- (n + 10) (n + 9) (n + 6) 2 (n + 5) (13 n + 661 n + 3252) a(n + 4) - 1/3 --------------------------------------- (n + 10) (n + 9) (n + 6) 2 2 (7 n + 213 n + 1034) a(n + 5) (n + 7) (7 n + 135 n + 570) a(n + 6) + ------------------------------ - ------------------------------------- (n + 9) (n + 10) (n + 10) (n + 9) (n + 6) 2 (n + 8) (28 n + 403 n + 1389) a(n + 7) + 1/3 --------------------------------------- (n + 10) (n + 9) (n + 6) 2 (16 n + 231 n + 800) a(n + 8) - 1/3 ------------------------------ + a(n + 9) = 0 (n + 10) (n + 6) Subject to the initial conditions a(1) = 0, a(2) = 0, a(3) = 1, a(4) = 3, a(5) = 6, a(6) = 14, a(7) = 32, a(8) = 66, a(9) = 138 Lemma , 5.2, : Let b(n) be the number of words of length n in the alphabet , {1, 2}, with more occurences of, {[1, 2, 2]}, then , {[2, 1, 2]} b(n) satisfies the following linear recurrence equation with polynomial coef\ ficients of order, 10 2 16 (n + 4) (n + 2) (n + 1) b(n) 24 (n + 2) (n + 3 n - 2) b(n + 1) - ------------------------------- + ---------------------------------- (n + 10) (n + 9) (n + 7) (n + 10) (n + 9) (n + 7) 3 2 4 (9 n + 163 n + 768 n + 1076) b(n + 2) + ----------------------------------------- (n + 10) (n + 9) (n + 7) 3 2 2 (59 n + 965 n + 4876 n + 7864) b(n + 3) - ------------------------------------------- (n + 10) (n + 9) (n + 7) 3 2 2 (72 n + 1303 n + 7481 n + 13884) b(n + 4) + --------------------------------------------- (n + 10) (n + 9) (n + 7) 3 2 2 (63 n + 1202 n + 7429 n + 14996) b(n + 5) - --------------------------------------------- (n + 10) (n + 9) (n + 7) 3 2 (95 n + 1827 n + 11574 n + 24148) b(n + 6) + -------------------------------------------- (n + 10) (n + 9) (n + 7) 3 2 (60 n + 1209 n + 8051 n + 17676) b(n + 7) - ------------------------------------------- (n + 10) (n + 9) (n + 7) 3 2 (28 n + 617 n + 4497 n + 10820) b(n + 8) + ------------------------------------------ (n + 10) (n + 9) (n + 7) 2 (8 n + 121 n + 450) 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) = 3, b(5) = 7, b(6) = 17, b(7) = 38, b(8) = 80, b(9) = 169, b(10) = 353 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.70522 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 Bob has a better chance, but not significantly so. ----------------------------------------- This took, 20.673, seconds to generate ----------------------------------------------------------------------------\ ----------------------- Question Mumber, 6, : If Alice bets that there are more occurrences of consec\ utive substrings in, {[2, 2, 1]}, than in, {[1, 2, 2]}, and Bob, bets vice versa, who is more likely to win? Answer: They are equally likely to win ----------------------------------------------------------------------------\ ----------------------- Question Mumber, 7, : If Alice bets that there are more occurrences of consec\ utive substrings in, {[2, 2, 2]}, than in, {[1, 2, 2]}, and Bob, bets vice versa, who is more likely to win? Answer: Bob is more likely to win. Let's be more quantitative. We need the following two lemmas Lemma , 7.1, : Let a(n) be the number of words of length n in the alphabet , {1, 2}, with more occurences of, {[2, 2, 2]}, then , {[1, 2, 2]} a(n) satisfies the following linear recurrence equation with polynomial coef\ ficients of order, 10 (n + 3) (n + 1) a(n) n (n + 1) a(n + 1) -32/3 -------------------- - 8/3 ------------------ (n + 10) (n + 7) (n + 10) (n + 7) 2 2 (17 n + 119 n + 210) a(n + 2) (25 n + 217 n + 456) a(n + 3) + 4/3 ------------------------------ - 2/3 ------------------------------ (n + 10) (n + 7) (n + 10) (n + 7) 2 (19 n + 331 n + 1188) a(n + 4) - 1/3 ------------------------------- (n + 10) (n + 7) 2 2 (59 n + 711 n + 2088) a(n + 5) (13 n + 150 n + 423) a(n + 6) + 1/3 ------------------------------- - 4/3 ------------------------------ (n + 10) (n + 7) (n + 10) (n + 7) 2 2 (11 n + 145 n + 504) a(n + 7) (10 n + 143 n + 486) a(n + 8) + 1/3 ------------------------------ + 2/3 ------------------------------ (n + 10) (n + 7) (n + 10) (n + 7) 2 (5 n + 79 n + 302) a(n + 9) - ---------------------------- + a(n + 10) = 0 (n + 10) (n + 7) Subject to the initial conditions a(1) = 0, a(2) = 0, a(3) = 1, a(4) = 2, a(5) = 5, a(6) = 11, a(7) = 26, a(8) = 56, a(9) = 121, a(10) = 255 Lemma , 7.2, : Let b(n) be the number of words of length n in the alphabet , {1, 2}, with more occurences of, {[1, 2, 2]}, then , {[2, 2, 2]} b(n) satisfies the following linear recurrence equation with polynomial coef\ ficients of order, 19 (n + 1) (n + 2) (n + 3) b(n) (2 n + 5) (n + 3) (n + 2) b(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) b(n + 2) + 32/3 -------------------------------- (n + 19) (n + 17) (n + 16) 2 16 (n + 4) (4 n + 41 n + 119) b(n + 3) + --------------------------------------- (n + 19) (n + 17) (n + 16) 3 2 4 (17 n + 368 n + 2799 n + 6888) b(n + 4) - ------------------------------------------- (n + 19) (n + 17) (n + 16) 3 2 (227 n + 5448 n + 41155 n + 100218) b(n + 5) - 4/3 ---------------------------------------------- (n + 19) (n + 17) (n + 16) 3 2 (371 n + 10374 n + 93319 n + 272880) b(n + 6) + 2/3 ----------------------------------------------- (n + 19) (n + 17) (n + 16) 3 2 (1625 n + 45084 n + 408091 n + 1214016) b(n + 7) + 1/3 -------------------------------------------------- (n + 19) (n + 17) (n + 16) 3 2 (587 n + 16936 n + 161921 n + 514380) b(n + 8) - ------------------------------------------------ (n + 19) (n + 17) (n + 16) 3 2 (26 n + 3213 n + 54346 n + 248871) b(n + 9) - 2/3 --------------------------------------------- (n + 19) (n + 17) (n + 16) 3 2 (397 n + 12898 n + 137591 n + 482434) b(n + 10) + ------------------------------------------------- (n + 19) (n + 17) (n + 16) 3 2 2 (236 n + 7115 n + 69690 n + 219335) b(n + 11) - ------------------------------------------------- (n + 19) (n + 17) (n + 16) 3 2 (265 n + 8430 n + 87941 n + 298560) b(n + 12) + 2/3 ----------------------------------------------- (n + 19) (n + 17) (n + 16) 3 2 (385 n + 12024 n + 117347 n + 341364) b(n + 13) + 1/3 ------------------------------------------------- (n + 19) (n + 17) (n + 16) 3 2 (103 n + 3194 n + 29685 n + 72578) b(n + 14) - ---------------------------------------------- (n + 19) (n + 17) (n + 16) 3 2 (17 n - 288 n - 18809 n - 159864) b(n + 15) + 1/3 --------------------------------------------- (n + 19) (n + 17) (n + 16) 2 (n + 15) (17 n + 477 n + 3268) b(n + 16) - 1/3 ----------------------------------------- (n + 19) (n + 17) (n + 16) 3 2 (49 n + 2382 n + 38531 n + 207414) b(n + 17) + 1/3 ---------------------------------------------- (n + 19) (n + 17) (n + 16) 2 (11 n + 376 n + 3201) b(n + 18) - 2/3 -------------------------------- + b(n + 19) = 0 (n + 17) (n + 19) 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) = 41, b(8) = 89, b(9) = 191, b(10) = 400, b(11) = 833, b(12) = 1717, b(13) = 3523, b(14) = 7184, b(15) = 14604, b(16) = 29588, b(17) = 59822, b(18) = 120695, b(19) = 243166 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.6982 1/2 - ------ 1/2 n The probability of Bob winning the bet, as n grows larger is approximately 0.099744 1/2 - -------- 1/2 n You can see that indeed Bob has a better chance, but not significantly so. ----------------------------------------- This took, 28.685, seconds to generate The best bet against, [1, 2, 2], is a member of, {[1, 1, 2], [2, 1, 1], [2, 2, 1]}, and then your edge, if you have n rolls, is exactly 0 The next best bet is a member of, {[1, 2, 1]}, 0.19946 and then your edge is approximately, - ------- 1/2 n The next best bet is a member of, {[2, 1, 2]}, 0.28202 and then your edge is approximately, - ------- 1/2 n The next best bet is a member of, {[1, 1, 1]}, 0.4886160 and then your edge is approximately, - --------- 1/2 n The next best bet is a member of, {[2, 2, 2]}, 0.598456 and then your edge is approximately, - -------- 1/2 n ----------------------- This ends this chapter that took, 100.408, seconds to generate. -------------------------------------------------------- This ends this book that took, 412.783, seconds to generate.