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, 1], Versus the number of occurences of all, 4, 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, {[2, 2, 2, 2]}, than in, {[1, 1, 1, 1]}, and Bob, bets vice versa, who is more likely to win? Answer: They are equally likely to win ----------------------------------------------------------------------------\ ----------------------- Question Mumber, 2, : If Alice bets that there are more occurrences of consec\ utive substrings in, {[1, 1, 1, 2]}, than in, {[1, 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, 3, 4}, with more occurences of, {[1, 1, 1, 2]}, then , {[1, 1, 1, 1]} a(n) satisfies the following linear recurrence equation with polynomial coef\ ficients of order, 29 3 2 (389131 n + 18891844 n + 305568827 n + 1646904410) a(n + 17) a(n + 29) - -------------------------------------------------------------- (n + 25) (n + 29) (n + 26) 3 2 (191719 n + 10289115 n + 183452186 n + 1086797256) a(n + 18) - -------------------------------------------------------------- (n + 25) (n + 29) (n + 26) 3 2 5 (2316 n + 124511 n + 2143173 n + 11711812) a(n + 19) - -------------------------------------------------------- (n + 25) (n + 29) (n + 26) 3 2 (71192 n + 3939743 n + 72453767 n + 443064788) a(n + 20) + ---------------------------------------------------------- (n + 25) (n + 29) (n + 26) 3 2 (18481 n + 1232416 n + 27102361 n + 196809478) a(n + 21) + ---------------------------------------------------------- (n + 25) (n + 29) (n + 26) 3 2 (18973 n + 1199721 n + 25345818 n + 179031752) a(n + 22) - 1/2 ---------------------------------------------------------- (n + 25) (n + 29) (n + 26) 3 2 (8329 n + 559218 n + 12469389 n + 92314920) a(n + 23) - 1/2 ------------------------------------------------------- (n + 25) (n + 29) (n + 26) 3 2 (1704 n + 119503 n + 2784447 n + 21558704) a(n + 24) - ------------------------------------------------------ (n + 25) (n + 29) (n + 26) 3 2 (3320 n + 236715 n + 5616317 n + 44346178) a(n + 25) + ------------------------------------------------------ (n + 25) (n + 29) (n + 26) 3 2 (1362 n + 99927 n + 2440087 n + 19833386) a(n + 26) - ----------------------------------------------------- (n + 25) (n + 29) (n + 26) 3 2 (527 n + 39813 n + 1000988 n + 8376852) a(n + 27) + 1/2 --------------------------------------------------- (n + 25) (n + 29) (n + 26) 3 2 72 (38381 n + 570597 n + 2801696 n + 4542716) a(n + 4) + -------------------------------------------------------- (n + 25) (n + 29) (n + 26) 3 2 6 (411215 n + 5642061 n + 21820168 n + 16765956) a(n + 5) + ----------------------------------------------------------- (n + 25) (n + 29) (n + 26) 3 2 (333239 n - 9943161 n - 197709254 n - 780675216) a(n + 6) + 3/2 ----------------------------------------------------------- (n + 25) (n + 29) (n + 26) 3 2 (1815245 n + 67623438 n + 740919005 n + 2524536104) a(n + 7) - 3/2 -------------------------------------------------------------- (n + 25) (n + 29) (n + 26) 3 2 (5557351 n + 181010280 n + 1905267413 n + 6525323016) a(n + 8) - ---------------------------------------------------------------- (n + 25) (n + 29) (n + 26) 3 2 (6584801 n + 208326191 n + 2179939582 n + 7537002400) a(n + 9) - ---------------------------------------------------------------- (n + 25) (n + 29) (n + 26) 3 2 (5229375 n + 159576510 n + 1602651895 n + 5270491646) a(n + 10) - ----------------------------------------------------------------- (n + 25) (n + 29) (n + 26) 3 2 (5215695 n + 140819415 n + 1122888458 n + 2210530860) a(n + 11) - 1/2 ----------------------------------------------------------------- (n + 25) (n + 29) (n + 26) 3 2 (305091 n + 47171960 n + 1063513417 n + 6502270892) a(n + 12) + 1/2 --------------------------------------------------------------- (n + 25) (n + 29) (n + 26) 3 2 2 (833476 n + 36825861 n + 540896417 n + 2634813372) a(n + 13) + ---------------------------------------------------------------- (n + 25) (n + 29) (n + 26) 3 2 2 (909354 n + 38160621 n + 533092031 n + 2475297622) a(n + 14) + ---------------------------------------------------------------- (n + 25) (n + 29) (n + 26) 3 2 2 (428538 n + 18257513 n + 256753697 n + 1189404184) a(n + 15) + ---------------------------------------------------------------- (n + 25) (n + 29) (n + 26) 3 2 (20121 n + 1423949 n + 33331592 n + 250519896) a(n + 16) - ---------------------------------------------------------- (n + 25) (n + 29) (n + 26) 2 (51 n + 2691 n + 35348) a(n + 28) - 1/2 ---------------------------------- (n + 29) (n + 26) 55296 (n + 4) (n + 2) (n + 1) a(n) + ---------------------------------- (n + 25) (n + 29) (n + 26) 2 13824 (n + 2) (23 n + 173 n + 314) a(n + 1) + -------------------------------------------- (n + 25) (n + 29) (n + 26) 2 3456 (n + 3) (281 n + 2424 n + 5220) a(n + 2) + ---------------------------------------------- (n + 25) (n + 29) (n + 26) 2 1728 (n + 4) (1135 n + 10840 n + 25914) a(n + 3) + ------------------------------------------------- = 0 (n + 25) (n + 29) (n + 26) Subject to the initial conditions a(1) = 0, a(2) = 0, a(3) = 0, a(4) = 1, a(5) = 7, a(6) = 40, a(7) = 208, a(8) = 1022, a(9) = 4843, a(10) = 22369, a(11) = 101374, a(12) = 452731, a(13) = 1998448, a(14) = 8738269, a(15) = 37908685, a(16) = 163368693, a(17) = 700059468, a(18) = 2985183374, a(19) = 12674986729, a(20) = 53615020704, a(21) = 226033319455, a(22) = 950080759672, a(23) = 3982742093871, a(24) = 16655204693461, a(25) = 69496177350517, a(26) = 289400482923457, a(27) = 1202925104139898, a(28) = 4991644216619993, a(29) = 20680999341447212 Lemma , 2.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, 1]}, then , {[1, 1, 1, 2]} b(n) satisfies the following linear recurrence equation with polynomial coef\ ficients of order, 13 2 192 (n + 4) (n + 1) b(n) 16 (17 n + 97 n + 132) b(n + 1) - ------------------------ - -------------------------------- (n + 13) (n + 9) (n + 13) (n + 9) 2 4 (15 n + 41) (5 n + 12) b(n + 2) (27 n - 1337 n - 5948) b(n + 3) - --------------------------------- - -------------------------------- (n + 13) (n + 9) (n + 13) (n + 9) 2 (21 n + 2800 n + 14444) b(n + 4) + 1/2 --------------------------------- (n + 13) (n + 9) 2 (102 n + 1765 n + 7223) b(n + 5) + 3/2 --------------------------------- (n + 13) (n + 9) 2 (246 n + 3031 n + 9726) b(n + 6) + 1/2 --------------------------------- (n + 13) (n + 9) 2 (400 n + 4665 n + 11659) b(n + 7) + 1/2 ---------------------------------- (n + 13) (n + 9) 2 (40 n + 735 n + 3964) b(n + 8) - 1/2 ------------------------------- (n + 13) (n + 9) 2 (108 n + 1831 n + 7711) b(n + 9) - 1/2 --------------------------------- (n + 13) (n + 9) 2 (114 n + 2039 n + 8586) b(n + 10) - 1/2 ---------------------------------- (n + 13) (n + 9) 2 (102 n + 1993 n + 9397) b(n + 11) + 1/2 ---------------------------------- (n + 13) (n + 9) 2 (25 n + 521 n + 2628) b(n + 12) - 1/2 -------------------------------- + b(n + 13) = 0 (n + 13) (n + 9) Subject to the initial conditions b(1) = 0, b(2) = 0, b(3) = 0, b(4) = 1, b(5) = 6, b(6) = 33, b(7) = 168, b(8) = 815, b(9) = 3828, b(10) = 17568, b(11) = 79236, b(12) = 352558, b(13) = 1551730 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 1.5 1/2 - ---- 1/2 n The probability of Bob winning the bet, as n grows larger is approximately 3.0 1/2 - ---- 1/2 n You can see that indeed Alice has a better chance, but not significantly so. ----------------------------------------- This took, 47.129, seconds to generate ----------------------------------------------------------------------------\ ----------------------- Question Mumber, 3, : If Alice bets that there are more occurrences of consec\ utive substrings in, {[1, 1, 2, 1]}, than in, {[1, 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, 1]}, then , {[1, 1, 1, 1]} a(n) satisfies the following linear recurrence equation with polynomial coef\ ficients of order, 23 58752 (n + 1) (n + 2) (n + 3) a(n) ---------------------------------- (n + 20) (n + 19) (n + 23) 12 (n + 3) (n + 2) (24254 n + 119689) a(n + 1) + ---------------------------------------------- (n + 20) (n + 19) (n + 23) 2 5 (n + 3) (135844 n + 1623121 n + 4520926) a(n + 2) - ---------------------------------------------------- (n + 20) (n + 19) (n + 23) 3 2 (1761645 n + 26279054 n + 131041461 n + 215884392) a(n + 3) + 1/2 ------------------------------------------------------------- (n + 20) (n + 19) (n + 23) 3 2 (15698165 n + 309780453 n + 2020207216 n + 4316092848) a(n + 4) - 1/6 ----------------------------------------------------------------- (n + 20) (n + 19) (n + 23) 3 2 2 (860997 n + 22569499 n + 192946788 n + 531944936) a(n + 5) - -------------------------------------------------------------- (n + 20) (n + 19) (n + 23) 3 2 (2231041 n + 136697589 n + 1842222662 n + 6937424832) a(n + 6) + 1/6 ---------------------------------------------------------------- (n + 20) (n + 19) (n + 23) 3 2 (16829209 n + 389572824 n + 2839175279 n + 6355070448) a(n + 7) - 1/6 ----------------------------------------------------------------- (n + 20) (n + 19) (n + 23) 3 2 (6295195 n + 178752714 n + 1595502743 n + 4486421412) a(n + 8) + 1/3 ---------------------------------------------------------------- (n + 20) (n + 19) (n + 23) 3 2 (1461410 n + 43636250 n + 428564707 n + 1375129191) a(n + 9) + -------------------------------------------------------------- (n + 20) (n + 19) (n + 23) 3 2 (1257495 n + 38199649 n + 385256555 n + 1292778510) a(n + 10) - --------------------------------------------------------------- (n + 20) (n + 19) (n + 23) 3 2 (1058277 n + 25462566 n + 188030837 n + 415083696) a(n + 11) + 1/2 -------------------------------------------------------------- (n + 20) (n + 19) (n + 23) 3 2 (777868 n + 25425495 n + 237619109 n + 531088836) a(n + 12) + 1/6 ------------------------------------------------------------- (n + 20) (n + 19) (n + 23) 3 2 (2793209 n + 86164911 n + 827830960 n + 2359586622) a(n + 13) - 1/6 --------------------------------------------------------------- (n + 20) (n + 19) (n + 23) 3 2 (416919 n + 13618045 n + 141565016 n + 460160620) a(n + 14) + 1/2 ------------------------------------------------------------- (n + 20) (n + 19) (n + 23) 3 2 (18883 n + 649331 n + 8391684 n + 43390838) a(n + 15) - 1/2 ------------------------------------------------------- (n + 20) (n + 19) (n + 23) 3 2 (11071 n + 220041 n - 1203832 n - 29932328) a(n + 16) - 1/2 ------------------------------------------------------- (n + 20) (n + 19) (n + 23) 3 2 (27280 n + 1161519 n + 16302977 n + 75683802) a(n + 17) + 1/6 --------------------------------------------------------- (n + 20) (n + 19) (n + 23) 3 2 (53443 n + 2758500 n + 47409161 n + 271396890) a(n + 18) - 1/6 ---------------------------------------------------------- (n + 20) (n + 19) (n + 23) 3 2 (34567 n + 1854942 n + 33115925 n + 196736166) a(n + 19) + 1/6 ---------------------------------------------------------- (n + 20) (n + 19) (n + 23) 3 2 (10765 n + 598659 n + 11072930 n + 68136288) a(n + 20) - 1/6 -------------------------------------------------------- (n + 20) (n + 19) (n + 23) 3 2 (1819 n + 104910 n + 2011769 n + 12830430) a(n + 21) + 1/6 ------------------------------------------------------ (n + 20) (n + 19) (n + 23) 2 (27 n + 1102 n + 11168) a(n + 22) - ---------------------------------- + a(n + 23) = 0 (n + 23) (n + 20) Subject to the initial conditions a(1) = 0, a(2) = 0, a(3) = 0, a(4) = 1, a(5) = 8, a(6) = 47, a(7) = 246, a(8) = 1215, a(9) = 5779, a(10) = 26757, a(11) = 121452, a(12) = 542968, a(13) = 2398420, a(14) = 10491540, a(15) = 45524540, a(16) = 196200768, a(17) = 840695157, a(18) = 3584295890, a(19) = 15215112326, a(20) = 64339953451, a(21) = 271150247982, a(22) = 1139257391477, a(23) = 4773653579355 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, 1]}, then , {[1, 1, 2, 1]} b(n) satisfies the following linear recurrence equation with polynomial coef\ ficients of order, 17 157056 (n + 1) (n + 2) (n + 3) b(n) - ----------------------------------- (n + 13) (n + 17) (n + 16) 4 (n + 3) (n + 2) (29894 n + 162149) b(n + 1) + --------------------------------------------- (n + 13) (n + 17) (n + 16) 2 (n + 3) (398324 n + 4138485 n + 10621558) b(n + 2) + --------------------------------------------------- (n + 13) (n + 17) (n + 16) 3 2 (400611 n + 7963690 n + 48567283 n + 92637576) b(n + 3) + 1/2 --------------------------------------------------------- (n + 13) (n + 17) (n + 16) 3 2 (18919 n + 320893 n + 3191962 n + 10530952) b(n + 4) + 1/2 ------------------------------------------------------ (n + 13) (n + 17) (n + 16) 3 2 (210651 n + 6681442 n + 60722455 n + 169101544) b(n + 5) - 1/2 ---------------------------------------------------------- (n + 13) (n + 17) (n + 16) 3 2 (19474 n + 126005 n + 174138 n + 1771452) b(n + 6) - ---------------------------------------------------- (n + 13) (n + 17) (n + 16) 3 2 (11515 n + 635948 n + 8338773 n + 31735012) b(n + 7) + 3/2 ------------------------------------------------------ (n + 13) (n + 17) (n + 16) 3 2 (67708 n + 2170927 n + 21617977 n + 68209584) b(n + 8) - 1/2 -------------------------------------------------------- (n + 13) (n + 17) (n + 16) 3 2 (30096 n + 686733 n + 4660879 n + 8182290) b(n + 9) + 1/2 ----------------------------------------------------- (n + 13) (n + 17) (n + 16) 3 2 (19074 n + 614044 n + 6452711 n + 22104406) b(n + 10) + ------------------------------------------------------- (n + 13) (n + 17) (n + 16) 3 2 (29788 n + 933793 n + 9617345 n + 32417870) b(n + 11) - 1/2 ------------------------------------------------------- (n + 13) (n + 17) (n + 16) 3 2 (1539 n + 24607 n - 47420 n - 1428600) b(n + 12) + 1/2 -------------------------------------------------- (n + 13) (n + 17) (n + 16) 3 2 (5166 n + 199563 n + 2545955 n + 10710410) b(n + 13) + 1/2 ------------------------------------------------------ (n + 13) (n + 17) (n + 16) 3 2 (2333 n + 92930 n + 1225983 n + 5349602) b(n + 14) - 1/2 ---------------------------------------------------- (n + 13) (n + 17) (n + 16) 3 2 (236 n + 9859 n + 136495 n + 625602) b(n + 15) + ------------------------------------------------ (n + 13) (n + 17) (n + 16) 2 (24 n + 669 n + 4607) b(n + 16) - -------------------------------- + b(n + 17) = 0 (n + 17) (n + 13) Subject to the initial conditions b(1) = 0, b(2) = 0, b(3) = 0, b(4) = 1, b(5) = 7, b(6) = 39, b(7) = 200, b(8) = 977, b(9) = 4611, b(10) = 21226, b(11) = 95938, b(12) = 427528, b(13) = 1883775, b(14) = 8223966, b(15) = 35628439, b(16) = 153353482, b(17) = 656413906 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 1.4 1/2 - ---- 1/2 n The probability of Bob winning the bet, as n grows larger is approximately 2.7 1/2 - ---- 1/2 n You can see that indeed Alice has a better chance, but not significantly so. ----------------------------------------- This took, 42.076, seconds to generate ----------------------------------------------------------------------------\ ----------------------- Question Mumber, 4, : If Alice bets that there are more occurrences of consec\ utive substrings in, {[1, 2, 1, 2]}, than in, {[1, 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, {[1, 2, 1, 2]}, then , {[1, 1, 1, 1]} a(n) satisfies the following linear recurrence equation with polynomial coef\ ficients of order, 38 (n + 1) (n + 2) (n + 3) a(n) -155648/3 ---------------------------- (n + 35) (n + 34) (n + 38) (275 n + 1052) (n + 3) (n + 2) a(n + 1) - 4096/3 --------------------------------------- (n + 35) (n + 34) (n + 38) 2 (23 n + 1632 n + 28889) a(n + 37) - ---------------------------------- - 2/3 (n + 38) (n + 35) 3 2 (1207639159 n + 51940995237 n + 742708415840 n + 3532804584360) a(n + 14) /((n + 35) (n + 34) (n + 38)) - 3 2 (456923115 n + 20714812960 n + 311279820477 n + 1551076707640) a(n + 15)/ ((n + 35) (n + 34) (n + 38)) - 1/3 3 2 (545566193 n + 25231044852 n + 383159989051 n + 1907236313352) a(n + 16)/ ((n + 35) (n + 34) (n + 38)) 3 2 2 (12864867 n + 847928327 n + 18329578457 n + 129639132193) a(n + 17) + ----------------------------------------------------------------------- (n + 35) (n + 34) (n + 38) 3 2 + 1/3 (268336613 n + 15675423237 n + 305461334062 n + 1983592488036) a(n + 18)/((n + 35) (n + 34) (n + 38)) + 1/2 3 2 (195185973 n + 11521535462 n + 226860670209 n + 1489493127204) a(n + 19)/ ((n + 35) (n + 34) (n + 38)) + 1/3 3 2 (149797438 n + 9419253591 n + 196807240211 n + 1366250332632) a(n + 20) ------------------------------------------------------------------------- (n + 35) (n + 34) (n + 38) + 3 2 (39994989 n + 2568559600 n + 54809049373 n + 388489008978) a(n + 21) 1/2 ---------------------------------------------------------------------- (n + 35) (n + 34) (n + 38) - 3 2 (21459923 n + 1241138577 n + 23854223260 n + 152947280676) a(n + 22) 1/6 ---------------------------------------------------------------------- (n + 35) (n + 34) (n + 38) - 3 2 (31939571 n + 2253514248 n + 52984958677 n + 415177832160) a(n + 23) 1/6 ---------------------------------------------------------------------- (n + 35) (n + 34) (n + 38) - 3 2 (12418145 n + 880482624 n + 20794570483 n + 163596076512) a(n + 24) 1/3 --------------------------------------------------------------------- (n + 35) (n + 34) (n + 38) 3 2 (2343068 n + 193013667 n + 5222571109 n + 46524232002) a(n + 25) - 1/3 ------------------------------------------------------------------ (n + 35) (n + 34) (n + 38) 3 2 (2099965 n + 164609685 n + 4310196122 n + 37701319512) a(n + 26) + 1/6 ------------------------------------------------------------------ (n + 35) (n + 34) (n + 38) 3 2 2 (134240 n + 10189275 n + 257021959 n + 2154649660) a(n + 27) + ---------------------------------------------------------------- (n + 35) (n + 34) (n + 38) 3 2 (372613 n + 31925207 n + 909103414 n + 8604922176) a(n + 28) + 1/2 -------------------------------------------------------------- (n + 35) (n + 34) (n + 38) 3 2 (160175 n + 13731258 n + 392633401 n + 3744837902) a(n + 29) - 1/2 -------------------------------------------------------------- (n + 35) (n + 34) (n + 38) 3 2 (104249 n + 9801123 n + 305864488 n + 3168768036) a(n + 30) + 1/6 ------------------------------------------------------------- (n + 35) (n + 34) (n + 38) 3 2 (177901 n + 16399260 n + 503270867 n + 5141569524) a(n + 31) - 1/6 -------------------------------------------------------------- (n + 35) (n + 34) (n + 38) 3 2 (14657 n + 1371085 n + 42733976 n + 443783144) a(n + 32) + ---------------------------------------------------------- (n + 35) (n + 34) (n + 38) 3 2 (14116 n + 1368645 n + 44221139 n + 476126406) a(n + 33) - 1/3 ---------------------------------------------------------- (n + 35) (n + 34) (n + 38) 3 2 (4729 n + 471043 n + 15630192 n + 172775988) a(n + 34) + 1/2 -------------------------------------------------------- (n + 35) (n + 34) (n + 38) 3 2 (1921 n + 194466 n + 6557749 n + 73667216) a(n + 35) - 1/2 ------------------------------------------------------ (n + 35) (n + 34) (n + 38) 3 2 (421 n + 43367 n + 1487946 n + 17005352) a(n + 36) + 1/2 ---------------------------------------------------- (n + 35) (n + 34) (n + 38) 3 2 256 (30335 n + 431599 n + 2048910 n + 3232200) a(n + 3) - --------------------------------------------------------- (n + 35) (n + 34) (n + 38) 3 2 (2336105 n + 39606204 n + 224933959 n + 426637260) a(n + 4) - 32/3 ------------------------------------------------------------- (n + 35) (n + 34) (n + 38) 3 2 64 (1013793 n + 19919008 n + 131178929 n + 289065774) a(n + 5) - ---------------------------------------------------------------- (n + 35) (n + 34) (n + 38) 3 2 16 (9270851 n + 206986954 n + 1548931535 n + 3881410420) a(n + 6) - ------------------------------------------------------------------- - (n + 35) (n + 34) (n + 38) 3 2 (216482479 n + 5406496536 n + 45223975745 n + 126662730888) a(n + 7) 4/3 ---------------------------------------------------------------------- (n + 35) (n + 34) (n + 38) - 3 2 (375458533 n + 10363174764 n + 95731285463 n + 295989198576) a(n + 8) 4/3 ----------------------------------------------------------------------- (n + 35) (n + 34) (n + 38) - 3 2 (281880661 n + 8518116531 n + 86069528699 n + 290888394993) a(n + 9) 8/3 ---------------------------------------------------------------------- (n + 35) (n + 34) (n + 38) - 4/3 3 2 (758159447 n + 24879669945 n + 272751755284 n + 999401665224) a(n + 10) ------------------------------------------------------------------------- (n + 35) (n + 34) (n + 38) 3 2 - 2/3 (1763802469 n + 62483210454 n + 738709793297 n + 2916322460340) a(n + 11)/((n + 35) (n + 34) (n + 38)) - 4/3 3 2 (914040086 n + 34726960179 n + 439870223899 n + 1858710150120) a(n + 12)/ ((n + 35) (n + 34) (n + 38)) - 2/3 3 2 (1596920917 n + 64803952596 n + 875617849241 n + 3941869731138) a(n + 13) /((n + 35) (n + 34) (n + 38)) + a(n + 38) 2 1024 (n + 3) (2002 n + 17037 n + 36769) a(n + 2) - ------------------------------------------------- = 0 (n + 35) (n + 34) (n + 38) Subject to the initial conditions a(1) = 0, a(2) = 0, a(3) = 0, a(4) = 1, a(5) = 8, a(6) = 47, a(7) = 247, a(8) = 1223, a(9) = 5824, a(10) = 26986, a(11) = 122565, a(12) = 548199, a(13) = 2422368, a(14) = 10599120, a(15) = 46000902, a(16) = 198285938, a(17) = 849737016, a(18) = 3623198511, a(19) = 15381390434, a(20) = 65046662045, a(21) = 274139241172, a(22) = 1151845379309, a(23) = 4826468228345, a(24) = 20174034636106, a(25) = 84136372208420, a(26) = 350178066098577, a(27) = 1454734272461759, a(28) = 6033012220739324, a(29) = 24980378173418332, a(30) = 103283263096113234, a(31) = 426455046522130476, a(32) = 1758613119058901653, a(33) = 7243663773396599330, a(34) = 29803736687876630697, a(35) = 122500528108096254655, a(36) = 503022682454212143075, a(37) = 2063690836534614466598, a(38) = 8459254272797382109902 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, 1]}, then , {[1, 2, 1, 2]} b(n) satisfies the following linear recurrence equation with polynomial coef\ ficients of order, 35 6144 (n + 1) (n + 2) (n + 3) b(n) 3072 (49 n + 228) (n + 3) (n + 2) b(n + 1) --------------------------------- + ------------------------------------------ (n + 35) (n + 33) (n + 31) (n + 35) (n + 33) (n + 31) 3 2 64 (52333 n + 782493 n + 3851210 n + 6233976) b(n + 3) + -------------------------------------------------------- (n + 35) (n + 33) (n + 31) 3 2 8 (1200473 n + 20848956 n + 120336919 n + 230518668) b(n + 4) + --------------------------------------------------------------- (n + 35) (n + 33) (n + 31) 3 2 16 (1377583 n + 27113904 n + 177910871 n + 388958682) b(n + 5) + ---------------------------------------------------------------- (n + 35) (n + 33) (n + 31) 3 2 12 (3400375 n + 74165746 n + 539998659 n + 1312430612) b(n + 6) + ----------------------------------------------------------------- (n + 35) (n + 33) (n + 31) 3 2 (62015911 n + 1475782896 n + 11694833153 n + 30872826840) b(n + 7) + -------------------------------------------------------------------- (n + 35) (n + 33) (n + 31) 3 2 2 (38813977 n + 993835164 n + 8446496675 n + 23830073568) b(n + 8) + -------------------------------------------------------------------- (n + 35) (n + 33) (n + 31) 3 2 6 (12869517 n + 348555009 n + 3104280602 n + 9070563618) b(n + 9) + ------------------------------------------------------------------- (n + 35) (n + 33) (n + 31) 3 2 3 (19780675 n + 556211615 n + 5069928818 n + 14844041292) b(n + 10) + --------------------------------------------------------------------- + (n + 35) (n + 33) (n + 31) 3 2 (54450371 n + 1445425164 n + 11268787405 n + 21603093132) b(n + 11) 1/2 --------------------------------------------------------------------- (n + 35) (n + 33) (n + 31) 3 2 (4138213 n + 628863864 n + 13759563119 n + 80786117460) b(n + 12) - 1/4 ------------------------------------------------------------------- (n + 35) (n + 33) (n + 31) - 3 2 (66337189 n + 2649584592 n + 34987236935 n + 151778109348) b(n + 13) 1/4 ---------------------------------------------------------------------- (n + 35) (n + 33) (n + 31) - 3 2 (53620225 n + 1845211296 n + 18843855077 n + 48119717898) b(n + 14) 1/4 --------------------------------------------------------------------- (n + 35) (n + 33) (n + 31) + 3 2 (3199477 n + 1196416566 n + 35999995889 n + 282836105124) b(n + 15) 1/8 --------------------------------------------------------------------- (n + 35) (n + 33) (n + 31) + 3 2 (39058276 n + 2378856129 n + 47170113623 n + 306092575908) b(n + 16) 1/4 ---------------------------------------------------------------------- (n + 35) (n + 33) (n + 31) + 1/8 3 2 (127818085 n + 6992442810 n + 127650183203 n + 777197583222) b(n + 17) ------------------------------------------------------------------------ + (n + 35) (n + 33) (n + 31) 3 2 (59842681 n + 3556930797 n + 70127157182 n + 458659531896) b(n + 18) 1/8 ---------------------------------------------------------------------- (n + 35) (n + 33) (n + 31) + 3 2 (47945483 n + 2694117150 n + 50285367427 n + 311518651476) b(n + 19) 1/8 ---------------------------------------------------------------------- (n + 35) (n + 33) (n + 31) 3 2 (3742249 n + 208300423 n + 3861375990 n + 23874323952) b(n + 20) - 3/4 ------------------------------------------------------------------ (n + 35) (n + 33) (n + 31) 3 2 (1548201 n + 68142470 n + 808374973 n + 1264968776) b(n + 21) + 3/8 --------------------------------------------------------------- (n + 35) (n + 33) (n + 31) 3 2 (6519917 n + 411546603 n + 8642281588 n + 60377452228) b(n + 22) - 3/8 ------------------------------------------------------------------ (n + 35) (n + 33) (n + 31) 3 2 (8177915 n + 514196064 n + 10705870747 n + 73761136626) b(n + 23) + 1/8 ------------------------------------------------------------------- (n + 35) (n + 33) (n + 31) 3 2 (869815 n + 58259333 n + 1294022563 n + 9524722620) b(n + 24) - 3/4 --------------------------------------------------------------- (n + 35) (n + 33) (n + 31) 3 2 (4540723 n + 323108838 n + 7644011777 n + 60113743590) b(n + 25) + 1/8 ------------------------------------------------------------------ (n + 35) (n + 33) (n + 31) 3 2 (686797 n + 50396041 n + 1228822310 n + 9953679288) b(n + 26) - 3/8 --------------------------------------------------------------- (n + 35) (n + 33) (n + 31) 3 2 (176941 n + 13663188 n + 350765896 n + 2992936355) b(n + 27) + 3/4 -------------------------------------------------------------- (n + 35) (n + 33) (n + 31) 3 2 (304385 n + 24537360 n + 658016389 n + 5869133460) b(n + 28) - 1/4 -------------------------------------------------------------- (n + 35) (n + 33) (n + 31) 3 2 (124340 n + 10367301 n + 287665303 n + 2655981318) b(n + 29) + 1/4 -------------------------------------------------------------- (n + 35) (n + 33) (n + 31) 3 2 (15360 n + 1332083 n + 38460332 n + 369658968) b(n + 30) - 3/4 ---------------------------------------------------------- (n + 35) (n + 33) (n + 31) 3 2 (11997 n + 1078680 n + 32295683 n + 321963184) b(n + 31) + 3/8 ---------------------------------------------------------- (n + 35) (n + 33) (n + 31) 3 2 (1797 n + 166088 n + 5112104 n + 52398680) b(n + 32) - 3/4 ------------------------------------------------------ (n + 35) (n + 33) (n + 31) 3 2 (1975 n + 186972 n + 5894585 n + 61885860) b(n + 33) + 1/8 ------------------------------------------------------ (n + 35) (n + 33) (n + 31) 3 2 (65 n + 6295 n + 203002 n + 2179840) b(n + 34) - 3/8 ------------------------------------------------ + b(n + 35) (n + 35) (n + 33) (n + 31) 2 768 (n + 3) (1090 n + 10157 n + 23153) b(n + 2) + ------------------------------------------------ = 0 (n + 35) (n + 33) (n + 31) Subject to the initial conditions b(1) = 0, b(2) = 0, b(3) = 0, b(4) = 1, b(5) = 7, b(6) = 40, b(7) = 207, b(8) = 1016, b(9) = 4809, b(10) = 22188, b(11) = 100460, b(12) = 448270, b(13) = 1977191, b(14) = 8638858, b(15) = 37450662, b(16) = 161283889, b(17) = 690665632, b(18) = 2943218459, b(19) = 12488899655, b(20) = 52795146583, b(21) = 222441493537, b(22) = 934424171941, b(23) = 3914802435835, b(24) = 16361582703201, b(25) = 68231852755586, b(26) = 283974530923255, b(27) = 1179710342232741, b(28) = 4892599496190372, b(29) = 20259524124253918, b(30) = 83771199787111531, b(31) = 345924495124053838, b(32) = 1426689411756361945, b(33) = 5877267885541324345, b(34) = 24185345690705352344, b(35) = 99423630497612265441 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 1.4 1/2 - ---- 1/2 n The probability of Bob winning the bet, as n grows larger is approximately 2.4 1/2 - ---- 1/2 n You can see that indeed Alice has a better chance, but not significantly so. ----------------------------------------- This took, 97.550, seconds to generate ----------------------------------------------------------------------------\ ----------------------- Question Mumber, 5, : If Alice bets that there are more occurrences of consec\ utive substrings in, {[2, 3, 2, 3]}, than in, {[1, 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, {[2, 3, 2, 3]}, then , {[1, 1, 1, 1]} a(n) satisfies the following linear recurrence equation with polynomial coef\ ficients of order, 38 3 2 -2/3 (396744013 n + 18180037149 n + 276673053275 n + 1399465105149) a(n + 15) /((n + 35) (n + 34) (n + 38)) - 1/3 3 2 (413185355 n + 20106199218 n + 324562930882 n + 1739505771624) a(n + 16)/ ((n + 35) (n + 34) (n + 38)) 3 2 (38841101 n + 1985674713 n + 33516077818 n + 187053912634) a(n + 17) - ---------------------------------------------------------------------- (n + 35) (n + 34) (n + 38) 3 2 (24269449 n + 1397252064 n + 26891512296 n + 172647571488) a(n + 18) + ---------------------------------------------------------------------- (n + 35) (n + 34) (n + 38) + 1/3 3 2 (110987977 n + 6587805981 n + 130357797464 n + 859432414830) a(n + 19) ------------------------------------------------------------------------ + (n + 35) (n + 34) (n + 38) 3 2 1/6 (207298469 n + 12822228801 n + 263996145658 n + 1808794502616) a(n + 20)/((n + 35) (n + 34) (n + 38)) + 3 2 (37641802 n + 2508102195 n + 55459524605 n + 407008887768) a(n + 21) 1/3 ---------------------------------------------------------------------- (n + 35) (n + 34) (n + 38) + 3 2 (15244666 n + 1026265323 n + 22940838395 n + 170244208374) a(n + 22) 1/3 ---------------------------------------------------------------------- (n + 35) (n + 34) (n + 38) - 3 2 (23025739 n + 1508453373 n + 32907109676 n + 239134528716) a(n + 23) 1/6 ---------------------------------------------------------------------- (n + 35) (n + 34) (n + 38) 3 2 (3943237 n + 304684377 n + 7787762855 n + 65901988032) a(n + 24) - 1/3 ------------------------------------------------------------------ (n + 35) (n + 34) (n + 38) 3 2 (4871705 n + 356299305 n + 8682030118 n + 70494821058) a(n + 25) - 1/3 ------------------------------------------------------------------ (n + 35) (n + 34) (n + 38) 3 2 (286530 n + 18925398 n + 408819731 n + 2875877614) a(n + 26) + -------------------------------------------------------------- (n + 35) (n + 34) (n + 38) 3 2 (53497 n + 5262415 n + 163429900 n + 1627221456) a(n + 27) + 1/2 ------------------------------------------------------------ (n + 35) (n + 34) (n + 38) 3 2 (1143047 n + 94111695 n + 2585795116 n + 23715083568) a(n + 28) + 1/6 ----------------------------------------------------------------- (n + 35) (n + 34) (n + 38) 3 2 (205615 n + 17452239 n + 496879016 n + 4747616820) a(n + 29) - 1/6 -------------------------------------------------------------- (n + 35) (n + 34) (n + 38) 3 2 (26861 n + 2643741 n + 86119022 n + 929363928) a(n + 30) + 1/2 ---------------------------------------------------------- (n + 35) (n + 34) (n + 38) 3 2 (76558 n + 7166793 n + 223541249 n + 2323247928) a(n + 31) - 1/3 ------------------------------------------------------------ (n + 35) (n + 34) (n + 38) 3 2 (34069 n + 3254469 n + 103636706 n + 1100145000) a(n + 32) + 1/3 ------------------------------------------------------------ (n + 35) (n + 34) (n + 38) 3 2 (14848 n + 1459773 n + 47813099 n + 521725770) a(n + 33) - 1/3 ---------------------------------------------------------- (n + 35) (n + 34) (n + 38) 3 2 (5989 n + 596341 n + 19780598 n + 218571280) a(n + 34) + 1/2 -------------------------------------------------------- (n + 35) (n + 34) (n + 38) 3 2 (1143 n + 115528 n + 3889745 n + 43627740) a(n + 35) - ------------------------------------------------------ (n + 35) (n + 34) (n + 38) 3 2 (93 n + 9571 n + 328078 n + 3745960) a(n + 36) + 5/2 ------------------------------------------------ (n + 35) (n + 34) (n + 38) 5488 (2 n + 1) (n + 2) (n + 1) a(n) + ----------------------------------- (n + 35) (n + 34) (n + 38) 2 2 (12 n + 851 n + 15055) a(n + 37) - ----------------------------------- (n + 38) (n + 35) 3 2 (49135 n + 692526 n + 2676614 n + 3115668) a(n + 2) + 14/3 ----------------------------------------------------- (n + 35) (n + 34) (n + 38) 3 2 (1914343 n + 42998619 n + 243659366 n + 407937420) a(n + 3) + 1/3 ------------------------------------------------------------- (n + 35) (n + 34) (n + 38) 3 2 (236110 n + 40405131 n + 375894233 n + 895304112) a(n + 4) + 2/3 ------------------------------------------------------------ (n + 35) (n + 34) (n + 38) 3 2 (14993912 n + 55599933 n - 905098793 n - 4166435214) a(n + 5) - 1/3 --------------------------------------------------------------- (n + 35) (n + 34) (n + 38) 3 2 (138810419 n + 1871224617 n + 6026084188 n - 1725181572) a(n + 6) - 1/6 ------------------------------------------------------------------- (n + 35) (n + 34) (n + 38) - 3 2 (395129075 n + 7333863651 n + 41997626710 n + 69385832460) a(n + 7) 1/6 --------------------------------------------------------------------- (n + 35) (n + 34) (n + 38) - 1/6 3 2 (836709907 n + 18736031661 n + 134934721556 n + 307840802400) a(n + 8) ------------------------------------------------------------------------ - (n + 35) (n + 34) (n + 38) 1/3 3 2 (723204233 n + 18688447578 n + 157604445337 n + 431492503008) a(n + 9) ------------------------------------------------------------------------ - (n + 35) (n + 34) (n + 38) 3 2 1/3 (1052256284 n + 30736863375 n + 295269884479 n + 931243642314) a(n + 10)/((n + 35) (n + 34) (n + 38)) - 1/2 3 2 (881443461 n + 28665501257 n + 307943835590 n + 1092493815832) a(n + 11)/ ((n + 35) (n + 34) (n + 38)) - 1/6 3 2 (2904840533 n + 104316272745 n + 1240873433284 n + 4891115235408) a(n + 12)/((n + 35) (n + 34) (n + 38)) - 1/6 3 2 (2779845599 n + 109150110063 n + 1422173589688 n + 6153010091412) a(n + 13)/((n + 35) (n + 34) (n + 38)) - 1/3 3 2 (1151753453 n + 49025434974 n + 692833213924 n + 3252948936096) a(n + 14) /((n + 35) (n + 34) (n + 38)) 2 (n + 2) (904 n + 5581 n + 6087) a(n + 1) + 196/3 ----------------------------------------- + a(n + 38) = 0 (n + 35) (n + 34) (n + 38) Subject to the initial conditions a(1) = 0, a(2) = 0, a(3) = 0, a(4) = 1, a(5) = 8, a(6) = 47, a(7) = 248, a(8) = 1230, a(9) = 5862, a(10) = 27181, a(11) = 123514, a(12) = 552650, a(13) = 2442747, a(14) = 10690745, a(15) = 46407024, a(16) = 200065783, a(17) = 857465553, a(18) = 3656500768, a(19) = 15523960835, a(20) = 65653637028, a(21) = 276710952338, a(22) = 1162695802595, a(23) = 4872078294553, a(24) = 20365127478748, a(25) = 84934641473892, a(26) = 353503929417372, a(27) = 1468557824348752, a(28) = 6090343326701964, a(29) = 25217678926458402, a(30) = 104263697092416745, a(31) = 430499051409012377, a(32) = 1775267760866302924, a(33) = 7312155674020510503, a(34) = 30085035595124537680, a(35) = 123654411068966659354, a(36) = 507750452409831379328, a(37) = 2083040982989671559599, a(38) = 8538372209040868062081 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, 1]}, then , {[2, 3, 2, 3]} b(n) satisfies the following linear recurrence equation with polynomial coef\ ficients of order, 35 3 2 (354224 n + 25712675 n + 620661139 n + 4980821808) b(n + 25) 3/4 -------------------------------------------------------------- (n + 35) (n + 33) (n + 31) 3 2 (351301 n + 26272035 n + 653506154 n + 5405761440) b(n + 26) - 3/8 -------------------------------------------------------------- (n + 35) (n + 33) (n + 31) 3 2 (135507 n + 10671632 n + 279781847 n + 2441690702) b(n + 27) + 3/4 -------------------------------------------------------------- (n + 35) (n + 33) (n + 31) 3 2 (528893 n + 43075569 n + 1168212562 n + 10549300776) b(n + 28) - 1/8 ---------------------------------------------------------------- (n + 35) (n + 33) (n + 31) 3 2 (119702 n + 10061433 n + 281604283 n + 2624320212) b(n + 29) + 1/4 -------------------------------------------------------------- (n + 35) (n + 33) (n + 31) 3 2 (8853 n + 771550 n + 22389824 n + 216332752) b(n + 30) - 3/2 -------------------------------------------------------- (n + 35) (n + 33) (n + 31) 3 2 (7293 n + 655962 n + 19646903 n + 195944234) b(n + 31) + 3/4 -------------------------------------------------------- (n + 35) (n + 33) (n + 31) 3 2 (12521 n + 1156245 n + 35557558 n + 364144704) b(n + 32) - 1/8 ---------------------------------------------------------- (n + 35) (n + 33) (n + 31) 3 2 (1081 n + 102264 n + 3221687 n + 33798864) b(n + 33) + 1/4 ------------------------------------------------------ (n + 35) (n + 33) (n + 31) 3 2 (203 n + 19653 n + 633550 n + 6800640) b(n + 34) - 1/8 -------------------------------------------------- (n + 35) (n + 33) (n + 31) 3 2 (32671 n + 503190 n + 2009822 n + 2374788) b(n + 2) - 7/2 ----------------------------------------------------- (n + 35) (n + 33) (n + 31) 3 2 (952375 n + 25672023 n + 154243970 n + 266108292) b(n + 3) - 1/4 ------------------------------------------------------------ (n + 35) (n + 33) (n + 31) 3 2 (231091 n + 28469130 n + 263657927 n + 632890128) b(n + 4) - 1/2 ------------------------------------------------------------ (n + 35) (n + 33) (n + 31) 3 2 (8143078 n + 19737243 n - 649388077 n - 2831030082) b(n + 5) + 1/4 -------------------------------------------------------------- (n + 35) (n + 33) (n + 31) 3 2 (26122789 n + 386079303 n + 1543885600 n + 877839468) b(n + 6) + 3/8 ---------------------------------------------------------------- + (n + 35) (n + 33) (n + 31) 3 2 (204217759 n + 4082485215 n + 26155805486 n + 52714620540) b(n + 7) 1/8 --------------------------------------------------------------------- (n + 35) (n + 33) (n + 31) + 3 2 (373230143 n + 8801987733 n + 68233334716 n + 173639946576) b(n + 8) 1/8 ---------------------------------------------------------------------- (n + 35) (n + 33) (n + 31) 3 2 (42733539 n + 1133370116 n + 9940552030 n + 28872999987) b(n + 9) + 3/2 ------------------------------------------------------------------- (n + 35) (n + 33) (n + 31) + 1/8 3 2 (527916535 n + 15331545717 n + 147147285092 n + 467600090172) b(n + 10) ------------------------------------------------------------------------- (n + 35) (n + 33) (n + 31) + 3 2 (131772245 n + 4113549689 n + 42183315178 n + 142196083828) b(n + 11) 3/8 ----------------------------------------------------------------------- (n + 35) (n + 33) (n + 31) + 3 2 (85145488 n + 2737937064 n + 28192591229 n + 91855770396) b(n + 12) 1/4 --------------------------------------------------------------------- (n + 35) (n + 33) (n + 31) 3 2 (2989417 n + 151384877 n + 2539021848 n + 13907486624) b(n + 13) - 9/8 ------------------------------------------------------------------ (n + 35) (n + 33) (n + 31) - 3 2 (108818225 n + 4508918601 n + 62544849928 n + 290207786916) b(n + 14) 1/8 ----------------------------------------------------------------------- (n + 35) (n + 33) (n + 31) - 3 2 (28653131 n + 1187353327 n + 16168036046 n + 72080853912) b(n + 15) 3/8 --------------------------------------------------------------------- (n + 35) (n + 33) (n + 31) 3 2 (4840339 n + 71744106 n - 1753519339 n - 26595117072) b(n + 16) - 1/4 ----------------------------------------------------------------- (n + 35) (n + 33) (n + 31) 3 2 (9461917 n + 537128331 n + 10161655118 n + 63987287976) b(n + 17) + 1/2 ------------------------------------------------------------------- (n + 35) (n + 33) (n + 31) + 3 2 (24365737 n + 1385343234 n + 26317870007 n + 166976169006) b(n + 18) 1/4 ---------------------------------------------------------------------- (n + 35) (n + 33) (n + 31) + 3 2 (26573389 n + 1552002843 n + 30125118104 n + 194269685748) b(n + 19) 1/8 ---------------------------------------------------------------------- (n + 35) (n + 33) (n + 31) 3 2 (1864111 n + 126725017 n + 2831249768 n + 20837892816) b(n + 20) + 3/8 ------------------------------------------------------------------ (n + 35) (n + 33) (n + 31) 3 2 (1205019 n + 79740259 n + 1776756044 n + 13324386560) b(n + 21) - 3/8 ----------------------------------------------------------------- (n + 35) (n + 33) (n + 31) 3 2 (520354 n + 33439931 n + 713255878 n + 5046715176) b(n + 22) - 3/2 -------------------------------------------------------------- (n + 35) (n + 33) (n + 31) 3 2 (21228 n - 818623 n - 72512071 n - 977025054) b(n + 23) + 3/4 --------------------------------------------------------- (n + 35) (n + 33) (n + 31) 3 2 (1734223 n + 120968259 n + 2796722774 n + 21409397520) b(n + 24) - 1/8 ------------------------------------------------------------------ (n + 35) (n + 33) (n + 31) 4116 (2 n + 1) (n + 2) (n + 1) b(n) - ----------------------------------- + b(n + 35) (n + 35) (n + 33) (n + 31) 2 49 (n + 2) (904 n + 5581 n + 6087) b(n + 1) - -------------------------------------------- = 0 (n + 35) (n + 33) (n + 31) Subject to the initial conditions b(1) = 0, b(2) = 0, b(3) = 0, b(4) = 1, b(5) = 7, b(6) = 40, b(7) = 208, b(8) = 1022, b(9) = 4841, b(10) = 22351, b(11) = 101246, b(12) = 451937, b(13) = 1993923, b(14) = 8713893, b(15) = 37782630, b(16) = 162736792, b(17) = 696968336, b(18) = 2970357915, b(19) = 12605031400, b(20) = 53289415078, b(21) = 224535349054, b(22) = 943258110753, b(23) = 3951938328771, b(24) = 16517193110152, b(25) = 68882034761142, b(26) = 286684143777490, b(27) = 1190976149247896, b(28) = 4939339896953750, b(29) = 20453067333824605, b(30) = 84571198267646159, b(31) = 349225818280737412, b(32) = 1440292245557958891, b(33) = 5933238746262527356, b(34) = 24415346509003677427, b(35) = 100367627586050933691 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 1.4 1/2 - ---- 1/2 n The probability of Bob winning the bet, as n grows larger is approximately 2.4 1/2 - ---- 1/2 n You can see that indeed Alice has a better chance, but not significantly so. ----------------------------------------- This took, 95.712, seconds to generate ----------------------------------------------------------------------------\ ----------------------- Question Mumber, 6, : If Alice bets that there are more occurrences of consec\ utive substrings in, {[1, 2, 2, 1]}, than in, {[1, 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, {[1, 2, 2, 1]}, then , {[1, 1, 1, 1]} a(n) satisfies the following linear recurrence equation with polynomial coef\ ficients of order, 34 3 2 (45816381 n + 1948601721 n + 26984614394 n + 120828885328) a(n + 14) -1/2 ---------------------------------------------------------------------- - (n + 30) (n + 34) (n + 31) 3 2 (28336928 n + 1072911759 n + 12388942837 n + 39470657952) a(n + 15) 1/3 --------------------------------------------------------------------- (n + 30) (n + 34) (n + 31) 3 2 (4979997 n + 379453627 n + 8356131214 n + 56816268032) a(n + 16) + 1/2 ------------------------------------------------------------------ (n + 30) (n + 34) (n + 31) + 3 2 (40782871 n + 2364048429 n + 45117577886 n + 283570954920) a(n + 17) 1/6 ---------------------------------------------------------------------- (n + 30) (n + 34) (n + 31) 3 2 (4860285 n + 266981779 n + 4894778900 n + 29904574532) a(n + 18) + ------------------------------------------------------------------ (n + 30) (n + 34) (n + 31) 3 2 (17117237 n + 881608305 n + 15035563558 n + 84941164512) a(n + 19) + 1/6 -------------------------------------------------------------------- (n + 30) (n + 34) (n + 31) 3 2 (469726 n + 47975169 n + 1392653993 n + 12380088228) a(n + 20) - 1/3 ---------------------------------------------------------------- (n + 30) (n + 34) (n + 31) 3 2 (910761 n + 52262627 n + 1021026150 n + 6841673736) a(n + 21) - 1/2 --------------------------------------------------------------- (n + 30) (n + 34) (n + 31) 3 2 2 (410681 n + 25380125 n + 519046636 n + 3509330932) a(n + 22) - ---------------------------------------------------------------- (n + 30) (n + 34) (n + 31) 3 2 2 (14143 n + 664249 n + 6640546 n - 25926058) a(n + 23) - --------------------------------------------------------- (n + 30) (n + 34) (n + 31) 3 2 (73349 n + 4004775 n + 67110895 n + 319563876) a(n + 24) + 4/3 ---------------------------------------------------------- (n + 30) (n + 34) (n + 31) 3 2 (49557 n + 3973799 n + 104389214 n + 899956268) a(n + 25) + ----------------------------------------------------------- (n + 30) (n + 34) (n + 31) 3 2 (50063 n + 3627885 n + 87208657 n + 695262510) a(n + 26) + 2/3 ---------------------------------------------------------- (n + 30) (n + 34) (n + 31) 3 2 2 (16398 n + 1193591 n + 28668193 n + 226776898) a(n + 27) - ------------------------------------------------------------ (n + 30) (n + 34) (n + 31) 3 2 (2641 n + 91644 n - 901348 n - 39054600) a(n + 28) + 2/3 ---------------------------------------------------- (n + 30) (n + 34) (n + 31) 3 2 (983 n + 94200 n + 2963839 n + 30703242) a(n + 29) + 2/3 ---------------------------------------------------- (n + 30) (n + 34) (n + 31) 3 2 (1743 n + 152515 n + 4443978 n + 43121016) a(n + 30) + ------------------------------------------------------ (n + 30) (n + 34) (n + 31) 3 2 3 (337 n + 30023 n + 890792 n + 8802776) a(n + 31) - ---------------------------------------------------- (n + 30) (n + 34) (n + 31) 3 2 (227 n + 20639 n + 624888 n + 6300816) a(n + 32) + -------------------------------------------------- (n + 30) (n + 34) (n + 31) 2 2 (12 n + 755 n + 11843) a(n + 33) - ----------------------------------- (n + 34) (n + 31) 2 576 (n + 2) (100 n + 565 n + 753) a(n + 1) - ------------------------------------------- + a(n + 34) (n + 30) (n + 34) (n + 31) 3 2 864 (331 n + 4492 n + 18375 n + 23638) a(n + 2) + ------------------------------------------------- (n + 30) (n + 34) (n + 31) 3 2 288 (9196 n + 149955 n + 777905 n + 1300230) a(n + 3) + ------------------------------------------------------- (n + 30) (n + 34) (n + 31) 3 2 216 (31115 n + 586491 n + 3585984 n + 7152924) a(n + 4) + --------------------------------------------------------- (n + 30) (n + 34) (n + 31) 3 2 12 (874634 n + 17691801 n + 117038725 n + 254041962) a(n + 5) + --------------------------------------------------------------- (n + 30) (n + 34) (n + 31) 3 2 18 (940903 n + 21022696 n + 156626171 n + 388622346) a(n + 6) + --------------------------------------------------------------- (n + 30) (n + 34) (n + 31) 3 2 6 (3254978 n + 74857845 n + 573879001 n + 1466879538) a(n + 7) + ---------------------------------------------------------------- (n + 30) (n + 34) (n + 31) 3 2 (12410765 n + 293740479 n + 2238471514 n + 5411910288) a(n + 8) + 3/2 ----------------------------------------------------------------- (n + 30) (n + 34) (n + 31) 3 2 (11692789 n + 33083655 n - 3329722990 n - 24863045904) a(n + 9) + 1/2 ----------------------------------------------------------------- (n + 30) (n + 34) (n + 31) 3 2 (4894689 n + 316033409 n + 5429624398 n + 27995849312) a(n + 10) - 3/2 ------------------------------------------------------------------ (n + 30) (n + 34) (n + 31) - 3 2 (45440021 n + 2084116647 n + 31070940304 n + 151274403648) a(n + 11) 1/2 ---------------------------------------------------------------------- (n + 30) (n + 34) (n + 31) 3 2 (30027176 n + 1311371343 n + 18895034083 n + 89985557220) a(n + 12) - --------------------------------------------------------------------- - (n + 30) (n + 34) (n + 31) 3 2 (66013623 n + 2760371977 n + 38041200222 n + 172587262496) a(n + 13) 1/2 ---------------------------------------------------------------------- (n + 30) (n + 34) (n + 31) 6912 (2 n + 3) (n + 2) (n + 1) a(n) - ----------------------------------- = 0 (n + 30) (n + 34) (n + 31) Subject to the initial conditions a(1) = 0, a(2) = 0, a(3) = 0, a(4) = 1, a(5) = 8, a(6) = 48, a(7) = 253, a(8) = 1255, a(9) = 5982, a(10) = 27744, a(11) = 126085, a(12) = 564196, a(13) = 2493879, a(14) = 10914756, a(15) = 47379664, a(16) = 204257589, a(17) = 875417225, a(18) = 3732964821, a(19) = 15848128627, a(20) = 67022301973, a(21) = 282468646465, a(22) = 1186839237134, a(23) = 4973025850882, a(24) = 20786110100824, a(25) = 86686147292067, a(26) = 360775545109299, a(27) = 1498688089973254, a(28) = 6214966394275430, a(29) = 25732290578430231, a(30) = 106385483196302674, a(31) = 439235066896718271, a(32) = 1811189616815347838, a(33) = 7459684528301318135, a(34) = 30690241760392064247 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, 1]}, then , {[1, 2, 2, 1]} b(n) satisfies the following linear recurrence equation with polynomial coef\ ficients of order, 20 6912 (2 n + 3) (n + 2) (n + 1) b(n) 576 (4 n + 33) (n + 2) (n + 1) b(n + 1) ----------------------------------- + --------------------------------------- (n + 20) (n + 19) (n + 16) (n + 20) (n + 19) (n + 16) 3 2 288 (65 n + 972 n + 4477 n + 6450) b(n + 2) - --------------------------------------------- (n + 20) (n + 19) (n + 16) 3 2 288 (472 n + 7857 n + 41639 n + 71034) b(n + 3) + ------------------------------------------------- (n + 20) (n + 19) (n + 16) 3 2 216 (645 n + 13781 n + 94112 n + 206596) b(n + 4) + --------------------------------------------------- (n + 20) (n + 19) (n + 16) 3 2 12 (22078 n + 501879 n + 3755795 n + 9238854) b(n + 5) + -------------------------------------------------------- (n + 20) (n + 19) (n + 16) 3 2 6 (4507 n + 143040 n + 1448279 n + 4685106) b(n + 6) + ------------------------------------------------------ (n + 20) (n + 19) (n + 16) 3 2 6 (10106 n + 221223 n + 1545775 n + 3391758) b(n + 7) + ------------------------------------------------------- (n + 20) (n + 19) (n + 16) 3 2 (17071 n + 581237 n + 6548510 n + 24307728) b(n + 8) - 9/2 ------------------------------------------------------ (n + 20) (n + 19) (n + 16) 3 2 (32303 n + 1798905 n + 25703074 n + 109224648) b(n + 9) + 1/2 --------------------------------------------------------- (n + 20) (n + 19) (n + 16) 3 2 (75545 n + 2717445 n + 31924498 n + 123192216) b(n + 10) - 1/2 ---------------------------------------------------------- (n + 20) (n + 19) (n + 16) 3 2 (9745 n + 485623 n + 7625572 n + 38417448) b(n + 11) + 3/2 ------------------------------------------------------ (n + 20) (n + 19) (n + 16) 3 2 (12661 n + 971601 n + 18774368 n + 107658192) b(n + 12) - 1/2 --------------------------------------------------------- (n + 20) (n + 19) (n + 16) 3 2 2 (5960 n + 293029 n + 4645891 n + 23985110) b(n + 13) + -------------------------------------------------------- (n + 20) (n + 19) (n + 16) 3 2 (3403 n + 185737 n + 3279422 n + 18911528) b(n + 14) - 1/2 ------------------------------------------------------ (n + 20) (n + 19) (n + 16) 3 2 (12079 n + 530799 n + 7698602 n + 36771480) b(n + 15) - 1/2 ------------------------------------------------------- (n + 20) (n + 19) (n + 16) 3 2 (8927 n + 413557 n + 6350584 n + 32291072) b(n + 16) + 1/2 ------------------------------------------------------ (n + 20) (n + 19) (n + 16) 3 2 (2935 n + 142291 n + 2289452 n + 12216512) b(n + 17) - 1/2 ------------------------------------------------------ (n + 20) (n + 19) (n + 16) 3 2 (175 n + 8865 n + 149098 n + 832072) b(n + 18) + 3/2 ------------------------------------------------ (n + 20) (n + 19) (n + 16) 2 (25 n + 846 n + 7100) b(n + 19) - -------------------------------- + b(n + 20) = 0 (n + 20) (n + 16) Subject to the initial conditions b(1) = 0, b(2) = 0, b(3) = 0, b(4) = 1, b(5) = 7, b(6) = 40, b(7) = 206, b(8) = 1010, b(9) = 4775, b(10) = 22018, b(11) = 99631, b(12) = 444370, b(13) = 1959249, b(14) = 8557767, b(15) = 37088988, b(16) = 159688253, b(17) = 683688170, b(18) = 2912933099, b(19) = 12358272623, b(20) = 52234767113 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 1.4 1/2 - ---- 1/2 n The probability of Bob winning the bet, as n grows larger is approximately 2.6 1/2 - ---- 1/2 n You can see that indeed Alice has a better chance, but not significantly so. ----------------------------------------- This took, 59.241, seconds to generate ----------------------------------------------------------------------------\ ----------------------- Question Mumber, 7, : If Alice bets that there are more occurrences of consec\ utive substrings in, {[1, 1, 2, 2]}, than in, {[1, 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 , 7.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, 2]}, then , {[1, 1, 1, 1]} a(n) satisfies the following linear recurrence equation with polynomial coef\ ficients of order, 33 2 (n + 3) (613 n + 7149 n + 20516) a(n + 2) -512/3 ------------------------------------------ (n + 30) (n + 29) (n + 33) 3 2 (1777 n - 11766 n - 257473 n - 729618) a(n + 3) + 128/3 ------------------------------------------------- (n + 30) (n + 29) (n + 33) 3 2 (96239 n + 1230276 n + 4391491 n + 3188586) a(n + 4) + 32/3 ------------------------------------------------------ (n + 30) (n + 29) (n + 33) 3 2 (564545 n + 9477714 n + 51064828 n + 86958153) a(n + 5) + 16/3 --------------------------------------------------------- (n + 30) (n + 29) (n + 33) 3 2 (8848733 n + 177362874 n + 1183050913 n + 2625531624) a(n + 6) + 2/3 ---------------------------------------------------------------- (n + 30) (n + 29) (n + 33) 3 2 (49176877 n + 1092549432 n + 8227501235 n + 21104473464) a(n + 7) + 1/6 ------------------------------------------------------------------- (n + 30) (n + 29) (n + 33) 3 2 (11115451 n + 241618986 n + 1766237255 n + 4455858924) a(n + 8) + 2/3 ----------------------------------------------------------------- (n + 30) (n + 29) (n + 33) 3 2 (4689981 n + 805272 n - 1162346889 n - 6929289236) a(n + 9) + 1/2 ------------------------------------------------------------- (n + 30) (n + 29) (n + 33) 3 2 (5970971 n + 282203116 n + 3931741635 n + 16982519158) a(n + 10) - ------------------------------------------------------------------ (n + 30) (n + 29) (n + 33) 3 2 (21127229 n + 851978706 n + 11225423401 n + 48412398684) a(n + 11) - 2/3 -------------------------------------------------------------------- (n + 30) (n + 29) (n + 33) - 3 2 (56774707 n + 2210578317 n + 28692086642 n + 123966540000) a(n + 12) 1/3 ---------------------------------------------------------------------- (n + 30) (n + 29) (n + 33) - 3 2 (113691691 n + 4434912276 n + 57622993121 n + 249362250768) a(n + 13) 1/6 ----------------------------------------------------------------------- (n + 30) (n + 29) (n + 33) 3 2 (13528059 n + 537648110 n + 7050464407 n + 30478421926) a(n + 14) - ------------------------------------------------------------------- (n + 30) (n + 29) (n + 33) 3 2 (10111899 n + 395949744 n + 4927485809 n + 19017442852) a(n + 15) - 1/2 ------------------------------------------------------------------- (n + 30) (n + 29) (n + 33) 3 2 (13606115 n + 701816166 n + 12209858119 n + 71280873984) a(n + 16) + 1/6 -------------------------------------------------------------------- (n + 30) (n + 29) (n + 33) 3 2 (4933287 n + 246673326 n + 4109320129 n + 22795400522) a(n + 17) + ------------------------------------------------------------------ (n + 30) (n + 29) (n + 33) 3 2 (3351109 n + 177283921 n + 3119136144 n + 18252404136) a(n + 18) + ------------------------------------------------------------------ (n + 30) (n + 29) (n + 33) 3 2 (1787603 n + 105214792 n + 2046892797 n + 13175277328) a(n + 19) + 1/2 ------------------------------------------------------------------ (n + 30) (n + 29) (n + 33) 3 2 (558525 n + 29914703 n + 531954832 n + 3145685632) a(n + 20) - -------------------------------------------------------------- (n + 30) (n + 29) (n + 33) 3 2 (1963789 n + 123020373 n + 2562314024 n + 17744715156) a(n + 21) - 1/3 ------------------------------------------------------------------ (n + 30) (n + 29) (n + 33) 3 2 (624530 n + 43028613 n + 982024273 n + 7427302590) a(n + 22) - 1/3 -------------------------------------------------------------- (n + 30) (n + 29) (n + 33) 3 2 (246713 n + 17455998 n + 412037821 n + 3242007708) a(n + 23) + 1/6 -------------------------------------------------------------- (n + 30) (n + 29) (n + 33) 3 2 (658007 n + 45312876 n + 1039961017 n + 7957674648) a(n + 24) + 1/6 --------------------------------------------------------------- (n + 30) (n + 29) (n + 33) 3 2 (46457 n + 3427740 n + 83759323 n + 677833080) a(n + 25) + 1/2 ---------------------------------------------------------- (n + 30) (n + 29) (n + 33) 3 2 (41870 n + 3043383 n + 73588798 n + 592120782) a(n + 26) - 2/3 ---------------------------------------------------------- (n + 30) (n + 29) (n + 33) 3 2 (21529 n + 1814208 n + 50330639 n + 460122768) a(n + 27) - 1/6 ---------------------------------------------------------- (n + 30) (n + 29) (n + 33) 3 2 (2897 n + 224118 n + 5746555 n + 48801020) a(n + 28) + ------------------------------------------------------ (n + 30) (n + 29) (n + 33) 3 2 (7747 n + 675588 n + 19596425 n + 189084480) a(n + 29) + 1/6 -------------------------------------------------------- (n + 30) (n + 29) (n + 33) 3 2 (2897 n + 250227 n + 7197892 n + 68958072) a(n + 30) - 1/3 ------------------------------------------------------ (n + 30) (n + 29) (n + 33) 3 2 (1351 n + 118836 n + 3480701 n + 33950376) a(n + 31) + 1/6 ------------------------------------------------------ + a(n + 33) (n + 30) (n + 29) (n + 33) 2 2 (12 n + 731 n + 11100) a(n + 32) - ----------------------------------- (n + 33) (n + 30) (n + 1) (n + 2) (n + 3) a(n) + 8192/3 ---------------------------- (n + 30) (n + 29) (n + 33) (20 n + 83) (n + 3) (n + 2) a(n + 1) - 4096/3 ------------------------------------ = 0 (n + 30) (n + 29) (n + 33) Subject to the initial conditions a(1) = 0, a(2) = 0, a(3) = 0, a(4) = 1, a(5) = 8, a(6) = 47, a(7) = 248, a(8) = 1230, a(9) = 5862, a(10) = 27181, a(11) = 123516, a(12) = 552672, a(13) = 2442909, a(14) = 10691767, a(15) = 46412921, a(16) = 200097808, a(17) = 857632089, a(18) = 3657339002, a(19) = 15528073723, a(20) = 65673407763, a(21) = 276804402326, a(22) = 1163131324794, a(23) = 4874083866811, a(24) = 20374268422339, a(25) = 84975932234651, a(26) = 353688984268899, a(27) = 1469381445776536, a(28) = 6093986363983465, a(29) = 25233703500659033, a(30) = 104333831852585910, a(31) = 430804619334304628, a(32) = 1776593585829367178, a(33) = 7317886566840908575 Lemma , 7.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, 1]}, then , {[1, 1, 2, 2]} b(n) satisfies the following linear recurrence equation with polynomial coef\ ficients of order, 13 2 128 (n + 3) (n + 1) b(n) 16 (13 n + 73 n + 96) b(n + 1) - ------------------------ - ------------------------------- (n + 13) (n + 9) (n + 13) (n + 9) 2 2 4 (5 n - 85 n - 294) b(n + 2) (65 n + 2225 n + 8004) b(n + 3) - ------------------------------ + -------------------------------- (n + 13) (n + 9) (n + 13) (n + 9) 2 (11 n + 3891 n + 21004) b(n + 4) + 1/4 --------------------------------- (n + 13) (n + 9) 2 (257 n + 3375 n + 11686) b(n + 5) + 1/2 ---------------------------------- (n + 13) (n + 9) 2 (586 n + 8073 n + 27974) b(n + 6) + 1/2 ---------------------------------- (n + 13) (n + 9) 2 (281 n + 2883 n + 4912) b(n + 7) + 1/2 --------------------------------- (n + 13) (n + 9) 2 (11 n + 482 n + 4044) b(n + 8) - 1/2 ------------------------------- (n + 13) (n + 9) 2 (169 n + 2494 n + 8313) b(n + 9) - 1/2 --------------------------------- (n + 13) (n + 9) 2 (80 n + 1611 n + 7858) b(n + 10) - 1/2 --------------------------------- (n + 13) (n + 9) 2 (95 n + 1896 n + 9193) b(n + 11) + 1/2 --------------------------------- (n + 13) (n + 9) 2 (49 n + 1027 n + 5220) b(n + 12) - 1/4 --------------------------------- + b(n + 13) = 0 (n + 13) (n + 9) Subject to the initial conditions b(1) = 0, b(2) = 0, b(3) = 0, b(4) = 1, b(5) = 7, b(6) = 39, b(7) = 201, b(8) = 983, b(9) = 4640, b(10) = 21369, b(11) = 96618, b(12) = 430660, b(13) = 1897897 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 1.4 1/2 - ---- 1/2 n The probability of Bob winning the bet, as n grows larger is approximately 2.7 1/2 - ---- 1/2 n You can see that indeed Alice has a better chance, but not significantly so. ----------------------------------------- This took, 47.010, seconds to generate ----------------------------------------------------------------------------\ ----------------------- Question Mumber, 8, : If Alice bets that there are more occurrences of consec\ utive substrings in, {[2, 1, 1, 2]}, than in, {[1, 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 , 8.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, 1, 2]}, then , {[1, 1, 1, 1]} a(n) satisfies the following linear recurrence equation with polynomial coef\ ficients of order, 39 2 2 (12 n + 875 n + 15918) a(n + 38) (n + 1) (n + 2) (n + 3) a(n) - ----------------------------------- + 16384/3 ---------------------------- (n + 39) (n + 36) (n + 35) (n + 39) (n + 36) (917 n + 4499) (n + 3) (n + 2) a(n + 1) + 1024/3 --------------------------------------- (n + 35) (n + 39) (n + 36) 2 (n + 3) (6868 n + 69735 n + 169520) a(n + 2) + 896/3 --------------------------------------------- (n + 35) (n + 39) (n + 36) 2 (n + 4) (756058 n + 9256967 n + 27461955) a(n + 3) + 32/3 --------------------------------------------------- (n + 35) (n + 39) (n + 36) 3 2 (223957 n + 15471480 n + 340418591 n + 2323284612) a(n + 28) + 1/3 -------------------------------------------------------------- (n + 35) (n + 39) (n + 36) 3 2 (162386 n + 12479979 n + 316222693 n + 2637869724) a(n + 29) - 2/3 -------------------------------------------------------------- (n + 35) (n + 39) (n + 36) 3 2 (348842 n + 29174475 n + 811311721 n + 7503193326) a(n + 30) + 1/3 -------------------------------------------------------------- (n + 35) (n + 39) (n + 36) 3 2 (49949 n + 5155284 n + 173806843 n + 1922705700) a(n + 31) + 1/6 ------------------------------------------------------------ (n + 35) (n + 39) (n + 36) 3 2 (18121 n + 1594817 n + 46556232 n + 450686540) a(n + 32) - ---------------------------------------------------------- (n + 35) (n + 39) (n + 36) 3 2 (21199 n + 2334450 n + 84183473 n + 997498638) a(n + 33) - 1/6 ---------------------------------------------------------- (n + 35) (n + 39) (n + 36) 3 2 (2509 n + 249600 n + 8264141 n + 91059870) a(n + 34) + 2/3 ------------------------------------------------------ (n + 35) (n + 39) (n + 36) 3 2 (1643 n + 169228 n + 5805737 n + 66344152) a(n + 35) + ------------------------------------------------------ (n + 35) (n + 39) (n + 36) 3 2 (1007 n + 104848 n + 3636573 n + 42018492) a(n + 36) - ------------------------------------------------------ (n + 35) (n + 39) (n + 36) 3 2 (227 n + 24044 n + 848303 n + 9969606) a(n + 37) + -------------------------------------------------- + a(n + 39) (n + 35) (n + 39) (n + 36) 3 2 32 (655638 n + 12336277 n + 75921627 n + 153153912) a(n + 4) + -------------------------------------------------------------- (n + 35) (n + 39) (n + 36) 3 2 (7990678 n + 167759199 n + 1160118251 n + 2646979638) a(n + 5) + 16/3 ---------------------------------------------------------------- (n + 35) (n + 39) (n + 36) 3 2 (28230239 n + 652470420 n + 5002529251 n + 12725860746) a(n + 6) + 8/3 ------------------------------------------------------------------ (n + 35) (n + 39) (n + 36) 3 2 32 (3412876 n + 83880933 n + 684989239 n + 1858620678) a(n + 7) + ----------------------------------------------------------------- (n + 35) (n + 39) (n + 36) 3 2 (51477062 n + 1317274947 n + 11124333265 n + 30949412916) a(n + 8) + 8/3 -------------------------------------------------------------------- (n + 35) (n + 39) (n + 36) + 3 2 (113850305 n + 3014647296 n + 25988240185 n + 72326071770) a(n + 9) 4/3 --------------------------------------------------------------------- (n + 35) (n + 39) (n + 36) + 3 2 (102026905 n + 2639277582 n + 20925261515 n + 46803233334) a(n + 10) 4/3 ---------------------------------------------------------------------- (n + 35) (n + 39) (n + 36) 3 2 4 (24246709 n + 559869208 n + 2983878815 n - 2799635644) a(n + 11) + -------------------------------------------------------------------- (n + 35) (n + 39) (n + 36) 3 2 4 (8781120 n + 40832547 n - 3322499877 n - 30624293560) a(n + 12) + ------------------------------------------------------------------- - (n + 35) (n + 39) (n + 36) 3 2 (45273145 n + 3399563232 n + 68039443817 n + 409232581794) a(n + 13) 2/3 ---------------------------------------------------------------------- (n + 35) (n + 39) (n + 36) - 2/3 3 2 (119914973 n + 6187960722 n + 104379575095 n + 576945034506) a(n + 14) ------------------------------------------------------------------------ - (n + 35) (n + 39) (n + 36) 2/3 3 2 (166917499 n + 8028619296 n + 128851286405 n + 689176458600) a(n + 15) ------------------------------------------------------------------------ (n + 35) (n + 39) (n + 36) 3 2 2 (49473874 n + 2435990793 n + 39923824507 n + 217684308308) a(n + 16) - ------------------------------------------------------------------------ (n + 35) (n + 39) (n + 36) - 1/3 3 2 (224969329 n + 11161329648 n + 183493613825 n + 998788843554) a(n + 17) ------------------------------------------------------------------------- (n + 35) (n + 39) (n + 36) - 1/3 3 2 (135031457 n + 6795837654 n + 112361805259 n + 608422925742) a(n + 18) ------------------------------------------------------------------------ (n + 35) (n + 39) (n + 36) 3 2 (6215113 n + 306263302 n + 4567664009 n + 18841747232) a(n + 19) - ------------------------------------------------------------------ (n + 35) (n + 39) (n + 36) 3 2 (3540700 n + 279548783 n + 7054898635 n + 57542188064) a(n + 20) + ------------------------------------------------------------------ + (n + 35) (n + 39) (n + 36) 3 2 (18435439 n + 1208162030 n + 26396347857 n + 192102621114) a(n + 21) 1/2 ---------------------------------------------------------------------- (n + 35) (n + 39) (n + 36) + 3 2 (35363741 n + 2256223749 n + 47953696678 n + 339558880788) a(n + 22) 1/3 ---------------------------------------------------------------------- (n + 35) (n + 39) (n + 36) + 3 2 (11933213 n + 944958648 n + 24187219903 n + 201359660316) a(n + 23) 1/6 --------------------------------------------------------------------- (n + 35) (n + 39) (n + 36) 3 2 (1553936 n + 113315235 n + 2736919279 n + 21873626832) a(n + 24) + 2/3 ------------------------------------------------------------------ (n + 35) (n + 39) (n + 36) 3 2 (559174 n + 34000815 n + 660305291 n + 4012087758) a(n + 25) + 2/3 -------------------------------------------------------------- (n + 35) (n + 39) (n + 36) 3 2 (4732835 n + 344158869 n + 8314034608 n + 66718866840) a(n + 26) - 1/3 ------------------------------------------------------------------ (n + 35) (n + 39) (n + 36) 3 2 (41201 n + 8566056 n + 359381935 n + 4264578304) a(n + 27) - 1/2 ------------------------------------------------------------ = 0 (n + 35) (n + 39) (n + 36) Subject to the initial conditions a(1) = 0, a(2) = 0, a(3) = 0, a(4) = 1, a(5) = 8, a(6) = 48, a(7) = 255, a(8) = 1269, a(9) = 6062, a(10) = 28153, a(11) = 128078, a(12) = 573562, a(13) = 2536820, a(14) = 11107957, a(15) = 48236504, a(16) = 208014189, a(17) = 891733676, a(18) = 3803284398, a(19) = 16149203789, a(20) = 68304142703, a(21) = 287899687330, a(22) = 1209752594249, a(23) = 5069335619165, a(24) = 21189579225970, a(25) = 88371388165366, a(26) = 367795842789035, a(27) = 1527862518655444, a(28) = 6335942220373183, a(29) = 26232933094747082, a(30) = 108453541331353730, a(31) = 447763471822435143, a(32) = 1846305181803919357, a(33) = 7604065071742060894, a(34) = 31283084908539577627, a(35) = 128565785480978483676, a(36) = 527862932778628033340, a(37) = 2165320535104212437628, a(38) = 8874658118574546099453, a(39) = 36343827274555000600930 Lemma , 8.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, 1]}, then , {[2, 1, 1, 2]} b(n) satisfies the following linear recurrence equation with polynomial coef\ ficients of order, 33 2 7 (3 n + 180 n + 2693) b(n + 32) (n + 1) (n + 2) (n + 3) b(n) - --------------------------------- - 16384/3 ---------------------------- (n + 33) (n + 29) (n + 29) (n + 33) (n + 32) (n + 3) (n + 2) (149 n + 659) b(n + 1) - 1024/3 -------------------------------------- (n + 29) (n + 33) (n + 32) 2 (n + 3) (308 n + 11055 n + 39088) b(n + 2) + 128/3 ------------------------------------------- (n + 29) (n + 33) (n + 32) 2 (n + 4) (33638 n + 516601 n + 1735677) b(n + 3) + 32/3 ------------------------------------------------ (n + 29) (n + 33) (n + 32) 3 2 (147742 n + 3090393 n + 20514743 n + 43775496) b(n + 4) + 32/3 --------------------------------------------------------- (n + 29) (n + 33) (n + 32) 3 2 (905218 n + 20957685 n + 157489385 n + 385927218) b(n + 5) + 16/3 ------------------------------------------------------------ (n + 29) (n + 33) (n + 32) 3 2 8 (1316619 n + 33986196 n + 286988367 n + 795111602) b(n + 6) + --------------------------------------------------------------- (n + 29) (n + 33) (n + 32) 3 2 (1785824 n + 50559795 n + 470869801 n + 1445281218) b(n + 7) + 32/3 -------------------------------------------------------------- (n + 29) (n + 33) (n + 32) 3 2 24 (1202696 n + 37002151 n + 375479679 n + 1258669708) b(n + 8) + ----------------------------------------------------------------- (n + 29) (n + 33) (n + 32) 3 2 4 (9308089 n + 311172856 n + 3436237105 n + 12549728850) b(n + 9) + ------------------------------------------------------------------- + (n + 29) (n + 33) (n + 32) 3 2 (31174501 n + 1122891540 n + 13376890889 n + 52752531786) b(n + 10) 4/3 --------------------------------------------------------------------- (n + 29) (n + 33) (n + 32) 3 2 (14954380 n + 579572787 n + 7429158644 n + 31521673545) b(n + 11) + 8/3 ------------------------------------------------------------------- (n + 29) (n + 33) (n + 32) 3 2 4 (8316160 n + 347224957 n + 4790763609 n + 21861037472) b(n + 12) + -------------------------------------------------------------------- + (n + 29) (n + 33) (n + 32) 3 2 (34578769 n + 1551837432 n + 22987832165 n + 112498822830) b(n + 13) 2/3 ---------------------------------------------------------------------- (n + 29) (n + 33) (n + 32) 3 2 (19815619 n + 962367558 n + 15375975593 n + 80933622966) b(n + 14) + 2/3 -------------------------------------------------------------------- (n + 29) (n + 33) (n + 32) 3 2 (8690471 n + 464254464 n + 8095782853 n + 46234214892) b(n + 15) + 2/3 ------------------------------------------------------------------ (n + 29) (n + 33) (n + 32) 3 2 2 (392224 n + 29301571 n + 640446463 n + 4334271980) b(n + 16) + ---------------------------------------------------------------- (n + 29) (n + 33) (n + 32) 3 2 (1882349 n + 77753904 n + 998227861 n + 3805035090) b(n + 17) - 1/3 --------------------------------------------------------------- (n + 29) (n + 33) (n + 32) 3 2 (2773741 n + 150972570 n + 2729431451 n + 16411602702) b(n + 18) - 1/3 ------------------------------------------------------------------ (n + 29) (n + 33) (n + 32) 3 2 (2198605 n + 131103714 n + 2596606169 n + 17091333936) b(n + 19) - 1/3 ------------------------------------------------------------------ (n + 29) (n + 33) (n + 32) 3 2 (173966 n + 16233597 n + 436760611 n + 3628115184) b(n + 20) - 1/3 -------------------------------------------------------------- (n + 29) (n + 33) (n + 32) 3 2 (64989 n + 5158046 n + 130773375 n + 1071086310) b(n + 21) - 1/2 ------------------------------------------------------------ (n + 29) (n + 33) (n + 32) 3 2 3 (8249 n + 540746 n + 11661605 n + 82682514) b(n + 22) + --------------------------------------------------------- (n + 29) (n + 33) (n + 32) 3 2 (223168 n + 15350781 n + 351642452 n + 2682611511) b(n + 23) + 1/3 -------------------------------------------------------------- (n + 29) (n + 33) (n + 32) 3 2 (17757 n + 1159656 n + 25001601 n + 177568252) b(n + 24) - ---------------------------------------------------------- (n + 29) (n + 33) (n + 32) 3 2 (1352 n + 93448 n + 2128189 n + 15894373) b(n + 25) + ----------------------------------------------------- (n + 29) (n + 33) (n + 32) 3 2 (4953 n + 391710 n + 10252939 n + 88747182) b(n + 26) + 1/2 ------------------------------------------------------- (n + 29) (n + 33) (n + 32) 3 2 (6749 n + 542777 n + 14510158 n + 128909296) b(n + 27) - -------------------------------------------------------- (n + 29) (n + 33) (n + 32) 3 2 (5045 n + 408270 n + 10993977 n + 98502780) b(n + 28) + 1/2 ------------------------------------------------------- (n + 29) (n + 33) (n + 32) 3 2 (1289 n + 114850 n + 3396373 n + 33336668) b(n + 29) + 1/2 ------------------------------------------------------ (n + 29) (n + 33) (n + 32) 3 2 (1285 n + 113488 n + 3336065 n + 32636406) b(n + 30) - 1/2 ------------------------------------------------------ (n + 29) (n + 33) (n + 32) 3 2 (345 n + 31062 n + 931055 n + 9289922) b(n + 31) + 1/2 -------------------------------------------------- + b(n + 33) = 0 (n + 29) (n + 33) (n + 32) Subject to the initial conditions b(1) = 0, b(2) = 0, b(3) = 0, b(4) = 1, b(5) = 7, b(6) = 40, b(7) = 208, b(8) = 1022, b(9) = 4841, b(10) = 22349, b(11) = 101230, b(12) = 451831, b(13) = 1993291, b(14) = 8710388, b(15) = 37764141, b(16) = 162642729, b(17) = 696502973, b(18) = 2968106118, b(19) = 12594330370, b(20) = 53239318260, b(21) = 224303771112, b(22) = 942199150620, b(23) = 3947141114577, b(24) = 16495638636651, b(25) = 68785885702131, b(26) = 286257994445194, b(27) = 1189098208047021, b(28) = 4931106947263945, b(29) = 20417142374923013, b(30) = 84415103183295854, b(31) = 348550210049003702, b(32) = 1437378484581521656, b(33) = 5920713396919942597 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 1.3 1/2 - ---- 1/2 n The probability of Bob winning the bet, as n grows larger is approximately 2.6 1/2 - ---- 1/2 n You can see that indeed Alice has a better chance, but not significantly so. ----------------------------------------- This took, 89.231, seconds to generate ----------------------------------------------------------------------------\ ----------------------- Question Mumber, 9, : If Alice bets that there are more occurrences of consec\ utive substrings in, {[1, 2, 1, 3]}, than in, {[1, 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 , 9.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, 3]}, then , {[1, 1, 1, 1]} a(n) satisfies the following linear recurrence equation with polynomial coef\ ficients of order, 30 (n + 1) (n + 2) (n + 3) a(n) (n + 4) (n + 3) (n + 2) a(n + 1) -8192/3 ---------------------------- - 8192/3 -------------------------------- (n + 30) (n + 27) (n + 26) (n + 30) (n + 27) (n + 26) 2 512 (n + 3) (77 n + 969 n + 2664) a(n + 2) - ------------------------------------------- (n + 30) (n + 27) (n + 26) 2 (27 n + 1480 n + 20205) a(n + 29) - ---------------------------------- + a(n + 30) (n + 27) (n + 30) 3 2 (1795 n + 31302 n + 175481 n + 316038) a(n + 3) - 128/3 ------------------------------------------------- (n + 30) (n + 27) (n + 26) 3 2 (3353 n + 19986 n - 73463 n - 448692) a(n + 4) + 64/3 ------------------------------------------------ (n + 30) (n + 27) (n + 26) 3 2 8 (24537 n + 500448 n + 3484071 n + 8198584) a(n + 5) + ------------------------------------------------------- (n + 30) (n + 27) (n + 26) 3 2 4 (112673 n + 2638590 n + 21765451 n + 61792830) a(n + 6) + ----------------------------------------------------------- (n + 30) (n + 27) (n + 26) 3 2 (350581 n + 7879989 n + 68600318 n + 224995440) a(n + 7) + 4/3 ---------------------------------------------------------- (n + 30) (n + 27) (n + 26) 3 2 (2039329 n + 35022396 n + 244285619 n + 872272872) a(n + 8) + 1/6 ------------------------------------------------------------- (n + 30) (n + 27) (n + 26) 3 2 (333048 n + 19369611 n + 265062735 n + 1033112500) a(n + 9) - 1/2 ------------------------------------------------------------- (n + 30) (n + 27) (n + 26) 3 2 (2136607 n + 68616297 n + 726125814 n + 2516005640) a(n + 10) - 1/2 --------------------------------------------------------------- (n + 30) (n + 27) (n + 26) 3 2 (10607437 n + 328506444 n + 3401912387 n + 11830896756) a(n + 11) - 1/6 ------------------------------------------------------------------- (n + 30) (n + 27) (n + 26) 3 2 (15642485 n + 561472407 n + 6691844998 n + 26510556792) a(n + 12) - 1/6 ------------------------------------------------------------------- (n + 30) (n + 27) (n + 26) 3 2 (3754633 n + 130430847 n + 1469518262 n + 5333328468) a(n + 13) - 1/3 ----------------------------------------------------------------- (n + 30) (n + 27) (n + 26) 3 2 (322600 n + 14347547 n + 206831017 n + 972213390) a(n + 14) - ------------------------------------------------------------- (n + 30) (n + 27) (n + 26) 3 2 (1790291 n + 61099734 n + 631475827 n + 1773987564) a(n + 15) + 1/6 --------------------------------------------------------------- (n + 30) (n + 27) (n + 26) 3 2 (4337066 n + 207802209 n + 3299939275 n + 17360473152) a(n + 16) + 1/6 ------------------------------------------------------------------ (n + 30) (n + 27) (n + 26) 3 2 (2024858 n + 105002187 n + 1813817581 n + 10444068636) a(n + 17) + 1/6 ------------------------------------------------------------------ (n + 30) (n + 27) (n + 26) 3 2 (612599 n + 23164587 n + 245061388 n + 487915356) a(n + 18) - 1/6 ------------------------------------------------------------- (n + 30) (n + 27) (n + 26) 3 2 (224713 n + 3243750 n - 116308663 n - 1831536384) a(n + 19) + 1/6 ------------------------------------------------------------- (n + 30) (n + 27) (n + 26) 3 2 (1221203 n + 65969271 n + 1176816724 n + 6923875920) a(n + 20) - 1/6 ---------------------------------------------------------------- (n + 30) (n + 27) (n + 26) 3 2 (19805 n + 936023 n + 13797168 n + 60437330) a(n + 21) + -------------------------------------------------------- (n + 30) (n + 27) (n + 26) 3 2 (180161 n + 11033610 n + 223846657 n + 1503568338) a(n + 22) + 1/3 -------------------------------------------------------------- (n + 30) (n + 27) (n + 26) 3 2 (26023 n + 1448122 n + 25699187 n + 141849684) a(n + 23) - 1/2 ---------------------------------------------------------- (n + 30) (n + 27) (n + 26) 3 2 (3505 n + 97761 n - 1115620 n - 34587888) a(n + 24) + 1/6 ----------------------------------------------------- (n + 30) (n + 27) (n + 26) 3 2 (21242 n + 1541241 n + 37225285 n + 299307078) a(n + 25) - 1/3 ---------------------------------------------------------- (n + 30) (n + 27) (n + 26) 3 2 (5422 n + 404321 n + 10038311 n + 82984162) a(n + 26) + ------------------------------------------------------- (n + 30) (n + 27) (n + 26) 3 2 (1763 n + 134989 n + 3441096 n + 29207292) a(n + 27) - ------------------------------------------------------ (n + 30) (n + 27) (n + 26) 3 2 2 (151 n + 11878 n + 311023 n + 2711280) a(n + 28) + ---------------------------------------------------- = 0 (n + 30) (n + 27) (n + 26) Subject to the initial conditions a(1) = 0, a(2) = 0, a(3) = 0, a(4) = 1, a(5) = 8, a(6) = 48, a(7) = 255, a(8) = 1270, a(9) = 6070, a(10) = 28200, a(11) = 128325, a(12) = 574783, a(13) = 2542623, a(14) = 11134795, a(15) = 48358159, a(16) = 208557229, a(17) = 894128382, a(18) = 3813741038, a(19) = 16194492727, a(20) = 68498954831, a(21) = 288732798250, a(22) = 1213297472603, a(23) = 5084352959226, a(24) = 21252952828920, a(25) = 88637913601987, a(26) = 368913333979553, a(27) = 1532535138655173, a(28) = 6355431853790290, a(29) = 26314042935687968, a(30) = 108790406926815539 Lemma , 9.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, 1]}, then , {[1, 2, 1, 3]} b(n) satisfies the following linear recurrence equation with polynomial coef\ ficients of order, 15 64 (n + 1) (n + 2) b(n) 16 (5 n + 17) (n + 2) b(n + 1) - ----------------------- - ------------------------------ (n + 15) (n + 11) (n + 15) (n + 11) 2 108 (n + 3) (n + 2) b(n + 2) (157 n + 3033 n + 9686) b(n + 3) - ---------------------------- + --------------------------------- (n + 15) (n + 11) (n + 15) (n + 11) 2 2 (40 n + 1216 n + 5299) b(n + 4) + ---------------------------------- (n + 15) (n + 11) 2 (1645 n + 25607 n + 96350) b(n + 5) + 1/4 ------------------------------------ (n + 15) (n + 11) 2 (2577 n + 35795 n + 125774) b(n + 6) + 1/4 ------------------------------------- (n + 15) (n + 11) 2 (465 n + 7013 n + 26250) b(n + 7) + 3/2 ---------------------------------- (n + 15) (n + 11) 2 2 (733 n + 11237 n + 40832) b(n + 8) (45 n + 444 n - 623) b(n + 9) + 1/2 ----------------------------------- + ------------------------------ (n + 15) (n + 11) (n + 15) (n + 11) 2 (348 n + 6057 n + 25198) b(n + 10) - 1/2 ----------------------------------- (n + 15) (n + 11) 2 (93 n + 2204 n + 12787) b(n + 11) - 1/2 ---------------------------------- (n + 15) (n + 11) 2 (23 n + 560 n + 3264) b(n + 12) - 1/2 -------------------------------- (n + 15) (n + 11) 2 (147 n + 3547 n + 20980) b(n + 13) + 1/4 ----------------------------------- (n + 15) (n + 11) 2 (45 n + 1127 n + 6910) b(n + 14) - 1/4 --------------------------------- + b(n + 15) = 0 (n + 15) (n + 11) Subject to the initial conditions b(1) = 0, b(2) = 0, b(3) = 0, b(4) = 1, b(5) = 7, b(6) = 40, b(7) = 207, b(8) = 1016, b(9) = 4808, b(10) = 22181, b(11) = 100416, b(12) = 448015, b(13) = 1975813, b(14) = 8631727, b(15) = 37414927 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 1.3 1/2 - ---- 1/2 n The probability of Bob winning the bet, as n grows larger is approximately 2.6 1/2 - ---- 1/2 n You can see that indeed Alice has a better chance, but not significantly so. ----------------------------------------- This took, 44.605, seconds to generate ----------------------------------------------------------------------------\ ----------------------- Question Mumber, 10, : If Alice bets that there are more occurrences of conse\ cutive substrings in, {[2, 1, 1, 3]}, than in, {[1, 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 , 10.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, 1, 3]}, then , {[1, 1, 1, 1]} a(n) satisfies the following linear recurrence equation with polynomial coef\ ficients of order, 36 3 2 (910277 n + 65810814 n + 1583617492 n + 12683834568) a(n + 24) -2/3 ---------------------------------------------------------------- (n + 33) (n + 32) (n + 36) 3 2 (553961 n + 46100427 n + 1262434690 n + 11404938456) a(n + 25) - 1/6 ---------------------------------------------------------------- (n + 33) (n + 32) (n + 36) 3 2 (336218 n + 25097157 n + 623671759 n + 5159710962) a(n + 26) + 1/3 -------------------------------------------------------------- (n + 33) (n + 32) (n + 36) 3 2 (453029 n + 36267897 n + 966969982 n + 8587183560) a(n + 27) + 1/6 -------------------------------------------------------------- (n + 33) (n + 32) (n + 36) 3 2 (4085 n + 397992 n + 12581719 n + 129979836) a(n + 28) + 4/3 -------------------------------------------------------- (n + 33) (n + 32) (n + 36) 3 2 (20573 n + 1713633 n + 47566928 n + 440140552) a(n + 29) - ---------------------------------------------------------- (n + 33) (n + 32) (n + 36) 3 2 (1765 n + 186348 n + 6318995 n + 69498858) a(n + 30) - 2/3 ------------------------------------------------------ (n + 33) (n + 32) (n + 36) 3 2 (3191 n + 276297 n + 7940536 n + 75710712) a(n + 31) + 1/3 ------------------------------------------------------ (n + 33) (n + 32) (n + 36) 3 2 4 (428 n + 40297 n + 1263452 n + 13192024) a(n + 32) + ------------------------------------------------------ (n + 33) (n + 32) (n + 36) 3 2 2 (505 n + 48041 n + 1522224 n + 16066068) a(n + 33) - ------------------------------------------------------ (n + 33) (n + 32) (n + 36) 3 2 (227 n + 22001 n + 710168 n + 7634964) a(n + 34) + -------------------------------------------------- + a(n + 36) (n + 33) (n + 32) (n + 36) 2 108 (n + 5) (492 n + 1745 n + 1508) a(n + 1) + --------------------------------------------- (n + 33) (n + 32) (n + 36) 2 18 (n + 6) (14581 n + 81411 n + 112268) a(n + 2) + ------------------------------------------------- (n + 33) (n + 32) (n + 36) 3024 (n + 4) (2 n + 1) (n + 1) a(n) + ----------------------------------- (n + 33) (n + 32) (n + 36) 2 2 (12 n + 803 n + 13401) a(n + 35) - ----------------------------------- (n + 36) (n + 33) 3 2 18 (49415 n + 731832 n + 3411625 n + 5088888) a(n + 3) + -------------------------------------------------------- (n + 33) (n + 32) (n + 36) 3 2 9 (253463 n + 4646469 n + 26994236 n + 50408816) a(n + 4) + ----------------------------------------------------------- (n + 33) (n + 32) (n + 36) 3 2 3 (1534820 n + 34381005 n + 242891461 n + 550319544) a(n + 5) + --------------------------------------------------------------- (n + 33) (n + 32) (n + 36) 3 2 (4904605 n + 134538747 n + 1142764034 n + 3084247800) a(n + 6) + 3/2 ---------------------------------------------------------------- (n + 33) (n + 32) (n + 36) 3 2 3 (2978467 n + 103751211 n + 1066356426 n + 3409132208) a(n + 7) + ------------------------------------------------------------------ (n + 33) (n + 32) (n + 36) 3 2 (13323175 n + 705353007 n + 9213706034 n + 35410186896) a(n + 8) + 1/2 ------------------------------------------------------------------ (n + 33) (n + 32) (n + 36) 3 2 (2073341 n - 207879835 n - 4585372472 n - 22900062632) a(n + 9) - ----------------------------------------------------------------- (n + 33) (n + 32) (n + 36) 3 2 (36157055 n + 452912581 n - 2644534954 n - 35447462720) a(n + 10) - 1/2 ------------------------------------------------------------------- (n + 33) (n + 32) (n + 36) 3 2 (38534220 n + 943371009 n + 6278760377 n + 6327118614) a(n + 11) - ------------------------------------------------------------------ - (n + 33) (n + 32) (n + 36) 3 2 (114722165 n + 3548652935 n + 34602688844 n + 102786259520) a(n + 12) 1/2 ----------------------------------------------------------------------- (n + 33) (n + 32) (n + 36) - 3 2 (134878901 n + 4840777033 n + 56548202208 n + 213707611800) a(n + 13) 1/2 ----------------------------------------------------------------------- (n + 33) (n + 32) (n + 36) - 1/6 3 2 (387031079 n + 15593119641 n + 206777875930 n + 901571113584) a(n + 14) ------------------------------------------------------------------------- (n + 33) (n + 32) (n + 36) - 3 2 (99081237 n + 4412366113 n + 64978608786 n + 316528203032) a(n + 15) 1/2 ---------------------------------------------------------------------- (n + 33) (n + 32) (n + 36) - 3 2 (56805607 n + 2783496343 n + 45182798494 n + 243187843872) a(n + 16) 1/2 ---------------------------------------------------------------------- (n + 33) (n + 32) (n + 36) - 3 2 (17649467 n + 980251601 n + 17964693318 n + 108936922784) a(n + 17) 1/2 --------------------------------------------------------------------- (n + 33) (n + 32) (n + 36) + 3 2 (22385159 n + 1050387147 n + 15895762432 n + 76066716300) a(n + 18) 1/6 --------------------------------------------------------------------- (n + 33) (n + 32) (n + 36) + 3 2 (15768137 n + 886114291 n + 16513450260 n + 101949366164) a(n + 19) 1/2 --------------------------------------------------------------------- (n + 33) (n + 32) (n + 36) + 3 2 (37344331 n + 2272906881 n + 45944216192 n + 308358271632) a(n + 20) 1/6 ---------------------------------------------------------------------- (n + 33) (n + 32) (n + 36) + 3 2 (15618713 n + 1032531159 n + 22646294914 n + 164831407104) a(n + 21) 1/6 ---------------------------------------------------------------------- (n + 33) (n + 32) (n + 36) 3 2 (68361 n - 596853 n - 126808928 n - 1773687812) a(n + 22) - ----------------------------------------------------------- (n + 33) (n + 32) (n + 36) 3 2 (1802731 n + 121138687 n + 2706293254 n + 20094505624) a(n + 23) - 1/2 ------------------------------------------------------------------ (n + 33) (n + 32) (n + 36) = 0 Subject to the initial conditions a(1) = 0, a(2) = 0, a(3) = 0, a(4) = 1, a(5) = 8, a(6) = 48, a(7) = 256, a(8) = 1277, a(9) = 6110, a(10) = 28408, a(11) = 129344, a(12) = 579592, a(13) = 2564731, a(14) = 11234478, a(15) = 48800960, a(16) = 210501034, a(17) = 902579543, a(18) = 3850192526, a(19) = 16350662076, a(20) = 69164204461, a(21) = 291552617679, a(22) = 1225198388014, a(23) = 5134389479233, a(24) = 21462619085379, a(25) = 89513828148255, a(26) = 372562720056906, a(27) = 1547702728750779, a(28) = 6418331781338985, a(29) = 26574361788978931, a(30) = 109865775565226987, a(31) = 453594697853595662, a(32) = 1870344326466163943, a(33) = 7703019891685620409, a(34) = 31689865985692654997, a(35) = 130235846955517346154, a(36) = 534711344988902718947 Lemma , 10.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, 1]}, then , {[2, 1, 1, 3]} b(n) satisfies the following linear recurrence equation with polynomial coef\ ficients of order, 11 2 18 (n + 1) (2 n + 1) b(n) (28 n + 103 n + 91) b(n + 1) ------------------------- + 9/2 ----------------------------- (n + 11) (n + 7) (n + 11) (n + 7) 2 (129 n + 747 n + 1058) b(n + 2) + 9/4 -------------------------------- (n + 11) (n + 7) 2 3 (103 n + 720 n + 1193) b(n + 3) + ---------------------------------- (n + 11) (n + 7) 2 (175 n + 1529 n + 3120) b(n + 4) + 3/2 --------------------------------- (n + 11) (n + 7) 2 2 (52 n + 557 n + 1301) b(n + 5) (26 n + 381 n + 1546) b(n + 6) + 3/2 ------------------------------- - ------------------------------- (n + 11) (n + 7) (n + 11) (n + 7) 2 2 (58 n + 741 n + 2273) b(n + 7) (31 n + 461 n + 1608) b(n + 8) - ------------------------------- - 3/2 ------------------------------- (n + 11) (n + 7) (n + 11) (n + 7) 2 2 6 (8 n + 127 n + 481) b(n + 9) (49 n + 831 n + 3362) b(n + 10) + ------------------------------- - 1/4 -------------------------------- (n + 11) (n + 7) (n + 11) (n + 7) + b(n + 11) = 0 Subject to the initial conditions b(1) = 0, b(2) = 0, b(3) = 0, b(4) = 1, b(5) = 7, b(6) = 40, b(7) = 208, b(8) = 1022, b(9) = 4841, b(10) = 22349, b(11) = 101228 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 1.3 1/2 - ---- 1/2 n The probability of Bob winning the bet, as n grows larger is approximately 2.6 1/2 - ---- 1/2 n You can see that indeed Alice has a better chance, but not significantly so. ----------------------------------------- This took, 52.077, seconds to generate The best bet against, [1, 1, 1, 1], is a member of, {[1, 1, 1, 2], [1, 1, 1, 3], [1, 1, 1, 4], [2, 1, 1, 1], [3, 1, 1, 1], [4, 1, 1, 1]}, 1.5 and then your edge, if you have n rolls, is approximately, ---- 1/2 n The next best bet is a member of, {[1, 1, 2, 1], [1, 1, 2, 2], [1, 1, 2, 3], [1, 1, 2, 4], [1, 1, 3, 1], [1, 1, 3, 2], [1, 1, 3, 3], [1, 1, 3, 4], [1, 1, 4, 1], [1, 1, 4, 2], [1, 1, 4, 3], [1, 1, 4, 4], [1, 2, 1, 1], [1, 2, 1, 3], [1, 2, 1, 4], [1, 2, 2, 2], [1, 2, 2, 3], [1, 2, 2, 4], [1, 2, 3, 2], [1, 2, 3, 3], [1, 2, 3, 4], [1, 2, 4, 2], [1, 2, 4, 3], [1, 2, 4, 4], [1, 3, 1, 1], [1, 3, 1, 2], [1, 3, 1, 4], [1, 3, 2, 2], [1, 3, 2, 3], [1, 3, 2, 4], [1, 3, 3, 2], [1, 3, 3, 3], [1, 3, 3, 4], [1, 3, 4, 2], [1, 3, 4, 3], [1, 3, 4, 4], [1, 4, 1, 1], [1, 4, 1, 2], [1, 4, 1, 3], [1, 4, 2, 2], [1, 4, 2, 3], [1, 4, 2, 4], [1, 4, 3, 2], [1, 4, 3, 3], [1, 4, 3, 4], [1, 4, 4, 2], [1, 4, 4, 3], [1, 4, 4, 4], [2, 1, 1, 2], [2, 1, 1, 3], [2, 1, 1, 4], [2, 1, 2, 2], [2, 1, 2, 3], [2, 1, 2, 4], [2, 1, 3, 1], [2, 1, 3, 2], [2, 1, 3, 3], [2, 1, 3, 4], [2, 1, 4, 1], [2, 1, 4, 2], [2, 1, 4, 3], [2, 1, 4, 4], [2, 2, 1, 1], [2, 2, 1, 2], [2, 2, 1, 3], [2, 2, 1, 4], [2, 2, 2, 1], [2, 2, 2, 3], [2, 2, 2, 4], [2, 2, 3, 1], [2, 2, 3, 2], [2, 2, 3, 3], [2, 2, 3, 4], [2, 2, 4, 1], [2, 2, 4, 2], [2, 2, 4, 3], [2, 2, 4, 4], [2, 3, 1, 1], [2, 3, 1, 2], [2, 3, 1, 3], [2, 3, 1, 4], [2, 3, 2, 1], [2, 3, 2, 2], [2, 3, 2, 4], [2, 3, 3, 1], [2, 3, 3, 2], [2, 3, 3, 3], [2, 3, 3, 4], [2, 3, 4, 1], [2, 3, 4, 2], [2, 3, 4, 3], [2, 3, 4, 4], [2, 4, 1, 1], [2, 4, 1, 2], [2, 4, 1, 3], [2, 4, 1, 4], [2, 4, 2, 1], [2, 4, 2, 2], [2, 4, 2, 3], [2, 4, 3, 1], [2, 4, 3, 2], [2, 4, 3, 3], [2, 4, 3, 4], [2, 4, 4, 1], [2, 4, 4, 2], [2, 4, 4, 3], [2, 4, 4, 4], [3, 1, 1, 2], [3, 1, 1, 3], [3, 1, 1, 4], [3, 1, 2, 1], [3, 1, 2, 2], [3, 1, 2, 3], [3, 1, 2, 4], [3, 1, 3, 2], [3, 1, 3, 3], [3, 1, 3, 4], [3, 1, 4, 1], [3, 1, 4, 2], [3, 1, 4, 3], [3, 1, 4, 4], [3, 2, 1, 1], [3, 2, 1, 2], [3, 2, 1, 3], [3, 2, 1, 4], [3, 2, 2, 1], [3, 2, 2, 2], [3, 2, 2, 3], [3, 2, 2, 4], [3, 2, 3, 1], [3, 2, 3, 3], [3, 2, 3, 4], [3, 2, 4, 1], [3, 2, 4, 2], [3, 2, 4, 3], [3, 2, 4, 4], [3, 3, 1, 1], [3, 3, 1, 2], [3, 3, 1, 3], [3, 3, 1, 4], [3, 3, 2, 1], [3, 3, 2, 2], [3, 3, 2, 3], [3, 3, 2, 4], [3, 3, 3, 1], [3, 3, 3, 2], [3, 3, 3, 4], [3, 3, 4, 1], [3, 3, 4, 2], [3, 3, 4, 3], [3, 3, 4, 4], [3, 4, 1, 1], [3, 4, 1, 2], [3, 4, 1, 3], [3, 4, 1, 4], [3, 4, 2, 1], [3, 4, 2, 2], [3, 4, 2, 3], [3, 4, 2, 4], [3, 4, 3, 1], [3, 4, 3, 2], [3, 4, 3, 3], [3, 4, 4, 1], [3, 4, 4, 2], [3, 4, 4, 3], [3, 4, 4, 4], [4, 1, 1, 2], [4, 1, 1, 3], [4, 1, 1, 4], [4, 1, 2, 1], [4, 1, 2, 2], [4, 1, 2, 3], [4, 1, 2, 4], [4, 1, 3, 1], [4, 1, 3, 2], [4, 1, 3, 3], [4, 1, 3, 4], [4, 1, 4, 2], [4, 1, 4, 3], [4, 1, 4, 4], [4, 2, 1, 1], [4, 2, 1, 2], [4, 2, 1, 3], [4, 2, 1, 4], [4, 2, 2, 1], [4, 2, 2, 2], [4, 2, 2, 3], [4, 2, 2, 4], [4, 2, 3, 1], [4, 2, 3, 2], [4, 2, 3, 3], [4, 2, 3, 4], [4, 2, 4, 1], [4, 2, 4, 3], [4, 2, 4, 4], [4, 3, 1, 1], [4, 3, 1, 2], [4, 3, 1, 3], [4, 3, 1, 4], [4, 3, 2, 1], [4, 3, 2, 2], [4, 3, 2, 3], [4, 3, 2, 4], [4, 3, 3, 1], [4, 3, 3, 2], [4, 3, 3, 3], [4, 3, 3, 4], [4, 3, 4, 1], [4, 3, 4, 2], [4, 3, 4, 4], [4, 4, 1, 1], [4, 4, 1, 2], [4, 4, 1, 3], [4, 4, 1, 4], [4, 4, 2, 1], [4, 4, 2, 2], [4, 4, 2, 3], [4, 4, 2, 4], [4, 4, 3, 1], [4, 4, 3, 2], [4, 4, 3, 3], [4, 4, 3, 4], [4, 4, 4, 1], 1.3 [4, 4, 4, 2], [4, 4, 4, 3]}, and then your edge is approximately, ---- 1/2 n The next best bet is a member of, {[1, 2, 2, 1], [1, 2, 3, 1], [1, 2, 4, 1], [1, 3, 2, 1], [1, 3, 3, 1], [1, 3, 4, 1], [1, 4, 2, 1], [1, 4, 3, 1], 1.2 [1, 4, 4, 1]}, and then your edge is approximately, ---- 1/2 n The next best bet is a member of, {[1, 2, 1, 2], [1, 3, 1, 3], [1, 4, 1, 4], [2, 1, 2, 1], [2, 3, 2, 3], [2, 4, 2, 4], [3, 1, 3, 1], [3, 2, 3, 2], [3, 4, 3, 4], [4, 1, 4, 1], [4, 2, 4, 2], [4, 3, 4, 3]}, 1.0 and then your edge is approximately, ---- 1/2 n The next best bet is a member of, {[2, 2, 2, 2], [3, 3, 3, 3], [4, 4, 4, 4]}, and then your edge is exactly 0 ----------------------- This ends this chapter that took, 587.308, seconds to generate.