The Relative Probablity of Winning a Daniel Litt style game when rolling a f\ air, 2, sides die marked with, {1, 2}, of number of occurrences of, [1, 1, 1, 1, 1], Versus the number of occurences of all, 5, letter words in, {1, 2} By Shalosh B. Ekhad ----------------------------------------------------------------------------\ ----------------------- Question Mumber, 1, : If Alice bets that there are more occurrences of consec\ utive substrings in, {[1, 1, 2, 1, 1]}, than in, {[1, 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 , 1.1, : Let a(n) be the number of words of length n in the alphabet , {1, 2}, with more occurences of, {[1, 1, 2, 1, 1]}, then , {[1, 1, 1, 1, 1]} a(n) satisfies the following linear recurrence equation with polynomial coef\ ficients of order, 38 2 (n + 3) (200 n + 3167 n + 9264) a(n + 2) 6/5 ----------------------------------------- (n + 33) (n + 38) (n + 34) 2 (40 n + 3293 n + 63699) a(n + 34) - 2/5 ---------------------------------- (n + 38) (n + 33) 2 (6 n + 423 n + 7432) a(n + 37) (n + 1) (n + 2) (n + 3) a(n) - 6/5 ------------------------------- - 192/5 ---------------------------- (n + 38) (n + 34) (n + 33) (n + 38) (n + 34) (33 n + 79) (n + 3) (n + 2) a(n + 1) - 24/5 ------------------------------------ + a(n + 38) (n + 33) (n + 38) (n + 34) 3 2 (5211 n + 126577 n - 1535262 n - 38983164) a(n + 21) + 3/10 ------------------------------------------------------ (n + 33) (n + 38) (n + 34) 3 2 (14904 n + 957935 n + 19991960 n + 134604588) a(n + 22) + 3/5 --------------------------------------------------------- (n + 33) (n + 38) (n + 34) 3 2 (8065 n + 807927 n + 23735972 n + 215544168) a(n + 23) + 1/5 -------------------------------------------------------- (n + 33) (n + 38) (n + 34) 3 2 (1087 n + 74596 n + 1651898 n + 11713564) a(n + 24) - 12/5 ----------------------------------------------------- (n + 33) (n + 38) (n + 34) 3 2 (8143 n + 919203 n + 29587844 n + 291312408) a(n + 25) - 1/10 -------------------------------------------------------- (n + 33) (n + 38) (n + 34) 3 2 (2767 n + 184887 n + 3864368 n + 24267356) a(n + 26) + 3/10 ------------------------------------------------------ (n + 33) (n + 38) (n + 34) 3 2 (595 n - 59133 n - 3927082 n - 50952648) a(n + 27) - 1/10 ---------------------------------------------------- (n + 33) (n + 38) (n + 34) 3 2 (1575 n + 112901 n + 2623682 n + 19571936) a(n + 28) - 3/5 ------------------------------------------------------ (n + 33) (n + 38) (n + 34) 3 2 (988 n + 73719 n + 1840829 n + 15481002) a(n + 29) + 2/5 ---------------------------------------------------- (n + 33) (n + 38) (n + 34) 3 2 (2135 n + 148137 n + 3216790 n + 20936568) a(n + 30) + 1/10 ------------------------------------------------------ (n + 33) (n + 38) (n + 34) 3 2 (316 n + 23235 n + 570671 n + 4777014) a(n + 31) - 1/5 -------------------------------------------------- (n + 33) (n + 38) (n + 34) 3 2 (373 n + 35853 n + 1144658 n + 12140592) a(n + 32) + 1/10 ---------------------------------------------------- (n + 33) (n + 38) (n + 34) 3 2 (97 n + 7740 n + 196133 n + 1531938) a(n + 33) - 2/5 ------------------------------------------------ (n + 33) (n + 38) (n + 34) 3 2 (17 n + 1629 n + 51838 n + 547656) a(n + 35) + 1/5 ---------------------------------------------- (n + 33) (n + 38) (n + 34) 3 2 (71 n + 7305 n + 250168 n + 2851824) a(n + 36) + 1/5 ------------------------------------------------ (n + 33) (n + 38) (n + 34) 3 2 (19030 n + 321057 n + 1718237 n + 2952564) a(n + 3) + 1/5 ----------------------------------------------------- (n + 33) (n + 38) (n + 34) 3 2 (63712 n + 1224369 n + 7585409 n + 15270744) a(n + 4) + 1/5 ------------------------------------------------------- (n + 33) (n + 38) (n + 34) 3 2 (30691 n + 653573 n + 4504746 n + 10106510) a(n + 5) + 3/5 ------------------------------------------------------ (n + 33) (n + 38) (n + 34) 3 2 (16855 n + 273573 n + 1055988 n - 371188) a(n + 6) + 3/10 ---------------------------------------------------- (n + 33) (n + 38) (n + 34) 3 2 (183865 n + 5880147 n + 59371220 n + 193238028) a(n + 7) - 1/10 ---------------------------------------------------------- (n + 33) (n + 38) (n + 34) 3 2 (94483 n + 3377403 n + 37375295 n + 131420676) a(n + 8) - 1/5 --------------------------------------------------------- (n + 33) (n + 38) (n + 34) 3 2 (9693 n + 260467 n + 2703462 n + 11432692) a(n + 9) + 3/10 ----------------------------------------------------- (n + 33) (n + 38) (n + 34) 3 2 (12318 n + 749201 n + 11857150 n + 56614368) a(n + 10) + 3/5 -------------------------------------------------------- (n + 33) (n + 38) (n + 34) 3 2 (20639 n + 199734 n - 3887291 n - 39801672) a(n + 11) - 2/5 ------------------------------------------------------- (n + 33) (n + 38) (n + 34) 3 2 (12329 n + 353295 n + 1071676 n - 17540904) a(n + 12) - 1/5 ------------------------------------------------------- (n + 33) (n + 38) (n + 34) 3 2 (86089 n + 3480593 n + 48924236 n + 238632192) a(n + 13) + 3/10 ---------------------------------------------------------- (n + 33) (n + 38) (n + 34) 3 2 (286489 n + 13894821 n + 226174280 n + 1235122956) a(n + 14) + 1/10 -------------------------------------------------------------- (n + 33) (n + 38) (n + 34) 3 2 (9679 n + 3401 n - 6611832 n - 67684256) a(n + 15) - 3/10 ---------------------------------------------------- (n + 33) (n + 38) (n + 34) 3 2 (93473 n + 5245212 n + 98837191 n + 623924412) a(n + 16) - 1/5 ---------------------------------------------------------- (n + 33) (n + 38) (n + 34) 3 2 (2849 n + 384369 n + 11339392 n + 96374526) a(n + 17) - ------------------------------------------------------- (n + 33) (n + 38) (n + 34) 3 2 (24428 n + 1326246 n + 22183327 n + 109756254) a(n + 18) + 1/5 ---------------------------------------------------------- (n + 33) (n + 38) (n + 34) 3 2 (54851 n + 1844859 n + 6915850 n - 159750336) a(n + 19) - 1/10 --------------------------------------------------------- (n + 33) (n + 38) (n + 34) 3 2 (98503 n + 5700567 n + 103996760 n + 582342360) a(n + 20) - 1/10 ----------------------------------------------------------- = 0 (n + 33) (n + 38) (n + 34) Subject to the initial conditions a(1) = 0, a(2) = 0, a(3) = 0, a(4) = 0, a(5) = 1, a(6) = 4, a(7) = 12, a(8) = 29, a(9) = 67, a(10) = 151, a(11) = 340, a(12) = 753, a(13) = 1642, a(14) = 3527, a(15) = 7512, a(16) = 15900, a(17) = 33489, a(18) = 70166, a(19) = 146319, a(20) = 303882, a(21) = 629064, a(22) = 1298536, a(23) = 2673638, a(24) = 5491886, a(25) = 11256887, a(26) = 23030131, a(27) = 47037780, a(28) = 95925934, a(29) = 195352928, a(30) = 397328074, a(31) = 807185515, a(32) = 1638085456, a(33) = 3321065313, a(34) = 6727120607, a(35) = 13615136605, a(36) = 27534895202, a(37) = 55646635363, a(38) = 112385789754 Lemma , 1.2, : Let b(n) be the number of words of length n in the alphabet , {1, 2}, with more occurences of, {[1, 1, 1, 1, 1]}, then , {[1, 1, 2, 1, 1]} b(n) satisfies the following linear recurrence equation with polynomial coef\ ficients of order, 24 2 (n + 3) (424 n + 3489 n + 6608) b(n + 2) 4/5 ----------------------------------------- + b(n + 24) (n + 22) (n + 19) (n + 24) (65 n + 271) (n + 3) (n + 2) b(n + 1) + 16/5 ------------------------------------- (n + 22) (n + 19) (n + 24) (n + 1) (n + 2) (n + 3) b(n) + 128/5 ---------------------------- (n + 22) (n + 19) (n + 24) 3 2 (114 n - 269 n - 7513 n - 17892) b(n + 3) - 2/5 ------------------------------------------- (n + 22) (n + 19) (n + 24) 3 2 (616 n + 6183 n + 14783 n - 3192) b(n + 4) - 2/5 -------------------------------------------- (n + 22) (n + 19) (n + 24) 3 2 (493 n + 12579 n + 106438 n + 290850) b(n + 5) + 2/5 ------------------------------------------------ (n + 22) (n + 19) (n + 24) 3 2 (2137 n + 54119 n + 455080 n + 1266812) b(n + 6) + 1/5 -------------------------------------------------- (n + 22) (n + 19) (n + 24) 3 2 (433 n + 13167 n + 124128 n + 374580) b(n + 7) - 1/5 ------------------------------------------------ (n + 22) (n + 19) (n + 24) 3 2 (1929 n + 57952 n + 582762 n + 1957876) b(n + 8) - 2/5 -------------------------------------------------- (n + 22) (n + 19) (n + 24) 3 2 (1727 n + 71379 n + 927788 n + 3871428) b(n + 9) - 1/5 -------------------------------------------------- (n + 22) (n + 19) (n + 24) 3 2 (1016 n + 31656 n + 327515 n + 1123910) b(n + 10) + 2/5 --------------------------------------------------- (n + 22) (n + 19) (n + 24) 3 2 (2419 n + 112369 n + 1649124 n + 7795636) b(n + 11) + 1/5 ----------------------------------------------------- (n + 22) (n + 19) (n + 24) 3 2 (41 n - 7135 n - 218578 n - 1541352) b(n + 12) - 1/5 ------------------------------------------------ (n + 22) (n + 19) (n + 24) 3 2 (857 n + 43151 n + 694738 n + 3623704) b(n + 13) - 2/5 -------------------------------------------------- (n + 22) (n + 19) (n + 24) 3 2 (29 n - 2883 n - 110092 n - 901408) b(n + 14) + 2/5 ----------------------------------------------- (n + 22) (n + 19) (n + 24) 3 2 (326 n + 17973 n + 316997 n + 1809308) b(n + 15) + 2/5 -------------------------------------------------- (n + 22) (n + 19) (n + 24) 3 2 (32 n + 4803 n + 134495 n + 1054652) b(n + 16) + 2/5 ------------------------------------------------ (n + 22) (n + 19) (n + 24) 3 2 (115 n + 6444 n + 118813 n + 722565) b(n + 17) - 4/5 ------------------------------------------------ (n + 22) (n + 19) (n + 24) 3 2 (199 n + 13533 n + 293096 n + 2049972) b(n + 18) - 1/5 -------------------------------------------------- (n + 22) (n + 19) (n + 24) 3 2 (645 n + 37255 n + 714736 n + 4554492) b(n + 19) + 1/5 -------------------------------------------------- (n + 22) (n + 19) (n + 24) 3 2 (39 n + 2256 n + 43486 n + 279300) b(n + 20) - 6/5 ---------------------------------------------- (n + 22) (n + 19) (n + 24) 3 2 (167 n + 9863 n + 193140 n + 1253364) b(n + 21) - 1/5 ------------------------------------------------- (n + 22) (n + 19) (n + 24) 3 2 (79 n + 4811 n + 97255 n + 652398) b(n + 22) + 2/5 ---------------------------------------------- (n + 22) (n + 19) (n + 24) 3 2 (47 n + 2957 n + 61752 n + 427932) b(n + 23) - 1/5 ---------------------------------------------- = 0 (n + 22) (n + 19) (n + 24) Subject to the initial conditions b(1) = 0, b(2) = 0, b(3) = 0, b(4) = 0, b(5) = 1, b(6) = 3, b(7) = 8, b(8) = 18, b(9) = 42, b(10) = 96, b(11) = 218, b(12) = 480, b(13) = 1042, b(14) = 2237, b(15) = 4783, b(16) = 10164, b(17) = 21475, b(18) = 45105, b(19) = 94332, b(20) = 196593, b(21) = 408515, b(22) = 846448, b(23) = 1749245, b(24) = 3606399 This enables us to compute the first, 20000, terms of these sequences The probability of Alice winning the bet, as n grows larger is approximately 0.1509 1/2 - ------ 1/2 n The probability of Bob winning the bet, as n grows larger is approximately 1.06 1/2 - ---- 1/2 n You can see that indeed Alice has a better chance, but not significantly so. ----------------------------------------- This took, 68.114, seconds to generate ----------------------------------------------------------------------------\ ----------------------- Question Mumber, 2, : If Alice bets that there are more occurrences of consec\ utive substrings in, {[1, 2, 1, 2, 1]}, than in, {[1, 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}, with more occurences of, {[1, 2, 1, 2, 1]}, then , {[1, 1, 1, 1, 1]} a(n) satisfies the following linear recurrence equation with polynomial coef\ ficients of order, 46 2 (2 n + 3) (n + 2) (n + 1) a(n) (6 n + 519 n + 11200) a(n + 45) -16/5 ------------------------------ - 6/5 -------------------------------- (n + 42) (n + 41) (n + 46) (n + 46) (n + 42) 3 2 (436 n + 53685 n + 2201501 n + 30065646) a(n + 42) + a(n + 46) + 1/5 ---------------------------------------------------- (n + 42) (n + 41) (n + 46) 3 2 (403 n + 50079 n + 2072978 n + 28584240) a(n + 43) - 1/10 ---------------------------------------------------- (n + 42) (n + 41) (n + 46) 3 2 (50 n + 6309 n + 265126 n + 3710760) a(n + 44) + 2/5 ------------------------------------------------ (n + 42) (n + 41) (n + 46) 3 2 (37733 n + 3938869 n + 113459156 n + 996370504) a(n + 21) - 3/10 ----------------------------------------------------------- (n + 42) (n + 41) (n + 46) 3 2 (520663 n + 30711675 n + 573893960 n + 3291032940) a(n + 22) + 1/10 -------------------------------------------------------------- (n + 42) (n + 41) (n + 46) 3 2 (1206275 n + 81268107 n + 1808282986 n + 13262537184) a(n + 23) - 1/10 ----------------------------------------------------------------- (n + 42) (n + 41) (n + 46) 3 2 (98452 n + 6069577 n + 118031741 n + 696745536) a(n + 24) + 3/5 ----------------------------------------------------------- (n + 42) (n + 41) (n + 46) 3 2 (1181177 n + 79348881 n + 1741786480 n + 12403237128) a(n + 25) - 1/10 ----------------------------------------------------------------- (n + 42) (n + 41) (n + 46) 3 2 (611125 n + 39874791 n + 829637126 n + 5353150176) a(n + 26) + 1/10 -------------------------------------------------------------- (n + 42) (n + 41) (n + 46) 3 2 (158209 n + 8835129 n + 129324722 n + 166466550) a(n + 27) - 1/5 ------------------------------------------------------------ (n + 42) (n + 41) (n + 46) 3 2 (105052 n + 5140665 n + 43694738 n - 498341208) a(n + 28) + 1/5 ----------------------------------------------------------- (n + 42) (n + 41) (n + 46) 3 2 (73045 n + 7384659 n + 242810762 n + 2611943706) a(n + 29) + 2/5 ------------------------------------------------------------ (n + 42) (n + 41) (n + 46) 3 2 (158179 n + 15605154 n + 507144461 n + 5438368134) a(n + 30) - 1/5 -------------------------------------------------------------- (n + 42) (n + 41) (n + 46) 3 2 (396217 n + 37988541 n + 1207958666 n + 12741520992) a(n + 31) + 1/10 ---------------------------------------------------------------- (n + 42) (n + 41) (n + 46) 3 2 (17695 n + 1673557 n + 52691412 n + 552229957) a(n + 32) - 12/5 ---------------------------------------------------------- (n + 42) (n + 41) (n + 46) 3 2 (150253 n + 14427642 n + 461247605 n + 4909093266) a(n + 33) + 1/5 -------------------------------------------------------------- (n + 42) (n + 41) (n + 46) 3 2 (238601 n + 23182347 n + 749417056 n + 8060389140) a(n + 34) - 1/10 -------------------------------------------------------------- (n + 42) (n + 41) (n + 46) 3 2 (156121 n + 15283971 n + 497529524 n + 5385318960) a(n + 35) + 1/10 -------------------------------------------------------------- (n + 42) (n + 41) (n + 46) 3 2 (82535 n + 8190897 n + 269913922 n + 2952888384) a(n + 36) - 1/10 ------------------------------------------------------------ (n + 42) (n + 41) (n + 46) 3 2 (7772 n + 782663 n + 26125375 n + 288931710) a(n + 37) + 3/5 -------------------------------------------------------- (n + 42) (n + 41) (n + 46) 3 2 (18895 n + 1893717 n + 62588504 n + 680872980) a(n + 38) - 1/10 ---------------------------------------------------------- (n + 42) (n + 41) (n + 46) 3 2 (5195 n + 505539 n + 15949282 n + 161352888) a(n + 39) + 1/10 -------------------------------------------------------- (n + 42) (n + 41) (n + 46) 3 2 (193 n + 16586 n + 415891 n + 2456424) a(n + 40) - 3/5 -------------------------------------------------- (n + 42) (n + 41) (n + 46) 3 2 (275 n + 36477 n + 1593706 n + 22976104) a(n + 41) - 3/10 ---------------------------------------------------- (n + 42) (n + 41) (n + 46) 3 2 (44 n + 549 n + 2173 n + 2760) a(n + 2) + 8/5 ----------------------------------------- (n + 42) (n + 41) (n + 46) 3 2 (165 n + 2654 n + 13503 n + 22084) a(n + 3) + 12/5 --------------------------------------------- (n + 42) (n + 41) (n + 46) 3 2 (839 n + 12723 n + 58204 n + 76728) a(n + 4) + 2/5 ---------------------------------------------- (n + 42) (n + 41) (n + 46) 3 2 (2819 n + 60639 n + 433216 n + 1021512) a(n + 5) + 2/5 -------------------------------------------------- (n + 42) (n + 41) (n + 46) 3 2 (9100 n + 227403 n + 1888481 n + 5199318) a(n + 6) + 2/5 ---------------------------------------------------- (n + 42) (n + 41) (n + 46) 3 2 (12661 n + 358962 n + 3429089 n + 10951146) a(n + 7) + 2/5 ------------------------------------------------------ (n + 42) (n + 41) (n + 46) 3 2 (51181 n + 1641258 n + 17404553 n + 61091232) a(n + 8) + 1/5 -------------------------------------------------------- (n + 42) (n + 41) (n + 46) 3 2 (87817 n + 2578593 n + 24853448 n + 78659880) a(n + 9) + 1/10 -------------------------------------------------------- (n + 42) (n + 41) (n + 46) 3 2 (47653 n + 673251 n - 4829314 n - 71244288) a(n + 10) + 1/10 ------------------------------------------------------- (n + 42) (n + 41) (n + 46) 3 2 (1098 n + 266483 n + 6644177 n + 43337828) a(n + 11) - 3/5 ------------------------------------------------------ (n + 42) (n + 41) (n + 46) 3 2 (20905 n + 1241397 n + 22236600 n + 125317504) a(n + 12) - 9/10 ---------------------------------------------------------- (n + 42) (n + 41) (n + 46) 3 2 (252431 n + 11219865 n + 169211926 n + 862585224) a(n + 13) - 1/10 ------------------------------------------------------------- (n + 42) (n + 41) (n + 46) 3 2 (35517 n + 1632366 n + 22945661 n + 96660890) a(n + 14) - 3/5 --------------------------------------------------------- (n + 42) (n + 41) (n + 46) 3 2 (47413 n + 946577 n - 9354358 n - 200263004) a(n + 15) - 3/10 -------------------------------------------------------- (n + 42) (n + 41) (n + 46) 3 2 (12678 n + 1983756 n + 60420113 n + 517205660) a(n + 16) + 3/5 ---------------------------------------------------------- (n + 42) (n + 41) (n + 46) 3 2 (556313 n + 33479139 n + 669583666 n + 4458356988) a(n + 17) + 1/10 -------------------------------------------------------------- (n + 42) (n + 41) (n + 46) 3 2 (249646 n + 19401321 n + 465141800 n + 3546159156) a(n + 18) + 1/5 -------------------------------------------------------------- (n + 42) (n + 41) (n + 46) 3 2 (141438 n + 7889725 n + 146046503 n + 894828770) a(n + 19) + 3/5 ------------------------------------------------------------ (n + 42) (n + 41) (n + 46) 3 2 (605623 n + 41143701 n + 906626924 n + 6495222240) a(n + 20) + 1/10 -------------------------------------------------------------- (n + 42) (n + 41) (n + 46) 2 (n + 2) (2 n + 29 n + 63) a(n + 1) + 8/5 ----------------------------------- = 0 (n + 42) (n + 41) (n + 46) Subject to the initial conditions a(1) = 0, a(2) = 0, a(3) = 0, a(4) = 0, a(5) = 1, a(6) = 4, a(7) = 11, a(8) = 28, a(9) = 66, a(10) = 151, a(11) = 341, a(12) = 752, a(13) = 1636, a(14) = 3526, a(15) = 7521, a(16) = 15931, a(17) = 33547, a(18) = 70247, a(19) = 146461, a(20) = 304177, a(21) = 629523, a(22) = 1299054, a(23) = 2673537, a(24) = 5489253, a(25) = 11247004, a(26) = 23000454, a(27) = 46956524, a(28) = 95717427, a(29) = 194840394, a(30) = 396110820, a(31) = 804365599, a(32) = 1631665312, a(33) = 3306655847, a(34) = 6695172593, a(35) = 13545033828, a(36) = 27382451486, a(37) = 55317647264, a(38) = 111680431105, a(39) = 225337488984, a(40) = 454414034344, a(41) = 915902521547, a(42) = 1845193367242, a(43) = 3715729636529, a(44) = 7479442577000, a(45) = 15049757453856, a(46) = 30271654255578 Lemma , 2.2, : Let b(n) be the number of words of length n in the alphabet , {1, 2}, with more occurences of, {[1, 1, 1, 1, 1]}, then , {[1, 2, 1, 2, 1]} b(n) satisfies the following linear recurrence equation with polynomial coef\ ficients of order, 43 3 2 (57823 n + 4229676 n + 103374821 n + 842744754) b(n + 21) b(n + 43) - 2/15 ----------------------------------------------------------- (n + 43) (n + 40) (n + 38) 3 2 (135251 n + 7935363 n + 148422550 n + 862338744) b(n + 22) - 1/15 ------------------------------------------------------------ (n + 43) (n + 40) (n + 38) 3 2 (2365 n + 29294 n - 2834781 n - 52221473) b(n + 23) + 4/5 ----------------------------------------------------- (n + 43) (n + 40) (n + 38) 3 2 (4328 n + 34655 n - 6687274 n - 121032308) b(n + 24) - 2/5 ------------------------------------------------------ (n + 43) (n + 40) (n + 38) 3 2 (60869 n + 3681369 n + 68662972 n + 366312378) b(n + 25) + 2/15 ---------------------------------------------------------- (n + 43) (n + 40) (n + 38) 3 2 (3932 n + 243155 n + 4562450 n + 23276428) b(n + 26) - 6/5 ------------------------------------------------------ (n + 43) (n + 40) (n + 38) 3 2 (28755 n + 2201039 n + 55760726 n + 466941362) b(n + 27) + 2/5 ---------------------------------------------------------- (n + 43) (n + 40) (n + 38) 3 2 (34714 n + 2835648 n + 77125131 n + 698343404) b(n + 28) - 2/5 ---------------------------------------------------------- (n + 43) (n + 40) (n + 38) 3 2 (226307 n + 19613463 n + 565849576 n + 5433426456) b(n + 29) + 1/15 -------------------------------------------------------------- (n + 43) (n + 40) (n + 38) 3 2 (249227 n + 22333317 n + 666442558 n + 6622105080) b(n + 30) - 1/15 -------------------------------------------------------------- (n + 43) (n + 40) (n + 38) 3 2 (18353 n + 1697471 n + 52293382 n + 536547132) b(n + 31) + 4/5 ---------------------------------------------------------- (n + 43) (n + 40) (n + 38) 3 2 (93881 n + 8920419 n + 282308230 n + 2975578524) b(n + 32) - 2/15 ------------------------------------------------------------ (n + 43) (n + 40) (n + 38) 3 2 (36487 n + 3544290 n + 114707849 n + 1236872697) b(n + 33) + 4/15 ------------------------------------------------------------ (n + 43) (n + 40) (n + 38) 3 2 (50449 n + 5014797 n + 166090745 n + 1832870550) b(n + 34) - 2/15 ------------------------------------------------------------ (n + 43) (n + 40) (n + 38) 3 2 (22211 n + 2255729 n + 76321548 n + 860323788) b(n + 35) + 1/5 ---------------------------------------------------------- (n + 43) (n + 40) (n + 38) 3 2 (39385 n + 4084785 n + 141127418 n + 1624342128) b(n + 36) - 1/15 ------------------------------------------------------------ (n + 43) (n + 40) (n + 38) 3 2 (10462 n + 1110279 n + 39243197 n + 461983950) b(n + 37) + 2/15 ---------------------------------------------------------- (n + 43) (n + 40) (n + 38) 3 2 (3469 n + 376703 n + 13621044 n + 164000780) b(n + 38) - 1/5 -------------------------------------------------------- (n + 43) (n + 40) (n + 38) 3 2 (4453 n + 494619 n + 18291548 n + 225213552) b(n + 39) + 1/15 -------------------------------------------------------- (n + 43) (n + 40) (n + 38) 3 2 (1631 n + 185715 n + 7040500 n + 88864056) b(n + 40) - 1/15 ------------------------------------------------------ (n + 43) (n + 40) (n + 38) 3 2 (181 n + 21121 n + 820612 n + 10615852) b(n + 41) + 1/5 --------------------------------------------------- (n + 43) (n + 40) (n + 38) 3 2 (133 n + 15831 n + 627392 n + 8278524) b(n + 42) - 1/15 -------------------------------------------------- (n + 43) (n + 40) (n + 38) 32 (2 n + 3) (n + 2) (n + 1) b(n) + -- ------------------------------ 15 (n + 43) (n + 40) (n + 38) 3 2 16 (44 n + 549 n + 2173 n + 2760) b(n + 2) - -- ----------------------------------------- 15 (n + 43) (n + 40) (n + 38) 3 2 (607 n + 9810 n + 50981 n + 85740) b(n + 3) - 8/15 --------------------------------------------- (n + 43) (n + 40) (n + 38) 3 2 (1197 n + 22577 n + 138596 n + 278040) b(n + 4) - 4/5 ------------------------------------------------- (n + 43) (n + 40) (n + 38) 3 2 (1577 n + 32433 n + 218716 n + 484656) b(n + 5) - 4/5 ------------------------------------------------- (n + 43) (n + 40) (n + 38) 3 2 (5872 n + 122643 n + 846005 n + 1920774) b(n + 6) - 4/15 --------------------------------------------------- (n + 43) (n + 40) (n + 38) 3 2 (3307 n + 85884 n + 749589 n + 2193390) b(n + 7) - 4/5 -------------------------------------------------- (n + 43) (n + 40) (n + 38) 3 2 (12667 n + 321060 n + 2777717 n + 8281920) b(n + 8) - 2/15 ----------------------------------------------------- (n + 43) (n + 40) (n + 38) 3 2 (221 n + 111109 n + 2289880 n + 11927208) b(n + 9) + 1/5 ---------------------------------------------------- (n + 43) (n + 40) (n + 38) 3 2 (5625 n + 265279 n + 4173366 n + 21221504) b(n + 10) + 1/5 ------------------------------------------------------ (n + 43) (n + 40) (n + 38) 3 2 (17836 n + 782691 n + 11241755 n + 53027344) b(n + 11) + 2/5 -------------------------------------------------------- (n + 43) (n + 40) (n + 38) 3 2 (149837 n + 7515225 n + 123271600 n + 661559760) b(n + 12) + 1/15 ------------------------------------------------------------ (n + 43) (n + 40) (n + 38) 3 2 (93423 n + 4636707 n + 76841072 n + 423577512) b(n + 13) + 1/5 ---------------------------------------------------------- (n + 43) (n + 40) (n + 38) 3 2 (340819 n + 18005235 n + 315324272 n + 1830585852) b(n + 14) + 1/15 -------------------------------------------------------------- (n + 43) (n + 40) (n + 38) 3 2 (88073 n + 5120935 n + 97023148 n + 602627284) b(n + 15) + 1/5 ---------------------------------------------------------- (n + 43) (n + 40) (n + 38) 3 2 (337667 n + 18309291 n + 331658866 n + 2005495128) b(n + 16) + 1/15 -------------------------------------------------------------- (n + 43) (n + 40) (n + 38) 3 2 (40159 n + 2745471 n + 57919064 n + 386922162) b(n + 17) + 2/15 ---------------------------------------------------------- (n + 43) (n + 40) (n + 38) 3 2 (29357 n + 1439484 n + 22278700 n + 103566648) b(n + 18) + 2/15 ---------------------------------------------------------- (n + 43) (n + 40) (n + 38) 3 2 (11941 n + 725413 n + 14907424 n + 103667986) b(n + 19) - 4/5 --------------------------------------------------------- (n + 43) (n + 40) (n + 38) 3 2 (27187 n + 1749637 n + 37319156 n + 264176348) b(n + 20) - 2/5 ---------------------------------------------------------- (n + 43) (n + 40) (n + 38) 2 16 (n + 2) (2 n + 29 n + 63) b(n + 1) - -- ----------------------------------- = 0 15 (n + 43) (n + 40) (n + 38) Subject to the initial conditions b(1) = 0, b(2) = 0, b(3) = 0, b(4) = 0, b(5) = 1, b(6) = 3, b(7) = 8, b(8) = 20, b(9) = 46, b(10) = 106, b(11) = 239, b(12) = 525, b(13) = 1145, b(14) = 2469, b(15) = 5273, b(16) = 11200, b(17) = 23635, b(18) = 49620, b(19) = 103761, b(20) = 216107, b(21) = 448624, b(22) = 928677, b(23) = 1917274, b(24) = 3949205, b(25) = 8117809, b(26) = 16654952, b(27) = 34112808, b(28) = 69762704, b(29) = 142467990, b(30) = 290574314, b(31) = 591952645, b(32) = 1204614265, b(33) = 2448944606, b(34) = 4974072392, b(35) = 10094335771, b(36) = 20469318647, b(37) = 41477562193, b(38) = 83990423510, b(39) = 169970448634, b(40) = 343765754637, b(41) = 694887337074, b(42) = 1403926368644, b(43) = 2835088769826 This enables us to compute the first, 20000, terms of these sequences The probability of Alice winning the bet, as n grows larger is approximately 0.2054 1/2 - ------ 1/2 n The probability of Bob winning the bet, as n grows larger is approximately 0.890 1/2 - ----- 1/2 n You can see that indeed Alice has a better chance, but not significantly so. ----------------------------------------- This took, 122.520, seconds to generate ----------------------------------------------------------------------------\ ----------------------- Question Mumber, 3, : If Alice bets that there are more occurrences of consec\ utive substrings in, {[1, 2, 2, 2, 1]}, than in, {[1, 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}, with more occurences of, {[1, 2, 2, 2, 1]}, then , {[1, 1, 1, 1, 1]} a(n) satisfies the following linear recurrence equation with polynomial coef\ ficients of order, 46 (2 n + 3) (n + 2) (n + 1) a(n) a(n + 46) - 16/5 ------------------------------ (n + 42) (n + 41) (n + 46) 2 (n + 2) (2 n + 23 n + 33) a(n + 1) - 8/5 ----------------------------------- (n + 42) (n + 41) (n + 46) 2 (6 n + 519 n + 11200) a(n + 45) - 6/5 -------------------------------- (n + 46) (n + 42) 3 2 (81001 n + 6057771 n + 148836518 n + 1198224048) a(n + 28) - 1/10 ------------------------------------------------------------ (n + 42) (n + 41) (n + 46) 3 2 (32137 n + 2523129 n + 66545420 n + 591175380) a(n + 29) + 1/10 ---------------------------------------------------------- (n + 42) (n + 41) (n + 46) 3 2 (455 n + 33629 n + 925091 n + 9823510) a(n + 30) + 3/5 -------------------------------------------------- (n + 42) (n + 41) (n + 46) 3 2 (375 n - 61695 n - 4590592 n - 71424196) a(n + 31) + 3/10 ---------------------------------------------------- (n + 42) (n + 41) (n + 46) 3 2 (18581 n + 1753236 n + 54505090 n + 557570268) a(n + 32) + 1/5 ---------------------------------------------------------- (n + 42) (n + 41) (n + 46) 3 2 (11677 n + 1142517 n + 37054712 n + 397919844) a(n + 33) - 1/10 ---------------------------------------------------------- (n + 42) (n + 41) (n + 46) 3 2 (1707 n + 126117 n + 2808296 n + 16881492) a(n + 34) - 3/10 ------------------------------------------------------ (n + 42) (n + 41) (n + 46) 3 2 (3517 n + 295401 n + 7711214 n + 59076048) a(n + 35) - 1/10 ------------------------------------------------------ (n + 42) (n + 41) (n + 46) 3 2 (41 n - 5068 n - 494567 n - 9305252) a(n + 36) + 6/5 ------------------------------------------------ (n + 42) (n + 41) (n + 46) 3 2 (4235 n + 399561 n + 12370066 n + 125323920) a(n + 37) - 1/10 -------------------------------------------------------- (n + 42) (n + 41) (n + 46) 3 2 (2077 n + 210816 n + 7080701 n + 78641766) a(n + 38) + 1/5 ------------------------------------------------------ (n + 42) (n + 41) (n + 46) 3 2 (1351 n + 151863 n + 5656034 n + 69774360) a(n + 39) + 1/10 ------------------------------------------------------ (n + 42) (n + 41) (n + 46) 3 2 (667 n + 68859 n + 2326598 n + 25587960) a(n + 40) - 1/5 ---------------------------------------------------- (n + 42) (n + 41) (n + 46) 3 2 (16 n + 1227 n + 21926 n - 60735) a(n + 41) + 4/5 --------------------------------------------- (n + 42) (n + 41) (n + 46) 3 2 (28 n + 3351 n + 133496 n + 1770360) a(n + 42) - 4/5 ------------------------------------------------ (n + 42) (n + 41) (n + 46) 3 2 (3 n + 329 n + 11808 n + 137940) a(n + 43) + 6/5 -------------------------------------------- (n + 42) (n + 41) (n + 46) 3 2 (71 n + 9009 n + 380680 n + 5357040) a(n + 44) + 1/5 ------------------------------------------------ (n + 42) (n + 41) (n + 46) 3 2 (15361 n + 563817 n + 6710726 n + 26019984) a(n + 11) + 1/10 ------------------------------------------------------- (n + 42) (n + 41) (n + 46) 3 2 (2185 n + 94479 n + 1661146 n + 10407088) a(n + 12) - 3/10 ----------------------------------------------------- (n + 42) (n + 41) (n + 46) 3 2 (47785 n + 3358125 n + 68955752 n + 438677532) a(n + 13) - 1/10 ---------------------------------------------------------- (n + 42) (n + 41) (n + 46) 3 2 (7818 n + 404676 n + 6572029 n + 33747270) a(n + 14) + 3/5 ------------------------------------------------------ (n + 42) (n + 41) (n + 46) 3 2 (16675 n + 499629 n + 4605224 n + 13196820) a(n + 15) + 1/10 ------------------------------------------------------- (n + 42) (n + 41) (n + 46) 3 2 (9850 n + 335205 n + 2561068 n - 5046124) a(n + 16) - 3/5 ----------------------------------------------------- (n + 42) (n + 41) (n + 46) 3 2 (14159 n + 691971 n + 3564988 n - 78407076) a(n + 17) - 1/10 ------------------------------------------------------- (n + 42) (n + 41) (n + 46) 3 2 (30503 n + 1385517 n + 16780768 n + 24083124) a(n + 18) - 1/10 --------------------------------------------------------- (n + 42) (n + 41) (n + 46) 3 2 (74875 n + 3755475 n + 62760686 n + 349202400) a(n + 19) - 1/10 ---------------------------------------------------------- (n + 42) (n + 41) (n + 46) 3 2 (66311 n + 3578709 n + 61897420 n + 335444880) a(n + 20) + 1/5 ---------------------------------------------------------- (n + 42) (n + 41) (n + 46) 3 2 (10087 n + 2787585 n + 100442462 n + 966920928) a(n + 21) + 1/10 ----------------------------------------------------------- (n + 42) (n + 41) (n + 46) 3 2 (23557 n + 1343838 n + 24072491 n + 126900810) a(n + 22) + 1/5 ---------------------------------------------------------- (n + 42) (n + 41) (n + 46) 3 2 (67879 n + 4535079 n + 103901942 n + 816450792) a(n + 23) + 1/10 ----------------------------------------------------------- (n + 42) (n + 41) (n + 46) 3 2 (1643 n + 615825 n + 22433002 n + 201324312) a(n + 24) - 1/10 -------------------------------------------------------- (n + 42) (n + 41) (n + 46) 3 2 (3577 n + 472213 n + 18020116 n + 211058716) a(n + 25) - 3/10 -------------------------------------------------------- (n + 42) (n + 41) (n + 46) 3 2 (13883 n + 1109085 n + 28482124 n + 232385388) a(n + 26) - 1/10 ---------------------------------------------------------- (n + 42) (n + 41) (n + 46) 3 2 (4823 n + 269179 n + 5023054 n + 34901296) a(n + 27) - 3/10 ------------------------------------------------------ (n + 42) (n + 41) (n + 46) 3 2 (4 n + 51 n + 224 n + 324) a(n + 2) + 16/5 ------------------------------------- (n + 42) (n + 41) (n + 46) 3 2 (55 n + 819 n + 4484 n + 8316) a(n + 3) - 4/5 ----------------------------------------- (n + 42) (n + 41) (n + 46) 3 2 (599 n + 12207 n + 78688 n + 162684) a(n + 4) + 2/5 ----------------------------------------------- (n + 42) (n + 41) (n + 46) 3 2 (1243 n + 32406 n + 266513 n + 700182) a(n + 5) + 2/5 ------------------------------------------------- (n + 42) (n + 41) (n + 46) 3 2 (1289 n + 34023 n + 282094 n + 749280) a(n + 6) - 2/5 ------------------------------------------------- (n + 42) (n + 41) (n + 46) 3 2 (1167 n + 32635 n + 285808 n + 796836) a(n + 7) + 3/5 ------------------------------------------------- (n + 42) (n + 41) (n + 46) 3 2 (6989 n + 283395 n + 3626758 n + 14819064) a(n + 8) - 1/10 ----------------------------------------------------- (n + 42) (n + 41) (n + 46) 3 2 (19165 n + 740357 n + 9436112 n + 39460420) a(n + 9) + 3/10 ------------------------------------------------------ (n + 42) (n + 41) (n + 46) 3 2 (30029 n + 1313823 n + 18075676 n + 79485156) a(n + 10) - 1/10 --------------------------------------------------------- = 0 (n + 42) (n + 41) (n + 46) Subject to the initial conditions a(1) = 0, a(2) = 0, a(3) = 0, a(4) = 0, a(5) = 1, a(6) = 4, a(7) = 12, a(8) = 32, a(9) = 77, a(10) = 179, a(11) = 404, a(12) = 892, a(13) = 1944, a(14) = 4181, a(15) = 8908, a(16) = 18833, a(17) = 39544, a(18) = 82590, a(19) = 171674, a(20) = 355404, a(21) = 733229, a(22) = 1508057, a(23) = 3093431, a(24) = 6330494, a(25) = 12927759, a(26) = 26351325, a(27) = 53623747, a(28) = 108959196, a(29) = 221099621, a(30) = 448111317, a(31) = 907212292, a(32) = 1834853078, a(33) = 3707684547, a(34) = 7485983771, a(35) = 15103273709, a(36) = 30450742161, a(37) = 61355673811, a(38) = 123556219692, a(39) = 248684274991, a(40) = 500293248030, a(41) = 1006029271309, a(42) = 2022188958662, a(43) = 4063236269739, a(44) = 8161584514317, a(45) = 16388554912226, a(46) = 32898894974979 Lemma , 3.2, : Let b(n) be the number of words of length n in the alphabet , {1, 2}, with more occurences of, {[1, 1, 1, 1, 1]}, then , {[1, 2, 2, 2, 1]} b(n) satisfies the following linear recurrence equation with polynomial coef\ ficients of order, 25 2 (n + 2) (14 n + 65 n + 87) b(n + 1) -8/5 ------------------------------------ (n + 20) (n + 25) (n + 24) 2 (n + 6) (481 n + 7203 n + 23918) b(n + 4) + 2/5 ------------------------------------------ + b(n + 25) (n + 20) (n + 25) (n + 24) 2 (2 n + 3) (n + 2) (n + 1) b(n) 9 (n + 43 n + 458) b(n + 24) + 16/5 ------------------------------ - ----------------------------- (n + 20) (n + 25) (n + 24) (n + 25) (n + 20) 3 2 (859 n + 18258 n + 123965 n + 272094) b(n + 5) - 2/5 ------------------------------------------------ (n + 20) (n + 25) (n + 24) 3 2 (871 n + 20397 n + 156698 n + 397608) b(n + 6) + 2/5 ------------------------------------------------ (n + 20) (n + 25) (n + 24) 3 2 (303 n + 7823 n + 66140 n + 183716) b(n + 7) - 3/5 ---------------------------------------------- (n + 20) (n + 25) (n + 24) 3 2 (897 n + 28463 n + 300798 n + 1054824) b(n + 8) - 3/10 ------------------------------------------------- (n + 20) (n + 25) (n + 24) 3 2 (5453 n + 178449 n + 1921996 n + 6824892) b(n + 9) + 1/10 ---------------------------------------------------- (n + 20) (n + 25) (n + 24) 3 2 (5249 n + 180627 n + 2064460 n + 7849476) b(n + 10) - 1/10 ----------------------------------------------------- (n + 20) (n + 25) (n + 24) 3 2 (2543 n + 97251 n + 1234222 n + 5198400) b(n + 11) + 1/10 ---------------------------------------------------- (n + 20) (n + 25) (n + 24) 3 2 (281 n + 14743 n + 250138 n + 1375952) b(n + 12) + 3/10 -------------------------------------------------- (n + 20) (n + 25) (n + 24) 3 2 (2513 n + 141237 n + 2473672 n + 13840644) b(n + 13) - 1/10 ------------------------------------------------------ (n + 20) (n + 25) (n + 24) 3 2 (2683 n + 155361 n + 2817032 n + 16369764) b(n + 14) + 1/10 ------------------------------------------------------ (n + 20) (n + 25) (n + 24) 3 2 (1289 n + 81525 n + 1592182 n + 9896304) b(n + 15) - 1/10 ---------------------------------------------------- (n + 20) (n + 25) (n + 24) 3 2 (71 n + 1713 n + 20386 n + 192216) b(n + 16) - 1/10 ---------------------------------------------- (n + 20) (n + 25) (n + 24) 3 2 (151 n + 13059 n + 324172 n + 2483356) b(n + 17) + 3/10 -------------------------------------------------- (n + 20) (n + 25) (n + 24) 3 2 (563 n + 47625 n + 1183276 n + 9157884) b(n + 18) - 1/10 --------------------------------------------------- (n + 20) (n + 25) (n + 24) 3 2 (87 n + 7723 n + 200534 n + 1619552) b(n + 19) + 3/10 ------------------------------------------------ (n + 20) (n + 25) (n + 24) 3 2 (7 n - 447 n - 26090 n - 286768) b(n + 20) + 3/10 -------------------------------------------- (n + 20) (n + 25) (n + 24) 3 2 (257 n + 16257 n + 339748 n + 2343948) b(n + 21) + 1/10 -------------------------------------------------- (n + 20) (n + 25) (n + 24) 3 2 (161 n + 10163 n + 212712 n + 1474860) b(n + 22) - 3/10 -------------------------------------------------- (n + 20) (n + 25) (n + 24) 3 2 (311 n + 20211 n + 435886 n + 3117576) b(n + 23) + 1/10 -------------------------------------------------- (n + 20) (n + 25) (n + 24) 3 2 (4 n + 9 n - 64 n - 168) b(n + 2) + 16/5 ----------------------------------- (n + 20) (n + 25) (n + 24) 3 2 (n - 15 n - 16 n + 228) b(n + 3) - 4/5 ---------------------------------- = 0 (n + 20) (n + 25) (n + 24) Subject to the initial conditions b(1) = 0, b(2) = 0, b(3) = 0, b(4) = 0, b(5) = 1, b(6) = 3, b(7) = 8, b(8) = 20, b(9) = 46, b(10) = 106, b(11) = 237, b(12) = 521, b(13) = 1135, b(14) = 2439, b(15) = 5206, b(16) = 11034, b(17) = 23241, b(18) = 48735, b(19) = 101730, b(20) = 211582, b(21) = 438652, b(22) = 906748, b(23) = 1869717, b(24) = 3846585, b(25) = 7897590 This enables us to compute the first, 20000, terms of these sequences The probability of Alice winning the bet, as n grows larger is approximately 0.07286 1/2 - ------- 1/2 n The probability of Bob winning the bet, as n grows larger is approximately 1.09 1/2 - ---- 1/2 n You can see that indeed Alice has a better chance, but not significantly so. ----------------------------------------- This took, 85.268, seconds to generate ----------------------------------------------------------------------------\ ----------------------- Question Mumber, 4, : If Alice bets that there are more occurrences of consec\ utive substrings in, {[2, 1, 2, 1, 2]}, than in, {[1, 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}, with more occurences of, {[2, 1, 2, 1, 2]}, then , {[1, 1, 1, 1, 1]} a(n) satisfies the following linear recurrence equation with polynomial coef\ ficients of order, 42 3 2 (1303 n + 41481 n + 274220 n + 477600) a(n + 4) 3/5 ------------------------------------------------- (n + 42) (n + 38) (n + 37) 3 2 (69535 n + 1317881 n + 7816366 n + 14596560) a(n + 5) - 3/10 ------------------------------------------------------- (n + 42) (n + 38) (n + 37) 3 2 (3945 n + 217306 n + 2104581 n + 5503910) a(n + 6) + 3/5 ---------------------------------------------------- (n + 42) (n + 38) (n + 37) 3 2 (171604 n + 4667766 n + 39740747 n + 107440050) a(n + 7) - 2/5 ---------------------------------------------------------- (n + 42) (n + 38) (n + 37) 3 2 (917 n + 1675817 n + 25794712 n + 98176552) a(n + 8) + 3/10 ------------------------------------------------------ (n + 42) (n + 38) (n + 37) 3 2 (912323 n + 35318283 n + 407823244 n + 1466109828) a(n + 9) - 1/10 ------------------------------------------------------------- (n + 42) (n + 38) (n + 37) 3 2 (215663 n - 10785861 n - 272193200 n - 1411053468) a(n + 10) - 1/10 -------------------------------------------------------------- (n + 42) (n + 38) (n + 37) 3 2 (538525 n - 4989795 n - 284200834 n - 1786783332) a(n + 11) + 1/10 ------------------------------------------------------------- (n + 42) (n + 38) (n + 37) 3 2 (323989 n + 1859418 n - 88447855 n - 758283732) a(n + 12) - 2/5 ----------------------------------------------------------- (n + 42) (n + 38) (n + 37) 3 2 (686057 n + 19021568 n + 155631757 n + 323569468) a(n + 13) + 3/5 ------------------------------------------------------------- (n + 42) (n + 38) (n + 37) 3 2 (2136329 n + 55957146 n + 346636132 n - 211887180) a(n + 14) - 1/5 -------------------------------------------------------------- (n + 42) (n + 38) (n + 37) 3 2 (4050865 n + 143275623 n + 1614001304 n + 5689687194) a(n + 15) + 1/5 ----------------------------------------------------------------- (n + 42) (n + 38) (n + 37) 3 2 (4341364 n + 160791405 n + 1876724306 n + 6706813380) a(n + 16) - 1/5 ----------------------------------------------------------------- (n + 42) (n + 38) (n + 37) 3 2 (10630777 n + 439298445 n + 5866881308 n + 25134687180) a(n + 17) + 1/10 ------------------------------------------------------------------- (n + 42) (n + 38) (n + 37) 3 2 (1973437 n + 88188873 n + 1285061955 n + 6090455370) a(n + 18) - 3/5 ---------------------------------------------------------------- (n + 42) (n + 38) (n + 37) 3 2 (5628902 n + 266331819 n + 4111556005 n + 20649812706) a(n + 19) + 1/5 ------------------------------------------------------------------ (n + 42) (n + 38) (n + 37) 3 2 (5821958 n + 297366375 n + 4992840511 n + 27551322396) a(n + 20) - 1/5 ------------------------------------------------------------------ (n + 42) (n + 38) (n + 37) 3 2 (10095565 n + 541080105 n + 9530598584 n + 55137960024) a(n + 21) + 1/10 ------------------------------------------------------------------- (n + 42) (n + 38) (n + 37) 3 2 (1480256 n + 84265923 n + 1581203973 n + 9779742738) a(n + 22) - 3/5 ---------------------------------------------------------------- (n + 42) (n + 38) (n + 37) 3 2 (7442861 n + 445806441 n + 8812693654 n + 57499069368) a(n + 23) + 1/10 ------------------------------------------------------------------ (n + 42) (n + 38) (n + 37) 3 2 (1025 n + 10026 n + 30301 n + 28266) a(n + 3) - 18/5 ----------------------------------------------- (n + 42) (n + 38) (n + 37) 3 2 (2809858 n + 176098077 n + 3643818008 n + 24892803564) a(n + 24) - 1/5 ------------------------------------------------------------------ (n + 42) (n + 38) (n + 37) 3 2 (363368 n + 23956930 n + 522308733 n + 3766060505) a(n + 25) + 6/5 -------------------------------------------------------------- (n + 42) (n + 38) (n + 37) 3 2 (1009989 n + 69258627 n + 1570454626 n + 11775131496) a(n + 26) - 3/10 ----------------------------------------------------------------- (n + 42) (n + 38) (n + 37) 3 2 (1015367 n + 72692919 n + 1722241132 n + 13503309390) a(n + 27) + 1/5 ----------------------------------------------------------------- (n + 42) (n + 38) (n + 37) 3 2 (1336237 n + 99561333 n + 2455962830 n + 20057791992) a(n + 28) - 1/10 ----------------------------------------------------------------- (n + 42) (n + 38) (n + 37) 3 2 (386417 n + 29760927 n + 758660356 n + 6400585056) a(n + 29) + 1/5 -------------------------------------------------------------- (n + 42) (n + 38) (n + 37) 3 2 (447797 n + 35837265 n + 949868146 n + 8337841992) a(n + 30) - 1/10 -------------------------------------------------------------- (n + 42) (n + 38) (n + 37) 3 2 (118402 n + 9756657 n + 266116643 n + 2402087628) a(n + 31) + 1/5 ------------------------------------------------------------- (n + 42) (n + 38) (n + 37) 3 2 (35747 n + 3021289 n + 84439238 n + 780039864) a(n + 32) - 3/10 ---------------------------------------------------------- (n + 42) (n + 38) (n + 37) 3 2 (16419 n + 1428235 n + 41062520 n + 389982196) a(n + 33) + 3/10 ---------------------------------------------------------- (n + 42) (n + 38) (n + 37) 3 2 (16853 n + 1463067 n + 41677732 n + 388380756) a(n + 34) - 1/10 ---------------------------------------------------------- (n + 42) (n + 38) (n + 37) 3 2 (839 n + 67197 n + 1679608 n + 12464832) a(n + 35) + 2/5 ---------------------------------------------------- (n + 42) (n + 38) (n + 37) 3 2 (56 n - 7161 n - 690893 n - 12962484) a(n + 36) - 1/5 ------------------------------------------------- (n + 42) (n + 38) (n + 37) 3 2 (1153 n + 131391 n + 4962434 n + 62136288) a(n + 37) - 1/10 ------------------------------------------------------ (n + 42) (n + 38) (n + 37) 3 2 (152 n + 16811 n + 619143 n + 7593086) a(n + 38) + 3/5 -------------------------------------------------- (n + 42) (n + 38) (n + 37) 3 2 (403 n + 45243 n + 1691690 n + 21067800) a(n + 39) - 1/10 ---------------------------------------------------- (n + 42) (n + 38) (n + 37) 3 2 (50 n + 5709 n + 217054 n + 2748000) a(n + 40) + 2/5 ------------------------------------------------ (n + 42) (n + 38) (n + 37) 2 (n + 1) (43 n - 85 n - 786) a(n + 2) - 36/5 ------------------------------------- (n + 42) (n + 38) (n + 37) (n - 1) n (n + 1) a(n) n (7 n + 17) (n + 1) a(n + 1) - 864/5 -------------------------- - 432/5 ----------------------------- (n + 42) (n + 38) (n + 37) (n + 42) (n + 38) (n + 37) 2 (6 n + 471 n + 9220) a(n + 41) + a(n + 42) - 6/5 ------------------------------- = 0 (n + 38) (n + 42) Subject to the initial conditions a(1) = 0, a(2) = 0, a(3) = 0, a(4) = 0, a(5) = 1, a(6) = 4, a(7) = 11, a(8) = 28, a(9) = 68, a(10) = 157, a(11) = 353, a(12) = 782, a(13) = 1705, a(14) = 3671, a(15) = 7836, a(16) = 16599, a(17) = 34929, a(18) = 73110, a(19) = 152326, a(20) = 316094, a(21) = 653659, a(22) = 1347628, a(23) = 2770898, a(24) = 5683781, a(25) = 11634178, a(26) = 23769019, a(27) = 48478347, a(28) = 98723174, a(29) = 200765471, a(30) = 407768492, a(31) = 827261707, a(32) = 1676567137, a(33) = 3394587526, a(34) = 6867145911, a(35) = 13880984709, a(36) = 28038020574, a(37) = 56595652237, a(38) = 114169621169, a(39) = 230181691070, a(40) = 463834184937, a(41) = 934208508112, a(42) = 1880744370609 Lemma , 4.2, : Let b(n) be the number of words of length n in the alphabet , {1, 2}, with more occurences of, {[1, 1, 1, 1, 1]}, then , {[2, 1, 2, 1, 2]} b(n) satisfies the following linear recurrence equation with polynomial coef\ ficients of order, 39 3 2 (964297 n + 69917937 n + 1684107350 n + 13473435864) b(n + 26) -1/15 ---------------------------------------------------------------- (n + 39) (n + 36) (n + 34) 3 2 (658973 n + 49687059 n + 1244694484 n + 10357065144) b(n + 27) + 1/15 ---------------------------------------------------------------- (n + 39) (n + 36) (n + 34) 3 2 (438035 n + 34359321 n + 895571848 n + 7755089136) b(n + 28) - 1/15 -------------------------------------------------------------- (n + 39) (n + 36) (n + 34) 3 2 (138295 n + 11252502 n + 304295669 n + 2734412508) b(n + 29) + 2/15 -------------------------------------------------------------- (n + 39) (n + 36) (n + 34) 3 2 (81254 n + 6853551 n + 192169912 n + 1790934264) b(n + 30) - 2/15 ------------------------------------------------------------ (n + 39) (n + 36) (n + 34) 3 2 (92513 n + 8080869 n + 234706678 n + 2266466292) b(n + 31) + 1/15 ------------------------------------------------------------ (n + 39) (n + 36) (n + 34) 3 2 (16289 n + 1469707 n + 44104836 n + 440171312) b(n + 32) - 1/5 ---------------------------------------------------------- (n + 39) (n + 36) (n + 34) 3 2 (5950 n + 554541 n + 17194094 n + 177349806) b(n + 33) + 4/15 -------------------------------------------------------- (n + 39) (n + 36) (n + 34) 3 2 (11017 n + 1059417 n + 33900902 n + 360985944) b(n + 34) - 1/15 ---------------------------------------------------------- (n + 39) (n + 36) (n + 34) 3 2 (1505 n + 148943 n + 4905728 n + 53775904) b(n + 35) + 1/5 ------------------------------------------------------ (n + 39) (n + 36) (n + 34) 3 2 (1631 n + 166143 n + 5633068 n + 63569112) b(n + 36) - 1/15 ------------------------------------------------------ (n + 39) (n + 36) (n + 34) 3 2 (181 n + 18949 n + 660332 n + 7659756) b(n + 37) + 1/5 -------------------------------------------------- (n + 39) (n + 36) (n + 34) 3 2 (133 n + 14235 n + 507128 n + 6013740) b(n + 38) - 1/15 -------------------------------------------------- (n + 39) (n + 36) (n + 34) 3 2 (14609 n + 298663 n + 1904738 n + 3749328) b(n + 5) - 1/5 ----------------------------------------------------- (n + 39) (n + 36) (n + 34) 3 2 (15315 n + 259754 n + 1397211 n + 2398714) b(n + 6) + 2/5 ----------------------------------------------------- (n + 39) (n + 36) (n + 34) 3 2 (33017 n + 531993 n + 2622211 n + 3654078) b(n + 7) - 4/15 ----------------------------------------------------- (n + 39) (n + 36) (n + 34) 3 2 (54011 n + 940327 n + 4791700 n + 6094712) b(n + 8) + 1/5 ----------------------------------------------------- (n + 39) (n + 36) (n + 34) 3 2 (55237 n - 2729019 n - 61552444 n - 288926436) b(n + 9) - 1/15 --------------------------------------------------------- (n + 39) (n + 36) (n + 34) 3 2 (288031 n + 5089239 n + 19449776 n - 23998620) b(n + 10) + 1/15 ---------------------------------------------------------- (n + 39) (n + 36) (n + 34) 3 2 (312671 n + 18859155 n + 297217582 n + 1394981460) b(n + 11) + 1/15 -------------------------------------------------------------- (n + 39) (n + 36) (n + 34) 3 2 (3935 n + 3160347 n + 69568582 n + 384028104) b(n + 12) - 2/15 --------------------------------------------------------- (n + 39) (n + 36) (n + 34) 3 2 (299947 n + 14733039 n + 228129236 n + 1131278152) b(n + 13) + 1/5 -------------------------------------------------------------- (n + 39) (n + 36) (n + 34) 3 2 (60662 n + 2829700 n + 42980493 n + 213283842) b(n + 14) - 6/5 ---------------------------------------------------------- (n + 39) (n + 36) (n + 34) 3 2 (281715 n + 13300697 n + 207513596 n + 1069764330) b(n + 15) + 2/5 -------------------------------------------------------------- (n + 39) (n + 36) (n + 34) 3 2 (404039 n + 19274547 n + 305633487 n + 1610827820) b(n + 16) - 2/5 -------------------------------------------------------------- (n + 39) (n + 36) (n + 34) 3 2 (1295938 n + 63605853 n + 1038969119 n + 5648327730) b(n + 17) + 2/15 ---------------------------------------------------------------- (n + 39) (n + 36) (n + 34) 3 2 (528704 n + 27205677 n + 466104202 n + 2659697880) b(n + 18) - 2/5 -------------------------------------------------------------- (n + 39) (n + 36) (n + 34) 3 2 (3156359 n + 168118221 n + 2978646304 n + 17562080340) b(n + 19) + 1/15 ------------------------------------------------------------------ (n + 39) (n + 36) (n + 34) 3 2 (3120247 n + 174585435 n + 3249345488 n + 20124003048) b(n + 20) - 1/15 ------------------------------------------------------------------ (n + 39) (n + 36) (n + 34) 3 2 (740197 n + 43246554 n + 839905700 n + 5423825019) b(n + 21) + 4/15 -------------------------------------------------------------- (n + 39) (n + 36) (n + 34) 3 2 (1266179 n + 77269485 n + 1567013188 n + 10562375280) b(n + 22) - 2/15 ----------------------------------------------------------------- (n + 39) (n + 36) (n + 34) 3 2 (725593 n + 46384611 n + 985238332 n + 6953720152) b(n + 23) + 1/5 -------------------------------------------------------------- (n + 39) (n + 36) (n + 34) 3 2 (1724393 n + 114886407 n + 2542654084 n + 18692646432) b(n + 24) - 1/15 ------------------------------------------------------------------ (n + 39) (n + 36) (n + 34) 3 2 (653069 n + 45444966 n + 1050534835 n + 8066322432) b(n + 25) + 2/15 --------------------------------------------------------------- (n + 39) (n + 36) (n + 34) 3 2 (353 n + 1962 n + 1021 n - 2838) b(n + 3) + 12/5 ------------------------------------------- (n + 39) (n + 36) (n + 34) 3 2 (11801 n + 155223 n + 643492 n + 845184) b(n + 4) + 2/5 --------------------------------------------------- + b(n + 39) (n + 39) (n + 36) (n + 34) (n - 1) n (n + 1) b(n) n (7 n + 17) (n + 1) b(n + 1) + 576/5 -------------------------- + 288/5 ----------------------------- (n + 39) (n + 36) (n + 34) (n + 39) (n + 36) (n + 34) 2 (n + 1) (331 n + 1931 n + 2670) b(n + 2) + 24/5 ----------------------------------------- = 0 (n + 39) (n + 36) (n + 34) Subject to the initial conditions b(1) = 0, b(2) = 0, b(3) = 0, b(4) = 0, b(5) = 1, b(6) = 3, b(7) = 8, b(8) = 20, b(9) = 48, b(10) = 110, b(11) = 247, b(12) = 547, b(13) = 1192, b(14) = 2570, b(15) = 5497, b(16) = 11669, b(17) = 24619, b(18) = 51680, b(19) = 108002, b(20) = 224830, b(21) = 466469, b(22) = 964947, b(23) = 1990852, b(24) = 4097873, b(25) = 8417219, b(26) = 17256780, b(27) = 35319312, b(28) = 72176526, b(29) = 147289453, b(30) = 300187835, b(31) = 611094107, b(32) = 1242679097, b(33) = 2524547811, b(34) = 5124079516, b(35) = 10391691548, b(36) = 21058247718, b(37) = 42643089832, b(38) = 86295486334, b(39) = 174526326015 This enables us to compute the first, 20000, terms of these sequences The probability of Alice winning the bet, as n grows larger is approximately 0.1996 1/2 - ------ 1/2 n The probability of Bob winning the bet, as n grows larger is approximately 0.865 1/2 - ----- 1/2 n You can see that indeed Alice has a better chance, but not significantly so. ----------------------------------------- This took, 103.220, seconds to generate ----------------------------------------------------------------------------\ ----------------------- Question Mumber, 5, : If Alice bets that there are more occurrences of consec\ utive substrings in, {[2, 2, 1, 2, 2]}, than in, {[1, 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}, with more occurences of, {[2, 2, 1, 2, 2]}, then , {[1, 1, 1, 1, 1]} a(n) satisfies the following linear recurrence equation with polynomial coef\ ficients of order, 47 n (2 n + 3) (n + 1) a(n) a(n + 47) - 96/5 -------------------------- (n + 43) (n + 42) (n + 47) 3 2 (602605 n + 42091242 n + 969334163 n + 7352851902) a(n + 26) - 1/10 -------------------------------------------------------------- (n + 43) (n + 42) (n + 47) 3 2 (403457 n + 26625696 n + 572070793 n + 3986788134) a(n + 27) + 1/10 -------------------------------------------------------------- (n + 43) (n + 42) (n + 47) 3 2 (123557 n + 10779144 n + 307642363 n + 2877472584) a(n + 28) + 1/10 -------------------------------------------------------------- (n + 43) (n + 42) (n + 47) 3 2 (317821 n + 24190074 n + 606140099 n + 4991787294) a(n + 29) - 1/10 -------------------------------------------------------------- (n + 43) (n + 42) (n + 47) 3 2 (31321 n + 2368210 n + 58707567 n + 476081806) a(n + 30) + 3/5 ---------------------------------------------------------- (n + 43) (n + 42) (n + 47) 3 2 (118049 n + 10306374 n + 297548611 n + 2839008030) a(n + 31) + 1/10 -------------------------------------------------------------- (n + 43) (n + 42) (n + 47) 3 2 (77347 n + 6509073 n + 180881696 n + 1658805426) a(n + 32) - 1/5 ------------------------------------------------------------ (n + 43) (n + 42) (n + 47) 3 2 (9765 n + 772592 n + 19746553 n + 161213702) a(n + 33) + 3/10 -------------------------------------------------------- (n + 43) (n + 42) (n + 47) 3 2 (3930 n + 363332 n + 11118254 n + 112553027) a(n + 34) + 6/5 -------------------------------------------------------- (n + 43) (n + 42) (n + 47) 3 2 (22736 n + 2122266 n + 65541613 n + 669295749) a(n + 35) - 1/5 ---------------------------------------------------------- (n + 43) (n + 42) (n + 47) 3 2 (587 n + 37770 n + 579135 n - 757156) a(n + 36) + 3/10 ------------------------------------------------- (n + 43) (n + 42) (n + 47) 3 2 (13951 n + 1380570 n + 45162467 n + 487968504) a(n + 37) + 1/10 ---------------------------------------------------------- (n + 43) (n + 42) (n + 47) 3 2 (5969 n + 590118 n + 19267447 n + 207651354) a(n + 38) - 1/10 -------------------------------------------------------- (n + 43) (n + 42) (n + 47) 3 2 (236 n + 26991 n + 1046029 n + 13724040) a(n + 39) + 1/5 ---------------------------------------------------- (n + 43) (n + 42) (n + 47) 3 2 (263 n + 25400 n + 786249 n + 7654912) a(n + 40) + 3/10 -------------------------------------------------- (n + 43) (n + 42) (n + 47) 3 2 (133 n + 13002 n + 410087 n + 4125258) a(n + 41) - 1/5 -------------------------------------------------- (n + 43) (n + 42) (n + 47) 3 2 (32 n + 4170 n + 180691 n + 2603448) a(n + 42) + 4/5 ------------------------------------------------ (n + 43) (n + 42) (n + 47) 3 2 (109 n + 13800 n + 581651 n + 8161440) a(n + 43) - 2/5 -------------------------------------------------- (n + 43) (n + 42) (n + 47) 3 2 (6 n + 723 n + 28927 n + 384160) a(n + 44) + 6/5 -------------------------------------------- (n + 43) (n + 42) (n + 47) 3 2 (71 n + 9222 n + 398911 n + 5746800) a(n + 45) + 1/5 ------------------------------------------------ (n + 43) (n + 42) (n + 47) 3 2 (18392 n + 424746 n + 3209281 n + 7952013) a(n + 6) + 8/5 ----------------------------------------------------- (n + 43) (n + 42) (n + 47) 3 2 (52432 n + 1350054 n + 11450219 n + 32003583) a(n + 7) + 4/5 -------------------------------------------------------- (n + 43) (n + 42) (n + 47) 3 2 (39708 n + 1047379 n + 9155773 n + 26486766) a(n + 8) + 6/5 ------------------------------------------------------- (n + 43) (n + 42) (n + 47) 3 2 (99164 n + 2897357 n + 27948415 n + 89025462) a(n + 9) + 3/5 -------------------------------------------------------- (n + 43) (n + 42) (n + 47) 3 2 (66877 n + 1995448 n + 19408245 n + 61355670) a(n + 10) + 3/5 --------------------------------------------------------- (n + 43) (n + 42) (n + 47) 3 2 (22255 n - 1643391 n - 48446728 n - 304432836) a(n + 11) + 1/5 ---------------------------------------------------------- (n + 43) (n + 42) (n + 47) 3 2 (32177 n - 2990532 n - 93927353 n - 636811476) a(n + 12) + 1/10 ---------------------------------------------------------- (n + 43) (n + 42) (n + 47) 3 2 (62785 n + 2531341 n + 34253196 n + 153835124) a(n + 13) - 3/5 ---------------------------------------------------------- (n + 43) (n + 42) (n + 47) 3 2 (187587 n + 8843812 n + 137004963 n + 695287730) a(n + 14) - 3/10 ------------------------------------------------------------ (n + 43) (n + 42) (n + 47) 3 2 (3104 n - 87075 n - 4681865 n - 44507484) a(n + 15) - 1/5 ----------------------------------------------------- (n + 43) (n + 42) (n + 47) 3 2 (341897 n + 6619422 n - 56156903 n - 1192296000) a(n + 16) - 1/10 ------------------------------------------------------------ (n + 43) (n + 42) (n + 47) 3 2 (173425 n + 5830950 n + 31008461 n - 308139000) a(n + 17) - 1/10 ----------------------------------------------------------- (n + 43) (n + 42) (n + 47) 3 2 (410687 n + 21540804 n + 379421239 n + 2245232274) a(n + 18) + 1/5 -------------------------------------------------------------- (n + 43) (n + 42) (n + 47) 3 2 (19887 n + 3951248 n + 126426075 n + 1106400606) a(n + 19) + 3/10 ------------------------------------------------------------ (n + 43) (n + 42) (n + 47) 3 2 (62095 n + 4993122 n + 109005479 n + 679072740) a(n + 20) - 1/10 ----------------------------------------------------------- (n + 43) (n + 42) (n + 47) 3 2 (77723 n + 4098342 n + 69955055 n + 382820026) a(n + 21) + 6/5 ---------------------------------------------------------- (n + 43) (n + 42) (n + 47) 3 2 (66833 n + 2392732 n + 16688865 n - 75197310) a(n + 22) - 3/10 --------------------------------------------------------- (n + 43) (n + 42) (n + 47) 3 2 (104147 n + 6798715 n + 147149361 n + 1056196521) a(n + 23) - 3/5 ------------------------------------------------------------- (n + 43) (n + 42) (n + 47) 3 2 (89903 n + 5041864 n + 89070051 n + 479171974) a(n + 24) + 3/5 ---------------------------------------------------------- (n + 43) (n + 42) (n + 47) 3 2 (173101 n + 8477436 n + 117842189 n + 359486430) a(n + 25) - 1/10 ------------------------------------------------------------ (n + 43) (n + 42) (n + 47) 3 2 (25 n + 364 n + 1355 n + 1456) a(n + 2) + 48/5 ----------------------------------------- (n + 43) (n + 42) (n + 47) 3 2 (259 n + 3859 n + 17619 n + 25127) a(n + 3) + 48/5 --------------------------------------------- (n + 43) (n + 42) (n + 47) 3 2 (1303 n + 22494 n + 124725 n + 222510) a(n + 4) + 24/5 ------------------------------------------------- (n + 43) (n + 42) (n + 47) 3 2 (8660 n + 168885 n + 1081546 n + 2271225) a(n + 5) + 8/5 ---------------------------------------------------- (n + 43) (n + 42) (n + 47) 2 (6 n + 531 n + 11725) a(n + 46) - 6/5 -------------------------------- (n + 47) (n + 43) 2 (n + 1) (24 n + 119 n + 140) a(n + 1) - 48/5 -------------------------------------- = 0 (n + 43) (n + 42) (n + 47) Subject to the initial conditions a(1) = 0, a(2) = 0, a(3) = 0, a(4) = 0, a(5) = 1, a(6) = 4, a(7) = 12, a(8) = 31, a(9) = 75, a(10) = 173, a(11) = 389, a(12) = 858, a(13) = 1867, a(14) = 4015, a(15) = 8553, a(16) = 18077, a(17) = 37962, a(18) = 79291, a(19) = 164856, a(20) = 341398, a(21) = 704566, a(22) = 1449689, a(23) = 2974954, a(24) = 6090758, a(25) = 12444062, a(26) = 25377579, a(27) = 51667789, a(28) = 105037544, a(29) = 213249668, a(30) = 432421787, a(31) = 875894557, a(32) = 1772413799, a(33) = 3583327963, a(34) = 7238540668, a(35) = 14611329004, a(36) = 29473429775, a(37) = 59415410112, a(38) = 119706497970, a(39) = 241049987595, a(40) = 485161003020, a(41) = 976047477792, a(42) = 1962807265153, a(43) = 3945663293943, a(44) = 7928861002773, a(45) = 15928015372135, a(46) = 31987718947371, a(47) = 64222230737463 Lemma , 5.2, : Let b(n) be the number of words of length n in the alphabet , {1, 2}, with more occurences of, {[1, 1, 1, 1, 1]}, then , {[2, 2, 1, 2, 2]} b(n) satisfies the following linear recurrence equation with polynomial coef\ ficients of order, 41 n (2 n + 3) (n + 1) b(n) 64/5 -------------------------- (n + 41) (n + 39) (n + 36) 3 2 32 (205 n + 1848 n + 5315 n + 4872) b(n + 2) + -- ------------------------------------------- 15 (n + 41) (n + 39) (n + 36) 3 2 32 (175 n + 1317 n + 2597 n + 639) b(n + 3) + -- ------------------------------------------ 15 (n + 41) (n + 39) (n + 36) 3 2 16 (49 n + 5550 n + 48887 n + 109410) b(n + 4) - -- --------------------------------------------- 15 (n + 41) (n + 39) (n + 36) 3 2 (124 n + 1813 n + 7194 n + 7065) b(n + 5) + 16/5 ------------------------------------------- (n + 41) (n + 39) (n + 36) 3 2 (654 n + 19370 n + 169211 n + 461825) b(n + 6) + 16/5 ------------------------------------------------ (n + 41) (n + 39) (n + 36) 3 2 (14260 n + 442638 n + 4290737 n + 13278789) b(n + 7) + 8/15 ------------------------------------------------------ (n + 41) (n + 39) (n + 36) 3 2 (75964 n + 2436111 n + 25257473 n + 85196958) b(n + 8) + 4/15 -------------------------------------------------------- (n + 41) (n + 39) (n + 36) 3 2 (269068 n + 9301881 n + 104805995 n + 386208438) b(n + 9) + 2/15 ----------------------------------------------------------- (n + 41) (n + 39) (n + 36) 3 2 (363145 n + 13497060 n + 164157533 n + 654667134) b(n + 10) + 2/15 ------------------------------------------------------------- (n + 41) (n + 39) (n + 36) 3 2 (408233 n + 16118229 n + 208980634 n + 890326836) b(n + 11) + 2/15 ------------------------------------------------------------- (n + 41) (n + 39) (n + 36) 3 2 (708659 n + 30640800 n + 432772129 n + 2000272932) b(n + 12) + 1/15 -------------------------------------------------------------- (n + 41) (n + 39) (n + 36) 3 2 (191611 n + 9716025 n + 156787718 n + 813946212) b(n + 13) + 2/15 ------------------------------------------------------------ (n + 41) (n + 39) (n + 36) 3 2 (10651 n + 3154920 n + 83030399 n + 565835898) b(n + 14) + 1/15 ---------------------------------------------------------- (n + 41) (n + 39) (n + 36) 3 2 (127417 n + 5038197 n + 65621012 n + 285064038) b(n + 15) - 2/15 ----------------------------------------------------------- (n + 41) (n + 39) (n + 36) 3 2 (398981 n + 18371958 n + 281108701 n + 1436331264) b(n + 16) - 1/15 -------------------------------------------------------------- (n + 41) (n + 39) (n + 36) 3 2 (403069 n + 21306048 n + 371948147 n + 2149582656) b(n + 17) - 1/15 -------------------------------------------------------------- (n + 41) (n + 39) (n + 36) 3 2 (111505 n + 6942633 n + 140418548 n + 928700712) b(n + 18) - 2/15 ------------------------------------------------------------ (n + 41) (n + 39) (n + 36) 3 2 (10001 n + 980850 n + 26255355 n + 213216090) b(n + 19) - 1/5 --------------------------------------------------------- (n + 41) (n + 39) (n + 36) 3 2 (11507 n + 274593 n - 2444480 n - 65834232) b(n + 20) + 2/15 ------------------------------------------------------- (n + 41) (n + 39) (n + 36) 2 (n + 1) (24 n + 119 n + 140) b(n + 1) + 32/5 -------------------------------------- + b(n + 41) (n + 41) (n + 39) (n + 36) 3 2 (24941 n + 1220356 n + 18339339 n + 78791820) b(n + 21) + 1/5 --------------------------------------------------------- (n + 41) (n + 39) (n + 36) 3 2 (63011 n + 3988224 n + 83213491 n + 572085534) b(n + 22) + 2/15 ---------------------------------------------------------- (n + 41) (n + 39) (n + 36) 3 2 (3163 n + 264564 n + 6994840 n + 59390135) b(n + 23) + 4/5 ------------------------------------------------------ (n + 41) (n + 39) (n + 36) 3 2 (4262 n + 255975 n + 5025753 n + 32199508) b(n + 24) - 2/5 ------------------------------------------------------ (n + 41) (n + 39) (n + 36) 3 2 (8965 n + 650175 n + 15667220 n + 125239902) b(n + 25) + 2/15 -------------------------------------------------------- (n + 41) (n + 39) (n + 36) 3 2 (314 n - 30390 n - 2156132 n - 29875323) b(n + 26) - 4/15 ---------------------------------------------------- (n + 41) (n + 39) (n + 36) 3 2 (37919 n + 2914026 n + 74260471 n + 627445608) b(n + 27) - 1/15 ---------------------------------------------------------- (n + 41) (n + 39) (n + 36) 3 2 (707 n + 6932 n - 1143363 n - 21908504) b(n + 28) + 1/5 --------------------------------------------------- (n + 41) (n + 39) (n + 36) 3 2 (819 n + 67231 n + 1836301 n + 16693925) b(n + 29) + 6/5 ---------------------------------------------------- (n + 41) (n + 39) (n + 36) 3 2 (3345 n + 278244 n + 7685929 n + 70472018) b(n + 30) - 1/5 ------------------------------------------------------ (n + 41) (n + 39) (n + 36) 3 2 (144 n + 16103 n + 581256 n + 6836749) b(n + 31) - 2/5 -------------------------------------------------- (n + 41) (n + 39) (n + 36) 3 2 (1329 n + 122119 n + 3732382 n + 37936752) b(n + 32) + 2/5 ------------------------------------------------------ (n + 41) (n + 39) (n + 36) 3 2 (393 n + 35372 n + 1052145 n + 10321570) b(n + 33) - 2/5 ---------------------------------------------------- (n + 41) (n + 39) (n + 36) 3 2 (747 n + 73440 n + 2403331 n + 26177322) b(n + 34) - 1/5 ---------------------------------------------------- (n + 41) (n + 39) (n + 36) 3 2 (309 n + 30775 n + 1018739 n + 11204557) b(n + 35) + 2/5 ---------------------------------------------------- (n + 41) (n + 39) (n + 36) 3 2 (46 n + 4561 n + 149997 n + 1635050) b(n + 36) - 2/5 ------------------------------------------------ (n + 41) (n + 39) (n + 36) 3 2 (207 n + 22232 n + 794739 n + 9455234) b(n + 37) - 1/5 -------------------------------------------------- (n + 41) (n + 39) (n + 36) 3 2 (117 n + 12682 n + 457607 n + 5496422) b(n + 38) + 1/5 -------------------------------------------------- (n + 41) (n + 39) (n + 36) 3 2 (10 n + 1164 n + 45053 n + 579853) b(n + 39) + 2/5 ---------------------------------------------- (n + 41) (n + 39) (n + 36) 3 2 (27 n + 3094 n + 118039 n + 1499200) b(n + 40) - 1/5 ------------------------------------------------ = 0 (n + 41) (n + 39) (n + 36) Subject to the initial conditions b(1) = 0, b(2) = 0, b(3) = 0, b(4) = 0, b(5) = 1, b(6) = 3, b(7) = 8, b(8) = 20, b(9) = 48, b(10) = 110, b(11) = 247, b(12) = 545, b(13) = 1188, b(14) = 2560, b(15) = 5469, b(16) = 11599, b(17) = 24454, b(18) = 51291, b(19) = 107107, b(20) = 222807, b(21) = 461946, b(22) = 954943, b(23) = 1968954, b(24) = 4050315, b(25) = 8314651, b(26) = 17036983, b(27) = 34850935, b(28) = 71183351, b(29) = 145192908, b(30) = 295780001, b(31) = 601860688, b(32) = 1223401381, b(33) = 2484421543, b(34) = 5040788858, b(35) = 10219244168, b(36) = 20702045008, b(37) = 41908918421, b(38) = 84785307758, b(39) = 171425670753, b(40) = 346410118785, b(41) = 699651011928 This enables us to compute the first, 20000, terms of these sequences The probability of Alice winning the bet, as n grows larger is approximately 0.1369 1/2 - ------ 1/2 n The probability of Bob winning the bet, as n grows larger is approximately 0.958 1/2 - ----- 1/2 n You can see that indeed Alice has a better chance, but not significantly so. ----------------------------------------- This took, 116.647, seconds to generate ----------------------------------------------------------------------------\ ----------------------- Question Mumber, 6, : If Alice bets that there are more occurrences of consec\ utive substrings in, {[2, 2, 2, 2, 2]}, than in, {[1, 1, 1, 1, 1]}, and Bob, bets vice versa, who is more likely to win? Answer: They are equally likely to win ----------------------------------------------------------------------------\ ----------------------- Question Mumber, 7, : If Alice bets that there are more occurrences of consec\ utive substrings in, {[1, 1, 1, 1, 2]}, than in, {[1, 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}, with more occurences of, {[1, 1, 1, 1, 2]}, then , {[1, 1, 1, 1, 1]} a(n) satisfies the following linear recurrence equation with polynomial coef\ ficients of order, 33 3 2 (2659 n + 28002 n - 37627 n - 717690) a(n + 6) -1/10 ------------------------------------------------ (n + 33) (n + 29) (n + 28) 3 2 (2053 n + 79395 n + 924896 n + 3355488) a(n + 7) + 1/5 -------------------------------------------------- (n + 33) (n + 29) (n + 28) 3 2 (1283 n + 43344 n + 466801 n + 1618740) a(n + 8) + 1/2 -------------------------------------------------- (n + 33) (n + 29) (n + 28) 3 2 (4775 n + 129852 n + 1074907 n + 2447358) a(n + 9) + 1/10 ---------------------------------------------------- (n + 33) (n + 29) (n + 28) 3 2 (n + 98148 n + 2330573 n + 13881486) a(n + 10) - 1/10 ------------------------------------------------ (n + 33) (n + 29) (n + 28) 3 2 (6505 n + 331392 n + 5203994 n + 26016765) a(n + 11) - 1/5 ------------------------------------------------------ (n + 33) (n + 29) (n + 28) 3 2 (9595 n + 500808 n + 8061353 n + 41205288) a(n + 12) - 1/10 ------------------------------------------------------ (n + 33) (n + 29) (n + 28) 3 2 (1775 n + 84057 n + 1300229 n + 6559975) a(n + 13) - 3/5 ---------------------------------------------------- (n + 33) (n + 29) (n + 28) 3 2 (460 n + 14543 n + 127723 n + 174271) a(n + 14) - 6/5 ------------------------------------------------- (n + 33) (n + 29) (n + 28) (n + 5) (n + 2) (n + 1) a(n) - 192/5 ---------------------------- + a(n + 33) (n + 33) (n + 29) (n + 28) 3 2 (4019 n + 245892 n + 4759288 n + 29726385) a(n + 15) + 1/5 ------------------------------------------------------ (n + 33) (n + 29) (n + 28) 3 2 (2237 n + 96622 n + 1368153 n + 6339204) a(n + 16) - 3/10 ---------------------------------------------------- (n + 33) (n + 29) (n + 28) 3 2 (1385 n + 75362 n + 1370062 n + 8295573) a(n + 17) + 3/5 ---------------------------------------------------- (n + 33) (n + 29) (n + 28) 3 2 (445 n + 18244 n + 232285 n + 857110) a(n + 18) + 3/5 ------------------------------------------------- (n + 33) (n + 29) (n + 28) 3 2 (355 n + 1154 n - 334091 n - 4307106) a(n + 19) + 3/10 ------------------------------------------------- (n + 33) (n + 29) (n + 28) 3 2 (4679 n + 271446 n + 5191183 n + 32693616) a(n + 20) + 1/5 ------------------------------------------------------ (n + 33) (n + 29) (n + 28) 3 2 (4966 n + 288285 n + 5543093 n + 35243034) a(n + 21) - 1/5 ------------------------------------------------------ (n + 33) (n + 29) (n + 28) 3 2 (94 n + 4623 n + 74279 n + 406278) a(n + 22) - 2/5 ---------------------------------------------- (n + 33) (n + 29) (n + 28) 3 2 (669 n + 40128 n + 784993 n + 4987730) a(n + 23) - 3/10 -------------------------------------------------- (n + 33) (n + 29) (n + 28) 3 2 (941 n + 54498 n + 1031497 n + 6358752) a(n + 24) + 1/10 --------------------------------------------------- (n + 33) (n + 29) (n + 28) 3 2 (2659 n + 164724 n + 3304097 n + 21271872) a(n + 25) + 1/10 ------------------------------------------------------ (n + 33) (n + 29) (n + 28) 3 2 (1733 n + 102696 n + 1899877 n + 10466994) a(n + 26) - 1/10 ------------------------------------------------------ (n + 33) (n + 29) (n + 28) 3 2 (223 n + 14398 n + 298733 n + 1961038) a(n + 27) + 3/10 -------------------------------------------------- (n + 33) (n + 29) (n + 28) 3 2 3 (4 n + 275 n + 6165 n + 44816) a(n + 28) - -------------------------------------------- (n + 33) (n + 29) (n + 28) 3 2 (35 n + 2856 n + 77509 n + 699720) a(n + 29) - 1/2 ---------------------------------------------- (n + 33) (n + 29) (n + 28) 3 2 (16 n + 1401 n + 40691 n + 392136) a(n + 30) - 2/5 ---------------------------------------------- (n + 33) (n + 29) (n + 28) 3 2 (179 n + 15474 n + 444889 n + 4254834) a(n + 31) + 1/10 -------------------------------------------------- (n + 33) (n + 29) (n + 28) 2 (19 n + 1142 n + 17073) a(n + 32) - 2/5 ---------------------------------- (n + 29) (n + 33) 2 (n + 2) (4 n + 35 n + 71) a(n + 1) - 192/5 ----------------------------------- (n + 33) (n + 29) (n + 28) 2 (n + 3) (77 n + 781 n + 1944) a(n + 2) - 24/5 --------------------------------------- (n + 33) (n + 29) (n + 28) 2 (n + 4) (136 n + 1481 n + 4065) a(n + 3) - 24/5 ----------------------------------------- (n + 33) (n + 29) (n + 28) 2 (n + 5) (994 n + 11707 n + 33693) a(n + 4) - 4/5 ------------------------------------------- (n + 33) (n + 29) (n + 28) 2 (n + 6) (1666 n + 18705 n + 45683) a(n + 5) - 2/5 -------------------------------------------- = 0 (n + 33) (n + 29) (n + 28) Subject to the initial conditions a(1) = 0, a(2) = 0, a(3) = 0, a(4) = 0, a(5) = 1, a(6) = 3, a(7) = 8, a(8) = 20, a(9) = 48, a(10) = 110, a(11) = 249, a(12) = 553, a(13) = 1212, a(14) = 2628, a(15) = 5651, a(16) = 12060, a(17) = 25585, a(18) = 53993, a(19) = 113429, a(20) = 237350, a(21) = 494934, a(22) = 1028870, a(23) = 2132943, a(24) = 4410875, a(25) = 9101293, a(26) = 18741543, a(27) = 38522230, a(28) = 79047951, a(29) = 161958751, a(30) = 331365306, a(31) = 677090525, a(32) = 1381868116, a(33) = 2817119530 Lemma , 7.2, : Let b(n) be the number of words of length n in the alphabet , {1, 2}, with more occurences of, {[1, 1, 1, 1, 1]}, then , {[1, 1, 1, 1, 2]} b(n) satisfies the following linear recurrence equation with polynomial coef\ ficients of order, 16 2 (n + 5) (n + 1) b(n) (5 n + 33 n + 58) b(n + 1) -64/5 -------------------- - 8/5 --------------------------- (n + 16) (n + 11) (n + 16) (n + 11) 2 2 (11 n + 65 n + 108) b(n + 2) (17 n + 25 n - 190) b(n + 3) - 4/5 ----------------------------- - 2/5 ----------------------------- (n + 16) (n + 11) (n + 16) (n + 11) 2 (115 n + 1441 n + 4516) b(n + 4) + 1/5 --------------------------------- (n + 16) (n + 11) 2 2 (59 n + 631 n + 1444) b(n + 5) (5 n + 70 n + 268) b(n + 6) - 1/5 ------------------------------- + 6/5 ---------------------------- (n + 16) (n + 11) (n + 16) (n + 11) 2 (5 n + 38) b(n + 7) (33 n + 975 n + 6160) b(n + 8) - 32/5 ------------------- - 1/5 ------------------------------- (n + 16) (n + 11) (n + 16) (n + 11) 2 (26 n + 501 n + 2358) b(n + 9) + 4/5 ------------------------------- (n + 16) (n + 11) (n + 10) (89 n + 799) b(n + 10) (4 n + 59) b(n + 11) - 1/5 ------------------------------- + 4/5 -------------------- (n + 16) (n + 11) (n + 16) (n + 11) 2 2 (9 n + 185 n + 832) b(n + 12) (3 n + 70 n + 425) b(n + 13) - 1/5 ------------------------------ + 2/5 ----------------------------- (n + 16) (n + 11) (n + 16) (n + 11) 2 2 (16 n + 391 n + 2278) b(n + 14) (5 n + 129 n + 802) b(n + 15) + 2/5 -------------------------------- - ------------------------------ (n + 16) (n + 11) (n + 16) (n + 11) + b(n + 16) = 0 Subject to the initial conditions b(1) = 0, b(2) = 0, b(3) = 0, b(4) = 0, b(5) = 1, b(6) = 2, b(7) = 5, b(8) = 12, b(9) = 28, b(10) = 63, b(11) = 142, b(12) = 312, b(13) = 680, b(14) = 1469, b(15) = 3151, b(16) = 6714 This enables us to compute the first, 20000, terms of these sequences The probability of Alice winning the bet, as n grows larger is approximately 0.04989 1/2 - ------- 1/2 n The probability of Bob winning the bet, as n grows larger is approximately 1.55 1/2 - ---- 1/2 n You can see that indeed Alice has a better chance, but not significantly so. ----------------------------------------- This took, 47.731, seconds to generate ----------------------------------------------------------------------------\ ----------------------- Question Mumber, 8, : If Alice bets that there are more occurrences of consec\ utive substrings in, {[1, 1, 1, 2, 1]}, than in, {[1, 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}, with more occurences of, {[1, 1, 1, 2, 1]}, then , {[1, 1, 1, 1, 1]} a(n) satisfies the following linear recurrence equation with polynomial coef\ ficients of order, 35 3 2 (727 n + 42217 n + 783200 n + 4598258) a(n + 26) a(n + 35) + 3/5 -------------------------------------------------- (n + 31) (n + 30) (n + 35) 3 2 (5279 n + 346296 n + 7277593 n + 48104496) a(n + 27) + 1/10 ------------------------------------------------------ (n + 31) (n + 30) (n + 35) 3 2 (743 n + 44448 n + 803707 n + 3974784) a(n + 28) - 1/5 -------------------------------------------------- (n + 31) (n + 30) (n + 35) 3 2 (251 n + 22374 n + 667141 n + 6650550) a(n + 29) + 1/5 -------------------------------------------------- (n + 31) (n + 30) (n + 35) 3 2 (19 n + 1757 n + 54044 n + 552993) a(n + 30) - 6/5 ---------------------------------------------- (n + 31) (n + 30) (n + 35) 3 2 (451 n + 38796 n + 1107497 n + 10489800) a(n + 31) - 1/10 ---------------------------------------------------- (n + 31) (n + 30) (n + 35) 3 2 (80 n + 6669 n + 183307 n + 1658520) a(n + 32) + 1/5 ------------------------------------------------ (n + 31) (n + 30) (n + 35) 3 2 (125 n + 11856 n + 374107 n + 3927432) a(n + 33) + 1/10 -------------------------------------------------- (n + 31) (n + 30) (n + 35) 3 2 (17127 n + 444896 n + 3980729 n + 12243928) a(n + 8) + 3/10 ------------------------------------------------------ (n + 31) (n + 30) (n + 35) 3 2 (21071 n + 809910 n + 10133143 n + 41188992) a(n + 9) - 1/10 ------------------------------------------------------- (n + 31) (n + 30) (n + 35) 3 2 (8900 n + 281905 n + 3202369 n + 12932892) a(n + 10) - 3/5 ------------------------------------------------------ (n + 31) (n + 30) (n + 35) 3 2 (53323 n + 2348610 n + 34826027 n + 171334752) a(n + 11) + 1/10 ---------------------------------------------------------- (n + 31) (n + 30) (n + 35) 3 2 (14831 n + 645564 n + 10174306 n + 55814940) a(n + 12) + 2/5 -------------------------------------------------------- (n + 31) (n + 30) (n + 35) 3 2 (9093 n + 318513 n + 3811400 n + 15606796) a(n + 13) - 3/5 ------------------------------------------------------ (n + 31) (n + 30) (n + 35) 3 2 (13031 n + 478608 n + 3574135 n - 10210512) a(n + 14) + 1/5 ------------------------------------------------------- (n + 31) (n + 30) (n + 35) 3 2 (139741 n + 6340434 n + 94856393 n + 464670216) a(n + 15) + 1/10 ----------------------------------------------------------- (n + 31) (n + 30) (n + 35) 3 2 (26600 n + 1243731 n + 18216229 n + 81543492) a(n + 16) - 1/5 --------------------------------------------------------- (n + 31) (n + 30) (n + 35) 3 2 (167233 n + 9097842 n + 163241573 n + 965298132) a(n + 17) - 1/10 ------------------------------------------------------------ (n + 31) (n + 30) (n + 35) 3 2 (3703 n + 48918 n - 1956547 n - 28804182) a(n + 18) + 1/5 ----------------------------------------------------- (n + 31) (n + 30) (n + 35) 3 2 (18524 n + 1083613 n + 20955077 n + 133990022) a(n + 19) + 3/5 ---------------------------------------------------------- (n + 31) (n + 30) (n + 35) 3 2 (1873 n + 41373 n - 465343 n - 10680237) a(n + 20) - 4/5 ---------------------------------------------------- (n + 31) (n + 30) (n + 35) 3 2 (10271 n + 619863 n + 12284502 n + 79809434) a(n + 21) - 3/5 -------------------------------------------------------- (n + 31) (n + 30) (n + 35) 3 2 (5689 n + 300860 n + 5105141 n + 27356386) a(n + 22) + 3/5 ------------------------------------------------------ (n + 31) (n + 30) (n + 35) 3 2 (15709 n + 963351 n + 19347848 n + 126849948) a(n + 23) + 1/5 --------------------------------------------------------- (n + 31) (n + 30) (n + 35) 3 2 (18293 n + 1133292 n + 23319439 n + 159720960) a(n + 24) - 1/10 ---------------------------------------------------------- (n + 31) (n + 30) (n + 35) 3 2 (15517 n + 947184 n + 18594599 n + 115821396) a(n + 25) - 1/10 --------------------------------------------------------- (n + 31) (n + 30) (n + 35) 3 2 (1825 n + 29136 n + 146903 n + 237840) a(n + 3) - 2/5 ------------------------------------------------- (n + 31) (n + 30) (n + 35) 3 2 (443 n - 8496 n - 138671 n - 430476) a(n + 4) - 1/5 ----------------------------------------------- (n + 31) (n + 30) (n + 35) 3 2 (1355 n + 47306 n + 430291 n + 1173156) a(n + 5) + 3/5 -------------------------------------------------- (n + 31) (n + 30) (n + 35) 3 2 (3040 n + 52197 n + 304925 n + 633504) a(n + 6) - 2/5 ------------------------------------------------- (n + 31) (n + 30) (n + 35) 3 2 (223 n - 4017 n - 105888 n - 490158) a(n + 7) + 6/5 ----------------------------------------------- (n + 31) (n + 30) (n + 35) (n + 1) (n + 2) (n + 3) a(n) + 32/5 ---------------------------- (n + 31) (n + 30) (n + 35) (n + 3) (n + 2) (37 n + 217) a(n + 1) - 8/5 ------------------------------------- (n + 31) (n + 30) (n + 35) 2 (n + 3) (523 n + 4989 n + 11342) a(n + 2) - 4/5 ------------------------------------------ (n + 31) (n + 30) (n + 35) 2 (6 n + 387 n + 6217) a(n + 34) - 6/5 ------------------------------- = 0 (n + 35) (n + 31) Subject to the initial conditions a(1) = 0, a(2) = 0, a(3) = 0, a(4) = 0, a(5) = 1, a(6) = 4, a(7) = 11, a(8) = 28, a(9) = 66, a(10) = 151, a(11) = 341, a(12) = 754, a(13) = 1644, a(14) = 3546, a(15) = 7573, a(16) = 16062, a(17) = 33862, a(18) = 71000, a(19) = 148206, a(20) = 308137, a(21) = 638428, a(22) = 1318800, a(23) = 2716907, a(24) = 5583793, a(25) = 11451314, a(26) = 23439161, a(27) = 47893224, a(28) = 97706391, a(29) = 199044445, a(30) = 404959285, a(31) = 822916204, a(32) = 1670422192, a(33) = 3387369081, a(34) = 6862766999, a(35) = 13892100021 Lemma , 8.2, : Let b(n) be the number of words of length n in the alphabet , {1, 2}, with more occurences of, {[1, 1, 1, 1, 1]}, then , {[1, 1, 1, 2, 1]} b(n) satisfies the following linear recurrence equation with polynomial coef\ ficients of order, 22 (n + 1) (n + 2) (n + 3) b(n) (n + 3) (n + 2) (9 n + 29) b(n + 1) -96/5 ---------------------------- - 24/5 ----------------------------------- (n + 22) (n + 21) (n + 17) (n + 22) (n + 21) (n + 17) 2 (n + 3) (13 n - 53 n - 294) b(n + 2) + 12/5 ------------------------------------- (n + 22) (n + 21) (n + 17) 3 2 (149 n + 2400 n + 11659 n + 18072) b(n + 3) + 2/5 --------------------------------------------- (n + 22) (n + 21) (n + 17) 3 2 (1003 n + 21000 n + 140585 n + 303492) b(n + 4) + 1/5 ------------------------------------------------- (n + 22) (n + 21) (n + 17) 3 2 (323 n + 3690 n - 725 n - 68172) b(n + 5) - 1/5 ------------------------------------------- (n + 22) (n + 21) (n + 17) 3 2 (358 n + 8733 n + 69869 n + 183446) b(n + 6) - 6/5 ---------------------------------------------- (n + 22) (n + 21) (n + 17) 3 2 (494 n + 9183 n + 45853 n + 33126) b(n + 7) + 2/5 --------------------------------------------- (n + 22) (n + 21) (n + 17) 3 2 (347 n + 10014 n + 82219 n + 179820) b(n + 8) + 1/5 ----------------------------------------------- (n + 22) (n + 21) (n + 17) 3 2 (127 n + 672 n - 22708 n - 164601) b(n + 9) - 2/5 --------------------------------------------- (n + 22) (n + 21) (n + 17) 3 2 (931 n + 39882 n + 558293 n + 2548266) b(n + 10) + 1/5 -------------------------------------------------- (n + 22) (n + 21) (n + 17) 3 2 (445 n + 21195 n + 306644 n + 1396812) b(n + 11) - 2/5 -------------------------------------------------- (n + 22) (n + 21) (n + 17) 3 2 (229 n + 18690 n + 385973 n + 2352336) b(n + 12) - 1/5 -------------------------------------------------- (n + 22) (n + 21) (n + 17) 3 2 (454 n + 25584 n + 441293 n + 2411343) b(n + 13) + 2/5 -------------------------------------------------- (n + 22) (n + 21) (n + 17) 3 2 (107 n + 5510 n + 89481 n + 465894) b(n + 14) - 3/5 ----------------------------------------------- (n + 22) (n + 21) (n + 17) 3 2 (230 n + 11553 n + 193123 n + 1074486) b(n + 15) - 2/5 -------------------------------------------------- (n + 22) (n + 21) (n + 17) 3 2 (233 n + 13062 n + 243181 n + 1503756) b(n + 16) + 1/5 -------------------------------------------------- (n + 22) (n + 21) (n + 17) 3 2 (31 n + 1230 n + 14524 n + 43649) b(n + 17) + 6/5 --------------------------------------------- (n + 22) (n + 21) (n + 17) 3 2 (31 n + 438 n - 13387 n - 201486) b(n + 18) - 1/5 --------------------------------------------- (n + 22) (n + 21) (n + 17) 3 2 (32 n + 1781 n + 32823 n + 200124) b(n + 19) - 6/5 ---------------------------------------------- (n + 22) (n + 21) (n + 17) 3 2 6 (5 n + 281 n + 5234 n + 32278) b(n + 20) + -------------------------------------------- (n + 22) (n + 21) (n + 17) 2 9 (n + 37 n + 338) b(n + 21) - ----------------------------- + b(n + 22) = 0 (n + 22) (n + 17) Subject to the initial conditions b(1) = 0, b(2) = 0, b(3) = 0, b(4) = 0, b(5) = 1, b(6) = 3, b(7) = 7, b(8) = 17, b(9) = 39, b(10) = 89, b(11) = 201, b(12) = 441, b(13) = 958, b(14) = 2064, b(15) = 4408, b(16) = 9366, b(17) = 19785, b(18) = 41577, b(19) = 87033, b(20) = 181513, b(21) = 377356, b(22) = 782346 This enables us to compute the first, 20000, terms of these sequences The probability of Alice winning the bet, as n grows larger is approximately 0.08147 1/2 - ------- 1/2 n The probability of Bob winning the bet, as n grows larger is approximately 1.22 1/2 - ---- 1/2 n You can see that indeed Alice has a better chance, but not significantly so. ----------------------------------------- This took, 60.549, seconds to generate ----------------------------------------------------------------------------\ ----------------------- Question Mumber, 9, : If Alice bets that there are more occurrences of consec\ utive substrings in, {[1, 1, 1, 2, 2]}, than in, {[1, 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}, with more occurences of, {[1, 1, 1, 2, 2]}, then , {[1, 1, 1, 1, 1]} a(n) satisfies the following linear recurrence equation with polynomial coef\ ficients of order, 38 (n + 4) (n + 2) (n + 1) a(n) a(n + 38) + 192/5 ---------------------------- (n + 33) (n + 38) (n + 34) (2 n + 5) (n + 5) (n + 2) a(n + 1) - 384/5 ---------------------------------- (n + 33) (n + 38) (n + 34) 3 2 (2 n - 93 n - 860 n - 1680) a(n + 2) + 32/5 -------------------------------------- (n + 33) (n + 38) (n + 34) 3 2 (10 n + 143 n + 797 n + 1552) a(n + 3) - 144/5 ---------------------------------------- (n + 33) (n + 38) (n + 34) 3 2 (641 n + 5277 n - 1754 n - 62568) a(n + 4) + 4/5 -------------------------------------------- (n + 33) (n + 38) (n + 34) 3 2 (566 n + 15267 n + 117355 n + 275052) a(n + 5) + 4/5 ------------------------------------------------ (n + 33) (n + 38) (n + 34) 3 2 (1705 n + 25173 n + 105824 n + 86832) a(n + 6) + 2/5 ------------------------------------------------ (n + 33) (n + 38) (n + 34) 3 2 (1211 n + 35229 n + 296782 n + 745308) a(n + 7) + 2/5 ------------------------------------------------- (n + 33) (n + 38) (n + 34) 3 2 (4931 n + 241995 n + 3497374 n + 15438648) a(n + 8) + 1/10 ----------------------------------------------------- (n + 33) (n + 38) (n + 34) 3 2 (4613 n + 361770 n + 9362800 n + 79885956) a(n + 30) - 1/5 ------------------------------------------------------ (n + 33) (n + 38) (n + 34) 3 2 (1609 n + 132087 n + 3588602 n + 32253330) a(n + 31) + 1/5 ------------------------------------------------------ (n + 33) (n + 38) (n + 34) 3 2 (77 n - 81 n - 228356 n - 4700124) a(n + 32) - 1/10 ---------------------------------------------- (n + 33) (n + 38) (n + 34) 3 2 (163 n + 16688 n + 568131 n + 6432138) a(n + 33) - 3/10 -------------------------------------------------- (n + 33) (n + 38) (n + 34) 3 2 (233 n + 23359 n + 779832 n + 8669676) a(n + 34) + 3/10 -------------------------------------------------- (n + 33) (n + 38) (n + 34) 3 2 (249 n + 24920 n + 830373 n + 9213162) a(n + 35) - 3/10 -------------------------------------------------- (n + 33) (n + 38) (n + 34) 3 2 (401 n + 40629 n + 1370230 n + 15383832) a(n + 36) + 1/10 ---------------------------------------------------- (n + 33) (n + 38) (n + 34) 2 (17 n + 1191 n + 20784) a(n + 37) - 3/5 ---------------------------------- (n + 38) (n + 34) 3 2 (4663 n + 50202 n - 91765 n - 1151724) a(n + 9) + 1/10 ------------------------------------------------- (n + 33) (n + 38) (n + 34) 3 2 (549 n + 29335 n + 480600 n + 2390800) a(n + 10) - 3/10 -------------------------------------------------- (n + 33) (n + 38) (n + 34) 3 2 (31979 n + 1342734 n + 18226183 n + 80495952) a(n + 11) - 1/10 --------------------------------------------------------- (n + 33) (n + 38) (n + 34) 3 2 (453 n - 51493 n - 1839956 n - 14129216) a(n + 12) + 3/10 ---------------------------------------------------- (n + 33) (n + 38) (n + 34) 3 2 (2059 n + 331437 n + 7751120 n + 49158048) a(n + 13) + 1/5 ------------------------------------------------------ (n + 33) (n + 38) (n + 34) 3 2 (109 n - 103326 n - 2796568 n - 18576396) a(n + 14) + 1/5 ----------------------------------------------------- (n + 33) (n + 38) (n + 34) 3 2 (27649 n + 1642356 n + 31103825 n + 190494048) a(n + 15) + 1/5 ---------------------------------------------------------- (n + 33) (n + 38) (n + 34) 3 2 (29025 n + 1630055 n + 30090634 n + 183210504) a(n + 16) - 3/10 ---------------------------------------------------------- (n + 33) (n + 38) (n + 34) 3 2 (24565 n + 1433592 n + 27729947 n + 177908300) a(n + 17) + 3/10 ---------------------------------------------------------- (n + 33) (n + 38) (n + 34) 3 2 (22181 n + 1511133 n + 33133574 n + 236198592) a(n + 18) - 3/10 ---------------------------------------------------------- (n + 33) (n + 38) (n + 34) 3 2 (91409 n + 6081216 n + 132500389 n + 949387026) a(n + 19) + 1/10 ----------------------------------------------------------- (n + 33) (n + 38) (n + 34) 3 2 (9735 n + 722624 n + 17267597 n + 134135410) a(n + 20) - 3/5 -------------------------------------------------------- (n + 33) (n + 38) (n + 34) 3 2 (32105 n + 2716074 n + 70737175 n + 584224686) a(n + 21) + 1/10 ---------------------------------------------------------- (n + 33) (n + 38) (n + 34) 3 2 (17479 n + 1196365 n + 26822766 n + 196957828) a(n + 22) - 3/10 ---------------------------------------------------------- (n + 33) (n + 38) (n + 34) 3 2 (26363 n + 1740216 n + 37515157 n + 262602288) a(n + 23) + 1/10 ---------------------------------------------------------- (n + 33) (n + 38) (n + 34) 3 2 (3844 n + 208815 n + 3216491 n + 10067700) a(n + 24) - 1/5 ------------------------------------------------------ (n + 33) (n + 38) (n + 34) 3 2 (21337 n + 1265574 n + 23259701 n + 124087596) a(n + 25) + 1/10 ---------------------------------------------------------- (n + 33) (n + 38) (n + 34) 3 2 (22277 n + 1434225 n + 29438122 n + 187345200) a(n + 26) - 1/10 ---------------------------------------------------------- (n + 33) (n + 38) (n + 34) 3 2 (22219 n + 1569966 n + 36168773 n + 269466054) a(n + 27) + 1/10 ---------------------------------------------------------- (n + 33) (n + 38) (n + 34) 3 2 (23017 n + 1668819 n + 39559238 n + 304878192) a(n + 28) - 1/10 ---------------------------------------------------------- (n + 33) (n + 38) (n + 34) 3 2 (4172 n + 308844 n + 7479178 n + 58967391) a(n + 29) + 2/5 ------------------------------------------------------ = 0 (n + 33) (n + 38) (n + 34) Subject to the initial conditions a(1) = 0, a(2) = 0, a(3) = 0, a(4) = 0, a(5) = 1, a(6) = 4, a(7) = 11, a(8) = 28, a(9) = 68, a(10) = 158, a(11) = 356, a(12) = 789, a(13) = 1724, a(14) = 3721, a(15) = 7955, a(16) = 16879, a(17) = 35583, a(18) = 74597, a(19) = 155656, a(20) = 323485, a(21) = 669888, a(22) = 1382921, a(23) = 2847090, a(24) = 5847176, a(25) = 11982427, a(26) = 24507295, a(27) = 50036041, a(28) = 101995526, a(29) = 207612992, a(30) = 422046433, a(31) = 856936594, a(32) = 1738059691, a(33) = 3521666526, a(34) = 7129107212, a(35) = 14419746397, a(36) = 29143698497, a(37) = 58860303657, a(38) = 118799575004 Lemma , 9.2, : Let b(n) be the number of words of length n in the alphabet , {1, 2}, with more occurences of, {[1, 1, 1, 1, 1]}, then , {[1, 1, 1, 2, 2]} b(n) satisfies the following linear recurrence equation with polynomial coef\ ficients of order, 17 (n + 4) (n + 1) b(n) (n + 5) (11 n + 24) b(n + 1) -48/5 -------------------- - 8/5 ---------------------------- (n + 17) (n + 12) (n + 17) (n + 12) 2 2 (5 n + 31 n + 56) b(n + 2) (25 n + 277 n + 724) b(n + 3) - 12/5 --------------------------- + 2/5 ------------------------------ (n + 17) (n + 12) (n + 17) (n + 12) 2 2 (61 n + 968 n + 3378) b(n + 4) (45 n + 87 n - 1462) b(n + 5) + 2/5 ------------------------------- - 1/5 ------------------------------ (n + 17) (n + 12) (n + 17) (n + 12) 2 (55 n + 951 n + 3590) b(n + 6) - 1/5 ------------------------------- (n + 17) (n + 12) 2 (10 n + 287 n + 1627) b(n + 7) - 4/5 ------------------------------- (n + 17) (n + 12) 2 (47 n + 721 n + 2606) b(n + 8) + 2/5 ------------------------------- (n + 17) (n + 12) 2 (105 n + 1967 n + 8954) b(n + 9) + 1/5 --------------------------------- (n + 17) (n + 12) 2 (35 n + 782 n + 4496) b(n + 10) - 2/5 -------------------------------- (n + 17) (n + 12) 2 (71 n + 1355 n + 6210) b(n + 11) - 1/5 --------------------------------- (n + 17) (n + 12) 2 2 (5 n + 91 n + 276) b(n + 12) (n + 25 n + 12) b(n + 13) - 2/5 ----------------------------- - 1/5 -------------------------- (n + 17) (n + 12) (n + 17) (n + 12) 2 2 (11 n + 261 n + 1464) b(n + 14) (n + 51 n + 510) b(n + 15) + 4/5 -------------------------------- + 2/5 --------------------------- (n + 17) (n + 12) (n + 17) (n + 12) 2 (19 n + 539 n + 3720) b(n + 16) - 1/5 -------------------------------- + b(n + 17) = 0 (n + 17) (n + 12) Subject to the initial conditions b(1) = 0, b(2) = 0, b(3) = 0, b(4) = 0, b(5) = 1, b(6) = 3, b(7) = 7, b(8) = 17, b(9) = 40, b(10) = 91, b(11) = 202, b(12) = 445, b(13) = 968, b(14) = 2083, b(15) = 4449, b(16) = 9444, b(17) = 19935 This enables us to compute the first, 20000, terms of these sequences The probability of Alice winning the bet, as n grows larger is approximately 0.0407180 1/2 - --------- 1/2 n The probability of Bob winning the bet, as n grows larger is approximately 1.26 1/2 - ---- 1/2 n You can see that indeed Alice has a better chance, but not significantly so. ----------------------------------------- This took, 57.658, seconds to generate ----------------------------------------------------------------------------\ ----------------------- Question Mumber, 10, : If Alice bets that there are more occurrences of conse\ cutive substrings in, {[1, 1, 2, 2, 1]}, than in, {[1, 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}, with more occurences of, {[1, 1, 2, 2, 1]}, then , {[1, 1, 1, 1, 1]} a(n) satisfies the following linear recurrence equation with polynomial coef\ ficients of order, 32 2 (n + 3) (865 n + 6732 n + 12998) a(n + 2) 3/5 ------------------------------------------ (n + 32) (n + 28) (n + 27) (n + 1) (n + 2) (n + 3) a(n) + 252/5 ---------------------------- (n + 32) (n + 28) (n + 27) (89 n + 368) (n + 3) (n + 2) a(n + 1) - 18/5 ------------------------------------- + a(n + 32) (n + 32) (n + 28) (n + 27) 3 2 (1681 n + 25704 n + 127283 n + 205344) a(n + 3) - 3/10 ------------------------------------------------- (n + 32) (n + 28) (n + 27) 3 2 (5951 n + 162867 n + 1223464 n + 2793192) a(n + 4) + 1/10 ---------------------------------------------------- (n + 32) (n + 28) (n + 27) 3 2 (3611 n + 104802 n + 890095 n + 2350104) a(n + 5) - 3/10 --------------------------------------------------- (n + 32) (n + 28) (n + 27) 3 2 (11309 n + 352329 n + 3413316 n + 10504332) a(n + 6) + 3/10 ------------------------------------------------------ (n + 32) (n + 28) (n + 27) 3 2 (13540 n + 467219 n + 5036747 n + 17310038) a(n + 7) - 3/5 ------------------------------------------------------ (n + 32) (n + 28) (n + 27) 3 2 (2422 n + 88869 n + 1018331 n + 3727646) a(n + 8) + 18/5 --------------------------------------------------- (n + 32) (n + 28) (n + 27) 3 2 (323 n + 195876 n + 3870763 n + 19472958) a(n + 9) - 1/5 ---------------------------------------------------- (n + 32) (n + 28) (n + 27) 3 2 (32200 n + 673971 n + 1860857 n - 18172800) a(n + 10) - 1/5 ------------------------------------------------------- (n + 32) (n + 28) (n + 27) 3 2 (9 n - 574248 n - 14632637 n - 92574464) a(n + 11) + 3/10 ---------------------------------------------------- (n + 32) (n + 28) (n + 27) 3 2 (16182 n + 1291853 n + 25482579 n + 148386372) a(n + 12) + 3/10 ---------------------------------------------------------- (n + 32) (n + 28) (n + 27) 3 2 (49610 n + 541821 n - 15287717 n - 184466316) a(n + 13) + 1/10 --------------------------------------------------------- (n + 32) (n + 28) (n + 27) 3 2 (122273 n + 4486275 n + 49287694 n + 143235612) a(n + 14) - 1/10 ----------------------------------------------------------- (n + 32) (n + 28) (n + 27) 3 2 (105973 n + 4697268 n + 66132023 n + 290719548) a(n + 15) + 1/10 ----------------------------------------------------------- (n + 32) (n + 28) (n + 27) 3 2 (40678 n + 2047655 n + 33358553 n + 175503848) a(n + 16) - 3/10 ---------------------------------------------------------- (n + 32) (n + 28) (n + 27) 3 2 (53992 n + 2705983 n + 44565595 n + 240657364) a(n + 17) + 3/10 ---------------------------------------------------------- (n + 32) (n + 28) (n + 27) 3 2 (139829 n + 7038609 n + 117734320 n + 654883500) a(n + 18) - 1/10 ------------------------------------------------------------ (n + 32) (n + 28) (n + 27) 3 2 (33865 n + 1851519 n + 34148042 n + 212847846) a(n + 19) + 1/5 ---------------------------------------------------------- (n + 32) (n + 28) (n + 27) 3 2 (4918 n + 295153 n + 5959519 n + 40509796) a(n + 20) - 3/5 ------------------------------------------------------ (n + 32) (n + 28) (n + 27) 3 2 (16367 n + 872127 n + 15241948 n + 87406920) a(n + 21) + 1/5 -------------------------------------------------------- (n + 32) (n + 28) (n + 27) 3 2 (2613 n + 134893 n + 2217855 n + 11384307) a(n + 22) - 6/5 ------------------------------------------------------ (n + 32) (n + 28) (n + 27) 3 2 (22085 n + 1199118 n + 20804017 n + 113243160) a(n + 23) + 1/10 ---------------------------------------------------------- (n + 32) (n + 28) (n + 27) 3 2 (14344 n + 830577 n + 15471569 n + 91415808) a(n + 24) - 1/10 -------------------------------------------------------- (n + 32) (n + 28) (n + 27) 3 2 (6920 n + 412479 n + 7873699 n + 47270316) a(n + 25) + 1/10 ------------------------------------------------------ (n + 32) (n + 28) (n + 27) 3 2 (2447 n + 155541 n + 3215962 n + 21502800) a(n + 26) - 1/10 ------------------------------------------------------ (n + 32) (n + 28) (n + 27) 3 2 (163 n + 11858 n + 287249 n + 2320334) a(n + 27) + 3/5 -------------------------------------------------- (n + 32) (n + 28) (n + 27) 3 2 (25 n + 2258 n + 66401 n + 638252) a(n + 28) + 3/10 ---------------------------------------------- (n + 32) (n + 28) (n + 27) 3 2 (605 n + 49455 n + 1344718 n + 12164160) a(n + 29) - 1/10 ---------------------------------------------------- (n + 32) (n + 28) (n + 27) 3 2 (97 n + 8076 n + 223649 n + 2060490) a(n + 30) + 2/5 ------------------------------------------------ (n + 32) (n + 28) (n + 27) 2 (17 n + 987 n + 14250) a(n + 31) - 3/5 --------------------------------- = 0 (n + 28) (n + 32) Subject to the initial conditions a(1) = 0, a(2) = 0, a(3) = 0, a(4) = 0, a(5) = 1, a(6) = 4, a(7) = 12, a(8) = 31, a(9) = 74, a(10) = 171, a(11) = 384, a(12) = 849, a(13) = 1849, a(14) = 3979, a(15) = 8485, a(16) = 17949, a(17) = 37735, a(18) = 78900, a(19) = 164215, a(20) = 340428, a(21) = 703267, a(22) = 1448460, a(23) = 2975279, a(24) = 6097103, a(25) = 12468242, a(26) = 25448890, a(27) = 51856151, a(28) = 105504550, a(29) = 214361440, a(30) = 434993383, a(31) = 881716535, a(32) = 1785377184 Lemma , 10.2, : Let b(n) be the number of words of length n in the alphabet , {1, 2}, with more occurences of, {[1, 1, 1, 1, 1]}, then , {[1, 1, 2, 2, 1]} b(n) satisfies the following linear recurrence equation with polynomial coef\ ficients of order, 23 (n + 1) (n + 2) (n + 3) b(n) (5 n + 32) (n + 3) (n + 2) b(n + 1) -252/5 ---------------------------- - 198/5 ----------------------------------- (n + 22) (n + 18) (n + 23) (n + 22) (n + 18) (n + 23) 2 (n + 3) (1367 n + 13068 n + 28906) b(n + 2) + 3/5 -------------------------------------------- (n + 22) (n + 18) (n + 23) 3 2 (2183 n + 26496 n + 94717 n + 95472) b(n + 3) - 3/10 ----------------------------------------------- (n + 22) (n + 18) (n + 23) 3 2 (5749 n + 92409 n + 512168 n + 980904) b(n + 4) + 1/10 ------------------------------------------------- (n + 22) (n + 18) (n + 23) 3 2 (3359 n + 65790 n + 429151 n + 928776) b(n + 5) - 3/10 ------------------------------------------------- (n + 22) (n + 18) (n + 23) 3 2 (2457 n + 47375 n + 293130 n + 574836) b(n + 6) + 3/10 ------------------------------------------------- (n + 22) (n + 18) (n + 23) 3 2 (6007 n + 155124 n + 1381649 n + 4205592) b(n + 7) - 1/10 ---------------------------------------------------- (n + 22) (n + 18) (n + 23) 3 2 (4613 n + 134301 n + 1255768 n + 3769584) b(n + 8) + 1/10 ---------------------------------------------------- (n + 22) (n + 18) (n + 23) 3 2 (117 n - 17722 n - 406847 n - 2170096) b(n + 9) - 3/10 ------------------------------------------------- (n + 22) (n + 18) (n + 23) 3 2 (457 n + 40475 n + 693874 n + 3349776) b(n + 10) - 3/10 -------------------------------------------------- (n + 22) (n + 18) (n + 23) 3 2 (1042 n + 55725 n + 861293 n + 4133544) b(n + 11) + 1/5 --------------------------------------------------- (n + 22) (n + 18) (n + 23) 3 2 (2461 n + 134784 n + 2257523 n + 11975796) b(n + 12) - 1/10 ------------------------------------------------------ (n + 22) (n + 18) (n + 23) 3 2 (3052 n + 166635 n + 2828471 n + 15325740) b(n + 13) + 1/10 ------------------------------------------------------ (n + 22) (n + 18) (n + 23) 3 2 (2299 n + 120831 n + 2048876 n + 11323464) b(n + 14) - 1/10 ------------------------------------------------------ (n + 22) (n + 18) (n + 23) 3 2 (181 n + 13064 n + 276087 n + 1815016) b(n + 15) + 3/10 -------------------------------------------------- (n + 22) (n + 18) (n + 23) 3 2 (845 n + 49365 n + 927088 n + 5652696) b(n + 16) - 1/10 -------------------------------------------------- (n + 22) (n + 18) (n + 23) 3 2 (503 n + 24954 n + 409287 n + 2216604) b(n + 17) + 3/10 -------------------------------------------------- (n + 22) (n + 18) (n + 23) 3 2 (815 n + 39657 n + 634402 n + 3322980) b(n + 18) - 1/10 -------------------------------------------------- (n + 22) (n + 18) (n + 23) 3 2 (85 n + 4356 n + 73287 n + 402652) b(n + 19) + 3/10 ---------------------------------------------- (n + 22) (n + 18) (n + 23) 3 2 (280 n + 16017 n + 303233 n + 1897260) b(n + 20) - 1/10 -------------------------------------------------- (n + 22) (n + 18) (n + 23) 3 2 (77 n + 4565 n + 89728 n + 584180) b(n + 21) + 3/10 ---------------------------------------------- (n + 22) (n + 18) (n + 23) 2 (8 n + 313 n + 3027) b(n + 22) - ------------------------------- + b(n + 23) = 0 (n + 23) (n + 18) Subject to the initial conditions b(1) = 0, b(2) = 0, b(3) = 0, b(4) = 0, b(5) = 1, b(6) = 3, b(7) = 8, b(8) = 19, b(9) = 44, b(10) = 101, b(11) = 225, b(12) = 497, b(13) = 1079, b(14) = 2321, b(15) = 4955, b(16) = 10502, b(17) = 22147, b(18) = 46460, b(19) = 97069, b(20) = 202057, b(21) = 419236, b(22) = 867430, b(23) = 1790185 This enables us to compute the first, 20000, terms of these sequences The probability of Alice winning the bet, as n grows larger is approximately 0.07542 1/2 - ------- 1/2 n The probability of Bob winning the bet, as n grows larger is approximately 1.13 1/2 - ---- 1/2 n You can see that indeed Alice has a better chance, but not significantly so. ----------------------------------------- This took, 57.390, seconds to generate ----------------------------------------------------------------------------\ ----------------------- Question Mumber, 11, : If Alice bets that there are more occurrences of conse\ cutive substrings in, {[1, 1, 2, 1, 2]}, than in, {[1, 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 , 11.1, : Let a(n) be the number of words of length n in the alphabet , {1, 2}, with more occurences of, {[1, 1, 2, 1, 2]}, then , {[1, 1, 1, 1, 1]} a(n) satisfies the following linear recurrence equation with polynomial coef\ ficients of order, 44 (n + 5) (n + 3) (n + 1) a(n) a(n + 44) - 384/5 ---------------------------- (n + 44) (n + 40) (n + 39) 3 2 (17 n - 825 n - 119528 n - 2433390) a(n + 37) - 2/5 ----------------------------------------------- (n + 44) (n + 40) (n + 39) 3 2 (496 n + 52677 n + 1861619 n + 21896658) a(n + 38) - 1/5 ---------------------------------------------------- (n + 44) (n + 40) (n + 39) 3 2 (233 n + 26079 n + 969364 n + 11963496) a(n + 39) - 1/5 --------------------------------------------------- (n + 44) (n + 40) (n + 39) 3 2 (103 n + 10074 n + 317279 n + 3164616) a(n + 40) + 1/10 -------------------------------------------------- (n + 44) (n + 40) (n + 39) 3 2 (29 n + 3359 n + 129458 n + 1660232) a(n + 41) + 3/10 ------------------------------------------------ (n + 44) (n + 40) (n + 39) 3 2 (20 n + 2451 n + 99985 n + 1357746) a(n + 42) + 2/5 ----------------------------------------------- (n + 44) (n + 40) (n + 39) 2 (n + 4) (179 n + 1515 n + 2326) a(n + 1) - 24/5 ----------------------------------------- (n + 44) (n + 40) (n + 39) 2 (n + 5) (329 n + 3583 n + 7864) a(n + 2) - 48/5 ----------------------------------------- (n + 44) (n + 40) (n + 39) 3 2 (6440 n + 132699 n + 844984 n + 1676100) a(n + 3) - 4/5 --------------------------------------------------- (n + 44) (n + 40) (n + 39) 3 2 (2961 n + 93082 n + 813027 n + 2119938) a(n + 4) - 6/5 -------------------------------------------------- (n + 44) (n + 40) (n + 39) 3 2 (6935 n + 783813 n + 10498522 n + 36545232) a(n + 5) - 1/10 ------------------------------------------------------ (n + 44) (n + 40) (n + 39) 3 2 (383 n - 203426 n - 3608899 n - 15319986) a(n + 6) + 3/10 ---------------------------------------------------- (n + 44) (n + 40) (n + 39) 3 2 (14621 n + 393342 n + 3281527 n + 8419818) a(n + 7) + 2/5 ----------------------------------------------------- (n + 44) (n + 40) (n + 39) 3 2 (31114 n + 1137975 n + 13416967 n + 51214124) a(n + 8) + 3/5 -------------------------------------------------------- (n + 44) (n + 40) (n + 39) 3 2 (113987 n + 4604892 n + 62526301 n + 279150144) a(n + 9) + 1/5 ---------------------------------------------------------- (n + 44) (n + 40) (n + 39) 3 2 (105877 n + 4090032 n + 65570381 n + 370783338) a(n + 10) + 1/10 ----------------------------------------------------------- (n + 44) (n + 40) (n + 39) 3 2 (26493 n + 1734651 n + 26717156 n + 114065788) a(n + 11) - 3/10 ---------------------------------------------------------- (n + 44) (n + 40) (n + 39) 3 2 (61875 n + 3831709 n + 68953578 n + 381515716) a(n + 12) - 3/10 ---------------------------------------------------------- (n + 44) (n + 40) (n + 39) 3 2 (27607 n + 2473776 n + 57867655 n + 398720534) a(n + 13) - 3/10 ---------------------------------------------------------- (n + 44) (n + 40) (n + 39) 3 2 (29653 n + 1127052 n + 9188231 n - 15536478) a(n + 14) + 2/5 -------------------------------------------------------- (n + 44) (n + 40) (n + 39) 3 2 (103093 n + 8558391 n + 180807860 n + 1118747280) a(n + 15) + 1/10 ------------------------------------------------------------- (n + 44) (n + 40) (n + 39) 3 2 (62345 n + 1198152 n - 11952117 n - 239983884) a(n + 16) - 3/10 ---------------------------------------------------------- (n + 44) (n + 40) (n + 39) 3 2 (141543 n + 6203598 n + 84116281 n + 333109958) a(n + 17) - 3/10 ----------------------------------------------------------- (n + 44) (n + 40) (n + 39) 3 2 (154768 n + 8793903 n + 160729046 n + 945138372) a(n + 18) - 1/5 ------------------------------------------------------------ (n + 44) (n + 40) (n + 39) 3 2 (106123 n + 2973300 n + 4507451 n - 253509906) a(n + 19) + 1/10 ---------------------------------------------------------- (n + 44) (n + 40) (n + 39) 3 2 (481283 n + 25395816 n + 437859169 n + 2456024796) a(n + 20) + 1/10 -------------------------------------------------------------- (n + 44) (n + 40) (n + 39) 3 2 (472591 n + 27878361 n + 538448486 n + 3393119604) a(n + 21) + 1/10 -------------------------------------------------------------- (n + 44) (n + 40) (n + 39) 3 2 (147251 n + 10653375 n + 245237470 n + 1804422060) a(n + 22) + 1/10 -------------------------------------------------------------- (n + 44) (n + 40) (n + 39) 3 2 (97160 n + 5404737 n + 95997016 n + 532733643) a(n + 23) - 1/5 ---------------------------------------------------------- (n + 44) (n + 40) (n + 39) 3 2 (280871 n + 17978601 n + 374773384 n + 2523708096) a(n + 24) - 1/10 -------------------------------------------------------------- (n + 44) (n + 40) (n + 39) 3 2 (155641 n + 11211465 n + 265510700 n + 2064234204) a(n + 25) - 1/10 -------------------------------------------------------------- (n + 44) (n + 40) (n + 39) 3 2 (6677 n + 1516950 n + 62956279 n + 729236826) a(n + 26) - 1/10 --------------------------------------------------------- (n + 44) (n + 40) (n + 39) 3 2 (74647 n + 4693014 n + 91479023 n + 519562008) a(n + 27) + 1/10 ---------------------------------------------------------- (n + 44) (n + 40) (n + 39) 3 2 (27823 n + 2078130 n + 50696186 n + 401888868) a(n + 28) + 1/5 ---------------------------------------------------------- (n + 44) (n + 40) (n + 39) 3 2 (32567 n + 3080742 n + 95081923 n + 961105236) a(n + 29) + 1/10 ---------------------------------------------------------- (n + 44) (n + 40) (n + 39) 3 2 (321 n + 171042 n + 9159535 n + 129362474) a(n + 30) + 3/10 ------------------------------------------------------ (n + 44) (n + 40) (n + 39) 3 2 (9013 n + 673065 n + 15752654 n + 110517636) a(n + 31) - 1/10 -------------------------------------------------------- (n + 44) (n + 40) (n + 39) 3 2 (439 n + 45200 n + 1526237 n + 16937478) a(n + 32) - 12/5 ---------------------------------------------------- (n + 44) (n + 40) (n + 39) 3 2 (9563 n + 948660 n + 31395265 n + 346664832) a(n + 33) - 1/10 -------------------------------------------------------- (n + 44) (n + 40) (n + 39) 3 2 (17 n - 8815 n - 638812 n - 10858452) a(n + 34) + 3/10 ------------------------------------------------- (n + 44) (n + 40) (n + 39) 3 2 (2365 n + 248919 n + 8731832 n + 102075312) a(n + 35) + 1/10 ------------------------------------------------------- (n + 44) (n + 40) (n + 39) 3 2 (4109 n + 415176 n + 13958803 n + 156214764) a(n + 36) + 1/10 -------------------------------------------------------- (n + 44) (n + 40) (n + 39) 2 (31 n + 2565 n + 52946) a(n + 43) - 1/5 ---------------------------------- = 0 (n + 40) (n + 44) Subject to the initial conditions a(1) = 0, a(2) = 0, a(3) = 0, a(4) = 0, a(5) = 1, a(6) = 4, a(7) = 12, a(8) = 31, a(9) = 76, a(10) = 178, a(11) = 404, a(12) = 896, a(13) = 1957, a(14) = 4220, a(15) = 9007, a(16) = 19064, a(17) = 40078, a(18) = 83773, a(19) = 174253, a(20) = 360942, a(21) = 744954, a(22) = 1532697, a(23) = 3144752, a(24) = 6436686, a(25) = 13146366, a(26) = 26799074, a(27) = 54537296, a(28) = 110816518, a(29) = 224864031, a(30) = 455721104, a(31) = 922558607, a(32) = 1865737213, a(33) = 3769723609, a(34) = 7610399162, a(35) = 15352416512, a(36) = 30948995006, a(37) = 62350941486, a(38) = 125542189162, a(39) = 252643344535, a(40) = 508179034815, a(41) = 1021724422470, a(42) = 2053405763072, a(43) = 4125286704309, a(44) = 8284855847262 Lemma , 11.2, : Let b(n) be the number of words of length n in the alphabet , {1, 2}, with more occurences of, {[1, 1, 1, 1, 1]}, then , {[1, 1, 2, 1, 2]} b(n) satisfies the following linear recurrence equation with polynomial coef\ ficients of order, 18 (n + 3) (n + 1) b(n) (n + 4) (7 n + 15) b(n + 1) -32/5 -------------------- - 8/5 --------------------------- (n + 18) (n + 13) (n + 18) (n + 13) 2 2 (5 n + 83 n + 210) b(n + 2) (25 n + 337 n + 912) b(n + 3) - 4/5 ---------------------------- + 2/5 ------------------------------ (n + 18) (n + 13) (n + 18) (n + 13) 2 (119 n + 2011 n + 7184) b(n + 4) + 1/5 --------------------------------- (n + 18) (n + 13) 2 (71 n + 489 n - 14) b(n + 5) - 1/5 ----------------------------- (n + 18) (n + 13) 2 (115 n + 1871 n + 7114) b(n + 6) - 1/5 --------------------------------- (n + 18) (n + 13) 2 (33 n + 187 n - 512) b(n + 7) + 1/5 ------------------------------ (n + 18) (n + 13) 2 (105 n + 1589 n + 5720) b(n + 8) + 1/5 --------------------------------- (n + 18) (n + 13) 2 (21 n + 413 n + 1992) b(n + 9) + 6/5 ------------------------------- (n + 18) (n + 13) 2 (25 n + 619 n + 3906) b(n + 10) - 2/5 -------------------------------- (n + 18) (n + 13) 2 (9 n + 197 n + 1110) b(n + 11) - 6/5 ------------------------------- (n + 18) (n + 13) 2 (41 n + 853 n + 4190) b(n + 12) (5 n + 191) b(n + 13) - 2/5 -------------------------------- + 2/5 --------------------- (n + 18) (n + 13) (n + 18) (n + 13) 2 (43 n + 963 n + 4946) b(n + 14) + 1/5 -------------------------------- (n + 18) (n + 13) 2 (9 n + 299 n + 2408) b(n + 15) (9 n + 164) b(n + 16) + 1/5 ------------------------------- + 1/5 --------------------- (n + 18) (n + 13) n + 18 2 (19 n + 577 n + 4278) b(n + 17) - 1/5 -------------------------------- + b(n + 18) = 0 (n + 18) (n + 13) Subject to the initial conditions b(1) = 0, b(2) = 0, b(3) = 0, b(4) = 0, b(5) = 1, b(6) = 3, b(7) = 8, b(8) = 19, b(9) = 45, b(10) = 103, b(11) = 230, b(12) = 505, b(13) = 1098, b(14) = 2362, b(15) = 5039, b(16) = 10676, b(17) = 22494, b(18) = 47162 This enables us to compute the first, 20000, terms of these sequences The probability of Alice winning the bet, as n grows larger is approximately 0.037693 1/2 - -------- 1/2 n The probability of Bob winning the bet, as n grows larger is approximately 1.169 1/2 - ----- 1/2 n You can see that indeed Alice has a better chance, but not significantly so. ----------------------------------------- This took, 71.324, seconds to generate ----------------------------------------------------------------------------\ ----------------------- Question Mumber, 12, : If Alice bets that there are more occurrences of conse\ cutive substrings in, {[1, 2, 1, 1, 2]}, than in, {[1, 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 , 12.1, : Let a(n) be the number of words of length n in the alphabet , {1, 2}, with more occurences of, {[1, 2, 1, 1, 2]}, then , {[1, 1, 1, 1, 1]} a(n) satisfies the following linear recurrence equation with polynomial coef\ ficients of order, 44 3 2 (10253 n + 836481 n + 22448134 n + 197756892) a(n + 31) a(n + 44) - 2/5 --------------------------------------------------------- (n + 44) (n + 40) (n + 39) 3 2 (19309 n + 1558452 n + 41054927 n + 350976492) a(n + 32) + 1/5 ---------------------------------------------------------- (n + 44) (n + 40) (n + 39) 3 2 (10112 n + 866697 n + 24490123 n + 227865750) a(n + 33) - 1/5 --------------------------------------------------------- (n + 44) (n + 40) (n + 39) 3 2 (521 n + 47591 n + 1446683 n + 14649760) a(n + 34) + 6/5 ---------------------------------------------------- (n + 44) (n + 40) (n + 39) 3 2 (1853 n + 167964 n + 4981963 n + 48120300) a(n + 35) + 1/5 ------------------------------------------------------ (n + 44) (n + 40) (n + 39) 3 2 (281 n + 8319 n - 431084 n - 13165596) a(n + 36) - 1/5 -------------------------------------------------- (n + 44) (n + 40) (n + 39) 3 2 (121 n + 15738 n + 658274 n + 8936907) a(n + 37) - 2/5 -------------------------------------------------- (n + 44) (n + 40) (n + 39) 3 2 (199 n + 21297 n + 759872 n + 9041532) a(n + 38) - 1/5 -------------------------------------------------- (n + 44) (n + 40) (n + 39) 3 2 (85 n + 10086 n + 397973 n + 5221020) a(n + 39) + 2/5 ------------------------------------------------- (n + 44) (n + 40) (n + 39) 3 2 (33 n + 3910 n + 154139 n + 2021652) a(n + 40) - 6/5 ------------------------------------------------ (n + 44) (n + 40) (n + 39) 3 2 (27 n + 3122 n + 120139 n + 1538596) a(n + 41) + 3/5 ------------------------------------------------ (n + 44) (n + 40) (n + 39) 3 2 (20 n + 2451 n + 99985 n + 1357746) a(n + 42) + 2/5 ----------------------------------------------- (n + 44) (n + 40) (n + 39) 3 2 (453554 n + 16538787 n + 200492857 n + 807410970) a(n + 13) + 4/5 ------------------------------------------------------------- (n + 44) (n + 40) (n + 39) 3 2 (171111 n + 5164417 n + 45899878 n + 103025836) a(n + 14) - 3/5 ----------------------------------------------------------- (n + 44) (n + 40) (n + 39) 3 2 (39417 n + 2546990 n + 47046169 n + 265102812) a(n + 15) - 3/5 ---------------------------------------------------------- (n + 44) (n + 40) (n + 39) 3 2 (2120401 n + 96466929 n + 1456996928 n + 7308286956) a(n + 16) + 1/5 ---------------------------------------------------------------- (n + 44) (n + 40) (n + 39) 3 2 (1679837 n + 74661309 n + 1097382718 n + 5344604886) a(n + 17) - 1/5 ---------------------------------------------------------------- (n + 44) (n + 40) (n + 39) 3 2 (373681 n + 17928951 n + 286051914 n + 1521112620) a(n + 18) + 3/5 -------------------------------------------------------------- (n + 44) (n + 40) (n + 39) 3 2 (254771 n + 15294159 n + 299120512 n + 1911227238) a(n + 19) + 1/5 -------------------------------------------------------------- (n + 44) (n + 40) (n + 39) 3 2 (1396195 n + 75068682 n + 1337470073 n + 7906960356) a(n + 20) - 1/5 ---------------------------------------------------------------- (n + 44) (n + 40) (n + 39) 3 2 (1126016 n + 61700295 n + 1118877619 n + 6724514724) a(n + 21) + 1/5 ---------------------------------------------------------------- (n + 44) (n + 40) (n + 39) 3 2 (716669 n + 42793191 n + 850627564 n + 5635560948) a(n + 22) - 1/5 -------------------------------------------------------------- (n + 44) (n + 40) (n + 39) 3 2 (72910 n + 4614303 n + 96566933 n + 669019210) a(n + 23) - 3/5 ---------------------------------------------------------- (n + 44) (n + 40) (n + 39) 3 2 (287006 n + 17883168 n + 367262449 n + 2485707150) a(n + 24) + 2/5 -------------------------------------------------------------- (n + 44) (n + 40) (n + 39) 3 2 (456994 n + 30141087 n + 658560263 n + 4770090930) a(n + 25) - 1/5 -------------------------------------------------------------- (n + 44) (n + 40) (n + 39) 3 2 (75504 n + 5371243 n + 127183969 n + 1002979958) a(n + 26) + 3/5 ------------------------------------------------------------ (n + 44) (n + 40) (n + 39) 3 2 (45854 n + 3254307 n + 75997513 n + 583467972) a(n + 27) + 2/5 ---------------------------------------------------------- (n + 44) (n + 40) (n + 39) 3 2 (72884 n + 5234496 n + 123487939 n + 955026702) a(n + 28) - 2/5 ----------------------------------------------------------- (n + 44) (n + 40) (n + 39) 3 2 (51125 n + 3932856 n + 100223218 n + 846261579) a(n + 29) + 2/5 ----------------------------------------------------------- (n + 44) (n + 40) (n + 39) 3 2 (12786 n + 1050531 n + 28737547 n + 261863830) a(n + 30) - 3/5 ---------------------------------------------------------- (n + 44) (n + 40) (n + 39) 2 (31 n + 2565 n + 52946) a(n + 43) - 1/5 ---------------------------------- (n + 40) (n + 44) 3 2 (19 n - 291 n - 988 n + 48) a(n + 2) + 256/5 -------------------------------------- (n + 44) (n + 40) (n + 39) 3 2 (167 n + 1683 n + 3940 n + 1056) a(n + 3) + 128/5 ------------------------------------------- (n + 44) (n + 40) (n + 39) 3 2 (391 n + 5973 n + 26562 n + 31880) a(n + 4) - 192/5 --------------------------------------------- (n + 44) (n + 40) (n + 39) 3 2 (451 n + 33963 n + 291230 n + 607344) a(n + 5) - 32/5 ------------------------------------------------ (n + 44) (n + 40) (n + 39) 3 2 (931 n - 33387 n - 383152 n - 831936) a(n + 6) - 16/5 ------------------------------------------------ (n + 44) (n + 40) (n + 39) 3 2 (23605 n + 586857 n + 4549848 n + 10968832) a(n + 7) - 24/5 ------------------------------------------------------ (n + 44) (n + 40) (n + 39) 3 2 (93103 n + 2568273 n + 21865034 n + 57331488) a(n + 8) + 4/5 -------------------------------------------------------- (n + 44) (n + 40) (n + 39) 3 2 (21081 n + 546912 n + 4623429 n + 12682166) a(n + 9) - 48/5 ------------------------------------------------------ (n + 44) (n + 40) (n + 39) 3 2 (34913 n + 1475043 n + 18279634 n + 70206528) a(n + 10) - 4/5 --------------------------------------------------------- (n + 44) (n + 40) (n + 39) 3 2 (215087 n + 8979273 n + 117024382 n + 481740120) a(n + 11) + 2/5 ------------------------------------------------------------ (n + 44) (n + 40) (n + 39) 3 2 (1550143 n + 54444585 n + 627388742 n + 2370516600) a(n + 12) - 1/5 --------------------------------------------------------------- (n + 44) (n + 40) (n + 39) (n - 2) (n + 2) (n + 1) a(n) + 6144/5 ---------------------------- (n + 44) (n + 40) (n + 39) n (n + 2) (3 n - 11) a(n + 1) - 1536/5 ----------------------------- = 0 (n + 44) (n + 40) (n + 39) Subject to the initial conditions a(1) = 0, a(2) = 0, a(3) = 0, a(4) = 0, a(5) = 1, a(6) = 4, a(7) = 12, a(8) = 31, a(9) = 75, a(10) = 174, a(11) = 393, a(12) = 870, a(13) = 1895, a(14) = 4079, a(15) = 8694, a(16) = 18388, a(17) = 38630, a(18) = 80713, a(19) = 167839, a(20) = 347619, a(21) = 717430, a(22) = 1476160, a(23) = 3029123, a(24) = 6201183, a(25) = 12668291, a(26) = 25831511, a(27) = 52584111, a(28) = 106882862, a(29) = 216957778, a(30) = 439859088, a(31) = 890786256, a(32) = 1802186985, a(33) = 3642774759, a(34) = 7357094632, a(35) = 14847509464, a(36) = 29943497912, a(37) = 60350194265, a(38) = 121564021402, a(39) = 244738620847, a(40) = 492481429039, a(41) = 990567791473, a(42) = 1991595183503, a(43) = 4002714248166, a(44) = 8041881009493 Lemma , 12.2, : Let b(n) be the number of words of length n in the alphabet , {1, 2}, with more occurences of, {[1, 1, 1, 1, 1]}, then , {[1, 2, 1, 1, 2]} b(n) satisfies the following linear recurrence equation with polynomial coef\ ficients of order, 35 2 (n + 2) (7 n - n - 36) b(n + 1) 512/5 -------------------------------- + b(n + 35) (n + 33) (n + 30) (n + 35) 3 2 (33323 n + 338517 n - 196919 n - 5378433) b(n + 8) + 4/15 ---------------------------------------------------- (n + 33) (n + 30) (n + 35) 3 2 (189533 n + 6531330 n + 65666767 n + 195835770) b(n + 9) + 1/15 ---------------------------------------------------------- (n + 33) (n + 30) (n + 35) 3 2 (119942 n + 3418518 n + 31213657 n + 89945511) b(n + 10) - 4/15 ---------------------------------------------------------- (n + 33) (n + 30) (n + 35) 3 2 (95664 n + 2574917 n + 22362686 n + 62637467) b(n + 11) + 2/5 --------------------------------------------------------- (n + 33) (n + 30) (n + 35) 3 2 (251357 n + 4903047 n + 17893882 n - 50077704) b(n + 12) - 1/15 ---------------------------------------------------------- (n + 33) (n + 30) (n + 35) 3 2 (205933 n + 10094844 n + 149086811 n + 679642668) b(n + 13) - 1/15 ------------------------------------------------------------- (n + 33) (n + 30) (n + 35) 3 2 (534227 n + 21299697 n + 278029126 n + 1183578408) b(n + 14) + 1/15 -------------------------------------------------------------- (n + 33) (n + 30) (n + 35) 3 2 (141146 n + 5469129 n + 69478756 n + 289087308) b(n + 15) - 4/15 ----------------------------------------------------------- (n + 33) (n + 30) (n + 35) 3 2 (198667 n + 6684735 n + 66964628 n + 176999448) b(n + 16) + 1/15 ----------------------------------------------------------- (n + 33) (n + 30) (n + 35) 3 2 (45047 n + 2417268 n + 42249826 n + 240711864) b(n + 17) + 4/15 ---------------------------------------------------------- (n + 33) (n + 30) (n + 35) 3 2 (123215 n + 6213610 n + 103658355 n + 571466346) b(n + 18) - 1/5 ------------------------------------------------------------ (n + 33) (n + 30) (n + 35) 3 2 (103515 n + 5291690 n + 89385175 n + 498432532) b(n + 19) + 1/5 ----------------------------------------------------------- (n + 33) (n + 30) (n + 35) 3 2 (25632 n + 1265701 n + 20309339 n + 105014032) b(n + 20) - 1/5 ---------------------------------------------------------- (n + 33) (n + 30) (n + 35) 3 2 (94397 n + 5648919 n + 112217248 n + 739981578) b(n + 21) - 1/15 ----------------------------------------------------------- (n + 33) (n + 30) (n + 35) 3 2 (35671 n + 2181864 n + 44285993 n + 298183656) b(n + 22) + 4/15 ---------------------------------------------------------- (n + 33) (n + 30) (n + 35) 3 2 (15673 n + 991642 n + 20811527 n + 144810580) b(n + 23) - 2/5 --------------------------------------------------------- (n + 33) (n + 30) (n + 35) 3 2 (14687 n + 935043 n + 19714672 n + 137525556) b(n + 24) + 1/15 --------------------------------------------------------- (n + 33) (n + 30) (n + 35) 3 2 (9023 n + 634641 n + 14819364 n + 114839590) b(n + 25) + 1/5 -------------------------------------------------------- (n + 33) (n + 30) (n + 35) 3 2 (10048 n + 732961 n + 17755525 n + 142780454) b(n + 26) - 1/5 --------------------------------------------------------- (n + 33) (n + 30) (n + 35) 3 2 (15422 n + 1160619 n + 29025181 n + 241174362) b(n + 27) + 1/15 ---------------------------------------------------------- (n + 33) (n + 30) (n + 35) 3 2 (152 n + 10363 n + 231484 n + 1694758) b(n + 28) - 2/5 -------------------------------------------------- (n + 33) (n + 30) (n + 35) 3 2 (4228 n + 350571 n + 9654953 n + 88280190) b(n + 29) - 1/15 ------------------------------------------------------ (n + 33) (n + 30) (n + 35) 3 2 (1065 n + 90638 n + 2564107 n + 24104994) b(n + 30) + 1/5 ----------------------------------------------------- (n + 33) (n + 30) (n + 35) 3 2 (91 n + 7904 n + 228260 n + 2191507) b(n + 31) - 4/5 ------------------------------------------------ (n + 33) (n + 30) (n + 35) 3 2 (95 n + 9663 n + 323278 n + 3562704) b(n + 32) - 1/15 ------------------------------------------------ (n + 33) (n + 30) (n + 35) 3 2 (70 n + 6633 n + 209105 n + 2192808) b(n + 33) + 4/15 ------------------------------------------------ (n + 33) (n + 30) (n + 35) 3 2 (37 n + 3563 n + 114162 n + 1216968) b(n + 34) - 1/5 ------------------------------------------------ (n + 33) (n + 30) (n + 35) 3 2 (41 n + 26 n - 345 n - 202) b(n + 2) - 128/5 -------------------------------------- (n + 33) (n + 30) (n + 35) 3 2 64 (29 n - 2496 n - 9413 n + 1800) b(n + 3) + -- ------------------------------------------ 15 (n + 33) (n + 30) (n + 35) 3 2 (657 n + 10402 n + 39113 n + 21112) b(n + 4) + 32/5 ---------------------------------------------- (n + 33) (n + 30) (n + 35) 3 2 (3897 n + 63568 n + 290697 n + 308442) b(n + 5) - 16/5 ------------------------------------------------- (n + 33) (n + 30) (n + 35) 3 2 (39055 n + 664614 n + 3374093 n + 4549350) b(n + 6) + 8/15 ----------------------------------------------------- (n + 33) (n + 30) (n + 35) 3 2 (27779 n + 474408 n + 2495913 n + 3821556) b(n + 7) - 4/5 ----------------------------------------------------- (n + 33) (n + 30) (n + 35) (n - 3) (n + 2) (n + 1) b(n) - 512/3 ---------------------------- = 0 (n + 33) (n + 30) (n + 35) Subject to the initial conditions b(1) = 0, b(2) = 0, b(3) = 0, b(4) = 0, b(5) = 1, b(6) = 3, b(7) = 8, b(8) = 20, b(9) = 47, b(10) = 108, b(11) = 242, b(12) = 534, b(13) = 1161, b(14) = 2501, b(15) = 5339, b(16) = 11321, b(17) = 23857, b(18) = 50030, b(19) = 104454, b(20) = 217274, b(21) = 450446, b(22) = 931168, b(23) = 1919968, b(24) = 3949755, b(25) = 8108786, b(26) = 16616666, b(27) = 33994710, b(28) = 69442757, b(29) = 141660951, b(30) = 288624841, b(31) = 587387007, b(32) = 1194162663, b(33) = 2425427154, b(34) = 4921887371, b(35) = 9979841273 This enables us to compute the first, 20000, terms of these sequences The probability of Alice winning the bet, as n grows larger is approximately 0.1058 1/2 - ------ 1/2 n The probability of Bob winning the bet, as n grows larger is approximately 1.02 1/2 - ---- 1/2 n You can see that indeed Alice has a better chance, but not significantly so. ----------------------------------------- This took, 100.127, seconds to generate ----------------------------------------------------------------------------\ ----------------------- Question Mumber, 13, : If Alice bets that there are more occurrences of conse\ cutive substrings in, {[1, 2, 1, 2, 2]}, than in, {[1, 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 , 13.1, : Let a(n) be the number of words of length n in the alphabet , {1, 2}, with more occurences of, {[1, 2, 1, 2, 2]}, then , {[1, 1, 1, 1, 1]} a(n) satisfies the following linear recurrence equation with polynomial coef\ ficients of order, 38 (n + 4) (n + 2) (n + 1) a(n) (n + 5) (7 n + 18) (n + 2) a(n + 1) -192/5 ---------------------------- + 96/5 ----------------------------------- (n + 33) (n + 38) (n + 34) (n + 33) (n + 38) (n + 34) 2 (n + 6) (47 n + 243 n + 310) a(n + 2) - 16/5 -------------------------------------- + a(n + 38) (n + 33) (n + 38) (n + 34) 3 2 (73 n + 2127 n + 15128 n + 31032) a(n + 3) - 8/5 -------------------------------------------- (n + 33) (n + 38) (n + 34) 3 2 (5 n - 508 n - 4959 n - 11416) a(n + 4) - 24/5 ----------------------------------------- (n + 33) (n + 38) (n + 34) 3 2 (43 n - 1515 n - 21846 n - 68072) a(n + 5) + 12/5 -------------------------------------------- (n + 33) (n + 38) (n + 34) 3 2 (932 n + 26169 n + 229468 n + 645924) a(n + 6) + 4/5 ------------------------------------------------ (n + 33) (n + 38) (n + 34) 3 2 (4457 n + 71517 n + 243586 n - 350964) a(n + 7) - 1/5 ------------------------------------------------- (n + 33) (n + 38) (n + 34) 3 2 (4741 n + 140742 n + 1501559 n + 5573076) a(n + 8) + 1/5 ---------------------------------------------------- (n + 33) (n + 38) (n + 34) 3 2 (2239 n + 76470 n + 876112 n + 3347257) a(n + 9) - 6/5 -------------------------------------------------- (n + 33) (n + 38) (n + 34) 3 2 (4847 n + 159252 n + 1849201 n + 7508658) a(n + 10) + 2/5 ----------------------------------------------------- (n + 33) (n + 38) (n + 34) 3 2 (385 n - 75243 n - 2060446 n - 13124664) a(n + 11) + 1/5 ---------------------------------------------------- (n + 33) (n + 38) (n + 34) 3 2 (2810 n + 112405 n + 1414630 n + 5577208) a(n + 12) + 6/5 ----------------------------------------------------- (n + 33) (n + 38) (n + 34) 3 2 (1693 n + 5731 n - 1056834 n - 11217448) a(n + 13) - 3/5 ---------------------------------------------------- (n + 33) (n + 38) (n + 34) 3 2 (2892 n + 159629 n + 3008156 n + 18934152) a(n + 14) - 6/5 ------------------------------------------------------ (n + 33) (n + 38) (n + 34) 3 2 (258 n + 35165 n + 969281 n + 7529050) a(n + 15) + 12/5 -------------------------------------------------- (n + 33) (n + 38) (n + 34) 3 2 (31033 n + 1847382 n + 34956401 n + 212886180) a(n + 16) - 1/5 ---------------------------------------------------------- (n + 33) (n + 38) (n + 34) 3 2 (9101 n + 527641 n + 9908913 n + 60554309) a(n + 17) + 6/5 ------------------------------------------------------ (n + 33) (n + 38) (n + 34) 3 2 (11312 n + 752149 n + 15827371 n + 106971758) a(n + 18) - 3/5 --------------------------------------------------------- (n + 33) (n + 38) (n + 34) 3 2 (21563 n + 1362030 n + 27771391 n + 183693696) a(n + 19) + 1/5 ---------------------------------------------------------- (n + 33) (n + 38) (n + 34) 3 2 (1129 n + 60012 n + 1034735 n + 5737908) a(n + 20) - 2/5 ---------------------------------------------------- (n + 33) (n + 38) (n + 34) 3 2 (11225 n + 545259 n + 8125546 n + 34373040) a(n + 21) - 1/5 ------------------------------------------------------- (n + 33) (n + 38) (n + 34) 3 2 (2981 n + 157277 n + 2752174 n + 16271216) a(n + 22) + 3/5 ------------------------------------------------------ (n + 33) (n + 38) (n + 34) 3 2 (6761 n + 415689 n + 8800102 n + 65030364) a(n + 23) - 1/5 ------------------------------------------------------ (n + 33) (n + 38) (n + 34) 3 2 (37 n - 43281 n - 1879798 n - 19541904) a(n + 24) + 1/5 --------------------------------------------------- (n + 33) (n + 38) (n + 34) 2 (17 n + 1191 n + 20784) a(n + 37) - 3/5 ---------------------------------- (n + 38) (n + 34) 3 2 (1651 n + 99489 n + 1876625 n + 10576665) a(n + 25) + 4/5 ----------------------------------------------------- (n + 33) (n + 38) (n + 34) 3 2 (4059 n + 242530 n + 4484773 n + 24106982) a(n + 26) - 3/5 ------------------------------------------------------ (n + 33) (n + 38) (n + 34) 3 2 (4414 n + 291131 n + 6194971 n + 41989500) a(n + 27) + 3/5 ------------------------------------------------------ (n + 33) (n + 38) (n + 34) 3 2 (2855 n + 192669 n + 4185361 n + 28847040) a(n + 28) - 2/5 ------------------------------------------------------ (n + 33) (n + 38) (n + 34) 3 2 (233 n + 14494 n + 271245 n + 1360424) a(n + 29) + 3/5 -------------------------------------------------- (n + 33) (n + 38) (n + 34) 3 2 (230 n + 19803 n + 567937 n + 5426742) a(n + 30) - 4/5 -------------------------------------------------- (n + 33) (n + 38) (n + 34) 3 2 (316 n + 26667 n + 745643 n + 6903858) a(n + 31) + 2/5 -------------------------------------------------- (n + 33) (n + 38) (n + 34) 3 2 (119 n + 9327 n + 234286 n + 1846008) a(n + 32) - 1/5 ------------------------------------------------- (n + 33) (n + 38) (n + 34) 3 2 (37 n + 3390 n + 103058 n + 1039149) a(n + 33) + 4/5 ------------------------------------------------ (n + 33) (n + 38) (n + 34) 3 2 (103 n + 10479 n + 354308 n + 3981780) a(n + 34) + 1/5 -------------------------------------------------- (n + 33) (n + 38) (n + 34) 3 2 (77 n + 7686 n + 255385 n + 2824956) a(n + 35) - 4/5 ------------------------------------------------ (n + 33) (n + 38) (n + 34) 3 2 (97 n + 9822 n + 331037 n + 3714072) a(n + 36) + 2/5 ------------------------------------------------ = 0 (n + 33) (n + 38) (n + 34) Subject to the initial conditions a(1) = 0, a(2) = 0, a(3) = 0, a(4) = 0, a(5) = 1, a(6) = 4, a(7) = 12, a(8) = 32, a(9) = 79, a(10) = 186, a(11) = 424, a(12) = 944, a(13) = 2064, a(14) = 4453, a(15) = 9503, a(16) = 20103, a(17) = 42222, a(18) = 88149, a(19) = 183105, a(20) = 378717, a(21) = 780414, a(22) = 1603048, a(23) = 3283670, a(24) = 6709867, a(25) = 13681603, a(26) = 27844348, a(27) = 56572728, a(28) = 114769750, a(29) = 232523969, a(30) = 470531658, a(31) = 951139354, a(32) = 1920793210, a(33) = 3875607070, a(34) = 7813728931, a(35) = 15742335009, a(36) = 31695774035, a(37) = 63779495284, a(38) = 128271947961 Lemma , 13.2, : Let b(n) be the number of words of length n in the alphabet , {1, 2}, with more occurences of, {[1, 1, 1, 1, 1]}, then , {[1, 2, 1, 2, 2]} b(n) satisfies the following linear recurrence equation with polynomial coef\ ficients of order, 19 (n + 1) (n + 2) b(n) (n + 2) (n - 3) b(n + 1) -16/5 -------------------- + 8/5 ------------------------ (n + 19) (n + 14) (n + 19) (n + 14) 2 (n + 7) (n + 2) b(n + 2) (n + 49 n + 178) b(n + 3) + 4/5 ------------------------ + 2/5 -------------------------- (n + 19) (n + 14) (n + 19) (n + 14) 2 (20 n + 346 n + 1239) b(n + 4) + 4/5 ------------------------------- (n + 19) (n + 14) 2 (151 n + 2121 n + 7022) b(n + 5) - 1/5 --------------------------------- (n + 19) (n + 14) 2 (45 n + 755 n + 3094) b(n + 6) + 1/5 ------------------------------- (n + 19) (n + 14) 2 (39 n + 491 n + 1534) b(n + 7) + 1/5 ------------------------------- (n + 19) (n + 14) 2 (65 n + 799 n + 1896) b(n + 8) + 1/5 ------------------------------- (n + 19) (n + 14) 2 (155 n + 3227 n + 16520) b(n + 9) + 1/5 ---------------------------------- (n + 19) (n + 14) 2 (17 n + 433 n + 2796) b(n + 10) - 2/5 -------------------------------- (n + 19) (n + 14) 2 (18 n + 401 n + 2335) b(n + 11) - 2/5 -------------------------------- (n + 19) (n + 14) 2 (33 n + 754 n + 4274) b(n + 12) - 2/5 -------------------------------- (n + 19) (n + 14) (35 n + 499) (n + 9) b(n + 13) - 2/5 ------------------------------ (n + 19) (n + 14) 2 (25 n + 543 n + 2660) b(n + 14) + 2/5 -------------------------------- (n + 19) (n + 14) 2 (3 n + 137 n + 1384) b(n + 15) + 1/5 ------------------------------- (n + 19) (n + 14) (n + 17) (17 n + 220) b(n + 16) (9 n + 173) b(n + 17) + 1/5 ------------------------------- + 1/5 --------------------- (n + 19) (n + 14) n + 19 2 (19 n + 615 n + 4874) b(n + 18) - 1/5 -------------------------------- + b(n + 19) = 0 (n + 19) (n + 14) Subject to the initial conditions b(1) = 0, b(2) = 0, b(3) = 0, b(4) = 0, b(5) = 1, b(6) = 3, b(7) = 8, b(8) = 20, b(9) = 47, b(10) = 108, b(11) = 242, b(12) = 533, b(13) = 1158, b(14) = 2492, b(15) = 5315, b(16) = 11257, b(17) = 23702, b(18) = 49655, b(19) = 103579 This enables us to compute the first, 20000, terms of these sequences The probability of Alice winning the bet, as n grows larger is approximately 0.036414 1/2 - -------- 1/2 n The probability of Bob winning the bet, as n grows larger is approximately 1.129 1/2 - ----- 1/2 n You can see that indeed Alice has a better chance, but not significantly so. ----------------------------------------- This took, 61.157, seconds to generate ----------------------------------------------------------------------------\ ----------------------- Question Mumber, 14, : If Alice bets that there are more occurrences of conse\ cutive substrings in, {[2, 1, 1, 1, 2]}, than in, {[1, 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 , 14.1, : Let a(n) be the number of words of length n in the alphabet , {1, 2}, with more occurences of, {[2, 1, 1, 1, 2]}, then , {[1, 1, 1, 1, 1]} a(n) satisfies the following linear recurrence equation with polynomial coef\ ficients of order, 31 2 (n - 1) (533 n + 3264 n + 3780) a(n + 3) 48/5 ----------------------------------------- (n + 31) (n + 27) (n + 26) 2 n (2367 n + 19842 n + 33583) a(n + 4) + 12/5 -------------------------------------- (n + 31) (n + 27) (n + 26) 2 (n + 1) (2944 n + 53237 n + 156912) a(n + 5) + 2/5 --------------------------------------------- (n + 31) (n + 27) (n + 26) 2 (n + 29) (41 n + 2033 n + 25230) a(n + 27) - 1/5 ------------------------------------------- (n + 31) (n + 27) (n + 26) 3 2 (5777 n + 20025 n - 124844 n - 266292) a(n + 6) - 1/5 ------------------------------------------------- (n + 31) (n + 27) (n + 26) 3 2 (7641 n + 112972 n + 508789 n + 722646) a(n + 7) - 3/5 -------------------------------------------------- (n + 31) (n + 27) (n + 26) 3 2 (1699 n + 54993 n + 471128 n + 1093968) a(n + 8) - 4/5 -------------------------------------------------- (n + 31) (n + 27) (n + 26) 3 2 (5453 n + 125490 n + 925401 n + 2161860) a(n + 9) - 6/5 --------------------------------------------------- (n + 31) (n + 27) (n + 26) 3 2 (7037 n + 268887 n + 2923738 n + 9349848) a(n + 10) - 1/5 ----------------------------------------------------- (n + 31) (n + 27) (n + 26) 3 2 (11267 n + 325800 n + 3103507 n + 9947682) a(n + 11) - 1/5 ------------------------------------------------------ (n + 31) (n + 27) (n + 26) 3 2 (27527 n + 655125 n + 4604200 n + 9292416) a(n + 12) + 1/5 ------------------------------------------------------ (n + 31) (n + 27) (n + 26) 3 2 (6509 n + 163734 n + 1336429 n + 3794004) a(n + 13) - 1/5 ----------------------------------------------------- (n + 31) (n + 27) (n + 26) 3 2 (9221 n + 374997 n + 4865944 n + 19892100) a(n + 14) + 1/5 ------------------------------------------------------ (n + 31) (n + 27) (n + 26) 3 2 (563 n - 54102 n - 1671947 n - 10645386) a(n + 15) - 1/5 ---------------------------------------------------- (n + 31) (n + 27) (n + 26) 3 2 (1957 n + 74660 n + 933557 n + 3872940) a(n + 16) + 6/5 --------------------------------------------------- (n + 31) (n + 27) (n + 26) 3 2 (6145 n + 242973 n + 3062846 n + 12125478) a(n + 17) - 2/5 ------------------------------------------------------ (n + 31) (n + 27) (n + 26) 3 2 (244 n + 4011 n - 26353 n - 361242) a(n + 18) + 2/5 ----------------------------------------------- (n + 31) (n + 27) (n + 26) 3 2 (338 n + 23937 n + 515017 n + 3450420) a(n + 19) - 2/5 -------------------------------------------------- (n + 31) (n + 27) (n + 26) 3 2 (944 n + 41775 n + 555199 n + 1978944) a(n + 20) + 2/5 -------------------------------------------------- (n + 31) (n + 27) (n + 26) 3 2 (736 n + 38142 n + 648197 n + 3621567) a(n + 21) - 4/5 -------------------------------------------------- (n + 31) (n + 27) (n + 26) 3 2 (505 n + 27315 n + 482318 n + 2769784) a(n + 22) + 3/5 -------------------------------------------------- (n + 31) (n + 27) (n + 26) 192 (n - 1) (n - 4) (n + 1) a(n) + -------------------------------- (n + 31) (n + 27) (n + 26) 2 (n - 3) (152 n + 321 n - 20) a(n + 1) + 32/5 -------------------------------------- (n + 31) (n + 27) (n + 26) 2 (n - 2) (109 n + 457 n + 320) a(n + 2) + 144/5 --------------------------------------- + a(n + 31) (n + 31) (n + 27) (n + 26) 2 (31 n + 1759 n + 24840) a(n + 30) - 1/5 ---------------------------------- (n + 27) (n + 31) 3 2 (473 n + 30810 n + 666247 n + 4790670) a(n + 23) + 1/5 -------------------------------------------------- (n + 31) (n + 27) (n + 26) 3 2 (29 n + 2170 n + 53595 n + 438700) a(n + 24) + 6/5 ---------------------------------------------- (n + 31) (n + 27) (n + 26) 3 2 (152 n + 9141 n + 177799 n + 1110750) a(n + 25) - 2/5 ------------------------------------------------- (n + 31) (n + 27) (n + 26) (59 n + 2895) (n + 22) a(n + 26) - 1/5 -------------------------------- (n + 27) (n + 31) 3 2 (37 n + 2757 n + 68006 n + 555120) a(n + 28) + 1/5 ---------------------------------------------- (n + 31) (n + 27) (n + 26) 3 2 (15 n + 1244 n + 34301 n + 314480) a(n + 29) + 3/5 ---------------------------------------------- = 0 (n + 31) (n + 27) (n + 26) Subject to the initial conditions a(1) = 0, a(2) = 0, a(3) = 0, a(4) = 0, a(5) = 1, a(6) = 4, a(7) = 12, a(8) = 32, a(9) = 79, a(10) = 185, a(11) = 420, a(12) = 932, a(13) = 2033, a(14) = 4378, a(15) = 9330, a(16) = 19717, a(17) = 41381, a(18) = 86347, a(19) = 179298, a(20) = 370760, a(21) = 763927, a(22) = 1569134, a(23) = 3214320, a(24) = 6568770, a(25) = 13395757, a(26) = 27267373, a(27) = 55411780, a(28) = 112440141, a(29) = 227860357, a(30) = 461214944, a(31) = 932560586 Lemma , 14.2, : Let b(n) be the number of words of length n in the alphabet , {1, 2}, with more occurences of, {[1, 1, 1, 1, 1]}, then , {[2, 1, 1, 1, 2]} b(n) satisfies the following linear recurrence equation with polynomial coef\ ficients of order, 25 3 2 (2407 n + 78345 n + 818744 n + 2763468) b(n + 14) -1/10 --------------------------------------------------- (n + 20) (n + 25) (n + 24) 3 2 (891 n + 32537 n + 385680 n + 1472144) b(n + 15) + 3/10 -------------------------------------------------- (n + 20) (n + 25) (n + 24) 3 2 (1139 n + 47187 n + 639556 n + 2818752) b(n + 16) - 1/10 --------------------------------------------------- (n + 20) (n + 25) (n + 24) 3 2 (77 n + 2643 n + 31138 n + 150000) b(n + 17) + 1/10 ---------------------------------------------- (n + 20) (n + 25) (n + 24) 3 2 (45 n + 2037 n + 30314 n + 150072) b(n + 18) + 3/10 ---------------------------------------------- (n + 20) (n + 25) (n + 24) 3 2 (379 n + 20667 n + 366626 n + 2101704) b(n + 19) + 1/10 -------------------------------------------------- (n + 20) (n + 25) (n + 24) 3 2 (451 n + 25005 n + 458198 n + 2770464) b(n + 20) - 1/10 -------------------------------------------------- (n + 20) (n + 25) (n + 24) 3 2 (37 n + 1773 n + 26804 n + 123828) b(n + 21) + 1/10 ---------------------------------------------- (n + 20) (n + 25) (n + 24) 3 2 (61 n + 3723 n + 75452 n + 507780) b(n + 22) + 1/10 ---------------------------------------------- (n + 20) (n + 25) (n + 24) 3 2 (17 n + 1157 n + 26082 n + 194632) b(n + 23) + 3/10 ---------------------------------------------- (n + 20) (n + 25) (n + 24) 192 (n - 1) (n - 4) (n + 1) b(n) - -------------------------------- + b(n + 25) (n + 20) (n + 25) (n + 24) 3 2 (26 n - 15 n - 169 n + 20) b(n + 1) - 96/5 ------------------------------------- (n + 20) (n + 25) (n + 24) 3 2 (109 n + 283 n - 506 n - 532) b(n + 2) - 48/5 ---------------------------------------- (n + 20) (n + 25) (n + 24) 3 2 (14 n + 94 n + 54 n + 299) b(n + 3) - 96/5 ------------------------------------- (n + 20) (n + 25) (n + 24) 3 2 (199 n + 2376 n + 2933 n - 2232) b(n + 4) - 4/5 ------------------------------------------- (n + 20) (n + 25) (n + 24) 3 2 (542 n + 3651 n + 5365 n + 9016) b(n + 5) + 6/5 ------------------------------------------- (n + 20) (n + 25) (n + 24) 3 2 (1231 n + 11783 n + 24024 n + 1720) b(n + 6) - 3/5 ---------------------------------------------- (n + 20) (n + 25) (n + 24) 3 2 (4820 n + 70599 n + 323767 n + 484548) b(n + 7) + 1/5 ------------------------------------------------- (n + 20) (n + 25) (n + 24) 3 2 (2873 n + 56121 n + 337780 n + 663216) b(n + 8) + 1/10 ------------------------------------------------- (n + 20) (n + 25) (n + 24) 3 2 (5533 n + 137403 n + 1071362 n + 2603976) b(n + 9) + 1/10 ---------------------------------------------------- (n + 20) (n + 25) (n + 24) 3 2 (8291 n + 153399 n + 768562 n + 832944) b(n + 10) - 1/10 --------------------------------------------------- (n + 20) (n + 25) (n + 24) 3 2 (6073 n + 152253 n + 1259930 n + 3516744) b(n + 11) + 1/10 ----------------------------------------------------- (n + 20) (n + 25) (n + 24) 3 2 (1817 n + 55131 n + 527974 n + 1516560) b(n + 12) - 1/10 --------------------------------------------------- (n + 20) (n + 25) (n + 24) 3 2 (449 n + 17457 n + 210508 n + 745452) b(n + 13) - 1/10 ------------------------------------------------- (n + 20) (n + 25) (n + 24) 2 (5 n + 219 n + 2374) b(n + 24) - ------------------------------- = 0 (n + 25) (n + 20) Subject to the initial conditions b(1) = 0, b(2) = 0, b(3) = 0, b(4) = 0, b(5) = 1, b(6) = 3, b(7) = 8, b(8) = 20, b(9) = 48, b(10) = 110, b(11) = 247, b(12) = 545, b(13) = 1186, b(14) = 2554, b(15) = 5451, b(16) = 11551, b(17) = 24330, b(18) = 50984, b(19) = 106371, b(20) = 221085, b(21) = 457991, b(22) = 946001, b(23) = 1948992, b(24) = 4006248, b(25) = 8218283 This enables us to compute the first, 20000, terms of these sequences The probability of Alice winning the bet, as n grows larger is approximately 0.070541 1/2 - -------- 1/2 n The probability of Bob winning the bet, as n grows larger is approximately 1.058 1/2 - ----- 1/2 n You can see that indeed Alice has a better chance, but not significantly so. ----------------------------------------- This took, 62.346, seconds to generate The best bet against, [1, 1, 1, 1, 1], is a member of, {[1, 1, 1, 1, 2], [2, 1, 1, 1, 1]}, 1.50011 and then your edge, if you have n rolls, is approximately, ------- 1/2 n The next best bet is a member of, {[1, 1, 1, 2, 2], [2, 2, 1, 1, 1]}, 1.2192820 and then your edge is approximately, --------- 1/2 n The next best bet is a member of, {[1, 1, 1, 2, 1], [1, 2, 1, 1, 1]}, 1.13853 and then your edge is approximately, ------- 1/2 n The next best bet is a member of, {[1, 1, 2, 1, 2], [1, 1, 2, 2, 2], [2, 1, 2, 1, 1], [2, 2, 2, 1, 1]}, 1.131307 and then your edge is approximately, -------- 1/2 n The next best bet is a member of, {[1, 2, 1, 2, 2], [1, 2, 2, 2, 2], [2, 2, 1, 2, 1], [2, 2, 2, 2, 1]}, 1.092586 and then your edge is approximately, -------- 1/2 n The next best bet is a member of, {[1, 1, 2, 2, 1], [1, 2, 2, 1, 1]}, 1.05458 and then your edge is approximately, ------- 1/2 n The next best bet is a member of, {[1, 2, 2, 2, 1]}, 1.01714 and then your edge is approximately, ------- 1/2 n The next best bet is a member of, {[2, 1, 1, 1, 2], [2, 1, 1, 2, 2], [2, 1, 2, 2, 2], [2, 2, 1, 1, 2], [2, 2, 2, 1, 2]}, 0.987459 and then your edge is approximately, -------- 1/2 n The next best bet is a member of, {[1, 2, 1, 1, 2], [1, 2, 2, 1, 2], [2, 1, 1, 2, 1], [2, 1, 2, 2, 1]}, 0.9142 and then your edge is approximately, ------ 1/2 n The next best bet is a member of, {[1, 1, 2, 1, 1]}, 0.9091 and then your edge is approximately, ------ 1/2 n The next best bet is a member of, {[2, 2, 1, 2, 2]}, 0.8211 and then your edge is approximately, ------ 1/2 n The next best bet is a member of, {[1, 2, 1, 2, 1]}, 0.6846 and then your edge is approximately, ------ 1/2 n The next best bet is a member of, {[2, 1, 2, 1, 2]}, 0.6654 and then your edge is approximately, ------ 1/2 n The next best bet is a member of, {[2, 2, 2, 2, 2]}, and then your edge is exactly 0 ----------------------- This ends this chapter that took, 1014.771, seconds to generate.