The Relative Probablity of Winning a Daniel Litt style game when rolling a f\ air, 4, sides die marked with, {1, 2, 3, 4}, of number of occurrences of, [1, 1, 1], Versus the number of occurences of all, 3, letter words in, {1, 2, 3, 4} 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, 3, 4}, 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 13824 (2 n + 3) (n + 2) (n + 1) a(n) - ------------------------------------ (n + 20) (n + 19) (n + 22) 2 1152 (n + 2) (332 n + 2243 n + 3495) a(n + 1) + ---------------------------------------------- (n + 20) (n + 19) (n + 22) 3 2 576 (559 n + 9096 n + 44231 n + 66054) a(n + 2) - ------------------------------------------------- (n + 20) (n + 19) (n + 22) 3 2 576 (22 n + 2193 n + 10397 n + 8238) a(n + 3) - ----------------------------------------------- (n + 20) (n + 19) (n + 22) 3 2 144 (1497 n + 66797 n + 579876 n + 1425700) a(n + 4) + ------------------------------------------------------ (n + 20) (n + 19) (n + 22) 3 2 72 (4362 n + 66943 n + 302503 n + 344782) a(n + 5) + ---------------------------------------------------- (n + 20) (n + 19) (n + 22) 3 2 12 (97685 n + 2063160 n + 15035785 n + 37580334) a(n + 6) + ----------------------------------------------------------- (n + 20) (n + 19) (n + 22) 3 2 12 (48424 n + 2150933 n + 26118311 n + 96214654) a(n + 7) + ----------------------------------------------------------- (n + 20) (n + 19) (n + 22) 3 2 3 (349705 n + 9649727 n + 88753678 n + 272443232) a(n + 8) + ------------------------------------------------------------ (n + 20) (n + 19) (n + 22) 3 2 3 (140305 n + 3955273 n + 31640844 n + 60976324) a(n + 9) + ----------------------------------------------------------- (n + 20) (n + 19) (n + 22) 3 2 (1164572 n + 39567768 n + 436961041 n + 1574540442) a(n + 10) - 2/3 --------------------------------------------------------------- (n + 20) (n + 19) (n + 22) 3 2 (509291 n + 22745373 n + 316260520 n + 1396053756) a(n + 11) - 1/3 -------------------------------------------------------------- (n + 20) (n + 19) (n + 22) 3 2 2 (52807 n + 2877992 n + 45703772 n + 224494072) a(n + 12) + ------------------------------------------------------------ (n + 20) (n + 19) (n + 22) 3 2 (3551 n + 284778 n + 3393529 n + 3155178) a(n + 13) - 2/3 ----------------------------------------------------- (n + 20) (n + 19) (n + 22) 3 2 (200543 n + 6967611 n + 76263094 n + 252978960) a(n + 14) + 1/3 ----------------------------------------------------------- (n + 20) (n + 19) (n + 22) 3 2 (25435 n + 961713 n + 11900582 n + 48118488) a(n + 15) - 4/3 -------------------------------------------------------- (n + 20) (n + 19) (n + 22) 3 2 (8779 n + 442569 n + 6956522 n + 33850704) a(n + 16) - 1/3 ------------------------------------------------------ (n + 20) (n + 19) (n + 22) 3 2 (8579 n + 350859 n + 4453372 n + 16469916) a(n + 17) + 1/3 ------------------------------------------------------ (n + 20) (n + 19) (n + 22) 3 2 (1681 n + 101211 n + 2000567 n + 13019946) a(n + 18) + 2/3 ------------------------------------------------------ (n + 20) (n + 19) (n + 22) 3 2 (891 n + 49889 n + 930260 n + 5776772) a(n + 19) - -------------------------------------------------- (n + 20) (n + 19) (n + 22) 3 2 (320 n + 18285 n + 347974 n + 2205648) a(n + 20) + 2/3 -------------------------------------------------- (n + 20) (n + 19) (n + 22) 2 (35 n + 1399 n + 13938) 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) = 8, a(5) = 45, a(6) = 231, a(7) = 1126, a(8) = 5277, a(9) = 24078, a(10) = 107787, a(11) = 475411, a(12) = 2072283, a(13) = 8947338, a(14) = 38328631, a(15) = 163110904, a(16) = 690242136, a(17) = 2906830065, a(18) = 12190250512, a(19) = 50933795977, a(20) = 212122728584, a(21) = 880872907524, a(22) = 3648524798341 Lemma , 1.2, : Let b(n) be the number of words of length n in the alphabet , {1, 2, 3, 4}, 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 13824 (2 n + 3) (n + 2) (n + 1) b(n) 1152 (4 n + 33) (n + 2) (n + 1) b(n + 1) ------------------------------------ + ---------------------------------------- (n + 15) (n + 14) (n + 12) (n + 15) (n + 14) (n + 12) 3 2 576 (175 n + 2268 n + 9323 n + 12270) b(n + 2) + ------------------------------------------------ (n + 15) (n + 14) (n + 12) 3 2 576 (176 n + 2931 n + 15781 n + 27474) b(n + 3) + ------------------------------------------------- (n + 15) (n + 14) (n + 12) 3 2 144 (613 n + 10589 n + 60296 n + 113332) b(n + 4) - --------------------------------------------------- (n + 15) (n + 14) (n + 12) 3 2 72 (734 n + 19115 n + 156847 n + 411454) b(n + 5) - --------------------------------------------------- (n + 15) (n + 14) (n + 12) 3 2 12 (2959 n + 88824 n + 809747 n + 2328522) b(n + 6) + ----------------------------------------------------- (n + 15) (n + 14) (n + 12) 3 2 12 (134 n + 2867 n - 2993 n - 134966) b(n + 7) - ------------------------------------------------ (n + 15) (n + 14) (n + 12) 3 2 3 (357 n + 52543 n + 879138 n + 3906368) b(n + 8) - --------------------------------------------------- (n + 15) (n + 14) (n + 12) 3 2 9 (767 n + 30247 n + 366812 n + 1412484) b(n + 9) + --------------------------------------------------- (n + 15) (n + 14) (n + 12) 3 2 (27605 n + 897675 n + 9646744 n + 34278156) b(n + 10) - 1/3 ------------------------------------------------------- (n + 15) (n + 14) (n + 12) 3 2 (15425 n + 507309 n + 5540470 n + 20081736) b(n + 11) + 1/3 ------------------------------------------------------- (n + 15) (n + 14) (n + 12) 3 2 (4639 n + 160461 n + 1844546 n + 7043064) b(n + 12) - 1/3 ----------------------------------------------------- (n + 15) (n + 14) (n + 12) 3 2 (799 n + 29295 n + 356960 n + 1444956) b(n + 13) + 1/3 -------------------------------------------------- (n + 15) (n + 14) (n + 12) 2 (25 n + 621 n + 3834) 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) = 7, b(5) = 38, b(6) = 194, b(7) = 940, b(8) = 4384, b(9) = 19953, b(10) = 89187, b(11) = 392987, b(12) = 1712117, b(13) = 7391021, b(14) = 31664003, b(15) = 134784233 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.757 1/2 - ----- 1/2 n The probability of Bob winning the bet, as n grows larger is approximately 1.26 1/2 - ---- 1/2 n You can see that indeed Alice has a better chance, but not significantly so. ----------------------------------------- This took, 38.918, seconds to generate ----------------------------------------------------------------------------\ ----------------------- Question Mumber, 2, : 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, 3, : 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 , 3.1, : Let a(n) be the number of words of length n in the alphabet , {1, 2, 3, 4}, 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, 21 36864 (n + 1) (n + 2) (n + 3) a(n) 18432 (n + 3) (n + 2) (8 n + 23) a(n + 1) ---------------------------------- + ----------------------------------------- (n + 19) (n + 18) (n + 21) (n + 19) (n + 18) (n + 21) 2 1536 (n + 3) (157 n + 1086 n + 1865) a(n + 2) + ---------------------------------------------- (n + 19) (n + 18) (n + 21) 3 2 128 (1126 n + 9135 n + 14855 n - 14388) a(n + 3) + -------------------------------------------------- (n + 19) (n + 18) (n + 21) 3 2 16 (5371 n + 155652 n + 1161197 n + 2577612) a(n + 4) - ------------------------------------------------------- (n + 19) (n + 18) (n + 21) 3 2 (6644 n - 20061 n - 1268135 n - 5536614) a(n + 5) - 16/3 --------------------------------------------------- (n + 19) (n + 18) (n + 21) 3 2 4 (67135 n + 2183394 n + 20967807 n + 62943744) a(n + 6) + ---------------------------------------------------------- (n + 19) (n + 18) (n + 21) 3 2 (1012381 n + 30528276 n + 293396111 n + 910578072) a(n + 7) + 1/3 ------------------------------------------------------------- (n + 19) (n + 18) (n + 21) 3 2 (706786 n + 17342535 n + 138569189 n + 354951192) a(n + 8) + 1/3 ------------------------------------------------------------ (n + 19) (n + 18) (n + 21) 3 2 (230800 n + 3087567 n - 7554901 n - 154580436) a(n + 9) + 1/3 --------------------------------------------------------- (n + 19) (n + 18) (n + 21) 3 2 (225170 n + 6871455 n + 69907582 n + 236644560) a(n + 10) - 2/3 ----------------------------------------------------------- (n + 19) (n + 18) (n + 21) 3 2 (130063 n + 4001365 n + 40359180 n + 132714636) a(n + 11) - ----------------------------------------------------------- (n + 19) (n + 18) (n + 21) 3 2 (36979 n + 1116064 n + 10914639 n + 34200924) a(n + 12) + --------------------------------------------------------- (n + 19) (n + 18) (n + 21) 3 2 (140443 n + 5416722 n + 69431525 n + 295807686) a(n + 13) + 1/3 ----------------------------------------------------------- (n + 19) (n + 18) (n + 21) 3 2 (8984 n + 192603 n + 250789 n - 9518526) a(n + 14) - 1/3 ---------------------------------------------------- (n + 19) (n + 18) (n + 21) 3 2 (13125 n + 591065 n + 8864652 n + 44284782) a(n + 15) - ------------------------------------------------------- (n + 19) (n + 18) (n + 21) 3 2 (1689 n + 74567 n + 1102010 n + 5464848) a(n + 16) + ---------------------------------------------------- (n + 19) (n + 18) (n + 21) 3 2 (7633 n + 379521 n + 6276284 n + 34520052) a(n + 17) + 1/3 ------------------------------------------------------ (n + 19) (n + 18) (n + 21) 3 2 (1242 n + 63975 n + 1097153 n + 6264998) a(n + 18) - ---------------------------------------------------- (n + 19) (n + 18) (n + 21) 3 2 4 (63 n + 3378 n + 60301 n + 358412) a(n + 19) + ------------------------------------------------ (n + 19) (n + 18) (n + 21) 2 (25 n + 945 n + 8896) a(n + 20) - -------------------------------- + a(n + 21) = 0 (n + 21) (n + 19) Subject to the initial conditions a(1) = 0, a(2) = 0, a(3) = 1, a(4) = 7, a(5) = 40, a(6) = 206, a(7) = 1003, a(8) = 4705, a(9) = 21505, a(10) = 96424, a(11) = 426013, a(12) = 1860297, a(13) = 8046747, a(14) = 34534136, a(15) = 147234798, a(16) = 624209536, a(17) = 2633578216, a(18) = 11064484887, a(19) = 46313702908, a(20) = 193226772775, a(21) = 803823809390 Lemma , 3.2, : Let b(n) be the number of words of length n in the alphabet , {1, 2, 3, 4}, 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 2 (n + 3) (n + 1) b(n) (9 n + 37 n + 40) b(n + 1) -512/3 -------------------- - 64/3 --------------------------- (n + 10) (n + 7) (n + 10) (n + 7) 2 (11 n + 213 n + 550) b(n + 2) + 16/3 ------------------------------ (n + 10) (n + 7) 2 (25 n + 505 n + 1788) b(n + 3) + 4/3 ------------------------------- (n + 10) (n + 7) 2 (123 n + 563 n + 188) b(n + 4) + 1/3 ------------------------------- (n + 10) (n + 7) 2 (355 n + 2659 n + 3076) b(n + 5) + 1/3 --------------------------------- (n + 10) (n + 7) 2 (17 n + 195 n + 570) b(n + 6) - 14/3 ------------------------------ (n + 10) (n + 7) 2 (165 n + 2095 n + 6172) b(n + 7) - 1/3 --------------------------------- (n + 10) (n + 7) 2 (75 n + 1090 n + 3836) b(n + 8) + 2/3 -------------------------------- (n + 10) (n + 7) 2 (37 n + 587 n + 2262) b(n + 9) - 1/3 ------------------------------- + b(n + 10) = 0 (n + 10) (n + 7) Subject to the initial conditions b(1) = 0, b(2) = 0, b(3) = 1, b(4) = 6, b(5) = 33, b(6) = 167, b(7) = 804, b(8) = 3744, b(9) = 17029, b(10) = 76099 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.776 1/2 - ----- 1/2 n The probability of Bob winning the bet, as n grows larger is approximately 1.48 1/2 - ---- 1/2 n You can see that indeed Alice has a better chance, but not significantly so. ----------------------------------------- This took, 26.536, seconds to generate ----------------------------------------------------------------------------\ ----------------------- Question Mumber, 4, : 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 , 4.1, : Let a(n) be the number of words of length n in the alphabet , {1, 2, 3, 4}, 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, 27 3 2 (225626 n + 2795463 n + 11571895 n + 15974124) a(n + 3) 64/3 --------------------------------------------------------- (n + 25) (n + 24) (n + 27) 3 2 64 (53850 n + 438871 n + 139985 n - 3517752) a(n + 4) + ------------------------------------------------------- (n + 25) (n + 24) (n + 27) 3 2 (224338 n + 2380713 n + 4424213 n - 10162638) a(n + 5) + 32/3 -------------------------------------------------------- (n + 25) (n + 24) (n + 27) 3 2 (228457 n + 9933990 n + 102199871 n + 304754826) a(n + 6) - 16/3 ----------------------------------------------------------- (n + 25) (n + 24) (n + 27) 3 2 32 (99399 n + 1510582 n + 4816779 n - 7838064) a(n + 7) - --------------------------------------------------------- (n + 25) (n + 24) (n + 27) 3 2 (153121 n + 6163266 n + 79760921 n + 330918384) a(n + 8) + 16/3 ---------------------------------------------------------- (n + 25) (n + 24) (n + 27) 3 2 (46358 n + 11197239 n + 204243067 n + 969597330) a(n + 9) + 16/3 ----------------------------------------------------------- (n + 25) (n + 24) (n + 27) 3 2 (2801921 n + 86450058 n + 902344399 n + 3186333510) a(n + 10) + 8/3 --------------------------------------------------------------- (n + 25) (n + 24) (n + 27) 3 2 16 (43462 n + 3164425 n + 54102733 n + 268970016) a(n + 11) + ------------------------------------------------------------- (n + 25) (n + 24) (n + 27) 3 2 (1560904 n + 51260589 n + 556125035 n + 1990577964) a(n + 12) + 8/3 --------------------------------------------------------------- (n + 25) (n + 24) (n + 27) 3 2 8 (343787 n + 11800954 n + 134108949 n + 506356918) a(n + 13) - --------------------------------------------------------------- (n + 25) (n + 24) (n + 27) 3 2 4 (245643 n + 7931963 n + 78858468 n + 224751932) a(n + 14) + ------------------------------------------------------------- (n + 25) (n + 24) (n + 27) 3 2 (2304163 n + 95278770 n + 1306375169 n + 5940180234) a(n + 15) - 2/3 ---------------------------------------------------------------- (n + 25) (n + 24) (n + 27) 3 2 4 (187417 n + 7920114 n + 110328221 n + 506248624) a(n + 16) + -------------------------------------------------------------- (n + 25) (n + 24) (n + 27) 3 2 2 (153197 n + 6839094 n + 100423777 n + 483864936) a(n + 17) - -------------------------------------------------------------- (n + 25) (n + 24) (n + 27) 3 2 2 (116352 n + 5805495 n + 96053657 n + 526752006) a(n + 18) + ------------------------------------------------------------- (n + 25) (n + 24) (n + 27) 3 2 (267859 n + 13663158 n + 230081189 n + 1277306682) a(n + 19) - 1/3 -------------------------------------------------------------- (n + 25) (n + 24) (n + 27) 3 2 (29107 n + 1470654 n + 24181961 n + 128410584) a(n + 20) + 2/3 ---------------------------------------------------------- (n + 25) (n + 24) (n + 27) 3 2 2 (3757 n + 208047 n + 3796009 n + 22779735) a(n + 21) - -------------------------------------------------------- (n + 25) (n + 24) (n + 27) 3 2 2 (331 n + 11426 n + 32843 n - 1277866) a(n + 22) + --------------------------------------------------- (n + 25) (n + 24) (n + 27) 3 2 2 (925 n + 65065 n + 1521801 n + 11836121) a(n + 23) + ------------------------------------------------------ (n + 25) (n + 24) (n + 27) 3 2 (1469 n + 103470 n + 2428003 n + 18981468) a(n + 24) - 2/3 ------------------------------------------------------ (n + 25) (n + 24) (n + 27) 3 2 (326 n + 23487 n + 563734 n + 4507893) a(n + 25) + 2/3 -------------------------------------------------- (n + 25) (n + 24) (n + 27) (n + 1) (n + 2) (n + 3) a(n) + 557056/3 ---------------------------- (n + 25) (n + 24) (n + 27) (2005 n + 8563) (n + 3) (n + 2) a(n + 1) + 2048/3 ---------------------------------------- (n + 25) (n + 24) (n + 27) 2 (n + 3) (28604 n + 207009 n + 345616) a(n + 2) + 256/3 ----------------------------------------------- + a(n + 27) (n + 25) (n + 24) (n + 27) 2 (35 n + 1749 n + 21808) a(n + 26) - 2/3 ---------------------------------- = 0 (n + 27) (n + 25) Subject to the initial conditions a(1) = 0, a(2) = 0, a(3) = 1, a(4) = 8, a(5) = 47, a(6) = 245, a(7) = 1199, a(8) = 5638, a(9) = 25785, a(10) = 115556, a(11) = 509919, a(12) = 2222912, a(13) = 9595699, a(14) = 41088365, a(15) = 174752029, a(16) = 738979558, a(17) = 3109587999, a(18) = 13029219805, a(19) = 54389130899, a(20) = 226296045796, a(21) = 938803202973, a(22) = 3884557754835, a(23) = 16035947319737, a(24) = 66059294040130, a(25) = 271610350913567, a(26) = 1114826913541230, a(27) = 4568605276774093 Lemma , 4.2, : Let b(n) be the number of words of length n in the alphabet , {1, 2, 3, 4}, 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, 24 2 7 (3 n + 129 n + 1384) b(n + 23) - --------------------------------- (n + 24) (n + 21) 3 2 (108358 n + 1685265 n + 8564993 n + 14229108) b(n + 3) + 64/3 -------------------------------------------------------- (n + 24) (n + 23) (n + 21) 3 2 (208142 n + 3837069 n + 23192611 n + 46051968) b(n + 4) + 64/3 --------------------------------------------------------- (n + 24) (n + 23) (n + 21) 3 2 32 (197898 n + 4118069 n + 28157137 n + 63422202) b(n + 5) + ------------------------------------------------------------ (n + 24) (n + 23) (n + 21) 3 2 (1163185 n + 27778650 n + 217463435 n + 559665042) b(n + 6) + 16/3 ------------------------------------------------------------- (n + 24) (n + 23) (n + 21) 3 2 (190313 n + 5088150 n + 44475211 n + 127439562) b(n + 7) + 64/3 ---------------------------------------------------------- (n + 24) (n + 23) (n + 21) 3 2 (256061 n + 8571240 n + 90005935 n + 301744992) b(n + 8) + 16/3 ---------------------------------------------------------- (n + 24) (n + 23) (n + 21) 3 2 (131648 n + 3288735 n + 27259501 n + 76197366) b(n + 9) - 16/3 --------------------------------------------------------- (n + 24) (n + 23) (n + 21) 3 2 (283375 n + 8795484 n + 91035419 n + 315510006) b(n + 10) - 8/3 ----------------------------------------------------------- (n + 24) (n + 23) (n + 21) 3 2 8 (81379 n + 2992418 n + 36377665 n + 146496098) b(n + 11) - ------------------------------------------------------------ (n + 24) (n + 23) (n + 21) 3 2 (48758 n + 1362519 n + 11664799 n + 28300932) b(n + 12) + 8/3 --------------------------------------------------------- (n + 24) (n + 23) (n + 21) 3 2 8 (3476 n + 162115 n + 2517547 n + 12945664) b(n + 13) - -------------------------------------------------------- (n + 24) (n + 23) (n + 21) 3 2 (113534 n + 4819581 n + 68096041 n + 320332146) b(n + 14) + 4/3 ----------------------------------------------------------- (n + 24) (n + 23) (n + 21) 3 2 (86701 n + 3604314 n + 49818707 n + 229171878) b(n + 15) - 2/3 ---------------------------------------------------------- (n + 24) (n + 23) (n + 21) 3 2 4 (6909 n + 326115 n + 5141820 n + 27076760) b(n + 16) + -------------------------------------------------------- (n + 24) (n + 23) (n + 21) 3 2 2 (11995 n + 608466 n + 10270427 n + 57670996) b(n + 17) - ---------------------------------------------------------- (n + 24) (n + 23) (n + 21) 3 2 2 (5225 n + 275202 n + 4820771 n + 28075142) b(n + 18) + -------------------------------------------------------- (n + 24) (n + 23) (n + 21) 3 2 (5975 n + 334902 n + 6242389 n + 38677038) b(n + 19) - 2/3 ------------------------------------------------------ (n + 24) (n + 23) (n + 21) 3 2 2 (1038 n + 61645 n + 1218119 n + 8007240) b(n + 20) + ------------------------------------------------------ (n + 24) (n + 23) (n + 21) 3 2 (813 n + 50208 n + 1032373 n + 7066962) b(n + 21) - --------------------------------------------------- (n + 24) (n + 23) (n + 21) 3 2 (181 n + 11568 n + 246205 n + 1744862) b(n + 22) + -------------------------------------------------- (n + 24) (n + 23) (n + 21) (n + 1) (n + 2) (n + 3) b(n) - 32768/3 ---------------------------- (n + 24) (n + 23) (n + 21) (235 n + 1261) (n + 3) (n + 2) b(n + 1) + 2048/3 --------------------------------------- (n + 24) (n + 23) (n + 21) 2 (n + 3) (8372 n + 83247 n + 198832) b(n + 2) + 256/3 --------------------------------------------- + b(n + 24) = 0 (n + 24) (n + 23) (n + 21) Subject to the initial conditions b(1) = 0, b(2) = 0, b(3) = 1, b(4) = 7, b(5) = 40, b(6) = 206, b(7) = 1001, b(8) = 4687, b(9) = 21379, b(10) = 95657, b(11) = 421725, b(12) = 1837649, b(13) = 7931958, b(14) = 33970256, b(15) = 144532023, b(16) = 611508677, b(17) = 2574860150, b(18) = 10796708122, b(19) = 45106650879, b(20) = 187839921325, b(21) = 779991462722, b(22) = 3230569132542, b(23) = 13349615512707, b(24) = 55049901196197 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.722 1/2 - ----- 1/2 n The probability of Bob winning the bet, as n grows larger is approximately 1.20 1/2 - ---- 1/2 n You can see that indeed Alice has a better chance, but not significantly so. ----------------------------------------- This took, 54.902, 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, 3, 4}, 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, 21 20480 (n + 1) (n + 2) (n + 3) a(n) 51200 (n - 1) (n + 3) (n + 2) a(n + 1) - ---------------------------------- + -------------------------------------- (n + 19) (n + 18) (n + 21) (n + 19) (n + 18) (n + 21) 2 256 (n + 3) (293 n + 2393 n + 4084) a(n + 2) + --------------------------------------------- (n + 19) (n + 18) (n + 21) 3 2 (4517 n + 51846 n + 237703 n + 409374) a(n + 3) + 64/3 ------------------------------------------------- (n + 19) (n + 18) (n + 21) 3 2 64 (1031 n + 31640 n + 217909 n + 423310) a(n + 4) - ---------------------------------------------------- (n + 19) (n + 18) (n + 21) 3 2 (63355 n + 1820568 n + 15577361 n + 41081772) a(n + 5) - 4/3 -------------------------------------------------------- (n + 19) (n + 18) (n + 21) 3 2 (5630 n - 1585359 n - 21012017 n - 67710264) a(n + 6) - 4/3 ------------------------------------------------------- (n + 19) (n + 18) (n + 21) 3 2 (863585 n + 20359404 n + 157460755 n + 401987736) a(n + 7) - 1/3 ------------------------------------------------------------ (n + 19) (n + 18) (n + 21) 3 2 (354861 n + 9872311 n + 91889178 n + 285613152) a(n + 8) + ---------------------------------------------------------- (n + 19) (n + 18) (n + 21) 3 2 (73775 n + 505520 n - 10525875 n - 82214668) a(n + 9) + ------------------------------------------------------- (n + 19) (n + 18) (n + 21) 3 2 2 (30010 n + 1312927 n + 17008572 n + 68571140) a(n + 10) + ----------------------------------------------------------- (n + 19) (n + 18) (n + 21) 3 2 (252101 n + 7757382 n + 77713549 n + 251378940) a(n + 11) - 2/3 ----------------------------------------------------------- (n + 19) (n + 18) (n + 21) 3 2 (68203 n + 1447830 n + 4724456 n - 33953868) a(n + 12) + 2/3 -------------------------------------------------------- (n + 19) (n + 18) (n + 21) 3 2 2 (16251 n + 465897 n + 3801641 n + 6378107) a(n + 13) - -------------------------------------------------------- (n + 19) (n + 18) (n + 21) 3 2 4 (13193 n + 511447 n + 6546420 n + 27610462) a(n + 14) + --------------------------------------------------------- (n + 19) (n + 18) (n + 21) 3 2 2 (11964 n + 487989 n + 6571990 n + 29172261) a(n + 15) - --------------------------------------------------------- (n + 19) (n + 18) (n + 21) 3 2 (1472 n + 115023 n + 2514352 n + 16803600) a(n + 16) - 2/3 ------------------------------------------------------ (n + 19) (n + 18) (n + 21) 3 2 (6395 n + 323730 n + 5455183 n + 30600468) a(n + 17) + 2/3 ------------------------------------------------------ (n + 19) (n + 18) (n + 21) 3 2 (2393 n + 124098 n + 2143534 n + 12333036) a(n + 18) - 2/3 ------------------------------------------------------ (n + 19) (n + 18) (n + 21) 3 2 (859 n + 46194 n + 827177 n + 4932618) a(n + 19) + 1/3 -------------------------------------------------- (n + 19) (n + 18) (n + 21) 2 (79 n + 2991 n + 28208) a(n + 20) - 1/3 ---------------------------------- + a(n + 21) = 0 (n + 21) (n + 19) Subject to the initial conditions a(1) = 0, a(2) = 0, a(3) = 1, a(4) = 8, a(5) = 47, a(6) = 246, a(7) = 1206, a(8) = 5677, a(9) = 25983, a(10) = 116508, a(11) = 514333, a(12) = 2242861, a(13) = 9684180, a(14) = 41475155, a(15) = 176423505, a(16) = 746135481, a(17) = 3139987823, a(18) = 13157527226, a(19) = 54927681496, a(20) = 228545768343, a(21) = 948162200909 Lemma , 5.2, : Let b(n) be the number of words of length n in the alphabet , {1, 2, 3, 4}, 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) (5 n + 17) (n + 2) b(n + 1) -256/3 -------------------- - 64/3 --------------------------- (n + 11) (n + 8) (n + 11) (n + 8) 2 16 (7 n + 78) (n + 3) b(n + 2) (19 n - 297 n - 1654) b(n + 3) + ------------------------------ - 4/3 ------------------------------- (n + 11) (n + 8) (n + 11) (n + 8) 2 (70 n + 634 n + 1495) b(n + 4) + 8/3 ------------------------------- (n + 11) (n + 8) 2 (681 n + 6851 n + 16470) b(n + 5) + 1/3 ---------------------------------- (n + 11) (n + 8) 2 (77 n + 1897 n + 10106) b(n + 6) - 1/3 --------------------------------- (n + 11) (n + 8) 2 (222 n + 2791 n + 8339) b(n + 7) - 2/3 --------------------------------- (n + 11) (n + 8) 2 2 (39 n + 337 n + 240) b(n + 8) (50 n + 869 n + 3711) b(n + 9) + 1/3 ------------------------------ + 2/3 ------------------------------- (n + 11) (n + 8) (n + 11) (n + 8) 2 (11 n + 199 n + 882) b(n + 10) - ------------------------------- + b(n + 11) = 0 (n + 11) (n + 8) Subject to the initial conditions b(1) = 0, b(2) = 0, b(3) = 1, b(4) = 7, b(5) = 39, b(6) = 200, b(7) = 968, b(8) = 4521, b(9) = 20587, b(10) = 92002, b(11) = 405259 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.694 1/2 - ----- 1/2 n The probability of Bob winning the bet, as n grows larger is approximately 1.32 1/2 - ---- 1/2 n You can see that indeed Alice has a better chance, but not significantly so. ----------------------------------------- This took, 29.821, seconds to generate ----------------------------------------------------------------------------\ ----------------------- Question Mumber, 6, : If Alice bets that there are more occurrences of consec\ utive substrings in, {[2, 1, 3]}, 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 , 6.1, : Let a(n) be the number of words of length n in the alphabet , {1, 2, 3, 4}, with more occurences of, {[2, 1, 3]}, then , {[1, 1, 1]} a(n) satisfies the following linear recurrence equation with polynomial coef\ ficients of order, 25 2 72 (n + 4) (694 n + 2453 n + 2115) a(n + 1) -------------------------------------------- (n + 25) (n + 23) (n + 22) 3 2 (478669 n + 26706480 n + 436982207 n + 2219470116) a(n + 12) + 1/3 -------------------------------------------------------------- (n + 25) (n + 23) (n + 22) 3 2 2 (163583 n + 6088357 n + 74020128 n + 292346094) a(n + 13) - ------------------------------------------------------------- (n + 25) (n + 23) (n + 22) 3 2 (814381 n + 36733488 n + 546652313 n + 2684911278) a(n + 14) - 1/3 -------------------------------------------------------------- (n + 25) (n + 23) (n + 22) 3 2 (33937 n + 2380851 n + 49312553 n + 318484251) a(n + 15) - 2/3 ---------------------------------------------------------- (n + 25) (n + 23) (n + 22) 3 2 2 (41344 n + 1985857 n + 31627713 n + 166920228) a(n + 16) + ------------------------------------------------------------ (n + 25) (n + 23) (n + 22) 3 2 2 (17231 n + 940526 n + 17065662 n + 102971135) a(n + 17) + ----------------------------------------------------------- (n + 25) (n + 23) (n + 22) 3 2 (17465 n + 908064 n + 15697545 n + 90192570) a(n + 18) - -------------------------------------------------------- (n + 25) (n + 23) (n + 22) 3 2 (31187 n + 1809258 n + 34981573 n + 225468390) a(n + 19) - 1/3 ---------------------------------------------------------- (n + 25) (n + 23) (n + 22) 3 2 (4931 n + 283250 n + 5424091 n + 34638180) a(n + 20) + ------------------------------------------------------ (n + 25) (n + 23) (n + 22) 3 2 (2375 n + 158556 n + 3499867 n + 25566870) a(n + 21) + 1/3 ------------------------------------------------------ (n + 25) (n + 23) (n + 22) 3 2 (863 n + 55642 n + 1195017 n + 8549310) a(n + 22) - --------------------------------------------------- (n + 25) (n + 23) (n + 22) 3 2 (637 n + 42072 n + 925631 n + 6784140) a(n + 23) + 1/3 -------------------------------------------------- (n + 25) (n + 23) (n + 22) 3 2 6 (29672 n + 331623 n + 1145713 n + 1250670) a(n + 2) + ------------------------------------------------------- (n + 25) (n + 23) (n + 22) 3 2 3 (106189 n + 1772442 n + 8744087 n + 13376298) a(n + 3) + ---------------------------------------------------------- (n + 25) (n + 23) (n + 22) 3 2 2 (83666 n + 3250551 n + 24814609 n + 52992552) a(n + 4) + ---------------------------------------------------------- (n + 25) (n + 23) (n + 22) 3 2 6 (99877 n + 614675 n - 2598839 n - 15840493) a(n + 5) - -------------------------------------------------------- (n + 25) (n + 23) (n + 22) 3 2 2 (858693 n + 13862192 n + 70101641 n + 108003690) a(n + 6) - ------------------------------------------------------------- (n + 25) (n + 23) (n + 22) 3 2 (2145589 n + 46121652 n + 326532907 n + 764857916) a(n + 7) - ------------------------------------------------------------- (n + 25) (n + 23) (n + 22) 3 2 2 (588099 n + 16329626 n + 148960787 n + 449425832) a(n + 8) - -------------------------------------------------------------- (n + 25) (n + 23) (n + 22) 3 2 (472139 n + 8688090 n + 36009063 n - 39151176) a(n + 9) + --------------------------------------------------------- (n + 25) (n + 23) (n + 22) 3 2 (4150019 n + 123560268 n + 1206533839 n + 3846866790) a(n + 10) + 1/3 ----------------------------------------------------------------- (n + 25) (n + 23) (n + 22) 3 2 2 (514299 n + 18576425 n + 220346781 n + 858667407) a(n + 11) + --------------------------------------------------------------- (n + 25) (n + 23) (n + 22) 2 (35 n + 1609 n + 18450) a(n + 24) - 2/3 ---------------------------------- (n + 23) (n + 25) 2880 (2 n + 1) (n + 3) (n + 1) a(n) + ----------------------------------- + a(n + 25) = 0 (n + 25) (n + 23) (n + 22) Subject to the initial conditions a(1) = 0, a(2) = 0, a(3) = 1, a(4) = 8, a(5) = 48, a(6) = 253, a(7) = 1246, a(8) = 5880, a(9) = 26952, a(10) = 120955, a(11) = 534190, a(12) = 2329770, a(13) = 10058775, a(14) = 43070350, a(15) = 183150585, a(16) = 774276863, a(17) = 3256920942, a(18) = 13640635798, a(19) = 56913858733, a(20) = 236676708298, a(21) = 981324548990, a(22) = 4058161102501, a(23) = 16742661830191, a(24) = 68928785524545, a(25) = 283234485048759 Lemma , 6.2, : Let b(n) be the number of words of length n in the alphabet , {1, 2, 3, 4}, with more occurences of, {[1, 1, 1]}, then , {[2, 1, 3]} b(n) satisfies the following linear recurrence equation with polynomial coef\ ficients of order, 8 2 24 (n + 1) (2 n + 1) b(n) 6 (28 n + 103 n + 91) b(n + 1) ------------------------- + ------------------------------- (n + 8) (n + 5) (n + 8) (n + 5) 2 2 (131 n + 641 n + 678) b(n + 2) 4 (n + 4 n + 27) b(n + 3) + ------------------------------- - -------------------------- (n + 8) (n + 5) (n + 8) (n + 5) 2 2 2 (33 n + 291 n + 652) b(n + 4) 2 (21 n + 201 n + 440) b(n + 5) - -------------------------------- - -------------------------------- (n + 8) (n + 5) (n + 8) (n + 5) 2 2 2 (23 n + 251 n + 654) b(n + 6) 4 (3 n + 36 n + 103) b(n + 7) + -------------------------------- - ------------------------------ (n + 8) (n + 5) (n + 8) (n + 5) + b(n + 8) = 0 Subject to the initial conditions b(1) = 0, b(2) = 0, b(3) = 1, b(4) = 7, b(5) = 40, b(6) = 206, b(7) = 1001, b(8) = 4685 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.678 1/2 - ----- 1/2 n The probability of Bob winning the bet, as n grows larger is approximately 1.29 1/2 - ---- 1/2 n You can see that indeed Alice has a better chance, but not significantly so. ----------------------------------------- This took, 35.035, seconds to generate The best bet against, [1, 1, 1], is a member of, {[1, 1, 2], [1, 1, 3], [1, 1, 4], [2, 1, 1], [3, 1, 1], [4, 1, 1]}, 0.704 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], [1, 2, 3], [1, 2, 4], [1, 3, 2], [1, 3, 3], [1, 3, 4], [1, 4, 2], [1, 4, 3], [1, 4, 4], [2, 2, 1], [2, 3, 1], [2, 4, 1], [3, 2, 1], [3, 3, 1], [3, 4, 1], [4, 2, 1], [4, 3, 1], [4, 4, 1] 0.626 }, and then your edge is approximately, ----- 1/2 n The next best bet is a member of, {[2, 1, 3], [2, 1, 4], [2, 2, 3], [2, 2, 4], [2, 3, 3], [2, 3, 4], [2, 4, 3], [2, 4, 4], [3, 1, 2], [3, 1, 4], [3, 2, 2], [3, 2, 4], [3, 3, 2], [3, 3, 4], [3, 4, 2], [3, 4, 4], [4, 1, 2], [4, 1, 3], [4, 2, 2], [4, 2, 3], [4, 3, 2], [4, 3, 3], [4, 4, 2], [4, 4, 3]}, 0.612 and then your edge is approximately, ----- 1/2 n The next best bet is a member of, {[1, 2, 1], [1, 3, 1], [1, 4, 1]}, 0.503 and then your edge is approximately, ----- 1/2 n The next best bet is a member of, {[2, 1, 2], [2, 3, 2], [2, 4, 2], [3, 1, 3], [3, 2, 3], [3, 4, 3], [4, 1, 4], [4, 2, 4], [4, 3, 4]}, 0.478 and then your edge is approximately, ----- 1/2 n The next best bet is a member of, {[2, 2, 2], [3, 3, 3], [4, 4, 4]}, and then your edge is exactly 0 ----------------------- This ends this chapter that took, 186.079, seconds to generate.