How to bet against any given, 3, -letter word in the David Litt game with a fair die with, 3, faces By Shalosh B. Ekhad ----------------------------------------------------------------- ----------------------------------------------------------------- Chapter Number, 1 The Relative Probablity of Winning a Daniel Litt style game when rolling a f\ air, 3, sides die marked with, {1, 2, 3}, of number of occurrences of, [1, 1, 1], Versus the number of occurences of all, 3, letter words in, {1, 2, 3} By Shalosh B. Ekhad ----------------------------------------------------------------------------\ ----------------------- Question Mumber, 1, : If Alice bets that there are more occurrences of consec\ utive substrings in, {[1, 2, 1]}, than in, {[1, 1, 1]}, and Bob, bets vice versa, who is more likely to win? Answer: Alice is more likely to win. Let's be more quantitative. We need the following two lemmas Lemma , 1.1, : Let a(n) be the number of words of length n in the alphabet , {1, 2, 3}, with more occurences of, {[1, 2, 1]}, then , {[1, 1, 1]} a(n) satisfies the following linear recurrence equation with polynomial coef\ ficients of order, 22 864 (2 n + 3) (n + 2) (n + 1) a(n) - ---------------------------------- (n + 20) (n + 19) (n + 22) 2 72 (n + 2) (211 n + 1417 n + 2196) a(n + 1) + -------------------------------------------- (n + 20) (n + 19) (n + 22) 3 2 24 (1874 n + 24231 n + 101137 n + 136110) a(n + 2) - ---------------------------------------------------- (n + 20) (n + 19) (n + 22) 3 2 18 (1031 n + 16147 n + 95466 n + 189056) a(n + 3) + --------------------------------------------------- (n + 20) (n + 19) (n + 22) 3 2 2 (12007 n + 426387 n + 3457706 n + 8173848) a(n + 4) + ------------------------------------------------------- (n + 20) (n + 19) (n + 22) 3 2 (33620 n + 430641 n + 1634809 n + 1514238) a(n + 5) + 4/3 ----------------------------------------------------- (n + 20) (n + 19) (n + 22) 3 2 (249397 n + 5665149 n + 43700510 n + 113907144) a(n + 6) + 1/3 ---------------------------------------------------------- (n + 20) (n + 19) (n + 22) 3 2 (30971 n + 66907 n - 5078414 n - 29210608) a(n + 7) - ----------------------------------------------------- (n + 20) (n + 19) (n + 22) 3 2 (17492 n + 75936 n - 3137663 n - 21684102) a(n + 8) + 4/3 ----------------------------------------------------- (n + 20) (n + 19) (n + 22) 3 2 (78895 n + 2165343 n + 22559306 n + 88193304) a(n + 9) - 1/3 -------------------------------------------------------- (n + 20) (n + 19) (n + 22) 3 2 (86903 n + 2879499 n + 30006490 n + 97758252) a(n + 10) - 2/3 --------------------------------------------------------- (n + 20) (n + 19) (n + 22) 3 2 (35785 n + 1178861 n + 12631086 n + 43941624) a(n + 11) + --------------------------------------------------------- (n + 20) (n + 19) (n + 22) 3 2 4 (2794 n + 152871 n + 2449223 n + 12152364) a(n + 12) + -------------------------------------------------------- (n + 20) (n + 19) (n + 22) 3 2 (22703 n + 1218579 n + 19620154 n + 98638752) a(n + 13) - 1/3 --------------------------------------------------------- (n + 20) (n + 19) (n + 22) 3 2 (3488 n + 131799 n + 1555828 n + 5512860) a(n + 14) + 4/3 ----------------------------------------------------- (n + 20) (n + 19) (n + 22) 3 2 (17915 n + 669507 n + 8023042 n + 30264288) a(n + 15) - 1/3 ------------------------------------------------------- (n + 20) (n + 19) (n + 22) 3 2 (1526 n + 60504 n + 790471 n + 3420258) a(n + 16) + 4/3 --------------------------------------------------- (n + 20) (n + 19) (n + 22) 3 2 (947 n + 42795 n + 601522 n + 2507976) a(n + 17) + 1/3 -------------------------------------------------- (n + 20) (n + 19) (n + 22) 3 2 (125 n + 2817 n - 19142 n - 527436) a(n + 18) - 2/3 ----------------------------------------------- (n + 20) (n + 19) (n + 22) 2 (163 n + 5989 n + 54956) a(n + 19) - ----------------------------------- (n + 19) (n + 20) 3 2 2 (41 n + 2367 n + 45512 n + 291464) a(n + 20) + ------------------------------------------------ (n + 20) (n + 19) (n + 22) 2 (15 n + 602 n + 6024) a(n + 21) - -------------------------------- + a(n + 22) = 0 (n + 22) (n + 20) Subject to the initial conditions a(1) = 0, a(2) = 0, a(3) = 1, a(4) = 6, a(5) = 24, a(6) = 89, a(7) = 319, a(8) = 1097, a(9) = 3668, a(10) = 12063, a(11) = 39137, a(12) = 125525, a(13) = 399054, a(14) = 1259640, a(15) = 3952195, a(16) = 12337292, a(17) = 38347670, a(18) = 118756679, a(19) = 366597733, a(20) = 1128537489, a(21) = 3465675586, a(22) = 10620171614 Lemma , 1.2, : Let b(n) be the number of words of length n in the alphabet , {1, 2, 3}, with more occurences of, {[1, 1, 1]}, then , {[1, 2, 1]} b(n) satisfies the following linear recurrence equation with polynomial coef\ ficients of order, 15 2 864 (2 n + 3) (n + 2) (n + 1) b(n) 72 (n + 2) (19 n + 73 n + 108) b(n + 1) ---------------------------------- - ---------------------------------------- (n + 15) (n + 14) (n + 12) (n + 15) (n + 14) (n + 12) 3 2 24 (266 n + 3387 n + 13861 n + 18246) b(n + 2) + ------------------------------------------------ (n + 15) (n + 14) (n + 12) 3 2 6 (203 n + 4791 n + 32338 n + 65568) b(n + 3) + ----------------------------------------------- (n + 15) (n + 14) (n + 12) 3 2 18 (595 n + 10771 n + 64214 n + 126080) b(n + 4) - -------------------------------------------------- (n + 15) (n + 14) (n + 12) 3 2 2 (1025 n + 8223 n - 29924 n - 254244) b(n + 5) + ------------------------------------------------- (n + 15) (n + 14) (n + 12) 3 2 (5003 n + 148867 n + 1365650 n + 3977112) b(n + 6) + ---------------------------------------------------- (n + 15) (n + 14) (n + 12) 3 2 (2559 n + 79895 n + 758594 n + 2270352) b(n + 7) - -------------------------------------------------- (n + 15) (n + 14) (n + 12) 3 2 4 (61 n - 520 n - 29421 n - 176232) b(n + 8) + ---------------------------------------------- (n + 15) (n + 14) (n + 12) 3 2 4 (137 n + 7303 n + 103456 n + 441324) b(n + 9) + ------------------------------------------------- (n + 15) (n + 14) (n + 12) 3 2 2 (569 n + 20519 n + 240600 n + 922932) b(n + 10) - --------------------------------------------------- (n + 15) (n + 14) (n + 12) 3 2 4 (253 n + 8575 n + 96430 n + 359730) b(n + 11) + ------------------------------------------------- (n + 15) (n + 14) (n + 12) 3 2 2 (235 n + 8201 n + 95120 n + 366504) b(n + 12) - ------------------------------------------------- (n + 15) (n + 14) (n + 12) 3 2 2 (61 n + 2243 n + 27412 n + 111300) b(n + 13) + ------------------------------------------------ (n + 15) (n + 14) (n + 12) 2 (17 n + 423 n + 2616) b(n + 14) - -------------------------------- + b(n + 15) = 0 (n + 15) (n + 12) Subject to the initial conditions b(1) = 0, b(2) = 0, b(3) = 1, b(4) = 5, b(5) = 19, b(6) = 71, b(7) = 254, b(8) = 868, b(9) = 2901, b(10) = 9555, b(11) = 31032, b(12) = 99678, b(13) = 317556, b(14) = 1004682, b(15) = 3159765 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.4233 1/2 - ------ 1/2 n The probability of Bob winning the bet, as n grows larger is approximately 0.8464 1/2 - ------ 1/2 n You can see that indeed Alice has a better chance, but not significantly so. ----------------------------------------- This took, 35.654, seconds to generate ----------------------------------------------------------------------------\ ----------------------- Question Mumber, 2, : If Alice bets that there are more occurrences of consec\ utive substrings in, {[2, 2, 2]}, than in, {[1, 1, 1]}, and Bob, bets vice versa, who is more likely to win? Answer: They are equally likely to win ----------------------------------------------------------------------------\ ----------------------- Question Mumber, 3, : If Alice bets that there are more occurrences of consec\ utive substrings in, {[1, 1, 2]}, than in, {[1, 1, 1]}, and Bob, bets vice versa, who is more likely to win? Answer: Alice is more likely to win. Let's be more quantitative. We need the following two lemmas Lemma , 3.1, : Let a(n) be the number of words of length n in the alphabet , {1, 2, 3}, with more occurences of, {[1, 1, 2]}, then , {[1, 1, 1]} a(n) satisfies the following linear recurrence equation with polynomial coef\ ficients of order, 21 1944 (n + 1) (n + 2) (n + 3) a(n) 648 (11 n + 32) (n + 3) (n + 2) a(n + 1) --------------------------------- + ---------------------------------------- (n + 19) (n + 18) (n + 21) (n + 19) (n + 18) (n + 21) 2 324 (n + 3) (29 n + 219 n + 410) a(n + 2) + ------------------------------------------ (n + 19) (n + 18) (n + 21) 3 2 36 (52 n + 177 n - 1819 n - 6726) a(n + 3) + -------------------------------------------- (n + 19) (n + 18) (n + 21) 3 2 6 (725 n + 13920 n + 79489 n + 139530) a(n + 4) - ------------------------------------------------- (n + 19) (n + 18) (n + 21) 3 2 6 (2281 n + 62871 n + 530540 n + 1416864) a(n + 5) + ---------------------------------------------------- (n + 19) (n + 18) (n + 21) 3 2 (26839 n + 743766 n + 6492557 n + 18229086) a(n + 6) + ------------------------------------------------------ (n + 19) (n + 18) (n + 21) 3 2 (3032 n + 4665 n - 714395 n - 4625442) a(n + 7) + 1/3 ------------------------------------------------- (n + 19) (n + 18) (n + 21) 3 2 (26128 n + 1121367 n + 13897661 n + 53471952) a(n + 8) - 1/3 -------------------------------------------------------- (n + 19) (n + 18) (n + 21) 3 2 (2503 n + 161232 n + 2492381 n + 11240784) a(n + 9) - 1/3 ----------------------------------------------------- (n + 19) (n + 18) (n + 21) 3 2 4 (3032 n + 73724 n + 533683 n + 974722) a(n + 10) - ---------------------------------------------------- (n + 19) (n + 18) (n + 21) 3 2 (2773 n + 79314 n + 672959 n + 1486392) a(n + 11) - 2/3 --------------------------------------------------- (n + 19) (n + 18) (n + 21) 3 2 (17000 n + 544224 n + 5669635 n + 19029189) a(n + 12) + 2/3 ------------------------------------------------------- (n + 19) (n + 18) (n + 21) 3 2 (64 n - 20799 n - 554167 n - 3556227) a(n + 13) - 2/3 ------------------------------------------------- (n + 19) (n + 18) (n + 21) 3 2 (5377 n + 204288 n + 2559041 n + 10553727) a(n + 14) - 2/3 ------------------------------------------------------ (n + 19) (n + 18) (n + 21) 3 2 2 (30 n + 6413 n + 168374 n + 1182627) a(n + 15) - -------------------------------------------------- (n + 19) (n + 18) (n + 21) 3 2 (1109 n + 54714 n + 897577 n + 4897632) a(n + 16) + 2/3 --------------------------------------------------- (n + 19) (n + 18) (n + 21) 3 2 (224 n + 11319 n + 189379 n + 1048836) a(n + 17) + 2/3 -------------------------------------------------- (n + 19) (n + 18) (n + 21) 3 2 (295 n + 15282 n + 263511 n + 1512492) a(n + 18) - -------------------------------------------------- (n + 19) (n + 18) (n + 21) 3 2 (320 n + 17205 n + 307969 n + 1835484) a(n + 19) + 1/3 -------------------------------------------------- (n + 19) (n + 18) (n + 21) 2 (50 n + 1893 n + 17851) a(n + 20) - 1/3 ---------------------------------- + a(n + 21) = 0 (n + 21) (n + 19) Subject to the initial conditions a(1) = 0, a(2) = 0, a(3) = 1, a(4) = 5, a(5) = 21, a(6) = 79, a(7) = 283, a(8) = 977, a(9) = 3290, a(10) = 10875, a(11) = 35443, a(12) = 114229, a(13) = 364843, a(14) = 1156685, a(15) = 3644488, a(16) = 11423152, a(17) = 35644648, a(18) = 110797293, a(19) = 343249281, a(20) = 1060272685, a(21) = 3266670158 Lemma , 3.2, : Let b(n) be the number of words of length n in the alphabet , {1, 2, 3}, with more occurences of, {[1, 1, 1]}, then , {[1, 1, 2]} b(n) satisfies the following linear recurrence equation with polynomial coef\ ficients of order, 10 2 54 (n + 3) (n + 1) b(n) 9 (5 n + 19 n + 20) b(n + 1) - ----------------------- - ----------------------------- (n + 10) (n + 7) (n + 10) (n + 7) 2 2 6 (9 n + 88 n + 187) b(n + 2) 2 (5 n + 19 n - 40) b(n + 3) + ------------------------------ - ----------------------------- (n + 10) (n + 7) (n + 10) (n + 7) 2 (31 n + 759 n + 2918) b(n + 4) - 1/3 ------------------------------- (n + 10) (n + 7) 2 2 (68 n + 612 n + 1171) b(n + 5) 2 (21 n + 233 n + 637) b(n + 6) + 2/3 ------------------------------- - -------------------------------- (n + 10) (n + 7) (n + 10) (n + 7) 2 (29 n + 351 n + 886) b(n + 7) (5 n + 43) (7 n + 41) b(n + 8) - 1/3 ------------------------------ + 2/3 ------------------------------ (n + 10) (n + 7) (n + 10) (n + 7) 2 (13 n + 206 n + 792) b(n + 9) - 2/3 ------------------------------ + b(n + 10) = 0 (n + 10) (n + 7) Subject to the initial conditions b(1) = 0, b(2) = 0, b(3) = 1, b(4) = 4, b(5) = 16, b(6) = 59, b(7) = 209, b(8) = 716, b(9) = 2401, b(10) = 7920 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.4073 1/2 - ------ 1/2 n The probability of Bob winning the bet, as n grows larger is approximately 1.059 1/2 - ----- 1/2 n You can see that indeed Alice has a better chance, but not significantly so. ----------------------------------------- This took, 28.256, seconds to generate ----------------------------------------------------------------------------\ ----------------------- Question Mumber, 4, : If Alice bets that there are more occurrences of consec\ utive substrings in, {[2, 1, 2]}, than in, {[1, 1, 1]}, and Bob, bets vice versa, who is more likely to win? Answer: Alice is more likely to win. Let's be more quantitative. We need the following two lemmas Lemma , 4.1, : Let a(n) be the number of words of length n in the alphabet , {1, 2, 3}, with more occurences of, {[2, 1, 2]}, then , {[1, 1, 1]} a(n) satisfies the following linear recurrence equation with polynomial coef\ ficients of order, 27 1872 (n + 1) (n + 2) (n + 3) a(n) 12 (n + 3) (n + 2) (1327 n + 5881) a(n + 1) --------------------------------- + ------------------------------------------- (n + 25) (n + 24) (n + 27) (n + 25) (n + 24) (n + 27) 2 2 (n + 3) (9968 n + 60609 n + 67768) a(n + 2) + ---------------------------------------------- (n + 25) (n + 24) (n + 27) 3 2 2 (539 n + 27573 n + 453930 n + 2368758) a(n + 21) - ---------------------------------------------------- (n + 25) (n + 24) (n + 27) 3 2 2 (126 n + 6297 n + 96841 n + 425776) a(n + 22) + ------------------------------------------------- (n + 25) (n + 24) (n + 27) 3 2 2 (82 n + 6281 n + 157821 n + 1304646) a(n + 23) + -------------------------------------------------- (n + 25) (n + 24) (n + 27) 3 2 2 (109 n + 7795 n + 185628 n + 1471998) a(n + 24) - --------------------------------------------------- (n + 25) (n + 24) (n + 27) 3 2 2 (43 n + 3116 n + 75227 n + 605074) a(n + 25) + ------------------------------------------------ (n + 25) (n + 24) (n + 27) 3 2 (52071 n + 653594 n + 2775227 n + 3964716) a(n + 3) + ----------------------------------------------------- (n + 25) (n + 24) (n + 27) 3 2 (365 n - 451094 n - 4821299 n - 12747952) a(n + 4) + ---------------------------------------------------- (n + 25) (n + 24) (n + 27) 3 2 2 (5800 n + 133407 n + 1083023 n + 3002904) a(n + 5) + ------------------------------------------------------ (n + 25) (n + 24) (n + 27) 3 2 6 (6087 n + 175665 n + 1448822 n + 3585078) a(n + 6) - ------------------------------------------------------ (n + 25) (n + 24) (n + 27) 3 2 2 (16981 n - 305287 n - 8077766 n - 36604956) a(n + 7) - -------------------------------------------------------- (n + 25) (n + 24) (n + 27) 3 2 (239108 n + 6028221 n + 52366201 n + 156824508) a(n + 8) + 2/3 ---------------------------------------------------------- (n + 25) (n + 24) (n + 27) 3 2 (7154 n - 1101636 n - 22475141 n - 107544078) a(n + 9) - 4/3 -------------------------------------------------------- (n + 25) (n + 24) (n + 27) 3 2 (980105 n + 25915500 n + 225154423 n + 641706180) a(n + 10) + 1/3 ------------------------------------------------------------- (n + 25) (n + 24) (n + 27) 3 2 (655765 n + 17556852 n + 151932287 n + 424383492) a(n + 11) - 1/3 ------------------------------------------------------------- (n + 25) (n + 24) (n + 27) 3 2 (141790 n + 4015992 n + 35511503 n + 93500817) a(n + 12) + 4/3 ---------------------------------------------------------- (n + 25) (n + 24) (n + 27) 3 2 10 (28801 n + 994130 n + 11341705 n + 42833058) a(n + 13) - ----------------------------------------------------------- (n + 25) (n + 24) (n + 27) 3 2 (251449 n + 8913654 n + 103314263 n + 390677022) a(n + 14) + 2/3 ------------------------------------------------------------ (n + 25) (n + 24) (n + 27) 3 2 (182039 n + 7145784 n + 92247361 n + 390941934) a(n + 15) - 2/3 ----------------------------------------------------------- (n + 25) (n + 24) (n + 27) 3 2 2 (53213 n + 2290924 n + 32622893 n + 153647442) a(n + 16) + ------------------------------------------------------------ (n + 25) (n + 24) (n + 27) 3 2 (78275 n + 3499524 n + 51586849 n + 250493766) a(n + 17) - 2/3 ---------------------------------------------------------- (n + 25) (n + 24) (n + 27) 3 2 (39502 n + 1914003 n + 30670697 n + 162393858) a(n + 18) + 2/3 ---------------------------------------------------------- (n + 25) (n + 24) (n + 27) 3 2 (47843 n + 2484654 n + 42718795 n + 242962632) a(n + 19) - 1/3 ---------------------------------------------------------- (n + 25) (n + 24) (n + 27) 3 2 (16297 n + 855666 n + 14781749 n + 83815356) a(n + 20) + 1/3 -------------------------------------------------------- + a(n + 27) (n + 25) (n + 24) (n + 27) 2 (15 n + 752 n + 9409) a(n + 26) - -------------------------------- = 0 (n + 27) (n + 25) Subject to the initial conditions a(1) = 0, a(2) = 0, a(3) = 1, a(4) = 6, a(5) = 26, a(6) = 99, a(7) = 354, a(8) = 1218, a(9) = 4078, a(10) = 13387, a(11) = 43303, a(12) = 138476, a(13) = 438803, a(14) = 1380249, a(15) = 4315261, a(16) = 13423279, a(17) = 41577618, a(18) = 128318265, a(19) = 394794775, a(20) = 1211418663, a(21) = 3708612247, a(22) = 11330581638, a(23) = 34556182414, a(24) = 105226444681, a(25) = 319984546540, a(26) = 971865922642, a(27) = 2948600615760 Lemma , 4.2, : Let b(n) be the number of words of length n in the alphabet , {1, 2, 3}, with more occurences of, {[1, 1, 1]}, then , {[2, 1, 2]} b(n) satisfies the following linear recurrence equation with polynomial coef\ ficients of order, 24 144 (n + 1) (n + 2) (n + 3) b(n) 12 (305 n + 1583) (n + 3) (n + 2) b(n + 1) - -------------------------------- + ------------------------------------------ (n + 24) (n + 23) (n + 21) (n + 24) (n + 23) (n + 21) 2 (13 n + 561 n + 6040) b(n + 23) - -------------------------------- (n + 24) (n + 21) 2 2 (n + 3) (7156 n + 70683 n + 168440) b(n + 2) + ----------------------------------------------- (n + 24) (n + 23) (n + 21) 2 (n + 20) (103 n + 4540 n + 50037) b(n + 22) + 2/3 -------------------------------------------- (n + 24) (n + 23) (n + 21) 3 2 (3215 n + 169095 n + 2957854 n + 17201592) b(n + 18) + 2/3 ------------------------------------------------------ (n + 24) (n + 23) (n + 21) 3 2 (2863 n + 158202 n + 2906483 n + 17745540) b(n + 19) - 1/3 ------------------------------------------------------ (n + 24) (n + 23) (n + 21) 3 2 (1225 n + 71826 n + 1400525 n + 9078588) b(n + 20) + 1/3 ---------------------------------------------------- (n + 24) (n + 23) (n + 21) 3 2 (295 n + 18195 n + 373568 n + 2552784) b(n + 21) - 2/3 -------------------------------------------------- (n + 24) (n + 23) (n + 21) 3 2 (47865 n + 746530 n + 3804673 n + 6336708) b(n + 3) + ----------------------------------------------------- (n + 24) (n + 23) (n + 21) 3 2 (82645 n + 1544878 n + 9413237 n + 18774140) b(n + 4) + ------------------------------------------------------- (n + 24) (n + 23) (n + 21) 3 2 (159724 n + 3324627 n + 22552019 n + 50090196) b(n + 5) + 2/3 --------------------------------------------------------- (n + 24) (n + 23) (n + 21) 3 2 (50498 n + 1308429 n + 10772155 n + 28541436) b(n + 6) + 4/3 -------------------------------------------------------- (n + 24) (n + 23) (n + 21) 3 2 (173 n - 368628 n - 5185889 n - 17362128) b(n + 7) - 1/3 ---------------------------------------------------- (n + 24) (n + 23) (n + 21) 3 2 (148999 n + 3372276 n + 25474205 n + 65221128) b(n + 8) - 1/3 --------------------------------------------------------- (n + 24) (n + 23) (n + 21) 3 2 (92129 n + 2842350 n + 28989541 n + 98165160) b(n + 9) - 2/3 -------------------------------------------------------- (n + 24) (n + 23) (n + 21) 3 2 (5615 n + 293388 n + 4200565 n + 18345336) b(n + 10) - 2/3 ------------------------------------------------------ (n + 24) (n + 23) (n + 21) 3 2 (4181 n + 226911 n + 3514666 n + 16746390) b(n + 11) - 4/3 ------------------------------------------------------ (n + 24) (n + 23) (n + 21) 3 2 4 (8040 n + 288135 n + 3429109 n + 13561224) b(n + 12) + -------------------------------------------------------- (n + 24) (n + 23) (n + 21) 3 2 (16793 n + 591504 n + 6976255 n + 27683388) b(n + 13) - 2/3 ------------------------------------------------------- (n + 24) (n + 23) (n + 21) 3 2 (16633 n + 702174 n + 9892481 n + 46501356) b(n + 14) + 2/3 ------------------------------------------------------- (n + 24) (n + 23) (n + 21) 3 2 4 (2871 n + 123436 n + 1765777 n + 8408790) b(n + 15) - ------------------------------------------------------- (n + 24) (n + 23) (n + 21) 3 2 (4147 n + 186150 n + 2785679 n + 13908336) b(n + 16) + 4/3 ------------------------------------------------------ (n + 24) (n + 23) (n + 21) 3 2 (4925 n + 244074 n + 4028833 n + 22144980) b(n + 17) - 2/3 ------------------------------------------------------ + b(n + 24) (n + 24) (n + 23) (n + 21) = 0 Subject to the initial conditions b(1) = 0, b(2) = 0, b(3) = 1, b(4) = 5, b(5) = 21, b(6) = 79, b(7) = 281, b(8) = 965, b(9) = 3230, b(10) = 10614, b(11) = 34395, b(12) = 110241, b(13) = 350250, b(14) = 1104858, b(15) = 3464673, b(16) = 10810907, b(17) = 33592029, b(18) = 104003961, b(19) = 321010589, b(20) = 988150391, b(21) = 3034656175, b(22) = 9300440437, b(23) = 28451870505, b(24) = 86900357189 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.3919 1/2 - ------ 1/2 n The probability of Bob winning the bet, as n grows larger is approximately 0.7836 1/2 - ------ 1/2 n You can see that indeed Alice has a better chance, but not significantly so. ----------------------------------------- This took, 53.519, seconds to generate ----------------------------------------------------------------------------\ ----------------------- Question Mumber, 5, : If Alice bets that there are more occurrences of consec\ utive substrings in, {[2, 1, 3]}, than in, {[1, 1, 1]}, and Bob, bets vice versa, who is more likely to win? Answer: Alice is more likely to win. Let's be more quantitative. We need the following two lemmas Lemma , 5.1, : Let a(n) be the number of words of length n in the alphabet , {1, 2, 3}, with more occurences of, {[2, 1, 3]}, then , {[1, 1, 1]} a(n) satisfies the following linear recurrence equation with polynomial coef\ ficients of order, 27 2 3 (n + 3) (529 n + 5115 n + 12782) a(n + 2) - -------------------------------------------- (n + 25) (n + 24) (n + 27) 54 (n + 1) (n + 2) (n + 3) a(n) 144 (n + 4) (n + 3) (n + 2) a(n + 1) + ------------------------------- - ------------------------------------ (n + 25) (n + 24) (n + 27) (n + 25) (n + 24) (n + 27) 2 (15 n + 752 n + 9409) a(n + 26) - -------------------------------- + a(n + 27) (n + 27) (n + 25) 3 2 (6565 n - 78614 n - 2415173 n - 10833962) a(n + 7) - ---------------------------------------------------- (n + 25) (n + 24) (n + 27) 3 2 (69380 n + 1622667 n + 12134728 n + 28595013) a(n + 8) - 2/3 -------------------------------------------------------- (n + 25) (n + 24) (n + 27) 3 2 (162649 n + 5116656 n + 52523375 n + 176618592) a(n + 9) - 1/3 ---------------------------------------------------------- (n + 25) (n + 24) (n + 27) 3 2 (20227 n + 1583478 n + 26610425 n + 128067150) a(n + 10) - 1/3 ---------------------------------------------------------- (n + 25) (n + 24) (n + 27) 3 2 2 (24661 n + 749292 n + 7272083 n + 22049388) a(n + 11) + --------------------------------------------------------- (n + 25) (n + 24) (n + 27) 3 2 (80788 n + 3110073 n + 39322256 n + 163295187) a(n + 12) + 2/3 ---------------------------------------------------------- (n + 25) (n + 24) (n + 27) 3 2 (7229 n + 566492 n + 11154971 n + 65017148) a(n + 13) + ------------------------------------------------------- (n + 25) (n + 24) (n + 27) 3 2 (24837 n + 929088 n + 11134663 n + 41939636) a(n + 14) - -------------------------------------------------------- (n + 25) (n + 24) (n + 27) 3 2 (66767 n + 3345282 n + 54591445 n + 290961618) a(n + 15) - 1/3 ---------------------------------------------------------- (n + 25) (n + 24) (n + 27) 3 2 (3659 n + 321525 n + 7626799 n + 54654681) a(n + 16) - 2/3 ------------------------------------------------------ (n + 25) (n + 24) (n + 27) 3 2 (10105 n + 506118 n + 8337343 n + 45067306) a(n + 17) + ------------------------------------------------------- (n + 25) (n + 24) (n + 27) 3 2 2 (2953 n + 179891 n + 3603315 n + 23784369) a(n + 18) + -------------------------------------------------------- (n + 25) (n + 24) (n + 27) 3 2 (4367 n + 228618 n + 3852001 n + 20557686) a(n + 19) - 1/3 ------------------------------------------------------ (n + 25) (n + 24) (n + 27) 3 2 (3653 n + 220962 n + 4459099 n + 30023958) a(n + 20) - ------------------------------------------------------ (n + 25) (n + 24) (n + 27) 3 2 (836 n + 44211 n + 749998 n + 3992943) a(n + 21) + 2/3 -------------------------------------------------- (n + 25) (n + 24) (n + 27) 3 2 (2953 n + 195576 n + 4319843 n + 31826364) a(n + 22) + 1/3 ------------------------------------------------------ (n + 25) (n + 24) (n + 27) 3 2 (737 n + 47424 n + 1015903 n + 7246992) a(n + 23) - 1/3 --------------------------------------------------- (n + 25) (n + 24) (n + 27) 3 2 (143 n + 10312 n + 247493 n + 1977012) a(n + 24) - -------------------------------------------------- (n + 25) (n + 24) (n + 27) 3 2 (81 n + 5872 n + 141819 n + 1141148) a(n + 25) + ------------------------------------------------ (n + 25) (n + 24) (n + 27) 3 2 3 (243 n + 6910 n + 49609 n + 103686) a(n + 3) - ------------------------------------------------ (n + 25) (n + 24) (n + 27) 3 2 4 (1687 n + 18608 n + 45391 n - 27942) a(n + 4) + ------------------------------------------------- (n + 25) (n + 24) (n + 27) 3 2 4 (3715 n + 67832 n + 385589 n + 672376) a(n + 5) + --------------------------------------------------- (n + 25) (n + 24) (n + 27) 3 2 (14663 n + 450294 n + 3973617 n + 10756362) a(n + 6) + ------------------------------------------------------ = 0 (n + 25) (n + 24) (n + 27) Subject to the initial conditions a(1) = 0, a(2) = 0, a(3) = 1, a(4) = 6, a(5) = 27, a(6) = 105, a(7) = 380, a(8) = 1314, a(9) = 4409, a(10) = 14480, a(11) = 46806, a(12) = 149468, a(13) = 472763, a(14) = 1483925, a(15) = 4628838, a(16) = 14364742, a(17) = 44387488, a(18) = 136664364, a(19) = 419488390, a(20) = 1284247530, a(21) = 3922850548, a(22) = 11959476936, a(23) = 36399183405, a(24) = 110620176566, a(25) = 335753314105, a(26) = 1017929773518, a(27) = 3083084677252 Lemma , 5.2, : Let b(n) be the number of words of length n in the alphabet , {1, 2, 3}, with more occurences of, {[1, 1, 1]}, then , {[2, 1, 3]} b(n) satisfies the following linear recurrence equation with polynomial coef\ ficients of order, 9 6 (n + 1) (n + 2) b(n) 2 (n + 19) (n + 2) b(n + 1) - ---------------------- - --------------------------- (n + 9) (n + 6) (n + 9) (n + 6) 2 (127 n + 771 n + 1142) b(n + 2) + 1/3 -------------------------------- (n + 9) (n + 6) 2 (55 n + 359 n + 510) b(n + 3) (n + 4) (4 n + 9) b(n + 4) + 1/3 ------------------------------ - 8/3 -------------------------- (n + 9) (n + 6) (n + 9) (n + 6) 2 2 (13 n + 71) b(n + 5) (2 n + 22 n + 51) b(n + 6) - ---------------------- - 8/3 --------------------------- n + 9 (n + 9) (n + 6) 2 (31 n + 403 n + 1266) b(n + 7) + 2/3 ------------------------------- (n + 9) (n + 6) 2 (25 n + 351 n + 1190) b(n + 8) - 1/3 ------------------------------- + b(n + 9) = 0 (n + 9) (n + 6) Subject to the initial conditions b(1) = 0, b(2) = 0, b(3) = 1, b(4) = 5, b(5) = 21, b(6) = 79, b(7) = 281, b(8) = 963, b(9) = 3218 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.3389 1/2 - ------ 1/2 n The probability of Bob winning the bet, as n grows larger is approximately 0.8809 1/2 - ------ 1/2 n You can see that indeed Alice has a better chance, but not significantly so. ----------------------------------------- This took, 36.925, seconds to generate ----------------------------------------------------------------------------\ ----------------------- Question Mumber, 6, : If Alice bets that there are more occurrences of consec\ utive substrings in, {[1, 2, 2]}, than in, {[1, 1, 1]}, and Bob, bets vice versa, who is more likely to win? Answer: Alice is more likely to win. Let's be more quantitative. We need the following two lemmas Lemma , 6.1, : Let a(n) be the number of words of length n in the alphabet , {1, 2, 3}, with more occurences of, {[1, 2, 2]}, then , {[1, 1, 1]} a(n) satisfies the following linear recurrence equation with polynomial coef\ ficients of order, 21 1701 (n + 1) (n + 2) (n + 3) a(n) 243 (17 n - 6) (n + 3) (n + 2) a(n + 1) - --------------------------------- + --------------------------------------- (n + 19) (n + 18) (n + 21) (n + 19) (n + 18) (n + 21) 2 27 (n + 3) (23 n + 849 n + 2056) a(n + 2) + ------------------------------------------ (n + 19) (n + 18) (n + 21) 3 2 27 (169 n + 2622 n + 15223 n + 29566) a(n + 3) + ------------------------------------------------ (n + 19) (n + 18) (n + 21) 3 2 3 (4840 n + 102225 n + 640325 n + 1246386) a(n + 4) - ----------------------------------------------------- (n + 19) (n + 18) (n + 21) 3 2 3 (3385 n + 49481 n + 170144 n - 13430) a(n + 5) + -------------------------------------------------- (n + 19) (n + 18) (n + 21) 3 2 3 (3482 n + 154207 n + 1603453 n + 4856894) a(n + 6) + ------------------------------------------------------ (n + 19) (n + 18) (n + 21) 3 2 (59075 n + 1667001 n + 14921170 n + 43094853) a(n + 7) - 2/3 -------------------------------------------------------- (n + 19) (n + 18) (n + 21) 3 2 (48074 n + 1363311 n + 12792103 n + 39801840) a(n + 8) + -------------------------------------------------------- (n + 19) (n + 18) (n + 21) 3 2 (43339 n + 1821123 n + 23081162 n + 92066364) a(n + 9) - 1/3 -------------------------------------------------------- (n + 19) (n + 18) (n + 21) 3 2 (4670 n - 401523 n - 9543323 n - 50468514) a(n + 10) - 1/3 ------------------------------------------------------ (n + 19) (n + 18) (n + 21) 3 2 (17090 n + 588018 n + 6477682 n + 22737687) a(n + 11) - 2/3 ------------------------------------------------------- (n + 19) (n + 18) (n + 21) 3 2 (38125 n + 1064469 n + 8719772 n + 17173824) a(n + 12) + 1/3 -------------------------------------------------------- (n + 19) (n + 18) (n + 21) 3 2 (21473 n + 582618 n + 4189831 n + 3190524) a(n + 13) - 1/3 ------------------------------------------------------ (n + 19) (n + 18) (n + 21) 3 2 (20273 n + 736650 n + 8707345 n + 33158730) a(n + 14) + 1/3 ------------------------------------------------------- (n + 19) (n + 18) (n + 21) 3 2 (14969 n + 617205 n + 8422702 n + 38001030) a(n + 15) - 1/3 ------------------------------------------------------- (n + 19) (n + 18) (n + 21) 3 2 (1855 n + 76245 n + 1022525 n + 4442649) a(n + 16) + 2/3 ---------------------------------------------------- (n + 19) (n + 18) (n + 21) 3 2 (1571 n + 84051 n + 1489312 n + 8745672) a(n + 17) + 1/3 ---------------------------------------------------- (n + 19) (n + 18) (n + 21) 2 2 (n + 17) (224 n + 7929 n + 70035) a(n + 18) - ---------------------------------------------- (n + 19) (n + 18) (n + 21) 3 2 (130 n + 7019 n + 126201 n + 755696) a(n + 19) + ------------------------------------------------ (n + 19) (n + 18) (n + 21) 2 (18 n + 683 n + 6457) a(n + 20) - -------------------------------- + a(n + 21) = 0 (n + 21) (n + 19) Subject to the initial conditions a(1) = 0, a(2) = 0, a(3) = 1, a(4) = 6, a(5) = 26, a(6) = 100, a(7) = 359, a(8) = 1238, a(9) = 4151, a(10) = 13641, a(11) = 44156, a(12) = 141269, a(13) = 447790, a(14) = 1408770, a(15) = 4404804, a(16) = 13701992, a(17) = 42439052, a(18) = 130965283, a(19) = 402889009, a(20) = 1236068210, a(21) = 3783416048 Lemma , 6.2, : Let b(n) be the number of words of length n in the alphabet , {1, 2, 3}, with more occurences of, {[1, 1, 1]}, then , {[1, 2, 2]} b(n) satisfies the following linear recurrence equation with polynomial coef\ ficients of order, 11 27 (n + 1) (n + 2) b(n) 18 (n + 5) (n + 2) b(n + 1) - ----------------------- - --------------------------- (n + 11) (n + 8) (n + 11) (n + 8) 2 2 3 (19 n + 205 n + 442) b(n + 2) (49 n + 341 n + 504) b(n + 3) + -------------------------------- - ------------------------------ (n + 11) (n + 8) (n + 11) (n + 8) 2 2 2 (15 n + 79 n + 44) b(n + 4) (185 n + 1903 n + 4656) b(n + 5) + ------------------------------ + 1/3 --------------------------------- (n + 11) (n + 8) (n + 11) (n + 8) 2 2 (95 n + 1399 n + 5352) b(n + 6) 2 (25 n + 308 n + 882) b(n + 7) - 1/3 -------------------------------- - -------------------------------- (n + 11) (n + 8) (n + 11) (n + 8) (65 n + 534) (n + 5) b(n + 8) (7 n + 72) (5 n + 39) b(n + 9) + 1/3 ----------------------------- + 1/3 ------------------------------ (n + 11) (n + 8) (n + 11) (n + 8) 2 (11 n + 200 n + 891) b(n + 10) - 2/3 ------------------------------- + b(n + 11) = 0 (n + 11) (n + 8) Subject to the initial conditions b(1) = 0, b(2) = 0, b(3) = 1, b(4) = 5, b(5) = 20, b(6) = 75, b(7) = 265, b(8) = 907, b(9) = 3030, b(10) = 9945, b(11) = 32208 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.3527 1/2 - ------ 1/2 n The probability of Bob winning the bet, as n grows larger is approximately 0.9169 1/2 - ------ 1/2 n You can see that indeed Alice has a better chance, but not significantly so. ----------------------------------------- This took, 30.484, seconds to generate The best bet against, [1, 1, 1], is a member of, {[1, 1, 2], [1, 1, 3], [2, 1, 1], [3, 1, 1]}, 0.6517 and then your edge, if you have n rolls, is approximately, ------ 1/2 n The next best bet is a member of, {[1, 2, 2], [1, 2, 3], [1, 3, 2], [1, 3, 3], [2, 2, 1], [2, 3, 1], [3, 2, 1], [3, 3, 1]}, 0.5642 and then your edge is approximately, ------ 1/2 n The next best bet is a member of, {[2, 1, 3], [2, 2, 3], [2, 3, 3], [3, 1, 2], [3, 2, 2], [3, 3, 2]}, 0.5420 and then your edge is approximately, ------ 1/2 n The next best bet is a member of, {[1, 2, 1], [1, 3, 1]}, 0.4231 and then your edge is approximately, ------ 1/2 n The next best bet is a member of, {[2, 1, 2], [2, 3, 2], [3, 1, 3], [3, 2, 3]}, 0.3917 and then your edge is approximately, ------ 1/2 n The next best bet is a member of, {[2, 2, 2], [3, 3, 3]}, and then your edge is exactly 0 ----------------------- This ends this chapter that took, 185.356, seconds to generate. ----------------------------------------------------------------- Chapter Number, 2 The Relative Probablity of Winning a Daniel Litt style game when rolling a f\ air, 3, sides die marked with, {1, 2, 3}, of number of occurrences of, [1, 1, 2], Versus the number of occurences of all, 3, letter words in, {1, 2, 3} By Shalosh B. Ekhad ----------------------------------------------------------------------------\ ----------------------- Question Mumber, 1, : If Alice bets that there are more occurrences of consec\ utive substrings in, {[1, 1, 1]}, than in, {[1, 1, 2]}, and Bob, bets vice versa, who is more likely to win? Answer: Bob is more likely to win. Let's be more quantitative. We need the following two lemmas Lemma , 1.1, : Let a(n) be the number of words of length n in the alphabet , {1, 2, 3}, with more occurences of, {[1, 1, 1]}, then , {[1, 1, 2]} a(n) satisfies the following linear recurrence equation with polynomial coef\ ficients of order, 10 2 54 (n + 3) (n + 1) a(n) 9 (5 n + 19 n + 20) a(n + 1) - ----------------------- - ----------------------------- (n + 10) (n + 7) (n + 10) (n + 7) 2 2 6 (9 n + 88 n + 187) a(n + 2) 2 (5 n + 19 n - 40) a(n + 3) + ------------------------------ - ----------------------------- (n + 10) (n + 7) (n + 10) (n + 7) 2 (31 n + 759 n + 2918) a(n + 4) - 1/3 ------------------------------- (n + 10) (n + 7) 2 2 (68 n + 612 n + 1171) a(n + 5) 2 (21 n + 233 n + 637) a(n + 6) + 2/3 ------------------------------- - -------------------------------- (n + 10) (n + 7) (n + 10) (n + 7) 2 (29 n + 351 n + 886) a(n + 7) (5 n + 43) (7 n + 41) a(n + 8) - 1/3 ------------------------------ + 2/3 ------------------------------ (n + 10) (n + 7) (n + 10) (n + 7) 2 (13 n + 206 n + 792) a(n + 9) - 2/3 ------------------------------ + a(n + 10) = 0 (n + 10) (n + 7) Subject to the initial conditions a(1) = 0, a(2) = 0, a(3) = 1, a(4) = 4, a(5) = 16, a(6) = 59, a(7) = 209, a(8) = 716, a(9) = 2401, a(10) = 7920 Lemma , 1.2, : Let b(n) be the number of words of length n in the alphabet , {1, 2, 3}, with more occurences of, {[1, 1, 2]}, then , {[1, 1, 1]} b(n) satisfies the following linear recurrence equation with polynomial coef\ ficients of order, 21 1944 (n + 1) (n + 2) (n + 3) b(n) 648 (11 n + 32) (n + 3) (n + 2) b(n + 1) --------------------------------- + ---------------------------------------- (n + 19) (n + 18) (n + 21) (n + 19) (n + 18) (n + 21) 2 324 (n + 3) (29 n + 219 n + 410) b(n + 2) + ------------------------------------------ (n + 19) (n + 18) (n + 21) 3 2 36 (52 n + 177 n - 1819 n - 6726) b(n + 3) + -------------------------------------------- (n + 19) (n + 18) (n + 21) 3 2 6 (725 n + 13920 n + 79489 n + 139530) b(n + 4) - ------------------------------------------------- (n + 19) (n + 18) (n + 21) 3 2 6 (2281 n + 62871 n + 530540 n + 1416864) b(n + 5) + ---------------------------------------------------- (n + 19) (n + 18) (n + 21) 3 2 (26839 n + 743766 n + 6492557 n + 18229086) b(n + 6) + ------------------------------------------------------ (n + 19) (n + 18) (n + 21) 3 2 (3032 n + 4665 n - 714395 n - 4625442) b(n + 7) + 1/3 ------------------------------------------------- (n + 19) (n + 18) (n + 21) 3 2 (26128 n + 1121367 n + 13897661 n + 53471952) b(n + 8) - 1/3 -------------------------------------------------------- (n + 19) (n + 18) (n + 21) 3 2 (2503 n + 161232 n + 2492381 n + 11240784) b(n + 9) - 1/3 ----------------------------------------------------- (n + 19) (n + 18) (n + 21) 3 2 4 (3032 n + 73724 n + 533683 n + 974722) b(n + 10) - ---------------------------------------------------- (n + 19) (n + 18) (n + 21) 3 2 (2773 n + 79314 n + 672959 n + 1486392) b(n + 11) - 2/3 --------------------------------------------------- (n + 19) (n + 18) (n + 21) 3 2 (17000 n + 544224 n + 5669635 n + 19029189) b(n + 12) + 2/3 ------------------------------------------------------- (n + 19) (n + 18) (n + 21) 3 2 (64 n - 20799 n - 554167 n - 3556227) b(n + 13) - 2/3 ------------------------------------------------- (n + 19) (n + 18) (n + 21) 3 2 (5377 n + 204288 n + 2559041 n + 10553727) b(n + 14) - 2/3 ------------------------------------------------------ (n + 19) (n + 18) (n + 21) 3 2 2 (30 n + 6413 n + 168374 n + 1182627) b(n + 15) - -------------------------------------------------- (n + 19) (n + 18) (n + 21) 3 2 (1109 n + 54714 n + 897577 n + 4897632) b(n + 16) + 2/3 --------------------------------------------------- (n + 19) (n + 18) (n + 21) 3 2 (224 n + 11319 n + 189379 n + 1048836) b(n + 17) + 2/3 -------------------------------------------------- (n + 19) (n + 18) (n + 21) 3 2 (295 n + 15282 n + 263511 n + 1512492) b(n + 18) - -------------------------------------------------- (n + 19) (n + 18) (n + 21) 3 2 (320 n + 17205 n + 307969 n + 1835484) b(n + 19) + 1/3 -------------------------------------------------- (n + 19) (n + 18) (n + 21) 2 (50 n + 1893 n + 17851) b(n + 20) - 1/3 ---------------------------------- + b(n + 21) = 0 (n + 21) (n + 19) Subject to the initial conditions b(1) = 0, b(2) = 0, b(3) = 1, b(4) = 5, b(5) = 21, b(6) = 79, b(7) = 283, b(8) = 977, b(9) = 3290, b(10) = 10875, b(11) = 35443, b(12) = 114229, b(13) = 364843, b(14) = 1156685, b(15) = 3644488, b(16) = 11423152, b(17) = 35644648, b(18) = 110797293, b(19) = 343249281, b(20) = 1060272685, b(21) = 3266670158 This enables us to compute the first, 20000, terms of these sequences The probability of Alice winning the bet, as n grows larger is approximately 1.059 1/2 - ----- 1/2 n The probability of Bob winning the bet, as n grows larger is approximately 0.4073 1/2 - ------ 1/2 n You can see that indeed Bob has a better chance, but not significantly so. ----------------------------------------- This took, 29.775, seconds to generate ----------------------------------------------------------------------------\ ----------------------- Question Mumber, 2, : If Alice bets that there are more occurrences of consec\ utive substrings in, {[1, 2, 1]}, than in, {[1, 1, 2]}, and Bob, bets vice versa, who is more likely to win? Answer: Bob is more likely to win. Let's be more quantitative. We need the following two lemmas Lemma , 2.1, : Let a(n) be the number of words of length n in the alphabet , {1, 2, 3}, with more occurences of, {[1, 2, 1]}, then , {[1, 1, 2]} a(n) satisfies the following linear recurrence equation with polynomial coef\ ficients of order, 15 162 (n + 1) (n + 2) (n + 3) a(n) 27 (43 n + 145) (n + 3) (n + 2) a(n + 1) -------------------------------- - ---------------------------------------- (n + 15) (n + 12) (n + 16) (n + 15) (n + 12) (n + 16) 2 9 (n + 3) (440 n + 3645 n + 7582) a(n + 2) + ------------------------------------------- (n + 15) (n + 12) (n + 16) 2 9 (n + 4) (955 n + 9779 n + 25134) a(n + 3) - -------------------------------------------- (n + 15) (n + 12) (n + 16) 2 9 (n + 5) (1363 n + 16045 n + 47382) a(n + 4) + ---------------------------------------------- (n + 15) (n + 12) (n + 16) 2 9 (n + 6) (1206 n + 14731 n + 44531) a(n + 5) - ---------------------------------------------- (n + 15) (n + 12) (n + 16) 2 9 (n + 7) (572 n + 4837 n + 3432) a(n + 6) + ------------------------------------------- (n + 15) (n + 12) (n + 16) 2 9 (n + 8) (27 n - 4393 n - 39476) a(n + 7) - ------------------------------------------- (n + 15) (n + 12) (n + 16) 2 6 (n + 9) (299 n + 10948 n + 76089) a(n + 8) - --------------------------------------------- (n + 15) (n + 12) (n + 16) 2 3 (n + 10) (751 n + 19688 n + 121659) a(n + 9) + ----------------------------------------------- (n + 15) (n + 12) (n + 16) 2 (n + 11) (1966 n + 44617 n + 250452) a(n + 10) - ----------------------------------------------- (n + 15) (n + 12) (n + 16) 2 (3599 n + 80241 n + 442366) a(n + 11) + 1/3 -------------------------------------- (n + 16) (n + 15) 2 (n + 13) (1441 n + 33377 n + 190860) a(n + 12) - 1/3 ----------------------------------------------- (n + 15) (n + 12) (n + 16) 2 (n + 14) (358 n + 8743 n + 52725) a(n + 13) + 1/3 -------------------------------------------- (n + 15) (n + 12) (n + 16) 2 (50 n + 1287 n + 8182) a(n + 14) - 1/3 --------------------------------- + a(n + 15) = 0 (n + 16) (n + 12) Subject to the initial conditions a(1) = 0, a(2) = 0, a(3) = 1, a(4) = 5, a(5) = 19, a(6) = 71, a(7) = 252, a(8) = 858, a(9) = 2864, a(10) = 9406, a(11) = 30465, a(12) = 97671, a(13) = 310575, a(14) = 980757, a(15) = 3079464 Lemma , 2.2, : Let b(n) be the number of words of length n in the alphabet , {1, 2, 3}, with more occurences of, {[1, 1, 2]}, then , {[1, 2, 1]} b(n) satisfies the following linear recurrence equation with polynomial coef\ ficients of order, 17 810 (n + 1) (n + 2) (n + 3) b(n) 27 (131 n + 245) (n + 3) (n + 2) b(n + 1) - -------------------------------- + ----------------------------------------- (n + 14) (n + 17) (n + 16) (n + 14) (n + 17) (n + 16) 9 (394 n + 1391) (n - 2) (n + 3) b(n + 2) - ----------------------------------------- (n + 14) (n + 17) (n + 16) 3 2 9 (386 n + 8613 n + 50665 n + 89760) b(n + 3) - ----------------------------------------------- (n + 14) (n + 17) (n + 16) 3 2 27 (88 n + 609 n - 2151 n - 14808) b(n + 4) + --------------------------------------------- (n + 14) (n + 17) (n + 16) 3 2 9 (3004 n + 74765 n + 586035 n + 1473258) b(n + 5) + ---------------------------------------------------- (n + 14) (n + 17) (n + 16) 3 2 9 (8294 n + 215969 n + 1820443 n + 5006346) b(n + 6) - ------------------------------------------------------ (n + 14) (n + 17) (n + 16) 3 2 9 (11914 n + 333715 n + 3057575 n + 9205968) b(n + 7) + ------------------------------------------------------- (n + 14) (n + 17) (n + 16) 3 2 3 (35800 n + 1064831 n + 10442739 n + 33847668) b(n + 8) - ---------------------------------------------------------- (n + 14) (n + 17) (n + 16) 3 2 3 (28450 n + 882599 n + 9086147 n + 31066050) b(n + 9) + -------------------------------------------------------- (n + 14) (n + 17) (n + 16) 3 2 (57574 n + 1849647 n + 19776509 n + 70378674) b(n + 10) - --------------------------------------------------------- (n + 14) (n + 17) (n + 16) 3 2 (98678 n + 3307503 n + 36893299 n + 136913376) b(n + 11) + 1/3 ---------------------------------------------------------- (n + 14) (n + 17) (n + 16) 3 2 (45344 n + 1603473 n + 18859177 n + 73743168) b(n + 12) - 1/3 --------------------------------------------------------- (n + 14) (n + 17) (n + 16) 3 2 (5260 n + 197467 n + 2465205 n + 10230342) b(n + 13) + ------------------------------------------------------ (n + 14) (n + 17) (n + 16) 3 2 (3934 n + 156933 n + 2081855 n + 9181386) b(n + 14) - 1/3 ----------------------------------------------------- (n + 14) (n + 17) (n + 16) 3 2 (658 n + 27831 n + 391427 n + 1830144) b(n + 15) + 1/3 -------------------------------------------------- (n + 14) (n + 17) (n + 16) 2 (22 n + 631 n + 4505) b(n + 16) - -------------------------------- + b(n + 17) = 0 (n + 17) (n + 14) Subject to the initial conditions b(1) = 0, b(2) = 0, b(3) = 1, b(4) = 5, b(5) = 20, b(6) = 76, b(7) = 271, b(8) = 929, b(9) = 3114, b(10) = 10248, b(11) = 33245, b(12) = 106693, b(13) = 339428, b(14) = 1072072, b(15) = 3366035, b(16) = 10515841, b(17) = 32713202 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.9974 1/2 - ------ 1/2 n The probability of Bob winning the bet, as n grows larger is approximately 0.7980 1/2 - ------ 1/2 n You can see that indeed Bob has a better chance, but not significantly so. ----------------------------------------- This took, 30.434, seconds to generate ----------------------------------------------------------------------------\ ----------------------- Question Mumber, 3, : If Alice bets that there are more occurrences of consec\ utive substrings in, {[2, 1, 1]}, than in, {[1, 1, 2]}, and Bob, bets vice versa, who is more likely to win? Answer: They are equally likely to win ----------------------------------------------------------------------------\ ----------------------- Question Mumber, 4, : If Alice bets that there are more occurrences of consec\ utive substrings in, {[2, 2, 2]}, than in, {[1, 1, 2]}, and Bob, bets vice versa, who is more likely to win? Answer: Bob is more likely to win. Let's be more quantitative. We need the following two lemmas Lemma , 4.1, : Let a(n) be the number of words of length n in the alphabet , {1, 2, 3}, with more occurences of, {[2, 2, 2]}, then , {[1, 1, 2]} a(n) satisfies the following linear recurrence equation with polynomial coef\ ficients of order, 11 27 (n + 1) (n + 2) a(n) 18 (n + 5) (n + 2) a(n + 1) - ----------------------- - --------------------------- (n + 11) (n + 8) (n + 11) (n + 8) 2 2 3 (19 n + 205 n + 442) a(n + 2) (49 n + 341 n + 504) a(n + 3) + -------------------------------- - ------------------------------ (n + 11) (n + 8) (n + 11) (n + 8) 2 2 2 (15 n + 79 n + 44) a(n + 4) (185 n + 1903 n + 4656) a(n + 5) + ------------------------------ + 1/3 --------------------------------- (n + 11) (n + 8) (n + 11) (n + 8) 2 2 (95 n + 1399 n + 5352) a(n + 6) 2 (25 n + 308 n + 882) a(n + 7) - 1/3 -------------------------------- - -------------------------------- (n + 11) (n + 8) (n + 11) (n + 8) (65 n + 534) (n + 5) a(n + 8) (7 n + 72) (5 n + 39) a(n + 9) + 1/3 ----------------------------- + 1/3 ------------------------------ (n + 11) (n + 8) (n + 11) (n + 8) 2 (11 n + 200 n + 891) a(n + 10) - 2/3 ------------------------------- + a(n + 11) = 0 (n + 11) (n + 8) Subject to the initial conditions a(1) = 0, a(2) = 0, a(3) = 1, a(4) = 5, a(5) = 20, a(6) = 75, a(7) = 265, a(8) = 907, a(9) = 3030, a(10) = 9945, a(11) = 32208 Lemma , 4.2, : Let b(n) be the number of words of length n in the alphabet , {1, 2, 3}, with more occurences of, {[1, 1, 2]}, then , {[2, 2, 2]} b(n) satisfies the following linear recurrence equation with polynomial coef\ ficients of order, 21 1701 (n + 1) (n + 2) (n + 3) b(n) 243 (17 n - 6) (n + 3) (n + 2) b(n + 1) - --------------------------------- + --------------------------------------- (n + 19) (n + 18) (n + 21) (n + 19) (n + 18) (n + 21) 2 27 (n + 3) (23 n + 849 n + 2056) b(n + 2) + ------------------------------------------ (n + 19) (n + 18) (n + 21) 3 2 27 (169 n + 2622 n + 15223 n + 29566) b(n + 3) + ------------------------------------------------ (n + 19) (n + 18) (n + 21) 3 2 3 (4840 n + 102225 n + 640325 n + 1246386) b(n + 4) - ----------------------------------------------------- (n + 19) (n + 18) (n + 21) 3 2 3 (3385 n + 49481 n + 170144 n - 13430) b(n + 5) + -------------------------------------------------- (n + 19) (n + 18) (n + 21) 3 2 3 (3482 n + 154207 n + 1603453 n + 4856894) b(n + 6) + ------------------------------------------------------ (n + 19) (n + 18) (n + 21) 3 2 (59075 n + 1667001 n + 14921170 n + 43094853) b(n + 7) - 2/3 -------------------------------------------------------- (n + 19) (n + 18) (n + 21) 3 2 (48074 n + 1363311 n + 12792103 n + 39801840) b(n + 8) + -------------------------------------------------------- (n + 19) (n + 18) (n + 21) 3 2 (43339 n + 1821123 n + 23081162 n + 92066364) b(n + 9) - 1/3 -------------------------------------------------------- (n + 19) (n + 18) (n + 21) 3 2 (4670 n - 401523 n - 9543323 n - 50468514) b(n + 10) - 1/3 ------------------------------------------------------ (n + 19) (n + 18) (n + 21) 3 2 (17090 n + 588018 n + 6477682 n + 22737687) b(n + 11) - 2/3 ------------------------------------------------------- (n + 19) (n + 18) (n + 21) 3 2 (38125 n + 1064469 n + 8719772 n + 17173824) b(n + 12) + 1/3 -------------------------------------------------------- (n + 19) (n + 18) (n + 21) 3 2 (21473 n + 582618 n + 4189831 n + 3190524) b(n + 13) - 1/3 ------------------------------------------------------ (n + 19) (n + 18) (n + 21) 3 2 (20273 n + 736650 n + 8707345 n + 33158730) b(n + 14) + 1/3 ------------------------------------------------------- (n + 19) (n + 18) (n + 21) 3 2 (14969 n + 617205 n + 8422702 n + 38001030) b(n + 15) - 1/3 ------------------------------------------------------- (n + 19) (n + 18) (n + 21) 3 2 (1855 n + 76245 n + 1022525 n + 4442649) b(n + 16) + 2/3 ---------------------------------------------------- (n + 19) (n + 18) (n + 21) 3 2 (1571 n + 84051 n + 1489312 n + 8745672) b(n + 17) + 1/3 ---------------------------------------------------- (n + 19) (n + 18) (n + 21) 2 2 (n + 17) (224 n + 7929 n + 70035) b(n + 18) - ---------------------------------------------- (n + 19) (n + 18) (n + 21) 3 2 (130 n + 7019 n + 126201 n + 755696) b(n + 19) + ------------------------------------------------ (n + 19) (n + 18) (n + 21) 2 (18 n + 683 n + 6457) b(n + 20) - -------------------------------- + b(n + 21) = 0 (n + 21) (n + 19) Subject to the initial conditions b(1) = 0, b(2) = 0, b(3) = 1, b(4) = 6, b(5) = 26, b(6) = 100, b(7) = 359, b(8) = 1238, b(9) = 4151, b(10) = 13641, b(11) = 44156, b(12) = 141269, b(13) = 447790, b(14) = 1408770, b(15) = 4404804, b(16) = 13701992, b(17) = 42439052, b(18) = 130965283, b(19) = 402889009, b(20) = 1236068210, b(21) = 3783416048 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.9169 1/2 - ------ 1/2 n The probability of Bob winning the bet, as n grows larger is approximately 0.3527 1/2 - ------ 1/2 n You can see that indeed Bob has a better chance, but not significantly so. ----------------------------------------- This took, 30.978, seconds to generate ----------------------------------------------------------------------------\ ----------------------- Question Mumber, 5, : If Alice bets that there are more occurrences of consec\ utive substrings in, {[3, 1, 1]}, than in, {[1, 1, 2]}, and Bob, bets vice versa, who is more likely to win? Answer: They are equally likely to win ----------------------------------------------------------------------------\ ----------------------- Question Mumber, 6, : If Alice bets that there are more occurrences of consec\ utive substrings in, {[3, 3, 3]}, than in, {[1, 1, 2]}, and Bob, bets vice versa, who is more likely to win? Answer: Bob is more likely to win. Let's be more quantitative. We need the following two lemmas Lemma , 6.1, : Let a(n) be the number of words of length n in the alphabet , {1, 2, 3}, with more occurences of, {[3, 3, 3]}, then , {[1, 1, 2]} a(n) satisfies the following linear recurrence equation with polynomial coef\ ficients of order, 9 6 (n + 1) (n + 2) a(n) 2 (n + 19) (n + 2) a(n + 1) - ---------------------- - --------------------------- (n + 9) (n + 6) (n + 9) (n + 6) 2 (127 n + 771 n + 1142) a(n + 2) + 1/3 -------------------------------- (n + 9) (n + 6) 2 (55 n + 359 n + 510) a(n + 3) (n + 4) (4 n + 9) a(n + 4) + 1/3 ------------------------------ - 8/3 -------------------------- (n + 9) (n + 6) (n + 9) (n + 6) 2 2 (13 n + 71) a(n + 5) (2 n + 22 n + 51) a(n + 6) - ---------------------- - 8/3 --------------------------- n + 9 (n + 9) (n + 6) 2 (31 n + 403 n + 1266) a(n + 7) + 2/3 ------------------------------- (n + 9) (n + 6) 2 (25 n + 351 n + 1190) a(n + 8) - 1/3 ------------------------------- + a(n + 9) = 0 (n + 9) (n + 6) Subject to the initial conditions a(1) = 0, a(2) = 0, a(3) = 1, a(4) = 5, a(5) = 21, a(6) = 79, a(7) = 281, a(8) = 963, a(9) = 3218 Lemma , 6.2, : Let b(n) be the number of words of length n in the alphabet , {1, 2, 3}, with more occurences of, {[1, 1, 2]}, then , {[3, 3, 3]} b(n) satisfies the following linear recurrence equation with polynomial coef\ ficients of order, 27 2 (15 n + 752 n + 9409) b(n + 26) - -------------------------------- + b(n + 27) (n + 27) (n + 25) 3 2 (69380 n + 1622667 n + 12134728 n + 28595013) b(n + 8) - 2/3 -------------------------------------------------------- (n + 25) (n + 24) (n + 27) 3 2 (162649 n + 5116656 n + 52523375 n + 176618592) b(n + 9) - 1/3 ---------------------------------------------------------- (n + 25) (n + 24) (n + 27) 3 2 (20227 n + 1583478 n + 26610425 n + 128067150) b(n + 10) - 1/3 ---------------------------------------------------------- (n + 25) (n + 24) (n + 27) 3 2 2 (24661 n + 749292 n + 7272083 n + 22049388) b(n + 11) + --------------------------------------------------------- (n + 25) (n + 24) (n + 27) 3 2 (80788 n + 3110073 n + 39322256 n + 163295187) b(n + 12) + 2/3 ---------------------------------------------------------- (n + 25) (n + 24) (n + 27) 3 2 (7229 n + 566492 n + 11154971 n + 65017148) b(n + 13) + ------------------------------------------------------- (n + 25) (n + 24) (n + 27) 3 2 (24837 n + 929088 n + 11134663 n + 41939636) b(n + 14) - -------------------------------------------------------- (n + 25) (n + 24) (n + 27) 3 2 (66767 n + 3345282 n + 54591445 n + 290961618) b(n + 15) - 1/3 ---------------------------------------------------------- (n + 25) (n + 24) (n + 27) 3 2 (3659 n + 321525 n + 7626799 n + 54654681) b(n + 16) - 2/3 ------------------------------------------------------ (n + 25) (n + 24) (n + 27) 3 2 (10105 n + 506118 n + 8337343 n + 45067306) b(n + 17) + ------------------------------------------------------- (n + 25) (n + 24) (n + 27) 3 2 2 (2953 n + 179891 n + 3603315 n + 23784369) b(n + 18) + -------------------------------------------------------- (n + 25) (n + 24) (n + 27) 3 2 (4367 n + 228618 n + 3852001 n + 20557686) b(n + 19) - 1/3 ------------------------------------------------------ (n + 25) (n + 24) (n + 27) 3 2 (3653 n + 220962 n + 4459099 n + 30023958) b(n + 20) - ------------------------------------------------------ (n + 25) (n + 24) (n + 27) 3 2 (836 n + 44211 n + 749998 n + 3992943) b(n + 21) + 2/3 -------------------------------------------------- (n + 25) (n + 24) (n + 27) 3 2 (2953 n + 195576 n + 4319843 n + 31826364) b(n + 22) + 1/3 ------------------------------------------------------ (n + 25) (n + 24) (n + 27) 3 2 (737 n + 47424 n + 1015903 n + 7246992) b(n + 23) - 1/3 --------------------------------------------------- (n + 25) (n + 24) (n + 27) 3 2 (143 n + 10312 n + 247493 n + 1977012) b(n + 24) - -------------------------------------------------- (n + 25) (n + 24) (n + 27) 3 2 (81 n + 5872 n + 141819 n + 1141148) b(n + 25) + ------------------------------------------------ (n + 25) (n + 24) (n + 27) 144 (n + 4) (n + 3) (n + 2) b(n + 1) 54 (n + 1) (n + 2) (n + 3) b(n) - ------------------------------------ + ------------------------------- (n + 25) (n + 24) (n + 27) (n + 25) (n + 24) (n + 27) 3 2 3 (243 n + 6910 n + 49609 n + 103686) b(n + 3) - ------------------------------------------------ (n + 25) (n + 24) (n + 27) 3 2 4 (1687 n + 18608 n + 45391 n - 27942) b(n + 4) + ------------------------------------------------- (n + 25) (n + 24) (n + 27) 3 2 4 (3715 n + 67832 n + 385589 n + 672376) b(n + 5) + --------------------------------------------------- (n + 25) (n + 24) (n + 27) 3 2 (14663 n + 450294 n + 3973617 n + 10756362) b(n + 6) + ------------------------------------------------------ (n + 25) (n + 24) (n + 27) 3 2 (6565 n - 78614 n - 2415173 n - 10833962) b(n + 7) - ---------------------------------------------------- (n + 25) (n + 24) (n + 27) 2 3 (n + 3) (529 n + 5115 n + 12782) b(n + 2) - -------------------------------------------- = 0 (n + 25) (n + 24) (n + 27) Subject to the initial conditions b(1) = 0, b(2) = 0, b(3) = 1, b(4) = 6, b(5) = 27, b(6) = 105, b(7) = 380, b(8) = 1314, b(9) = 4409, b(10) = 14480, b(11) = 46806, b(12) = 149468, b(13) = 472763, b(14) = 1483925, b(15) = 4628838, b(16) = 14364742, b(17) = 44387488, b(18) = 136664364, b(19) = 419488390, b(20) = 1284247530, b(21) = 3922850548, b(22) = 11959476936, b(23) = 36399183405, b(24) = 110620176566, b(25) = 335753314105, b(26) = 1017929773518, b(27) = 3083084677252 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.8809 1/2 - ------ 1/2 n The probability of Bob winning the bet, as n grows larger is approximately 0.3389 1/2 - ------ 1/2 n You can see that indeed Bob has a better chance, but not significantly so. ----------------------------------------- This took, 38.086, seconds to generate ----------------------------------------------------------------------------\ ----------------------- Question Mumber, 7, : If Alice bets that there are more occurrences of consec\ utive substrings in, {[1, 2, 2]}, than in, {[1, 1, 2]}, and Bob, bets vice versa, who is more likely to win? Answer: They are equally likely to win ----------------------------------------------------------------------------\ ----------------------- Question Mumber, 8, : If Alice bets that there are more occurrences of consec\ utive substrings in, {[2, 2, 1]}, than in, {[1, 1, 2]}, and Bob, bets vice versa, who is more likely to win? Answer: They are equally likely to win ----------------------------------------------------------------------------\ ----------------------- Question Mumber, 9, : If Alice bets that there are more occurrences of consec\ utive substrings in, {[3, 1, 3]}, than in, {[1, 1, 2]}, and Bob, bets vice versa, who is more likely to win? Answer: Bob is more likely to win. Let's be more quantitative. We need the following two lemmas Lemma , 9.1, : Let a(n) be the number of words of length n in the alphabet , {1, 2, 3}, with more occurences of, {[3, 1, 3]}, then , {[1, 1, 2]} a(n) satisfies the following linear recurrence equation with polynomial coef\ ficients of order, 9 3 (n + 1) (n + 2) a(n) (17 n + 71) (n + 2) a(n + 1) ---------------------- - ---------------------------- (n + 9) (n + 6) (n + 9) (n + 6) 2 2 (7 n - 30 n - 142) a(n + 2) (89 n + 547 n + 792) a(n + 3) - 2/3 ---------------------------- + 2/3 ------------------------------ (n + 9) (n + 6) (n + 9) (n + 6) 2 (74 n + 591 n + 1141) a(n + 4) - 4/3 ------------------------------- (n + 9) (n + 6) 2 (184 n + 1801 n + 4288) a(n + 5) + 2/3 --------------------------------- (n + 9) (n + 6) 2 2 2 (51 n + 580 n + 1606) a(n + 6) (71 n + 903 n + 2788) a(n + 7) - --------------------------------- + 2/3 ------------------------------- (n + 9) (n + 6) (n + 9) (n + 6) 2 (11 n + 153 n + 514) a(n + 8) - ------------------------------ + a(n + 9) = 0 (n + 9) (n + 6) Subject to the initial conditions a(1) = 0, a(2) = 0, a(3) = 1, a(4) = 6, a(5) = 26, a(6) = 99, a(7) = 352, a(8) = 1200, a(9) = 3978 Lemma , 9.2, : Let b(n) be the number of words of length n in the alphabet , {1, 2, 3}, with more occurences of, {[1, 1, 2]}, then , {[3, 1, 3]} b(n) satisfies the following linear recurrence equation with polynomial coef\ ficients of order, 23 27 (n + 1) (n + 2) (n + 3) b(n) 63 (n + 4) (n + 3) (n + 2) b(n + 1) ------------------------------- + ----------------------------------- (n + 20) (n + 23) (n + 22) (n + 20) (n + 23) (n + 22) 2 12 (n + 3) (50 n + 483 n + 1219) b(n + 2) - ------------------------------------------ (n + 20) (n + 23) (n + 22) 3 2 3 (185 n + 4012 n + 25769 n + 50610) b(n + 3) + ----------------------------------------------- (n + 20) (n + 23) (n + 22) 3 2 (737 n - 5603 n - 137866 n - 456192) b(n + 4) + ----------------------------------------------- (n + 20) (n + 23) (n + 22) 3 2 2 (1826 n + 20469 n + 17689 n - 234504) b(n + 5) - -------------------------------------------------- (n + 20) (n + 23) (n + 22) 3 2 3 (3529 n + 74954 n + 486691 n + 949122) b(n + 6) + --------------------------------------------------- (n + 20) (n + 23) (n + 22) 3 2 (15942 n + 455441 n + 3953459 n + 10684818) b(n + 7) - ------------------------------------------------------ (n + 20) (n + 23) (n + 22) 3 2 (24757 n + 1246425 n + 14946722 n + 51905292) b(n + 8) + 1/3 -------------------------------------------------------- (n + 20) (n + 23) (n + 22) 3 2 (13841 n + 56118 n - 2263045 n - 14584482) b(n + 9) + ----------------------------------------------------- (n + 20) (n + 23) (n + 22) 3 2 (43257 n + 890411 n + 4913264 n + 3599568) b(n + 10) - ------------------------------------------------------ (n + 20) (n + 23) (n + 22) 3 2 (205225 n + 5374932 n + 43893905 n + 106272834) b(n + 11) + 1/3 ----------------------------------------------------------- (n + 20) (n + 23) (n + 22) 3 2 (233311 n + 7042371 n + 68260730 n + 208610484) b(n + 12) - 1/3 ----------------------------------------------------------- (n + 20) (n + 23) (n + 22) 3 2 (214249 n + 7300614 n + 81076823 n + 290982426) b(n + 13) + 1/3 ----------------------------------------------------------- (n + 20) (n + 23) (n + 22) 3 2 (174649 n + 6679983 n + 84065312 n + 346693404) b(n + 14) - 1/3 ----------------------------------------------------------- (n + 20) (n + 23) (n + 22) 3 2 (133219 n + 5657388 n + 79487063 n + 368778630) b(n + 15) + 1/3 ----------------------------------------------------------- (n + 20) (n + 23) (n + 22) 3 2 (93890 n + 4353687 n + 67002553 n + 341925858) b(n + 16) - 1/3 ---------------------------------------------------------- (n + 20) (n + 23) (n + 22) 3 2 (57556 n + 2867061 n + 47487701 n + 261423966) b(n + 17) + 1/3 ---------------------------------------------------------- (n + 20) (n + 23) (n + 22) 3 2 (28585 n + 1510827 n + 26578916 n + 155603700) b(n + 18) - 1/3 ---------------------------------------------------------- (n + 20) (n + 23) (n + 22) 3 2 2 (1803 n + 100262 n + 1856673 n + 11448430) b(n + 19) + -------------------------------------------------------- (n + 20) (n + 23) (n + 22) 3 2 4 (246 n + 14309 n + 277201 n + 1788381) b(n + 20) - ---------------------------------------------------- (n + 20) (n + 23) (n + 22) 3 2 (181 n + 10964 n + 221165 n + 1485570) b(n + 21) + -------------------------------------------------- (n + 20) (n + 23) (n + 22) 2 (20 n + 817 n + 8327) b(n + 22) - -------------------------------- + b(n + 23) = 0 (n + 23) (n + 20) Subject to the initial conditions b(1) = 0, b(2) = 0, b(3) = 1, b(4) = 6, b(5) = 27, b(6) = 105, b(7) = 378, b(8) = 1298, b(9) = 4321, b(10) = 14077, b(11) = 45147, b(12) = 143103, b(13) = 449523, b(14) = 1402120, b(15) = 4348827, b(16) = 13427110, b(17) = 41302569, b(18) = 126659255, b(19) = 387422127, b(20) = 1182489407, b(21) = 3602624202, b(22) = 10958887373, b(23) = 33291686011 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.7726 1/2 - ------ 1/2 n The probability of Bob winning the bet, as n grows larger is approximately 0.6181 1/2 - ------ 1/2 n You can see that indeed Bob has a better chance, but not significantly so. ----------------------------------------- This took, 32.419, seconds to generate ----------------------------------------------------------------------------\ ----------------------- Question Mumber, 10, : If Alice bets that there are more occurrences of conse\ cutive substrings in, {[1, 3, 1]}, than in, {[1, 1, 2]}, and Bob, bets vice versa, who is more likely to win? Answer: Bob is more likely to win. Let's be more quantitative. We need the following two lemmas Lemma , 10.1, : Let a(n) be the number of words of length n in the alphabet , {1, 2, 3}, with more occurences of, {[1, 3, 1]}, then , {[1, 1, 2]} a(n) satisfies the following linear recurrence equation with polynomial coef\ ficients of order, 10 2 54 (n + 3) (n + 1) a(n) 9 (7 n + 35 n + 40) a(n + 1) - ----------------------- + ----------------------------- (n + 10) (n + 7) (n + 10) (n + 7) 2 2 3 (3 n - 65 n - 224) a(n + 2) 2 (5 n + 253 n + 893) a(n + 3) - ------------------------------ - ------------------------------- (n + 10) (n + 7) (n + 10) (n + 7) 2 (17 n - 570 n - 3104) a(n + 4) - 2/3 ------------------------------- (n + 10) (n + 7) 2 (26 n + 883 n + 4164) a(n + 5) - 2/3 ------------------------------- (n + 10) (n + 7) 2 (128 n + 1829 n + 6420) a(n + 6) + 2/3 --------------------------------- (n + 10) (n + 7) 2 2 2 (47 n + 654 n + 2244) a(n + 7) (70 n + 1037 n + 3762) a(n + 8) - --------------------------------- + 2/3 -------------------------------- (n + 10) (n + 7) (n + 10) (n + 7) 2 (11 n + 175 n + 678) a(n + 9) - ------------------------------ + a(n + 10) = 0 (n + 10) (n + 7) Subject to the initial conditions a(1) = 0, a(2) = 0, a(3) = 1, a(4) = 6, a(5) = 25, a(6) = 93, a(7) = 327, a(8) = 1110, a(9) = 3678, a(10) = 11973 Lemma , 10.2, : Let b(n) be the number of words of length n in the alphabet , {1, 2, 3}, with more occurences of, {[1, 1, 2]}, then , {[1, 3, 1]} b(n) satisfies the following linear recurrence equation with polynomial coef\ ficients of order, 18 972 (n + 1) (n + 2) (n + 3) b(n) 648 (5 n + 17) (n + 3) (n + 2) b(n + 1) - -------------------------------- + --------------------------------------- (n + 15) (n + 18) (n + 17) (n + 15) (n + 18) (n + 17) 2 81 (n + 3) (83 n + 669 n + 1350) b(n + 2) - ------------------------------------------ (n + 15) (n + 18) (n + 17) 3 2 9 (1021 n + 12876 n + 53777 n + 74454) b(n + 3) + ------------------------------------------------- (n + 15) (n + 18) (n + 17) 3 2 6 (881 n + 3993 n - 33158 n - 155472) b(n + 4) - ------------------------------------------------ (n + 15) (n + 18) (n + 17) 3 2 36 (127 n + 6419 n + 64841 n + 185473) b(n + 5) - ------------------------------------------------- (n + 15) (n + 18) (n + 17) 3 2 (16303 n + 560382 n + 5471261 n + 16447734) b(n + 6) + ------------------------------------------------------ (n + 15) (n + 18) (n + 17) 3 2 (85597 n + 2716296 n + 26935529 n + 85555458) b(n + 7) - 1/3 -------------------------------------------------------- (n + 15) (n + 18) (n + 17) 3 2 2 (20484 n + 623465 n + 6207901 n + 20320182) b(n + 8) + -------------------------------------------------------- (n + 15) (n + 18) (n + 17) 3 2 (147427 n + 4481088 n + 45224207 n + 151630794) b(n + 9) - 1/3 ---------------------------------------------------------- (n + 15) (n + 18) (n + 17) 3 2 4 (11928 n + 376507 n + 3955674 n + 13831118) b(n + 10) + --------------------------------------------------------- (n + 15) (n + 18) (n + 17) 3 2 (111931 n + 3755328 n + 41945363 n + 155933490) b(n + 11) - 1/3 ----------------------------------------------------------- (n + 15) (n + 18) (n + 17) 3 2 (35105 n + 1261374 n + 15090541 n + 60094632) b(n + 12) + 2/3 --------------------------------------------------------- (n + 15) (n + 18) (n + 17) 3 2 2 (5747 n + 220751 n + 2823348 n + 12020700) b(n + 13) - -------------------------------------------------------- (n + 15) (n + 18) (n + 17) 3 2 (12737 n + 520392 n + 7078813 n + 32053638) b(n + 14) + 1/3 ------------------------------------------------------- (n + 15) (n + 18) (n + 17) 3 2 (3367 n + 145578 n + 2095205 n + 10036146) b(n + 15) - 1/3 ------------------------------------------------------ (n + 15) (n + 18) (n + 17) 3 2 (298 n + 13575 n + 205775 n + 1037790) b(n + 16) + 2/3 -------------------------------------------------- (n + 15) (n + 18) (n + 17) 2 (21 n + 647 n + 4966) b(n + 17) - -------------------------------- + b(n + 18) = 0 (n + 18) (n + 15) Subject to the initial conditions b(1) = 0, b(2) = 0, b(3) = 1, b(4) = 6, b(5) = 26, b(6) = 99, b(7) = 352, b(8) = 1202, b(9) = 3996, b(10) = 13032, b(11) = 41896, b(12) = 133213, b(13) = 419909, b(14) = 1314462, b(15) = 4091556, b(16) = 12676782, b(17) = 39124406, b(18) = 120357528 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.8144 1/2 - ------ 1/2 n The probability of Bob winning the bet, as n grows larger is approximately 0.6516 1/2 - ------ 1/2 n You can see that indeed Bob has a better chance, but not significantly so. ----------------------------------------- This took, 27.501, seconds to generate ----------------------------------------------------------------------------\ ----------------------- Question Mumber, 11, : If Alice bets that there are more occurrences of conse\ cutive substrings in, {[2, 1, 3]}, than in, {[1, 1, 2]}, and Bob, bets vice versa, who is more likely to win? Answer: They are equally likely to win ----------------------------------------------------------------------------\ ----------------------- Question Mumber, 12, : If Alice bets that there are more occurrences of conse\ cutive substrings in, {[1, 1, 3]}, than in, {[1, 1, 2]}, and Bob, bets vice versa, who is more likely to win? Answer: They are equally likely to win The best bet against, [1, 1, 2], is a member of, {[1, 1, 3], [1, 2, 2], [1, 2, 3], [1, 3, 2], [1, 3, 3], [2, 1, 1], [2, 1, 3], [2, 2, 1], [2, 2, 3], [2, 3, 1], [2, 3, 3], [3, 1, 1], [3, 1, 2], [3, 2, 1], [3, 2, 2], [3, 3, 1], [3, 3, 2]}, and then your edge, if you have n rolls, is exactly 0 The next best bet is a member of, {[3, 1, 3], [3, 2, 3]}, 0.1545 and then your edge is approximately, - ------ 1/2 n The next best bet is a member of, {[1, 3, 1], [2, 1, 2], [2, 3, 2]}, 0.1628 and then your edge is approximately, - ------ 1/2 n The next best bet is a member of, {[1, 2, 1]}, 0.1994 and then your edge is approximately, - ------ 1/2 n The next best bet is a member of, {[3, 3, 3]}, 0.5420 and then your edge is approximately, - ------ 1/2 n The next best bet is a member of, {[2, 2, 2]}, 0.5642 and then your edge is approximately, - ------ 1/2 n The next best bet is a member of, {[1, 1, 1]}, 0.6517 and then your edge is approximately, - ------ 1/2 n ----------------------- This ends this chapter that took, 189.785, seconds to generate. ----------------------------------------------------------------- Chapter Number, 3 The Relative Probablity of Winning a Daniel Litt style game when rolling a f\ air, 3, sides die marked with, {1, 2, 3}, of number of occurrences of, [1, 2, 1], Versus the number of occurences of all, 3, letter words in, {1, 2, 3} By Shalosh B. Ekhad ----------------------------------------------------------------------------\ ----------------------- Question Mumber, 1, : If Alice bets that there are more occurrences of consec\ utive substrings in, {[1, 1, 1]}, than in, {[1, 2, 1]}, and Bob, bets vice versa, who is more likely to win? Answer: Bob is more likely to win. Let's be more quantitative. We need the following two lemmas Lemma , 1.1, : Let a(n) be the number of words of length n in the alphabet , {1, 2, 3}, with more occurences of, {[1, 1, 1]}, then , {[1, 2, 1]} a(n) satisfies the following linear recurrence equation with polynomial coef\ ficients of order, 15 2 864 (2 n + 3) (n + 2) (n + 1) a(n) 72 (n + 2) (19 n + 73 n + 108) a(n + 1) ---------------------------------- - ---------------------------------------- (n + 15) (n + 14) (n + 12) (n + 15) (n + 14) (n + 12) 3 2 24 (266 n + 3387 n + 13861 n + 18246) a(n + 2) + ------------------------------------------------ (n + 15) (n + 14) (n + 12) 3 2 6 (203 n + 4791 n + 32338 n + 65568) a(n + 3) + ----------------------------------------------- (n + 15) (n + 14) (n + 12) 3 2 18 (595 n + 10771 n + 64214 n + 126080) a(n + 4) - -------------------------------------------------- (n + 15) (n + 14) (n + 12) 3 2 2 (1025 n + 8223 n - 29924 n - 254244) a(n + 5) + ------------------------------------------------- (n + 15) (n + 14) (n + 12) 3 2 (5003 n + 148867 n + 1365650 n + 3977112) a(n + 6) + ---------------------------------------------------- (n + 15) (n + 14) (n + 12) 3 2 (2559 n + 79895 n + 758594 n + 2270352) a(n + 7) - -------------------------------------------------- (n + 15) (n + 14) (n + 12) 3 2 4 (61 n - 520 n - 29421 n - 176232) a(n + 8) + ---------------------------------------------- (n + 15) (n + 14) (n + 12) 3 2 4 (137 n + 7303 n + 103456 n + 441324) a(n + 9) + ------------------------------------------------- (n + 15) (n + 14) (n + 12) 3 2 2 (569 n + 20519 n + 240600 n + 922932) a(n + 10) - --------------------------------------------------- (n + 15) (n + 14) (n + 12) 3 2 4 (253 n + 8575 n + 96430 n + 359730) a(n + 11) + ------------------------------------------------- (n + 15) (n + 14) (n + 12) 3 2 2 (235 n + 8201 n + 95120 n + 366504) a(n + 12) - ------------------------------------------------- (n + 15) (n + 14) (n + 12) 3 2 2 (61 n + 2243 n + 27412 n + 111300) a(n + 13) + ------------------------------------------------ (n + 15) (n + 14) (n + 12) 2 (17 n + 423 n + 2616) a(n + 14) - -------------------------------- + a(n + 15) = 0 (n + 15) (n + 12) Subject to the initial conditions a(1) = 0, a(2) = 0, a(3) = 1, a(4) = 5, a(5) = 19, a(6) = 71, a(7) = 254, a(8) = 868, a(9) = 2901, a(10) = 9555, a(11) = 31032, a(12) = 99678, a(13) = 317556, a(14) = 1004682, a(15) = 3159765 Lemma , 1.2, : Let b(n) be the number of words of length n in the alphabet , {1, 2, 3}, with more occurences of, {[1, 2, 1]}, then , {[1, 1, 1]} b(n) satisfies the following linear recurrence equation with polynomial coef\ ficients of order, 22 864 (2 n + 3) (n + 2) (n + 1) b(n) - ---------------------------------- (n + 20) (n + 19) (n + 22) 2 72 (n + 2) (211 n + 1417 n + 2196) b(n + 1) + -------------------------------------------- (n + 20) (n + 19) (n + 22) 3 2 24 (1874 n + 24231 n + 101137 n + 136110) b(n + 2) - ---------------------------------------------------- (n + 20) (n + 19) (n + 22) 3 2 18 (1031 n + 16147 n + 95466 n + 189056) b(n + 3) + --------------------------------------------------- (n + 20) (n + 19) (n + 22) 3 2 2 (12007 n + 426387 n + 3457706 n + 8173848) b(n + 4) + ------------------------------------------------------- (n + 20) (n + 19) (n + 22) 3 2 (33620 n + 430641 n + 1634809 n + 1514238) b(n + 5) + 4/3 ----------------------------------------------------- (n + 20) (n + 19) (n + 22) 3 2 (249397 n + 5665149 n + 43700510 n + 113907144) b(n + 6) + 1/3 ---------------------------------------------------------- (n + 20) (n + 19) (n + 22) 3 2 (30971 n + 66907 n - 5078414 n - 29210608) b(n + 7) - ----------------------------------------------------- (n + 20) (n + 19) (n + 22) 3 2 (17492 n + 75936 n - 3137663 n - 21684102) b(n + 8) + 4/3 ----------------------------------------------------- (n + 20) (n + 19) (n + 22) 3 2 (78895 n + 2165343 n + 22559306 n + 88193304) b(n + 9) - 1/3 -------------------------------------------------------- (n + 20) (n + 19) (n + 22) 3 2 (86903 n + 2879499 n + 30006490 n + 97758252) b(n + 10) - 2/3 --------------------------------------------------------- (n + 20) (n + 19) (n + 22) 3 2 (35785 n + 1178861 n + 12631086 n + 43941624) b(n + 11) + --------------------------------------------------------- (n + 20) (n + 19) (n + 22) 3 2 4 (2794 n + 152871 n + 2449223 n + 12152364) b(n + 12) + -------------------------------------------------------- (n + 20) (n + 19) (n + 22) 3 2 (22703 n + 1218579 n + 19620154 n + 98638752) b(n + 13) - 1/3 --------------------------------------------------------- (n + 20) (n + 19) (n + 22) 3 2 (3488 n + 131799 n + 1555828 n + 5512860) b(n + 14) + 4/3 ----------------------------------------------------- (n + 20) (n + 19) (n + 22) 3 2 (17915 n + 669507 n + 8023042 n + 30264288) b(n + 15) - 1/3 ------------------------------------------------------- (n + 20) (n + 19) (n + 22) 3 2 (1526 n + 60504 n + 790471 n + 3420258) b(n + 16) + 4/3 --------------------------------------------------- (n + 20) (n + 19) (n + 22) 3 2 (947 n + 42795 n + 601522 n + 2507976) b(n + 17) + 1/3 -------------------------------------------------- (n + 20) (n + 19) (n + 22) 3 2 (125 n + 2817 n - 19142 n - 527436) b(n + 18) - 2/3 ----------------------------------------------- (n + 20) (n + 19) (n + 22) 2 (163 n + 5989 n + 54956) b(n + 19) - ----------------------------------- (n + 19) (n + 20) 3 2 2 (41 n + 2367 n + 45512 n + 291464) b(n + 20) + ------------------------------------------------ (n + 20) (n + 19) (n + 22) 2 (15 n + 602 n + 6024) b(n + 21) - -------------------------------- + b(n + 22) = 0 (n + 22) (n + 20) Subject to the initial conditions b(1) = 0, b(2) = 0, b(3) = 1, b(4) = 6, b(5) = 24, b(6) = 89, b(7) = 319, b(8) = 1097, b(9) = 3668, b(10) = 12063, b(11) = 39137, b(12) = 125525, b(13) = 399054, b(14) = 1259640, b(15) = 3952195, b(16) = 12337292, b(17) = 38347670, b(18) = 118756679, b(19) = 366597733, b(20) = 1128537489, b(21) = 3465675586, b(22) = 10620171614 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.8464 1/2 - ------ 1/2 n The probability of Bob winning the bet, as n grows larger is approximately 0.4233 1/2 - ------ 1/2 n You can see that indeed Bob has a better chance, but not significantly so. ----------------------------------------- This took, 38.998, seconds to generate ----------------------------------------------------------------------------\ ----------------------- Question Mumber, 2, : If Alice bets that there are more occurrences of consec\ utive substrings in, {[1, 3, 1]}, than in, {[1, 2, 1]}, and Bob, bets vice versa, who is more likely to win? Answer: They are equally likely to win ----------------------------------------------------------------------------\ ----------------------- Question Mumber, 3, : If Alice bets that there are more occurrences of consec\ utive substrings in, {[2, 1, 2]}, than in, {[1, 2, 1]}, and Bob, bets vice versa, who is more likely to win? Answer: They are equally likely to win ----------------------------------------------------------------------------\ ----------------------- Question Mumber, 4, : If Alice bets that there are more occurrences of consec\ utive substrings in, {[1, 1, 2]}, than in, {[1, 2, 1]}, and Bob, bets vice versa, who is more likely to win? Answer: Alice is more likely to win. Let's be more quantitative. We need the following two lemmas Lemma , 4.1, : Let a(n) be the number of words of length n in the alphabet , {1, 2, 3}, with more occurences of, {[1, 1, 2]}, then , {[1, 2, 1]} a(n) satisfies the following linear recurrence equation with polynomial coef\ ficients of order, 17 810 (n + 1) (n + 2) (n + 3) a(n) 27 (131 n + 245) (n + 3) (n + 2) a(n + 1) - -------------------------------- + ----------------------------------------- (n + 14) (n + 17) (n + 16) (n + 14) (n + 17) (n + 16) 9 (394 n + 1391) (n - 2) (n + 3) a(n + 2) - ----------------------------------------- (n + 14) (n + 17) (n + 16) 3 2 9 (386 n + 8613 n + 50665 n + 89760) a(n + 3) - ----------------------------------------------- (n + 14) (n + 17) (n + 16) 3 2 27 (88 n + 609 n - 2151 n - 14808) a(n + 4) + --------------------------------------------- (n + 14) (n + 17) (n + 16) 3 2 9 (3004 n + 74765 n + 586035 n + 1473258) a(n + 5) + ---------------------------------------------------- (n + 14) (n + 17) (n + 16) 3 2 9 (8294 n + 215969 n + 1820443 n + 5006346) a(n + 6) - ------------------------------------------------------ (n + 14) (n + 17) (n + 16) 3 2 9 (11914 n + 333715 n + 3057575 n + 9205968) a(n + 7) + ------------------------------------------------------- (n + 14) (n + 17) (n + 16) 3 2 3 (35800 n + 1064831 n + 10442739 n + 33847668) a(n + 8) - ---------------------------------------------------------- (n + 14) (n + 17) (n + 16) 3 2 3 (28450 n + 882599 n + 9086147 n + 31066050) a(n + 9) + -------------------------------------------------------- (n + 14) (n + 17) (n + 16) 3 2 (57574 n + 1849647 n + 19776509 n + 70378674) a(n + 10) - --------------------------------------------------------- (n + 14) (n + 17) (n + 16) 3 2 (98678 n + 3307503 n + 36893299 n + 136913376) a(n + 11) + 1/3 ---------------------------------------------------------- (n + 14) (n + 17) (n + 16) 3 2 (45344 n + 1603473 n + 18859177 n + 73743168) a(n + 12) - 1/3 --------------------------------------------------------- (n + 14) (n + 17) (n + 16) 3 2 (5260 n + 197467 n + 2465205 n + 10230342) a(n + 13) + ------------------------------------------------------ (n + 14) (n + 17) (n + 16) 3 2 (3934 n + 156933 n + 2081855 n + 9181386) a(n + 14) - 1/3 ----------------------------------------------------- (n + 14) (n + 17) (n + 16) 3 2 (658 n + 27831 n + 391427 n + 1830144) a(n + 15) + 1/3 -------------------------------------------------- (n + 14) (n + 17) (n + 16) 2 (22 n + 631 n + 4505) a(n + 16) - -------------------------------- + a(n + 17) = 0 (n + 17) (n + 14) Subject to the initial conditions a(1) = 0, a(2) = 0, a(3) = 1, a(4) = 5, a(5) = 20, a(6) = 76, a(7) = 271, a(8) = 929, a(9) = 3114, a(10) = 10248, a(11) = 33245, a(12) = 106693, a(13) = 339428, a(14) = 1072072, a(15) = 3366035, a(16) = 10515841, a(17) = 32713202 Lemma , 4.2, : Let b(n) be the number of words of length n in the alphabet , {1, 2, 3}, with more occurences of, {[1, 2, 1]}, then , {[1, 1, 2]} b(n) satisfies the following linear recurrence equation with polynomial coef\ ficients of order, 15 162 (n + 1) (n + 2) (n + 3) b(n) 27 (43 n + 145) (n + 3) (n + 2) b(n + 1) -------------------------------- - ---------------------------------------- (n + 15) (n + 12) (n + 16) (n + 15) (n + 12) (n + 16) 2 9 (n + 3) (440 n + 3645 n + 7582) b(n + 2) + ------------------------------------------- (n + 15) (n + 12) (n + 16) 2 9 (n + 4) (955 n + 9779 n + 25134) b(n + 3) - -------------------------------------------- (n + 15) (n + 12) (n + 16) 2 9 (n + 5) (1363 n + 16045 n + 47382) b(n + 4) + ---------------------------------------------- (n + 15) (n + 12) (n + 16) 2 9 (n + 6) (1206 n + 14731 n + 44531) b(n + 5) - ---------------------------------------------- (n + 15) (n + 12) (n + 16) 2 9 (n + 7) (572 n + 4837 n + 3432) b(n + 6) + ------------------------------------------- (n + 15) (n + 12) (n + 16) 2 9 (n + 8) (27 n - 4393 n - 39476) b(n + 7) - ------------------------------------------- (n + 15) (n + 12) (n + 16) 2 6 (n + 9) (299 n + 10948 n + 76089) b(n + 8) - --------------------------------------------- (n + 15) (n + 12) (n + 16) 2 3 (n + 10) (751 n + 19688 n + 121659) b(n + 9) + ----------------------------------------------- (n + 15) (n + 12) (n + 16) 2 (n + 11) (1966 n + 44617 n + 250452) b(n + 10) - ----------------------------------------------- (n + 15) (n + 12) (n + 16) 2 (3599 n + 80241 n + 442366) b(n + 11) + 1/3 -------------------------------------- (n + 16) (n + 15) 2 (n + 13) (1441 n + 33377 n + 190860) b(n + 12) - 1/3 ----------------------------------------------- (n + 15) (n + 12) (n + 16) 2 (n + 14) (358 n + 8743 n + 52725) b(n + 13) + 1/3 -------------------------------------------- (n + 15) (n + 12) (n + 16) 2 (50 n + 1287 n + 8182) b(n + 14) - 1/3 --------------------------------- + b(n + 15) = 0 (n + 16) (n + 12) Subject to the initial conditions b(1) = 0, b(2) = 0, b(3) = 1, b(4) = 5, b(5) = 19, b(6) = 71, b(7) = 252, b(8) = 858, b(9) = 2864, b(10) = 9406, b(11) = 30465, b(12) = 97671, b(13) = 310575, b(14) = 980757, b(15) = 3079464 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.7980 1/2 - ------ 1/2 n The probability of Bob winning the bet, as n grows larger is approximately 0.9974 1/2 - ------ 1/2 n You can see that indeed Alice has a better chance, but not significantly so. ----------------------------------------- This took, 31.761, seconds to generate ----------------------------------------------------------------------------\ ----------------------- Question Mumber, 5, : If Alice bets that there are more occurrences of consec\ utive substrings in, {[2, 1, 3]}, than in, {[1, 2, 1]}, and Bob, bets vice versa, who is more likely to win? Answer: Alice is more likely to win. Let's be more quantitative. We need the following two lemmas Lemma , 5.1, : Let a(n) be the number of words of length n in the alphabet , {1, 2, 3}, with more occurences of, {[2, 1, 3]}, then , {[1, 2, 1]} a(n) satisfies the following linear recurrence equation with polynomial coef\ ficients of order, 26 18 (41 n + 155) (n + 3) (n + 2) a(n + 1) - ---------------------------------------- (n + 25) (n + 23) (n + 26) 2 3 (n + 3) (863 n + 6585 n + 11602) a(n + 2) + -------------------------------------------- (n + 25) (n + 23) (n + 26) 2 2 (12 n + 559 n + 6500) a(n + 25) - ---------------------------------- + a(n + 26) (n + 26) (n + 23) 54 (n + 1) (n + 2) (n + 3) a(n) + ------------------------------- (n + 25) (n + 23) (n + 26) 3 2 (81671 n + 4970460 n + 100720315 n + 679493694) a(n + 21) - 1/3 ----------------------------------------------------------- (n + 25) (n + 23) (n + 26) 3 2 (8147 n + 519242 n + 11021113 n + 77899666) a(n + 22) + ------------------------------------------------------- (n + 25) (n + 23) (n + 26) 3 2 (2662 n + 176919 n + 3916043 n + 28867230) a(n + 23) - 2/3 ------------------------------------------------------ (n + 25) (n + 23) (n + 26) 3 2 (793 n + 54774 n + 1259963 n + 9651702) a(n + 24) + 1/3 --------------------------------------------------- (n + 25) (n + 23) (n + 26) 3 2 3 (215 n + 3028 n + 11171 n + 10314) a(n + 3) - ----------------------------------------------- (n + 25) (n + 23) (n + 26) 3 2 2 (4950 n + 69425 n + 334997 n + 556476) a(n + 4) - --------------------------------------------------- (n + 25) (n + 23) (n + 26) 3 2 (40487 n + 641526 n + 3300433 n + 5414370) a(n + 5) + 1/3 ----------------------------------------------------- (n + 25) (n + 23) (n + 26) 3 2 (47623 n + 1281996 n + 11652263 n + 35078502) a(n + 6) + 1/3 -------------------------------------------------------- (n + 25) (n + 23) (n + 26) 3 2 2 (38409 n + 1058281 n + 9897652 n + 31085514) a(n + 7) - --------------------------------------------------------- (n + 25) (n + 23) (n + 26) 3 2 (95991 n + 3111206 n + 33834025 n + 122331090) a(n + 8) + --------------------------------------------------------- (n + 25) (n + 23) (n + 26) 3 2 (379 n - 2352882 n - 52225375 n - 285960150) a(n + 9) + 1/3 ------------------------------------------------------- (n + 25) (n + 23) (n + 26) 3 2 (111365 n + 2941650 n + 22480126 n + 39787728) a(n + 10) - 4/3 ---------------------------------------------------------- (n + 25) (n + 23) (n + 26) 3 2 (345359 n + 11397417 n + 118883746 n + 382910574) a(n + 11) + 2/3 ------------------------------------------------------------- (n + 25) (n + 23) (n + 26) 3 2 4 (50408 n + 2066441 n + 26821574 n + 110446560) a(n + 12) - ------------------------------------------------------------ (n + 25) (n + 23) (n + 26) 3 2 2 (50133 n + 3063451 n + 52794540 n + 277114886) a(n + 13) + ------------------------------------------------------------ (n + 25) (n + 23) (n + 26) 3 2 (34511 n - 2933169 n - 100226894 n - 730425552) a(n + 14) + 2/3 ----------------------------------------------------------- (n + 25) (n + 23) (n + 26) 3 2 (208945 n + 5226852 n + 16182563 n - 226800258) a(n + 15) - 2/3 ----------------------------------------------------------- (n + 25) (n + 23) (n + 26) 3 2 (334354 n + 12911949 n + 155919953 n + 558980190) a(n + 16) + 2/3 ------------------------------------------------------------- (n + 25) (n + 23) (n + 26) 3 2 (738307 n + 33716058 n + 505120349 n + 2470129938) a(n + 17) - 1/3 -------------------------------------------------------------- (n + 25) (n + 23) (n + 26) 3 2 (309590 n + 15642267 n + 261886087 n + 1451248614) a(n + 18) + 2/3 -------------------------------------------------------------- (n + 25) (n + 23) (n + 26) 3 2 (134769 n + 7332304 n + 132599749 n + 796766850) a(n + 19) - ------------------------------------------------------------ (n + 25) (n + 23) (n + 26) 3 2 (103240 n + 5965509 n + 114714473 n + 733978644) a(n + 20) + 2/3 ------------------------------------------------------------ = 0 (n + 25) (n + 23) (n + 26) Subject to the initial conditions a(1) = 0, a(2) = 0, a(3) = 1, a(4) = 5, a(5) = 21, a(6) = 79, a(7) = 282, a(8) = 970, a(9) = 3252, a(10) = 10699, a(11) = 34703, a(12) = 111319, a(13) = 353924, a(14) = 1117121, a(15) = 3504958, a(16) = 10941581, a(17) = 34011526, a(18) = 105339081, a(19) = 325228983, a(20) = 1001395945, a(21) = 3076023894, a(22) = 9429035948, a(23) = 28849991275, a(24) = 88128475262, a(25) = 268817440700, a(26) = 818911493252 Lemma , 5.2, : Let b(n) be the number of words of length n in the alphabet , {1, 2, 3}, with more occurences of, {[1, 2, 1]}, then , {[2, 1, 3]} b(n) satisfies the following linear recurrence equation with polynomial coef\ ficients of order, 11 6 (n + 1) (n + 2) b(n) 2 (n + 2) (2 n - 19) b(n + 1) - ---------------------- + ----------------------------- (n + 11) (n + 8) (n + 11) (n + 8) 2 (313 n + 2331 n + 4130) b(n + 2) + 1/3 --------------------------------- (n + 11) (n + 8) 2 (193 n + 1831 n + 4226) b(n + 3) - --------------------------------- (n + 11) (n + 8) 2 (145 n + 1967 n + 6133) b(n + 4) + 2/3 --------------------------------- (n + 11) (n + 8) 2 (215 n + 1824 n + 3355) b(n + 5) + 2/3 --------------------------------- (n + 11) (n + 8) 2 (478 n + 5455 n + 15051) b(n + 6) - 2/3 ---------------------------------- (n + 11) (n + 8) 2 (460 n + 6009 n + 19055) b(n + 7) + 2/3 ---------------------------------- (n + 11) (n + 8) 2 (268 n + 3933 n + 14063) b(n + 8) - 2/3 ---------------------------------- (n + 11) (n + 8) 2 (95 n + 1544 n + 6129) b(n + 9) + 2/3 -------------------------------- (n + 11) (n + 8) 2 (37 n + 655 n + 2832) b(n + 10) - 1/3 -------------------------------- + b(n + 11) = 0 (n + 11) (n + 8) Subject to the initial conditions b(1) = 0, b(2) = 0, b(3) = 1, b(4) = 5, b(5) = 20, b(6) = 74, b(7) = 262, b(8) = 897, b(9) = 2997, b(10) = 9838, b(11) = 31867 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.7388 1/2 - ------ 1/2 n The probability of Bob winning the bet, as n grows larger is approximately 0.9235 1/2 - ------ 1/2 n You can see that indeed Alice has a better chance, but not significantly so. ----------------------------------------- This took, 38.145, seconds to generate ----------------------------------------------------------------------------\ ----------------------- Question Mumber, 6, : If Alice bets that there are more occurrences of consec\ utive substrings in, {[2, 2, 2]}, than in, {[1, 2, 1]}, and Bob, bets vice versa, who is more likely to win? Answer: Bob is more likely to win. Let's be more quantitative. We need the following two lemmas Lemma , 6.1, : Let a(n) be the number of words of length n in the alphabet , {1, 2, 3}, with more occurences of, {[2, 2, 2]}, then , {[1, 2, 1]} a(n) satisfies the following linear recurrence equation with polynomial coef\ ficients of order, 24 144 (n + 1) (n + 2) (n + 3) a(n) 12 (305 n + 1583) (n + 3) (n + 2) a(n + 1) - -------------------------------- + ------------------------------------------ (n + 24) (n + 23) (n + 21) (n + 24) (n + 23) (n + 21) 2 (n + 20) (103 n + 4540 n + 50037) a(n + 22) + 2/3 -------------------------------------------- (n + 24) (n + 23) (n + 21) 2 2 (n + 3) (7156 n + 70683 n + 168440) a(n + 2) + ----------------------------------------------- (n + 24) (n + 23) (n + 21) 2 (13 n + 561 n + 6040) a(n + 23) - -------------------------------- + a(n + 24) (n + 24) (n + 21) 3 2 (4925 n + 244074 n + 4028833 n + 22144980) a(n + 17) - 2/3 ------------------------------------------------------ (n + 24) (n + 23) (n + 21) 3 2 (3215 n + 169095 n + 2957854 n + 17201592) a(n + 18) + 2/3 ------------------------------------------------------ (n + 24) (n + 23) (n + 21) 3 2 (2863 n + 158202 n + 2906483 n + 17745540) a(n + 19) - 1/3 ------------------------------------------------------ (n + 24) (n + 23) (n + 21) 3 2 (1225 n + 71826 n + 1400525 n + 9078588) a(n + 20) + 1/3 ---------------------------------------------------- (n + 24) (n + 23) (n + 21) 3 2 (295 n + 18195 n + 373568 n + 2552784) a(n + 21) - 2/3 -------------------------------------------------- (n + 24) (n + 23) (n + 21) 3 2 (47865 n + 746530 n + 3804673 n + 6336708) a(n + 3) + ----------------------------------------------------- (n + 24) (n + 23) (n + 21) 3 2 (82645 n + 1544878 n + 9413237 n + 18774140) a(n + 4) + ------------------------------------------------------- (n + 24) (n + 23) (n + 21) 3 2 (159724 n + 3324627 n + 22552019 n + 50090196) a(n + 5) + 2/3 --------------------------------------------------------- (n + 24) (n + 23) (n + 21) 3 2 (50498 n + 1308429 n + 10772155 n + 28541436) a(n + 6) + 4/3 -------------------------------------------------------- (n + 24) (n + 23) (n + 21) 3 2 (173 n - 368628 n - 5185889 n - 17362128) a(n + 7) - 1/3 ---------------------------------------------------- (n + 24) (n + 23) (n + 21) 3 2 (148999 n + 3372276 n + 25474205 n + 65221128) a(n + 8) - 1/3 --------------------------------------------------------- (n + 24) (n + 23) (n + 21) 3 2 (92129 n + 2842350 n + 28989541 n + 98165160) a(n + 9) - 2/3 -------------------------------------------------------- (n + 24) (n + 23) (n + 21) 3 2 (5615 n + 293388 n + 4200565 n + 18345336) a(n + 10) - 2/3 ------------------------------------------------------ (n + 24) (n + 23) (n + 21) 3 2 (4181 n + 226911 n + 3514666 n + 16746390) a(n + 11) - 4/3 ------------------------------------------------------ (n + 24) (n + 23) (n + 21) 3 2 4 (8040 n + 288135 n + 3429109 n + 13561224) a(n + 12) + -------------------------------------------------------- (n + 24) (n + 23) (n + 21) 3 2 (16793 n + 591504 n + 6976255 n + 27683388) a(n + 13) - 2/3 ------------------------------------------------------- (n + 24) (n + 23) (n + 21) 3 2 (16633 n + 702174 n + 9892481 n + 46501356) a(n + 14) + 2/3 ------------------------------------------------------- (n + 24) (n + 23) (n + 21) 3 2 4 (2871 n + 123436 n + 1765777 n + 8408790) a(n + 15) - ------------------------------------------------------- (n + 24) (n + 23) (n + 21) 3 2 (4147 n + 186150 n + 2785679 n + 13908336) a(n + 16) + 4/3 ------------------------------------------------------ = 0 (n + 24) (n + 23) (n + 21) Subject to the initial conditions a(1) = 0, a(2) = 0, a(3) = 1, a(4) = 5, a(5) = 21, a(6) = 79, a(7) = 281, a(8) = 965, a(9) = 3230, a(10) = 10614, a(11) = 34395, a(12) = 110241, a(13) = 350250, a(14) = 1104858, a(15) = 3464673, a(16) = 10810907, a(17) = 33592029, a(18) = 104003961, a(19) = 321010589, a(20) = 988150391, a(21) = 3034656175, a(22) = 9300440437, a(23) = 28451870505, a(24) = 86900357189 Lemma , 6.2, : Let b(n) be the number of words of length n in the alphabet , {1, 2, 3}, with more occurences of, {[1, 2, 1]}, then , {[2, 2, 2]} b(n) satisfies the following linear recurrence equation with polynomial coef\ ficients of order, 27 1872 (n + 1) (n + 2) (n + 3) b(n) 12 (n + 3) (n + 2) (1327 n + 5881) b(n + 1) --------------------------------- + ------------------------------------------- (n + 25) (n + 24) (n + 27) (n + 25) (n + 24) (n + 27) 2 (15 n + 752 n + 9409) b(n + 26) - -------------------------------- + b(n + 27) (n + 27) (n + 25) 2 2 (n + 3) (9968 n + 60609 n + 67768) b(n + 2) + ---------------------------------------------- (n + 25) (n + 24) (n + 27) 3 2 2 (53213 n + 2290924 n + 32622893 n + 153647442) b(n + 16) + ------------------------------------------------------------ (n + 25) (n + 24) (n + 27) 3 2 (78275 n + 3499524 n + 51586849 n + 250493766) b(n + 17) - 2/3 ---------------------------------------------------------- (n + 25) (n + 24) (n + 27) 3 2 (39502 n + 1914003 n + 30670697 n + 162393858) b(n + 18) + 2/3 ---------------------------------------------------------- (n + 25) (n + 24) (n + 27) 3 2 (47843 n + 2484654 n + 42718795 n + 242962632) b(n + 19) - 1/3 ---------------------------------------------------------- (n + 25) (n + 24) (n + 27) 3 2 (16297 n + 855666 n + 14781749 n + 83815356) b(n + 20) + 1/3 -------------------------------------------------------- (n + 25) (n + 24) (n + 27) 3 2 2 (539 n + 27573 n + 453930 n + 2368758) b(n + 21) - ---------------------------------------------------- (n + 25) (n + 24) (n + 27) 3 2 2 (126 n + 6297 n + 96841 n + 425776) b(n + 22) + ------------------------------------------------- (n + 25) (n + 24) (n + 27) 3 2 2 (82 n + 6281 n + 157821 n + 1304646) b(n + 23) + -------------------------------------------------- (n + 25) (n + 24) (n + 27) 3 2 2 (109 n + 7795 n + 185628 n + 1471998) b(n + 24) - --------------------------------------------------- (n + 25) (n + 24) (n + 27) 3 2 2 (43 n + 3116 n + 75227 n + 605074) b(n + 25) + ------------------------------------------------ (n + 25) (n + 24) (n + 27) 3 2 (52071 n + 653594 n + 2775227 n + 3964716) b(n + 3) + ----------------------------------------------------- (n + 25) (n + 24) (n + 27) 3 2 (365 n - 451094 n - 4821299 n - 12747952) b(n + 4) + ---------------------------------------------------- (n + 25) (n + 24) (n + 27) 3 2 2 (5800 n + 133407 n + 1083023 n + 3002904) b(n + 5) + ------------------------------------------------------ (n + 25) (n + 24) (n + 27) 3 2 6 (6087 n + 175665 n + 1448822 n + 3585078) b(n + 6) - ------------------------------------------------------ (n + 25) (n + 24) (n + 27) 3 2 2 (16981 n - 305287 n - 8077766 n - 36604956) b(n + 7) - -------------------------------------------------------- (n + 25) (n + 24) (n + 27) 3 2 (239108 n + 6028221 n + 52366201 n + 156824508) b(n + 8) + 2/3 ---------------------------------------------------------- (n + 25) (n + 24) (n + 27) 3 2 (7154 n - 1101636 n - 22475141 n - 107544078) b(n + 9) - 4/3 -------------------------------------------------------- (n + 25) (n + 24) (n + 27) 3 2 (980105 n + 25915500 n + 225154423 n + 641706180) b(n + 10) + 1/3 ------------------------------------------------------------- (n + 25) (n + 24) (n + 27) 3 2 (655765 n + 17556852 n + 151932287 n + 424383492) b(n + 11) - 1/3 ------------------------------------------------------------- (n + 25) (n + 24) (n + 27) 3 2 (141790 n + 4015992 n + 35511503 n + 93500817) b(n + 12) + 4/3 ---------------------------------------------------------- (n + 25) (n + 24) (n + 27) 3 2 10 (28801 n + 994130 n + 11341705 n + 42833058) b(n + 13) - ----------------------------------------------------------- (n + 25) (n + 24) (n + 27) 3 2 (251449 n + 8913654 n + 103314263 n + 390677022) b(n + 14) + 2/3 ------------------------------------------------------------ (n + 25) (n + 24) (n + 27) 3 2 (182039 n + 7145784 n + 92247361 n + 390941934) b(n + 15) - 2/3 ----------------------------------------------------------- = 0 (n + 25) (n + 24) (n + 27) Subject to the initial conditions b(1) = 0, b(2) = 0, b(3) = 1, b(4) = 6, b(5) = 26, b(6) = 99, b(7) = 354, b(8) = 1218, b(9) = 4078, b(10) = 13387, b(11) = 43303, b(12) = 138476, b(13) = 438803, b(14) = 1380249, b(15) = 4315261, b(16) = 13423279, b(17) = 41577618, b(18) = 128318265, b(19) = 394794775, b(20) = 1211418663, b(21) = 3708612247, b(22) = 11330581638, b(23) = 34556182414, b(24) = 105226444681, b(25) = 319984546540, b(26) = 971865922642, b(27) = 2948600615760 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.7836 1/2 - ------ 1/2 n The probability of Bob winning the bet, as n grows larger is approximately 0.3919 1/2 - ------ 1/2 n You can see that indeed Bob has a better chance, but not significantly so. ----------------------------------------- This took, 56.830, seconds to generate ----------------------------------------------------------------------------\ ----------------------- Question Mumber, 7, : If Alice bets that there are more occurrences of consec\ utive substrings in, {[2, 3, 2]}, than in, {[1, 2, 1]}, and Bob, bets vice versa, who is more likely to win? Answer: They are equally likely to win ----------------------------------------------------------------------------\ ----------------------- Question Mumber, 8, : If Alice bets that there are more occurrences of consec\ utive substrings in, {[2, 2, 3]}, than in, {[1, 2, 1]}, and Bob, bets vice versa, who is more likely to win? Answer: Alice is more likely to win. Let's be more quantitative. We need the following two lemmas Lemma , 8.1, : Let a(n) be the number of words of length n in the alphabet , {1, 2, 3}, with more occurences of, {[2, 2, 3]}, then , {[1, 2, 1]} a(n) satisfies the following linear recurrence equation with polynomial coef\ ficients of order, 23 27 (n + 1) (n + 2) (n + 3) a(n) 63 (n + 4) (n + 3) (n + 2) a(n + 1) ------------------------------- + ----------------------------------- (n + 20) (n + 23) (n + 22) (n + 20) (n + 23) (n + 22) 2 12 (n + 3) (50 n + 483 n + 1219) a(n + 2) - ------------------------------------------ (n + 20) (n + 23) (n + 22) 3 2 3 (185 n + 4012 n + 25769 n + 50610) a(n + 3) + ----------------------------------------------- (n + 20) (n + 23) (n + 22) 3 2 (737 n - 5603 n - 137866 n - 456192) a(n + 4) + ----------------------------------------------- (n + 20) (n + 23) (n + 22) 3 2 2 (1826 n + 20469 n + 17689 n - 234504) a(n + 5) - -------------------------------------------------- (n + 20) (n + 23) (n + 22) 3 2 3 (3529 n + 74954 n + 486691 n + 949122) a(n + 6) + --------------------------------------------------- (n + 20) (n + 23) (n + 22) 3 2 (15942 n + 455441 n + 3953459 n + 10684818) a(n + 7) - ------------------------------------------------------ (n + 20) (n + 23) (n + 22) 3 2 (24757 n + 1246425 n + 14946722 n + 51905292) a(n + 8) + 1/3 -------------------------------------------------------- (n + 20) (n + 23) (n + 22) 3 2 (13841 n + 56118 n - 2263045 n - 14584482) a(n + 9) + ----------------------------------------------------- (n + 20) (n + 23) (n + 22) 3 2 (43257 n + 890411 n + 4913264 n + 3599568) a(n + 10) - ------------------------------------------------------ (n + 20) (n + 23) (n + 22) 3 2 (205225 n + 5374932 n + 43893905 n + 106272834) a(n + 11) + 1/3 ----------------------------------------------------------- (n + 20) (n + 23) (n + 22) 3 2 (233311 n + 7042371 n + 68260730 n + 208610484) a(n + 12) - 1/3 ----------------------------------------------------------- (n + 20) (n + 23) (n + 22) 3 2 (214249 n + 7300614 n + 81076823 n + 290982426) a(n + 13) + 1/3 ----------------------------------------------------------- (n + 20) (n + 23) (n + 22) 3 2 (174649 n + 6679983 n + 84065312 n + 346693404) a(n + 14) - 1/3 ----------------------------------------------------------- (n + 20) (n + 23) (n + 22) 3 2 (133219 n + 5657388 n + 79487063 n + 368778630) a(n + 15) + 1/3 ----------------------------------------------------------- (n + 20) (n + 23) (n + 22) 3 2 (93890 n + 4353687 n + 67002553 n + 341925858) a(n + 16) - 1/3 ---------------------------------------------------------- (n + 20) (n + 23) (n + 22) 3 2 (57556 n + 2867061 n + 47487701 n + 261423966) a(n + 17) + 1/3 ---------------------------------------------------------- (n + 20) (n + 23) (n + 22) 3 2 (28585 n + 1510827 n + 26578916 n + 155603700) a(n + 18) - 1/3 ---------------------------------------------------------- (n + 20) (n + 23) (n + 22) 3 2 2 (1803 n + 100262 n + 1856673 n + 11448430) a(n + 19) + -------------------------------------------------------- (n + 20) (n + 23) (n + 22) 3 2 4 (246 n + 14309 n + 277201 n + 1788381) a(n + 20) - ---------------------------------------------------- (n + 20) (n + 23) (n + 22) 3 2 (181 n + 10964 n + 221165 n + 1485570) a(n + 21) + -------------------------------------------------- (n + 20) (n + 23) (n + 22) 2 (20 n + 817 n + 8327) a(n + 22) - -------------------------------- + a(n + 23) = 0 (n + 23) (n + 20) Subject to the initial conditions a(1) = 0, a(2) = 0, a(3) = 1, a(4) = 6, a(5) = 27, a(6) = 105, a(7) = 378, a(8) = 1298, a(9) = 4321, a(10) = 14077, a(11) = 45147, a(12) = 143103, a(13) = 449523, a(14) = 1402120, a(15) = 4348827, a(16) = 13427110, a(17) = 41302569, a(18) = 126659255, a(19) = 387422127, a(20) = 1182489407, a(21) = 3602624202, a(22) = 10958887373, a(23) = 33291686011 Lemma , 8.2, : Let b(n) be the number of words of length n in the alphabet , {1, 2, 3}, with more occurences of, {[1, 2, 1]}, then , {[2, 2, 3]} b(n) satisfies the following linear recurrence equation with polynomial coef\ ficients of order, 9 3 (n + 1) (n + 2) b(n) (17 n + 71) (n + 2) b(n + 1) ---------------------- - ---------------------------- (n + 9) (n + 6) (n + 9) (n + 6) 2 2 (7 n - 30 n - 142) b(n + 2) (89 n + 547 n + 792) b(n + 3) - 2/3 ---------------------------- + 2/3 ------------------------------ (n + 9) (n + 6) (n + 9) (n + 6) 2 (74 n + 591 n + 1141) b(n + 4) - 4/3 ------------------------------- (n + 9) (n + 6) 2 (184 n + 1801 n + 4288) b(n + 5) + 2/3 --------------------------------- (n + 9) (n + 6) 2 2 2 (51 n + 580 n + 1606) b(n + 6) (71 n + 903 n + 2788) b(n + 7) - --------------------------------- + 2/3 ------------------------------- (n + 9) (n + 6) (n + 9) (n + 6) 2 (11 n + 153 n + 514) b(n + 8) - ------------------------------ + b(n + 9) = 0 (n + 9) (n + 6) Subject to the initial conditions b(1) = 0, b(2) = 0, b(3) = 1, b(4) = 6, b(5) = 26, b(6) = 99, b(7) = 352, b(8) = 1200, b(9) = 3978 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.6181 1/2 - ------ 1/2 n The probability of Bob winning the bet, as n grows larger is approximately 0.7726 1/2 - ------ 1/2 n You can see that indeed Alice has a better chance, but not significantly so. ----------------------------------------- This took, 33.011, seconds to generate ----------------------------------------------------------------------------\ ----------------------- Question Mumber, 9, : If Alice bets that there are more occurrences of consec\ utive substrings in, {[1, 1, 3]}, than in, {[1, 2, 1]}, and Bob, bets vice versa, who is more likely to win? Answer: Alice is more likely to win. Let's be more quantitative. We need the following two lemmas Lemma , 9.1, : Let a(n) be the number of words of length n in the alphabet , {1, 2, 3}, with more occurences of, {[1, 1, 3]}, then , {[1, 2, 1]} a(n) satisfies the following linear recurrence equation with polynomial coef\ ficients of order, 18 972 (n + 1) (n + 2) (n + 3) a(n) 648 (5 n + 17) (n + 3) (n + 2) a(n + 1) - -------------------------------- + --------------------------------------- (n + 15) (n + 18) (n + 17) (n + 15) (n + 18) (n + 17) 2 81 (n + 3) (83 n + 669 n + 1350) a(n + 2) - ------------------------------------------ (n + 15) (n + 18) (n + 17) 3 2 9 (1021 n + 12876 n + 53777 n + 74454) a(n + 3) + ------------------------------------------------- (n + 15) (n + 18) (n + 17) 3 2 6 (881 n + 3993 n - 33158 n - 155472) a(n + 4) - ------------------------------------------------ (n + 15) (n + 18) (n + 17) 3 2 36 (127 n + 6419 n + 64841 n + 185473) a(n + 5) - ------------------------------------------------- (n + 15) (n + 18) (n + 17) 3 2 (16303 n + 560382 n + 5471261 n + 16447734) a(n + 6) + ------------------------------------------------------ (n + 15) (n + 18) (n + 17) 3 2 (85597 n + 2716296 n + 26935529 n + 85555458) a(n + 7) - 1/3 -------------------------------------------------------- (n + 15) (n + 18) (n + 17) 3 2 2 (20484 n + 623465 n + 6207901 n + 20320182) a(n + 8) + -------------------------------------------------------- (n + 15) (n + 18) (n + 17) 3 2 (147427 n + 4481088 n + 45224207 n + 151630794) a(n + 9) - 1/3 ---------------------------------------------------------- (n + 15) (n + 18) (n + 17) 3 2 4 (11928 n + 376507 n + 3955674 n + 13831118) a(n + 10) + --------------------------------------------------------- (n + 15) (n + 18) (n + 17) 3 2 (111931 n + 3755328 n + 41945363 n + 155933490) a(n + 11) - 1/3 ----------------------------------------------------------- (n + 15) (n + 18) (n + 17) 3 2 (35105 n + 1261374 n + 15090541 n + 60094632) a(n + 12) + 2/3 --------------------------------------------------------- (n + 15) (n + 18) (n + 17) 3 2 2 (5747 n + 220751 n + 2823348 n + 12020700) a(n + 13) - -------------------------------------------------------- (n + 15) (n + 18) (n + 17) 3 2 (12737 n + 520392 n + 7078813 n + 32053638) a(n + 14) + 1/3 ------------------------------------------------------- (n + 15) (n + 18) (n + 17) 3 2 (3367 n + 145578 n + 2095205 n + 10036146) a(n + 15) - 1/3 ------------------------------------------------------ (n + 15) (n + 18) (n + 17) 3 2 (298 n + 13575 n + 205775 n + 1037790) a(n + 16) + 2/3 -------------------------------------------------- (n + 15) (n + 18) (n + 17) 2 (21 n + 647 n + 4966) a(n + 17) - -------------------------------- + a(n + 18) = 0 (n + 18) (n + 15) Subject to the initial conditions a(1) = 0, a(2) = 0, a(3) = 1, a(4) = 6, a(5) = 26, a(6) = 99, a(7) = 352, a(8) = 1202, a(9) = 3996, a(10) = 13032, a(11) = 41896, a(12) = 133213, a(13) = 419909, a(14) = 1314462, a(15) = 4091556, a(16) = 12676782, a(17) = 39124406, a(18) = 120357528 Lemma , 9.2, : Let b(n) be the number of words of length n in the alphabet , {1, 2, 3}, with more occurences of, {[1, 2, 1]}, then , {[1, 1, 3]} b(n) satisfies the following linear recurrence equation with polynomial coef\ ficients of order, 10 2 54 (n + 3) (n + 1) b(n) 9 (7 n + 35 n + 40) b(n + 1) - ----------------------- + ----------------------------- (n + 10) (n + 7) (n + 10) (n + 7) 2 2 3 (3 n - 65 n - 224) b(n + 2) 2 (5 n + 253 n + 893) b(n + 3) - ------------------------------ - ------------------------------- (n + 10) (n + 7) (n + 10) (n + 7) 2 (17 n - 570 n - 3104) b(n + 4) - 2/3 ------------------------------- (n + 10) (n + 7) 2 (26 n + 883 n + 4164) b(n + 5) - 2/3 ------------------------------- (n + 10) (n + 7) 2 (128 n + 1829 n + 6420) b(n + 6) + 2/3 --------------------------------- (n + 10) (n + 7) 2 2 2 (47 n + 654 n + 2244) b(n + 7) (70 n + 1037 n + 3762) b(n + 8) - --------------------------------- + 2/3 -------------------------------- (n + 10) (n + 7) (n + 10) (n + 7) 2 (11 n + 175 n + 678) b(n + 9) - ------------------------------ + b(n + 10) = 0 (n + 10) (n + 7) Subject to the initial conditions b(1) = 0, b(2) = 0, b(3) = 1, b(4) = 6, b(5) = 25, b(6) = 93, b(7) = 327, b(8) = 1110, b(9) = 3678, b(10) = 11973 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.6516 1/2 - ------ 1/2 n The probability of Bob winning the bet, as n grows larger is approximately 0.8144 1/2 - ------ 1/2 n You can see that indeed Alice has a better chance, but not significantly so. ----------------------------------------- This took, 28.332, seconds to generate The best bet against, [1, 2, 1], is a member of, {[1, 1, 2], [2, 1, 1]}, 0.1994 and then your edge, if you have n rolls, is approximately, ------ 1/2 n The next best bet is a member of, {[2, 1, 3], [3, 1, 2]}, 0.1847 and then your edge is approximately, ------ 1/2 n The next best bet is a member of, {[1, 1, 3], [1, 2, 2], [1, 2, 3], [1, 3, 2], [1, 3, 3], [2, 2, 1], [2, 3, 1], [3, 1, 1], [3, 2, 1], [3, 3, 1]}, 0.1628 and then your edge is approximately, ------ 1/2 n The next best bet is a member of, {[2, 2, 3], [2, 3, 3], [3, 2, 2], [3, 3, 2]}, 0.1545 and then your edge is approximately, ------ 1/2 n The next best bet is a member of, {[1, 3, 1], [2, 1, 2], [2, 3, 2], [3, 1, 3], [3, 2, 3]}, and then your edge is exactly 0 The next best bet is a member of, {[2, 2, 2], [3, 3, 3]}, 0.3917 and then your edge is approximately, - ------ 1/2 n The next best bet is a member of, {[1, 1, 1]}, 0.4231 and then your edge is approximately, - ------ 1/2 n ----------------------- This ends this chapter that took, 227.611, seconds to generate. ----------------------------------------------------------------- Chapter Number, 4 The Relative Probablity of Winning a Daniel Litt style game when rolling a f\ air, 3, sides die marked with, {1, 2, 3}, of number of occurrences of, [1, 2, 2], Versus the number of occurences of all, 3, letter words in, {1, 2, 3} By Shalosh B. Ekhad ----------------------------------------------------------------------------\ ----------------------- Question Mumber, 1, : If Alice bets that there are more occurrences of consec\ utive substrings in, {[1, 1, 1]}, than in, {[1, 2, 2]}, and Bob, bets vice versa, who is more likely to win? Answer: Bob is more likely to win. Let's be more quantitative. We need the following two lemmas Lemma , 1.1, : Let a(n) be the number of words of length n in the alphabet , {1, 2, 3}, with more occurences of, {[1, 1, 1]}, then , {[1, 2, 2]} a(n) satisfies the following linear recurrence equation with polynomial coef\ ficients of order, 11 27 (n + 1) (n + 2) a(n) 18 (n + 5) (n + 2) a(n + 1) - ----------------------- - --------------------------- (n + 11) (n + 8) (n + 11) (n + 8) 2 2 3 (19 n + 205 n + 442) a(n + 2) (49 n + 341 n + 504) a(n + 3) + -------------------------------- - ------------------------------ (n + 11) (n + 8) (n + 11) (n + 8) 2 2 2 (15 n + 79 n + 44) a(n + 4) (185 n + 1903 n + 4656) a(n + 5) + ------------------------------ + 1/3 --------------------------------- (n + 11) (n + 8) (n + 11) (n + 8) 2 2 (95 n + 1399 n + 5352) a(n + 6) 2 (25 n + 308 n + 882) a(n + 7) - 1/3 -------------------------------- - -------------------------------- (n + 11) (n + 8) (n + 11) (n + 8) (65 n + 534) (n + 5) a(n + 8) (7 n + 72) (5 n + 39) a(n + 9) + 1/3 ----------------------------- + 1/3 ------------------------------ (n + 11) (n + 8) (n + 11) (n + 8) 2 (11 n + 200 n + 891) a(n + 10) - 2/3 ------------------------------- + a(n + 11) = 0 (n + 11) (n + 8) Subject to the initial conditions a(1) = 0, a(2) = 0, a(3) = 1, a(4) = 5, a(5) = 20, a(6) = 75, a(7) = 265, a(8) = 907, a(9) = 3030, a(10) = 9945, a(11) = 32208 Lemma , 1.2, : Let b(n) be the number of words of length n in the alphabet , {1, 2, 3}, with more occurences of, {[1, 2, 2]}, then , {[1, 1, 1]} b(n) satisfies the following linear recurrence equation with polynomial coef\ ficients of order, 21 1701 (n + 1) (n + 2) (n + 3) b(n) 243 (17 n - 6) (n + 3) (n + 2) b(n + 1) - --------------------------------- + --------------------------------------- (n + 19) (n + 18) (n + 21) (n + 19) (n + 18) (n + 21) 2 27 (n + 3) (23 n + 849 n + 2056) b(n + 2) + ------------------------------------------ (n + 19) (n + 18) (n + 21) 3 2 27 (169 n + 2622 n + 15223 n + 29566) b(n + 3) + ------------------------------------------------ (n + 19) (n + 18) (n + 21) 3 2 3 (4840 n + 102225 n + 640325 n + 1246386) b(n + 4) - ----------------------------------------------------- (n + 19) (n + 18) (n + 21) 3 2 3 (3385 n + 49481 n + 170144 n - 13430) b(n + 5) + -------------------------------------------------- (n + 19) (n + 18) (n + 21) 3 2 3 (3482 n + 154207 n + 1603453 n + 4856894) b(n + 6) + ------------------------------------------------------ (n + 19) (n + 18) (n + 21) 3 2 (59075 n + 1667001 n + 14921170 n + 43094853) b(n + 7) - 2/3 -------------------------------------------------------- (n + 19) (n + 18) (n + 21) 3 2 (48074 n + 1363311 n + 12792103 n + 39801840) b(n + 8) + -------------------------------------------------------- (n + 19) (n + 18) (n + 21) 3 2 (43339 n + 1821123 n + 23081162 n + 92066364) b(n + 9) - 1/3 -------------------------------------------------------- (n + 19) (n + 18) (n + 21) 3 2 (4670 n - 401523 n - 9543323 n - 50468514) b(n + 10) - 1/3 ------------------------------------------------------ (n + 19) (n + 18) (n + 21) 3 2 (17090 n + 588018 n + 6477682 n + 22737687) b(n + 11) - 2/3 ------------------------------------------------------- (n + 19) (n + 18) (n + 21) 3 2 (38125 n + 1064469 n + 8719772 n + 17173824) b(n + 12) + 1/3 -------------------------------------------------------- (n + 19) (n + 18) (n + 21) 3 2 (21473 n + 582618 n + 4189831 n + 3190524) b(n + 13) - 1/3 ------------------------------------------------------ (n + 19) (n + 18) (n + 21) 3 2 (20273 n + 736650 n + 8707345 n + 33158730) b(n + 14) + 1/3 ------------------------------------------------------- (n + 19) (n + 18) (n + 21) 3 2 (14969 n + 617205 n + 8422702 n + 38001030) b(n + 15) - 1/3 ------------------------------------------------------- (n + 19) (n + 18) (n + 21) 3 2 (1855 n + 76245 n + 1022525 n + 4442649) b(n + 16) + 2/3 ---------------------------------------------------- (n + 19) (n + 18) (n + 21) 3 2 (1571 n + 84051 n + 1489312 n + 8745672) b(n + 17) + 1/3 ---------------------------------------------------- (n + 19) (n + 18) (n + 21) 2 2 (n + 17) (224 n + 7929 n + 70035) b(n + 18) - ---------------------------------------------- (n + 19) (n + 18) (n + 21) 3 2 (130 n + 7019 n + 126201 n + 755696) b(n + 19) + ------------------------------------------------ (n + 19) (n + 18) (n + 21) 2 (18 n + 683 n + 6457) b(n + 20) - -------------------------------- + b(n + 21) = 0 (n + 21) (n + 19) Subject to the initial conditions b(1) = 0, b(2) = 0, b(3) = 1, b(4) = 6, b(5) = 26, b(6) = 100, b(7) = 359, b(8) = 1238, b(9) = 4151, b(10) = 13641, b(11) = 44156, b(12) = 141269, b(13) = 447790, b(14) = 1408770, b(15) = 4404804, b(16) = 13701992, b(17) = 42439052, b(18) = 130965283, b(19) = 402889009, b(20) = 1236068210, b(21) = 3783416048 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.9169 1/2 - ------ 1/2 n The probability of Bob winning the bet, as n grows larger is approximately 0.3527 1/2 - ------ 1/2 n You can see that indeed Bob has a better chance, but not significantly so. ----------------------------------------- This took, 33.132, seconds to generate ----------------------------------------------------------------------------\ ----------------------- Question Mumber, 2, : If Alice bets that there are more occurrences of consec\ utive substrings in, {[2, 1, 2]}, than in, {[1, 2, 2]}, and Bob, bets vice versa, who is more likely to win? Answer: Bob is more likely to win. Let's be more quantitative. We need the following two lemmas Lemma , 2.1, : Let a(n) be the number of words of length n in the alphabet , {1, 2, 3}, with more occurences of, {[2, 1, 2]}, then , {[1, 2, 2]} a(n) satisfies the following linear recurrence equation with polynomial coef\ ficients of order, 15 162 (n + 1) (n + 2) (n + 3) a(n) 27 (43 n + 145) (n + 3) (n + 2) a(n + 1) -------------------------------- - ---------------------------------------- (n + 15) (n + 12) (n + 16) (n + 15) (n + 12) (n + 16) 2 9 (n + 3) (440 n + 3645 n + 7582) a(n + 2) + ------------------------------------------- (n + 15) (n + 12) (n + 16) 2 9 (n + 4) (955 n + 9779 n + 25134) a(n + 3) - -------------------------------------------- (n + 15) (n + 12) (n + 16) 2 9 (n + 5) (1363 n + 16045 n + 47382) a(n + 4) + ---------------------------------------------- (n + 15) (n + 12) (n + 16) 2 9 (n + 6) (1206 n + 14731 n + 44531) a(n + 5) - ---------------------------------------------- (n + 15) (n + 12) (n + 16) 2 9 (n + 7) (572 n + 4837 n + 3432) a(n + 6) + ------------------------------------------- (n + 15) (n + 12) (n + 16) 2 9 (n + 8) (27 n - 4393 n - 39476) a(n + 7) - ------------------------------------------- (n + 15) (n + 12) (n + 16) 2 6 (n + 9) (299 n + 10948 n + 76089) a(n + 8) - --------------------------------------------- (n + 15) (n + 12) (n + 16) 2 3 (n + 10) (751 n + 19688 n + 121659) a(n + 9) + ----------------------------------------------- (n + 15) (n + 12) (n + 16) 2 (n + 11) (1966 n + 44617 n + 250452) a(n + 10) - ----------------------------------------------- (n + 15) (n + 12) (n + 16) 2 (3599 n + 80241 n + 442366) a(n + 11) + 1/3 -------------------------------------- (n + 16) (n + 15) 2 (n + 13) (1441 n + 33377 n + 190860) a(n + 12) - 1/3 ----------------------------------------------- (n + 15) (n + 12) (n + 16) 2 (n + 14) (358 n + 8743 n + 52725) a(n + 13) + 1/3 -------------------------------------------- (n + 15) (n + 12) (n + 16) 2 (50 n + 1287 n + 8182) a(n + 14) - 1/3 --------------------------------- + a(n + 15) = 0 (n + 16) (n + 12) Subject to the initial conditions a(1) = 0, a(2) = 0, a(3) = 1, a(4) = 5, a(5) = 19, a(6) = 71, a(7) = 252, a(8) = 858, a(9) = 2864, a(10) = 9406, a(11) = 30465, a(12) = 97671, a(13) = 310575, a(14) = 980757, a(15) = 3079464 Lemma , 2.2, : Let b(n) be the number of words of length n in the alphabet , {1, 2, 3}, with more occurences of, {[1, 2, 2]}, then , {[2, 1, 2]} b(n) satisfies the following linear recurrence equation with polynomial coef\ ficients of order, 17 810 (n + 1) (n + 2) (n + 3) b(n) 27 (131 n + 245) (n + 3) (n + 2) b(n + 1) - -------------------------------- + ----------------------------------------- (n + 14) (n + 17) (n + 16) (n + 14) (n + 17) (n + 16) 9 (394 n + 1391) (n - 2) (n + 3) b(n + 2) - ----------------------------------------- (n + 14) (n + 17) (n + 16) 3 2 9 (386 n + 8613 n + 50665 n + 89760) b(n + 3) - ----------------------------------------------- (n + 14) (n + 17) (n + 16) 3 2 27 (88 n + 609 n - 2151 n - 14808) b(n + 4) + --------------------------------------------- (n + 14) (n + 17) (n + 16) 3 2 9 (3004 n + 74765 n + 586035 n + 1473258) b(n + 5) + ---------------------------------------------------- (n + 14) (n + 17) (n + 16) 3 2 9 (8294 n + 215969 n + 1820443 n + 5006346) b(n + 6) - ------------------------------------------------------ (n + 14) (n + 17) (n + 16) 3 2 9 (11914 n + 333715 n + 3057575 n + 9205968) b(n + 7) + ------------------------------------------------------- (n + 14) (n + 17) (n + 16) 3 2 3 (35800 n + 1064831 n + 10442739 n + 33847668) b(n + 8) - ---------------------------------------------------------- (n + 14) (n + 17) (n + 16) 3 2 3 (28450 n + 882599 n + 9086147 n + 31066050) b(n + 9) + -------------------------------------------------------- (n + 14) (n + 17) (n + 16) 3 2 (57574 n + 1849647 n + 19776509 n + 70378674) b(n + 10) - --------------------------------------------------------- (n + 14) (n + 17) (n + 16) 3 2 (98678 n + 3307503 n + 36893299 n + 136913376) b(n + 11) + 1/3 ---------------------------------------------------------- (n + 14) (n + 17) (n + 16) 3 2 (45344 n + 1603473 n + 18859177 n + 73743168) b(n + 12) - 1/3 --------------------------------------------------------- (n + 14) (n + 17) (n + 16) 3 2 (5260 n + 197467 n + 2465205 n + 10230342) b(n + 13) + ------------------------------------------------------ (n + 14) (n + 17) (n + 16) 3 2 (3934 n + 156933 n + 2081855 n + 9181386) b(n + 14) - 1/3 ----------------------------------------------------- (n + 14) (n + 17) (n + 16) 3 2 (658 n + 27831 n + 391427 n + 1830144) b(n + 15) + 1/3 -------------------------------------------------- (n + 14) (n + 17) (n + 16) 2 (22 n + 631 n + 4505) b(n + 16) - -------------------------------- + b(n + 17) = 0 (n + 17) (n + 14) Subject to the initial conditions b(1) = 0, b(2) = 0, b(3) = 1, b(4) = 5, b(5) = 20, b(6) = 76, b(7) = 271, b(8) = 929, b(9) = 3114, b(10) = 10248, b(11) = 33245, b(12) = 106693, b(13) = 339428, b(14) = 1072072, b(15) = 3366035, b(16) = 10515841, b(17) = 32713202 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.9974 1/2 - ------ 1/2 n The probability of Bob winning the bet, as n grows larger is approximately 0.7980 1/2 - ------ 1/2 n You can see that indeed Bob has a better chance, but not significantly so. ----------------------------------------- This took, 32.980, seconds to generate ----------------------------------------------------------------------------\ ----------------------- Question Mumber, 3, : If Alice bets that there are more occurrences of consec\ utive substrings in, {[2, 2, 1]}, than in, {[1, 2, 2]}, and Bob, bets vice versa, who is more likely to win? Answer: They are equally likely to win ----------------------------------------------------------------------------\ ----------------------- Question Mumber, 4, : If Alice bets that there are more occurrences of consec\ utive substrings in, {[2, 2, 2]}, than in, {[1, 2, 2]}, and Bob, bets vice versa, who is more likely to win? Answer: Bob is more likely to win. Let's be more quantitative. We need the following two lemmas Lemma , 4.1, : Let a(n) be the number of words of length n in the alphabet , {1, 2, 3}, with more occurences of, {[2, 2, 2]}, then , {[1, 2, 2]} a(n) satisfies the following linear recurrence equation with polynomial coef\ ficients of order, 10 2 54 (n + 3) (n + 1) a(n) 9 (5 n + 19 n + 20) a(n + 1) - ----------------------- - ----------------------------- (n + 10) (n + 7) (n + 10) (n + 7) 2 2 6 (9 n + 88 n + 187) a(n + 2) 2 (5 n + 19 n - 40) a(n + 3) + ------------------------------ - ----------------------------- (n + 10) (n + 7) (n + 10) (n + 7) 2 (31 n + 759 n + 2918) a(n + 4) - 1/3 ------------------------------- (n + 10) (n + 7) 2 2 (68 n + 612 n + 1171) a(n + 5) 2 (21 n + 233 n + 637) a(n + 6) + 2/3 ------------------------------- - -------------------------------- (n + 10) (n + 7) (n + 10) (n + 7) 2 (29 n + 351 n + 886) a(n + 7) (5 n + 43) (7 n + 41) a(n + 8) - 1/3 ------------------------------ + 2/3 ------------------------------ (n + 10) (n + 7) (n + 10) (n + 7) 2 (13 n + 206 n + 792) a(n + 9) - 2/3 ------------------------------ + a(n + 10) = 0 (n + 10) (n + 7) Subject to the initial conditions a(1) = 0, a(2) = 0, a(3) = 1, a(4) = 4, a(5) = 16, a(6) = 59, a(7) = 209, a(8) = 716, a(9) = 2401, a(10) = 7920 Lemma , 4.2, : Let b(n) be the number of words of length n in the alphabet , {1, 2, 3}, with more occurences of, {[1, 2, 2]}, then , {[2, 2, 2]} b(n) satisfies the following linear recurrence equation with polynomial coef\ ficients of order, 21 1944 (n + 1) (n + 2) (n + 3) b(n) 648 (11 n + 32) (n + 3) (n + 2) b(n + 1) --------------------------------- + ---------------------------------------- (n + 19) (n + 18) (n + 21) (n + 19) (n + 18) (n + 21) 2 324 (n + 3) (29 n + 219 n + 410) b(n + 2) + ------------------------------------------ (n + 19) (n + 18) (n + 21) 3 2 36 (52 n + 177 n - 1819 n - 6726) b(n + 3) + -------------------------------------------- (n + 19) (n + 18) (n + 21) 3 2 6 (725 n + 13920 n + 79489 n + 139530) b(n + 4) - ------------------------------------------------- (n + 19) (n + 18) (n + 21) 3 2 6 (2281 n + 62871 n + 530540 n + 1416864) b(n + 5) + ---------------------------------------------------- (n + 19) (n + 18) (n + 21) 3 2 (26839 n + 743766 n + 6492557 n + 18229086) b(n + 6) + ------------------------------------------------------ (n + 19) (n + 18) (n + 21) 3 2 (3032 n + 4665 n - 714395 n - 4625442) b(n + 7) + 1/3 ------------------------------------------------- (n + 19) (n + 18) (n + 21) 3 2 (26128 n + 1121367 n + 13897661 n + 53471952) b(n + 8) - 1/3 -------------------------------------------------------- (n + 19) (n + 18) (n + 21) 3 2 (2503 n + 161232 n + 2492381 n + 11240784) b(n + 9) - 1/3 ----------------------------------------------------- (n + 19) (n + 18) (n + 21) 3 2 4 (3032 n + 73724 n + 533683 n + 974722) b(n + 10) - ---------------------------------------------------- (n + 19) (n + 18) (n + 21) 3 2 (2773 n + 79314 n + 672959 n + 1486392) b(n + 11) - 2/3 --------------------------------------------------- (n + 19) (n + 18) (n + 21) 3 2 (17000 n + 544224 n + 5669635 n + 19029189) b(n + 12) + 2/3 ------------------------------------------------------- (n + 19) (n + 18) (n + 21) 3 2 (64 n - 20799 n - 554167 n - 3556227) b(n + 13) - 2/3 ------------------------------------------------- (n + 19) (n + 18) (n + 21) 3 2 (5377 n + 204288 n + 2559041 n + 10553727) b(n + 14) - 2/3 ------------------------------------------------------ (n + 19) (n + 18) (n + 21) 3 2 2 (30 n + 6413 n + 168374 n + 1182627) b(n + 15) - -------------------------------------------------- (n + 19) (n + 18) (n + 21) 3 2 (1109 n + 54714 n + 897577 n + 4897632) b(n + 16) + 2/3 --------------------------------------------------- (n + 19) (n + 18) (n + 21) 3 2 (224 n + 11319 n + 189379 n + 1048836) b(n + 17) + 2/3 -------------------------------------------------- (n + 19) (n + 18) (n + 21) 3 2 (295 n + 15282 n + 263511 n + 1512492) b(n + 18) - -------------------------------------------------- (n + 19) (n + 18) (n + 21) 3 2 (320 n + 17205 n + 307969 n + 1835484) b(n + 19) + 1/3 -------------------------------------------------- (n + 19) (n + 18) (n + 21) 2 (50 n + 1893 n + 17851) b(n + 20) - 1/3 ---------------------------------- + b(n + 21) = 0 (n + 21) (n + 19) Subject to the initial conditions b(1) = 0, b(2) = 0, b(3) = 1, b(4) = 5, b(5) = 21, b(6) = 79, b(7) = 283, b(8) = 977, b(9) = 3290, b(10) = 10875, b(11) = 35443, b(12) = 114229, b(13) = 364843, b(14) = 1156685, b(15) = 3644488, b(16) = 11423152, b(17) = 35644648, b(18) = 110797293, b(19) = 343249281, b(20) = 1060272685, b(21) = 3266670158 This enables us to compute the first, 20000, terms of these sequences The probability of Alice winning the bet, as n grows larger is approximately 1.059 1/2 - ----- 1/2 n The probability of Bob winning the bet, as n grows larger is approximately 0.4073 1/2 - ------ 1/2 n You can see that indeed Bob has a better chance, but not significantly so. ----------------------------------------- This took, 32.263, seconds to generate ----------------------------------------------------------------------------\ ----------------------- Question Mumber, 5, : If Alice bets that there are more occurrences of consec\ utive substrings in, {[2, 2, 3]}, than in, {[1, 2, 2]}, and Bob, bets vice versa, who is more likely to win? Answer: They are equally likely to win ----------------------------------------------------------------------------\ ----------------------- Question Mumber, 6, : If Alice bets that there are more occurrences of consec\ utive substrings in, {[3, 3, 3]}, than in, {[1, 2, 2]}, and Bob, bets vice versa, who is more likely to win? Answer: Bob is more likely to win. Let's be more quantitative. We need the following two lemmas Lemma , 6.1, : Let a(n) be the number of words of length n in the alphabet , {1, 2, 3}, with more occurences of, {[3, 3, 3]}, then , {[1, 2, 2]} a(n) satisfies the following linear recurrence equation with polynomial coef\ ficients of order, 9 6 (n + 1) (n + 2) a(n) 2 (n + 19) (n + 2) a(n + 1) - ---------------------- - --------------------------- (n + 9) (n + 6) (n + 9) (n + 6) 2 (127 n + 771 n + 1142) a(n + 2) + 1/3 -------------------------------- (n + 9) (n + 6) 2 (55 n + 359 n + 510) a(n + 3) (n + 4) (4 n + 9) a(n + 4) + 1/3 ------------------------------ - 8/3 -------------------------- (n + 9) (n + 6) (n + 9) (n + 6) 2 2 (13 n + 71) a(n + 5) (2 n + 22 n + 51) a(n + 6) - ---------------------- - 8/3 --------------------------- n + 9 (n + 9) (n + 6) 2 (31 n + 403 n + 1266) a(n + 7) + 2/3 ------------------------------- (n + 9) (n + 6) 2 (25 n + 351 n + 1190) a(n + 8) - 1/3 ------------------------------- + a(n + 9) = 0 (n + 9) (n + 6) Subject to the initial conditions a(1) = 0, a(2) = 0, a(3) = 1, a(4) = 5, a(5) = 21, a(6) = 79, a(7) = 281, a(8) = 963, a(9) = 3218 Lemma , 6.2, : Let b(n) be the number of words of length n in the alphabet , {1, 2, 3}, with more occurences of, {[1, 2, 2]}, then , {[3, 3, 3]} b(n) satisfies the following linear recurrence equation with polynomial coef\ ficients of order, 27 2 (15 n + 752 n + 9409) b(n + 26) - -------------------------------- + b(n + 27) (n + 27) (n + 25) 2 3 (n + 3) (529 n + 5115 n + 12782) b(n + 2) - -------------------------------------------- (n + 25) (n + 24) (n + 27) 3 2 4 (1687 n + 18608 n + 45391 n - 27942) b(n + 4) + ------------------------------------------------- (n + 25) (n + 24) (n + 27) 3 2 4 (3715 n + 67832 n + 385589 n + 672376) b(n + 5) + --------------------------------------------------- (n + 25) (n + 24) (n + 27) 3 2 (14663 n + 450294 n + 3973617 n + 10756362) b(n + 6) + ------------------------------------------------------ (n + 25) (n + 24) (n + 27) 3 2 (6565 n - 78614 n - 2415173 n - 10833962) b(n + 7) - ---------------------------------------------------- (n + 25) (n + 24) (n + 27) 3 2 (69380 n + 1622667 n + 12134728 n + 28595013) b(n + 8) - 2/3 -------------------------------------------------------- (n + 25) (n + 24) (n + 27) 3 2 (162649 n + 5116656 n + 52523375 n + 176618592) b(n + 9) - 1/3 ---------------------------------------------------------- (n + 25) (n + 24) (n + 27) 3 2 (20227 n + 1583478 n + 26610425 n + 128067150) b(n + 10) - 1/3 ---------------------------------------------------------- (n + 25) (n + 24) (n + 27) 3 2 2 (24661 n + 749292 n + 7272083 n + 22049388) b(n + 11) + --------------------------------------------------------- (n + 25) (n + 24) (n + 27) 3 2 (80788 n + 3110073 n + 39322256 n + 163295187) b(n + 12) + 2/3 ---------------------------------------------------------- (n + 25) (n + 24) (n + 27) 3 2 (7229 n + 566492 n + 11154971 n + 65017148) b(n + 13) + ------------------------------------------------------- (n + 25) (n + 24) (n + 27) 3 2 (24837 n + 929088 n + 11134663 n + 41939636) b(n + 14) - -------------------------------------------------------- (n + 25) (n + 24) (n + 27) 3 2 (66767 n + 3345282 n + 54591445 n + 290961618) b(n + 15) - 1/3 ---------------------------------------------------------- (n + 25) (n + 24) (n + 27) 3 2 (3659 n + 321525 n + 7626799 n + 54654681) b(n + 16) - 2/3 ------------------------------------------------------ (n + 25) (n + 24) (n + 27) 3 2 (10105 n + 506118 n + 8337343 n + 45067306) b(n + 17) + ------------------------------------------------------- (n + 25) (n + 24) (n + 27) 3 2 2 (2953 n + 179891 n + 3603315 n + 23784369) b(n + 18) + -------------------------------------------------------- (n + 25) (n + 24) (n + 27) 3 2 (4367 n + 228618 n + 3852001 n + 20557686) b(n + 19) - 1/3 ------------------------------------------------------ (n + 25) (n + 24) (n + 27) 3 2 (3653 n + 220962 n + 4459099 n + 30023958) b(n + 20) - ------------------------------------------------------ (n + 25) (n + 24) (n + 27) 3 2 (836 n + 44211 n + 749998 n + 3992943) b(n + 21) + 2/3 -------------------------------------------------- (n + 25) (n + 24) (n + 27) 3 2 (2953 n + 195576 n + 4319843 n + 31826364) b(n + 22) + 1/3 ------------------------------------------------------ (n + 25) (n + 24) (n + 27) 3 2 (737 n + 47424 n + 1015903 n + 7246992) b(n + 23) - 1/3 --------------------------------------------------- (n + 25) (n + 24) (n + 27) 3 2 (143 n + 10312 n + 247493 n + 1977012) b(n + 24) - -------------------------------------------------- (n + 25) (n + 24) (n + 27) 3 2 (81 n + 5872 n + 141819 n + 1141148) b(n + 25) + ------------------------------------------------ (n + 25) (n + 24) (n + 27) 54 (n + 1) (n + 2) (n + 3) b(n) 144 (n + 4) (n + 3) (n + 2) b(n + 1) + ------------------------------- - ------------------------------------ (n + 25) (n + 24) (n + 27) (n + 25) (n + 24) (n + 27) 3 2 3 (243 n + 6910 n + 49609 n + 103686) b(n + 3) - ------------------------------------------------ = 0 (n + 25) (n + 24) (n + 27) Subject to the initial conditions b(1) = 0, b(2) = 0, b(3) = 1, b(4) = 6, b(5) = 27, b(6) = 105, b(7) = 380, b(8) = 1314, b(9) = 4409, b(10) = 14480, b(11) = 46806, b(12) = 149468, b(13) = 472763, b(14) = 1483925, b(15) = 4628838, b(16) = 14364742, b(17) = 44387488, b(18) = 136664364, b(19) = 419488390, b(20) = 1284247530, b(21) = 3922850548, b(22) = 11959476936, b(23) = 36399183405, b(24) = 110620176566, b(25) = 335753314105, b(26) = 1017929773518, b(27) = 3083084677252 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.8809 1/2 - ------ 1/2 n The probability of Bob winning the bet, as n grows larger is approximately 0.3389 1/2 - ------ 1/2 n You can see that indeed Bob has a better chance, but not significantly so. ----------------------------------------- This took, 39.814, seconds to generate ----------------------------------------------------------------------------\ ----------------------- Question Mumber, 7, : If Alice bets that there are more occurrences of consec\ utive substrings in, {[1, 1, 2]}, than in, {[1, 2, 2]}, and Bob, bets vice versa, who is more likely to win? Answer: They are equally likely to win ----------------------------------------------------------------------------\ ----------------------- Question Mumber, 8, : If Alice bets that there are more occurrences of consec\ utive substrings in, {[2, 1, 1]}, than in, {[1, 2, 2]}, and Bob, bets vice versa, who is more likely to win? Answer: They are equally likely to win ----------------------------------------------------------------------------\ ----------------------- Question Mumber, 9, : If Alice bets that there are more occurrences of consec\ utive substrings in, {[3, 1, 3]}, than in, {[1, 2, 2]}, and Bob, bets vice versa, who is more likely to win? Answer: Bob is more likely to win. Let's be more quantitative. We need the following two lemmas Lemma , 9.1, : Let a(n) be the number of words of length n in the alphabet , {1, 2, 3}, with more occurences of, {[3, 1, 3]}, then , {[1, 2, 2]} a(n) satisfies the following linear recurrence equation with polynomial coef\ ficients of order, 9 3 (n + 1) (n + 2) a(n) (17 n + 71) (n + 2) a(n + 1) ---------------------- - ---------------------------- (n + 9) (n + 6) (n + 9) (n + 6) 2 2 (7 n - 30 n - 142) a(n + 2) (89 n + 547 n + 792) a(n + 3) - 2/3 ---------------------------- + 2/3 ------------------------------ (n + 9) (n + 6) (n + 9) (n + 6) 2 (74 n + 591 n + 1141) a(n + 4) - 4/3 ------------------------------- (n + 9) (n + 6) 2 (184 n + 1801 n + 4288) a(n + 5) + 2/3 --------------------------------- (n + 9) (n + 6) 2 2 2 (51 n + 580 n + 1606) a(n + 6) (71 n + 903 n + 2788) a(n + 7) - --------------------------------- + 2/3 ------------------------------- (n + 9) (n + 6) (n + 9) (n + 6) 2 (11 n + 153 n + 514) a(n + 8) - ------------------------------ + a(n + 9) = 0 (n + 9) (n + 6) Subject to the initial conditions a(1) = 0, a(2) = 0, a(3) = 1, a(4) = 6, a(5) = 26, a(6) = 99, a(7) = 352, a(8) = 1200, a(9) = 3978 Lemma , 9.2, : Let b(n) be the number of words of length n in the alphabet , {1, 2, 3}, with more occurences of, {[1, 2, 2]}, then , {[3, 1, 3]} b(n) satisfies the following linear recurrence equation with polynomial coef\ ficients of order, 23 27 (n + 1) (n + 2) (n + 3) b(n) 63 (n + 4) (n + 3) (n + 2) b(n + 1) ------------------------------- + ----------------------------------- (n + 20) (n + 23) (n + 22) (n + 20) (n + 23) (n + 22) 2 12 (n + 3) (50 n + 483 n + 1219) b(n + 2) - ------------------------------------------ (n + 20) (n + 23) (n + 22) 3 2 3 (185 n + 4012 n + 25769 n + 50610) b(n + 3) + ----------------------------------------------- (n + 20) (n + 23) (n + 22) 3 2 (737 n - 5603 n - 137866 n - 456192) b(n + 4) + ----------------------------------------------- (n + 20) (n + 23) (n + 22) 3 2 2 (1826 n + 20469 n + 17689 n - 234504) b(n + 5) - -------------------------------------------------- (n + 20) (n + 23) (n + 22) 3 2 3 (3529 n + 74954 n + 486691 n + 949122) b(n + 6) + --------------------------------------------------- (n + 20) (n + 23) (n + 22) 3 2 (15942 n + 455441 n + 3953459 n + 10684818) b(n + 7) - ------------------------------------------------------ (n + 20) (n + 23) (n + 22) 3 2 (24757 n + 1246425 n + 14946722 n + 51905292) b(n + 8) + 1/3 -------------------------------------------------------- (n + 20) (n + 23) (n + 22) 3 2 (13841 n + 56118 n - 2263045 n - 14584482) b(n + 9) + ----------------------------------------------------- (n + 20) (n + 23) (n + 22) 3 2 (43257 n + 890411 n + 4913264 n + 3599568) b(n + 10) - ------------------------------------------------------ (n + 20) (n + 23) (n + 22) 3 2 (205225 n + 5374932 n + 43893905 n + 106272834) b(n + 11) + 1/3 ----------------------------------------------------------- (n + 20) (n + 23) (n + 22) 3 2 (233311 n + 7042371 n + 68260730 n + 208610484) b(n + 12) - 1/3 ----------------------------------------------------------- (n + 20) (n + 23) (n + 22) 3 2 (214249 n + 7300614 n + 81076823 n + 290982426) b(n + 13) + 1/3 ----------------------------------------------------------- (n + 20) (n + 23) (n + 22) 3 2 (174649 n + 6679983 n + 84065312 n + 346693404) b(n + 14) - 1/3 ----------------------------------------------------------- (n + 20) (n + 23) (n + 22) 3 2 (133219 n + 5657388 n + 79487063 n + 368778630) b(n + 15) + 1/3 ----------------------------------------------------------- (n + 20) (n + 23) (n + 22) 3 2 (93890 n + 4353687 n + 67002553 n + 341925858) b(n + 16) - 1/3 ---------------------------------------------------------- (n + 20) (n + 23) (n + 22) 3 2 (57556 n + 2867061 n + 47487701 n + 261423966) b(n + 17) + 1/3 ---------------------------------------------------------- (n + 20) (n + 23) (n + 22) 3 2 (28585 n + 1510827 n + 26578916 n + 155603700) b(n + 18) - 1/3 ---------------------------------------------------------- (n + 20) (n + 23) (n + 22) 3 2 2 (1803 n + 100262 n + 1856673 n + 11448430) b(n + 19) + -------------------------------------------------------- (n + 20) (n + 23) (n + 22) 3 2 4 (246 n + 14309 n + 277201 n + 1788381) b(n + 20) - ---------------------------------------------------- (n + 20) (n + 23) (n + 22) 3 2 (181 n + 10964 n + 221165 n + 1485570) b(n + 21) + -------------------------------------------------- (n + 20) (n + 23) (n + 22) 2 (20 n + 817 n + 8327) b(n + 22) - -------------------------------- + b(n + 23) = 0 (n + 23) (n + 20) Subject to the initial conditions b(1) = 0, b(2) = 0, b(3) = 1, b(4) = 6, b(5) = 27, b(6) = 105, b(7) = 378, b(8) = 1298, b(9) = 4321, b(10) = 14077, b(11) = 45147, b(12) = 143103, b(13) = 449523, b(14) = 1402120, b(15) = 4348827, b(16) = 13427110, b(17) = 41302569, b(18) = 126659255, b(19) = 387422127, b(20) = 1182489407, b(21) = 3602624202, b(22) = 10958887373, b(23) = 33291686011 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.7726 1/2 - ------ 1/2 n The probability of Bob winning the bet, as n grows larger is approximately 0.6181 1/2 - ------ 1/2 n You can see that indeed Bob has a better chance, but not significantly so. ----------------------------------------- This took, 33.877, seconds to generate ----------------------------------------------------------------------------\ ----------------------- Question Mumber, 10, : If Alice bets that there are more occurrences of conse\ cutive substrings in, {[1, 2, 1]}, than in, {[1, 2, 2]}, and Bob, bets vice versa, who is more likely to win? Answer: Bob is more likely to win. Let's be more quantitative. We need the following two lemmas Lemma , 10.1, : Let a(n) be the number of words of length n in the alphabet , {1, 2, 3}, with more occurences of, {[1, 2, 1]}, then , {[1, 2, 2]} a(n) satisfies the following linear recurrence equation with polynomial coef\ ficients of order, 10 2 54 (n + 3) (n + 1) a(n) 9 (7 n + 35 n + 40) a(n + 1) - ----------------------- + ----------------------------- (n + 10) (n + 7) (n + 10) (n + 7) 2 2 3 (3 n - 65 n - 224) a(n + 2) 2 (5 n + 253 n + 893) a(n + 3) - ------------------------------ - ------------------------------- (n + 10) (n + 7) (n + 10) (n + 7) 2 (17 n - 570 n - 3104) a(n + 4) - 2/3 ------------------------------- (n + 10) (n + 7) 2 (26 n + 883 n + 4164) a(n + 5) - 2/3 ------------------------------- (n + 10) (n + 7) 2 (128 n + 1829 n + 6420) a(n + 6) + 2/3 --------------------------------- (n + 10) (n + 7) 2 2 2 (47 n + 654 n + 2244) a(n + 7) (70 n + 1037 n + 3762) a(n + 8) - --------------------------------- + 2/3 -------------------------------- (n + 10) (n + 7) (n + 10) (n + 7) 2 (11 n + 175 n + 678) a(n + 9) - ------------------------------ + a(n + 10) = 0 (n + 10) (n + 7) Subject to the initial conditions a(1) = 0, a(2) = 0, a(3) = 1, a(4) = 6, a(5) = 25, a(6) = 93, a(7) = 327, a(8) = 1110, a(9) = 3678, a(10) = 11973 Lemma , 10.2, : Let b(n) be the number of words of length n in the alphabet , {1, 2, 3}, with more occurences of, {[1, 2, 2]}, then , {[1, 2, 1]} b(n) satisfies the following linear recurrence equation with polynomial coef\ ficients of order, 18 972 (n + 1) (n + 2) (n + 3) b(n) 648 (5 n + 17) (n + 3) (n + 2) b(n + 1) - -------------------------------- + --------------------------------------- (n + 15) (n + 18) (n + 17) (n + 15) (n + 18) (n + 17) 2 81 (n + 3) (83 n + 669 n + 1350) b(n + 2) - ------------------------------------------ (n + 15) (n + 18) (n + 17) 3 2 9 (1021 n + 12876 n + 53777 n + 74454) b(n + 3) + ------------------------------------------------- (n + 15) (n + 18) (n + 17) 3 2 6 (881 n + 3993 n - 33158 n - 155472) b(n + 4) - ------------------------------------------------ (n + 15) (n + 18) (n + 17) 3 2 36 (127 n + 6419 n + 64841 n + 185473) b(n + 5) - ------------------------------------------------- (n + 15) (n + 18) (n + 17) 3 2 (16303 n + 560382 n + 5471261 n + 16447734) b(n + 6) + ------------------------------------------------------ (n + 15) (n + 18) (n + 17) 3 2 (85597 n + 2716296 n + 26935529 n + 85555458) b(n + 7) - 1/3 -------------------------------------------------------- (n + 15) (n + 18) (n + 17) 3 2 2 (20484 n + 623465 n + 6207901 n + 20320182) b(n + 8) + -------------------------------------------------------- (n + 15) (n + 18) (n + 17) 3 2 (147427 n + 4481088 n + 45224207 n + 151630794) b(n + 9) - 1/3 ---------------------------------------------------------- (n + 15) (n + 18) (n + 17) 3 2 4 (11928 n + 376507 n + 3955674 n + 13831118) b(n + 10) + --------------------------------------------------------- (n + 15) (n + 18) (n + 17) 3 2 (111931 n + 3755328 n + 41945363 n + 155933490) b(n + 11) - 1/3 ----------------------------------------------------------- (n + 15) (n + 18) (n + 17) 3 2 (35105 n + 1261374 n + 15090541 n + 60094632) b(n + 12) + 2/3 --------------------------------------------------------- (n + 15) (n + 18) (n + 17) 3 2 2 (5747 n + 220751 n + 2823348 n + 12020700) b(n + 13) - -------------------------------------------------------- (n + 15) (n + 18) (n + 17) 3 2 (12737 n + 520392 n + 7078813 n + 32053638) b(n + 14) + 1/3 ------------------------------------------------------- (n + 15) (n + 18) (n + 17) 3 2 (3367 n + 145578 n + 2095205 n + 10036146) b(n + 15) - 1/3 ------------------------------------------------------ (n + 15) (n + 18) (n + 17) 3 2 (298 n + 13575 n + 205775 n + 1037790) b(n + 16) + 2/3 -------------------------------------------------- (n + 15) (n + 18) (n + 17) 2 (21 n + 647 n + 4966) b(n + 17) - -------------------------------- + b(n + 18) = 0 (n + 18) (n + 15) Subject to the initial conditions b(1) = 0, b(2) = 0, b(3) = 1, b(4) = 6, b(5) = 26, b(6) = 99, b(7) = 352, b(8) = 1202, b(9) = 3996, b(10) = 13032, b(11) = 41896, b(12) = 133213, b(13) = 419909, b(14) = 1314462, b(15) = 4091556, b(16) = 12676782, b(17) = 39124406, b(18) = 120357528 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.8144 1/2 - ------ 1/2 n The probability of Bob winning the bet, as n grows larger is approximately 0.6516 1/2 - ------ 1/2 n You can see that indeed Bob has a better chance, but not significantly so. ----------------------------------------- This took, 28.498, seconds to generate ----------------------------------------------------------------------------\ ----------------------- Question Mumber, 11, : If Alice bets that there are more occurrences of conse\ cutive substrings in, {[2, 1, 3]}, than in, {[1, 2, 2]}, and Bob, bets vice versa, who is more likely to win? Answer: They are equally likely to win ----------------------------------------------------------------------------\ ----------------------- Question Mumber, 12, : If Alice bets that there are more occurrences of conse\ cutive substrings in, {[1, 1, 3]}, than in, {[1, 2, 2]}, and Bob, bets vice versa, who is more likely to win? Answer: They are equally likely to win The best bet against, [1, 2, 2], is a member of, {[1, 1, 2], [1, 1, 3], [1, 2, 3], [1, 3, 2], [1, 3, 3], [2, 1, 1], [2, 1, 3], [2, 2, 1], [2, 2, 3], [2, 3, 1], [2, 3, 3], [3, 1, 1], [3, 1, 2], [3, 2, 1], [3, 2, 2], [3, 3, 1], [3, 3, 2]}, and then your edge, if you have n rolls, is exactly 0 The next best bet is a member of, {[3, 1, 3], [3, 2, 3]}, 0.1545 and then your edge is approximately, - ------ 1/2 n The next best bet is a member of, {[1, 2, 1], [1, 3, 1], [2, 3, 2]}, 0.1628 and then your edge is approximately, - ------ 1/2 n The next best bet is a member of, {[2, 1, 2]}, 0.1994 and then your edge is approximately, - ------ 1/2 n The next best bet is a member of, {[3, 3, 3]}, 0.5420 and then your edge is approximately, - ------ 1/2 n The next best bet is a member of, {[1, 1, 1]}, 0.5642 and then your edge is approximately, - ------ 1/2 n The next best bet is a member of, {[2, 2, 2]}, 0.6517 and then your edge is approximately, - ------ 1/2 n ----------------------- This ends this chapter that took, 201.430, seconds to generate. ----------------------------------------------------------------- Chapter Number, 5 The Relative Probablity of Winning a Daniel Litt style game when rolling a f\ air, 3, sides die marked with, {1, 2, 3}, of number of occurrences of, [1, 2, 3], Versus the number of occurences of all, 3, letter words in, {1, 2, 3} By Shalosh B. Ekhad ----------------------------------------------------------------------------\ ----------------------- Question Mumber, 1, : If Alice bets that there are more occurrences of consec\ utive substrings in, {[2, 2, 2]}, than in, {[1, 2, 3]}, and Bob, bets vice versa, who is more likely to win? Answer: Bob is more likely to win. Let's be more quantitative. We need the following two lemmas Lemma , 1.1, : Let a(n) be the number of words of length n in the alphabet , {1, 2, 3}, with more occurences of, {[2, 2, 2]}, then , {[1, 2, 3]} a(n) satisfies the following linear recurrence equation with polynomial coef\ ficients of order, 9 6 (n + 1) (n + 2) a(n) 2 (n + 19) (n + 2) a(n + 1) - ---------------------- - --------------------------- (n + 9) (n + 6) (n + 9) (n + 6) 2 (127 n + 771 n + 1142) a(n + 2) + 1/3 -------------------------------- (n + 9) (n + 6) 2 (55 n + 359 n + 510) a(n + 3) (n + 4) (4 n + 9) a(n + 4) + 1/3 ------------------------------ - 8/3 -------------------------- (n + 9) (n + 6) (n + 9) (n + 6) 2 2 (13 n + 71) a(n + 5) (2 n + 22 n + 51) a(n + 6) - ---------------------- - 8/3 --------------------------- n + 9 (n + 9) (n + 6) 2 (31 n + 403 n + 1266) a(n + 7) + 2/3 ------------------------------- (n + 9) (n + 6) 2 (25 n + 351 n + 1190) a(n + 8) - 1/3 ------------------------------- + a(n + 9) = 0 (n + 9) (n + 6) Subject to the initial conditions a(1) = 0, a(2) = 0, a(3) = 1, a(4) = 5, a(5) = 21, a(6) = 79, a(7) = 281, a(8) = 963, a(9) = 3218 Lemma , 1.2, : Let b(n) be the number of words of length n in the alphabet , {1, 2, 3}, with more occurences of, {[1, 2, 3]}, then , {[2, 2, 2]} b(n) satisfies the following linear recurrence equation with polynomial coef\ ficients of order, 27 54 (n + 1) (n + 2) (n + 3) b(n) 144 (n + 4) (n + 3) (n + 2) b(n + 1) ------------------------------- - ------------------------------------ (n + 25) (n + 24) (n + 27) (n + 25) (n + 24) (n + 27) 2 (15 n + 752 n + 9409) b(n + 26) + b(n + 27) - -------------------------------- (n + 27) (n + 25) 2 3 (n + 3) (529 n + 5115 n + 12782) b(n + 2) - -------------------------------------------- (n + 25) (n + 24) (n + 27) 3 2 (836 n + 44211 n + 749998 n + 3992943) b(n + 21) + 2/3 -------------------------------------------------- (n + 25) (n + 24) (n + 27) 3 2 (2953 n + 195576 n + 4319843 n + 31826364) b(n + 22) + 1/3 ------------------------------------------------------ (n + 25) (n + 24) (n + 27) 3 2 (737 n + 47424 n + 1015903 n + 7246992) b(n + 23) - 1/3 --------------------------------------------------- (n + 25) (n + 24) (n + 27) 3 2 (143 n + 10312 n + 247493 n + 1977012) b(n + 24) - -------------------------------------------------- (n + 25) (n + 24) (n + 27) 3 2 (81 n + 5872 n + 141819 n + 1141148) b(n + 25) + ------------------------------------------------ (n + 25) (n + 24) (n + 27) 3 2 3 (243 n + 6910 n + 49609 n + 103686) b(n + 3) - ------------------------------------------------ (n + 25) (n + 24) (n + 27) 3 2 4 (1687 n + 18608 n + 45391 n - 27942) b(n + 4) + ------------------------------------------------- (n + 25) (n + 24) (n + 27) 3 2 4 (3715 n + 67832 n + 385589 n + 672376) b(n + 5) + --------------------------------------------------- (n + 25) (n + 24) (n + 27) 3 2 (14663 n + 450294 n + 3973617 n + 10756362) b(n + 6) + ------------------------------------------------------ (n + 25) (n + 24) (n + 27) 3 2 (6565 n - 78614 n - 2415173 n - 10833962) b(n + 7) - ---------------------------------------------------- (n + 25) (n + 24) (n + 27) 3 2 (69380 n + 1622667 n + 12134728 n + 28595013) b(n + 8) - 2/3 -------------------------------------------------------- (n + 25) (n + 24) (n + 27) 3 2 (162649 n + 5116656 n + 52523375 n + 176618592) b(n + 9) - 1/3 ---------------------------------------------------------- (n + 25) (n + 24) (n + 27) 3 2 (20227 n + 1583478 n + 26610425 n + 128067150) b(n + 10) - 1/3 ---------------------------------------------------------- (n + 25) (n + 24) (n + 27) 3 2 2 (24661 n + 749292 n + 7272083 n + 22049388) b(n + 11) + --------------------------------------------------------- (n + 25) (n + 24) (n + 27) 3 2 (80788 n + 3110073 n + 39322256 n + 163295187) b(n + 12) + 2/3 ---------------------------------------------------------- (n + 25) (n + 24) (n + 27) 3 2 (7229 n + 566492 n + 11154971 n + 65017148) b(n + 13) + ------------------------------------------------------- (n + 25) (n + 24) (n + 27) 3 2 (24837 n + 929088 n + 11134663 n + 41939636) b(n + 14) - -------------------------------------------------------- (n + 25) (n + 24) (n + 27) 3 2 (66767 n + 3345282 n + 54591445 n + 290961618) b(n + 15) - 1/3 ---------------------------------------------------------- (n + 25) (n + 24) (n + 27) 3 2 (3659 n + 321525 n + 7626799 n + 54654681) b(n + 16) - 2/3 ------------------------------------------------------ (n + 25) (n + 24) (n + 27) 3 2 (10105 n + 506118 n + 8337343 n + 45067306) b(n + 17) + ------------------------------------------------------- (n + 25) (n + 24) (n + 27) 3 2 2 (2953 n + 179891 n + 3603315 n + 23784369) b(n + 18) + -------------------------------------------------------- (n + 25) (n + 24) (n + 27) 3 2 (4367 n + 228618 n + 3852001 n + 20557686) b(n + 19) - 1/3 ------------------------------------------------------ (n + 25) (n + 24) (n + 27) 3 2 (3653 n + 220962 n + 4459099 n + 30023958) b(n + 20) - ------------------------------------------------------ = 0 (n + 25) (n + 24) (n + 27) Subject to the initial conditions b(1) = 0, b(2) = 0, b(3) = 1, b(4) = 6, b(5) = 27, b(6) = 105, b(7) = 380, b(8) = 1314, b(9) = 4409, b(10) = 14480, b(11) = 46806, b(12) = 149468, b(13) = 472763, b(14) = 1483925, b(15) = 4628838, b(16) = 14364742, b(17) = 44387488, b(18) = 136664364, b(19) = 419488390, b(20) = 1284247530, b(21) = 3922850548, b(22) = 11959476936, b(23) = 36399183405, b(24) = 110620176566, b(25) = 335753314105, b(26) = 1017929773518, b(27) = 3083084677252 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.8809 1/2 - ------ 1/2 n The probability of Bob winning the bet, as n grows larger is approximately 0.3389 1/2 - ------ 1/2 n You can see that indeed Bob has a better chance, but not significantly so. ----------------------------------------- This took, 39.803, seconds to generate ----------------------------------------------------------------------------\ ----------------------- Question Mumber, 2, : If Alice bets that there are more occurrences of consec\ utive substrings in, {[1, 1, 1]}, than in, {[1, 2, 3]}, and Bob, bets vice versa, who is more likely to win? Answer: Bob is more likely to win. Let's be more quantitative. We need the following two lemmas Lemma , 2.1, : Let a(n) be the number of words of length n in the alphabet , {1, 2, 3}, with more occurences of, {[1, 1, 1]}, then , {[1, 2, 3]} a(n) satisfies the following linear recurrence equation with polynomial coef\ ficients of order, 11 27 (n + 1) (n + 2) a(n) 18 (n + 5) (n + 2) a(n + 1) - ----------------------- - --------------------------- (n + 11) (n + 8) (n + 11) (n + 8) 2 2 3 (19 n + 205 n + 442) a(n + 2) (49 n + 341 n + 504) a(n + 3) + -------------------------------- - ------------------------------ (n + 11) (n + 8) (n + 11) (n + 8) 2 2 2 (15 n + 79 n + 44) a(n + 4) (185 n + 1903 n + 4656) a(n + 5) + ------------------------------ + 1/3 --------------------------------- (n + 11) (n + 8) (n + 11) (n + 8) 2 2 (95 n + 1399 n + 5352) a(n + 6) 2 (25 n + 308 n + 882) a(n + 7) - 1/3 -------------------------------- - -------------------------------- (n + 11) (n + 8) (n + 11) (n + 8) (65 n + 534) (n + 5) a(n + 8) (7 n + 72) (5 n + 39) a(n + 9) + 1/3 ----------------------------- + 1/3 ------------------------------ (n + 11) (n + 8) (n + 11) (n + 8) 2 (11 n + 200 n + 891) a(n + 10) - 2/3 ------------------------------- + a(n + 11) = 0 (n + 11) (n + 8) Subject to the initial conditions a(1) = 0, a(2) = 0, a(3) = 1, a(4) = 5, a(5) = 20, a(6) = 75, a(7) = 265, a(8) = 907, a(9) = 3030, a(10) = 9945, a(11) = 32208 Lemma , 2.2, : Let b(n) be the number of words of length n in the alphabet , {1, 2, 3}, with more occurences of, {[1, 2, 3]}, then , {[1, 1, 1]} b(n) satisfies the following linear recurrence equation with polynomial coef\ ficients of order, 21 1701 (n + 1) (n + 2) (n + 3) b(n) 243 (17 n - 6) (n + 3) (n + 2) b(n + 1) - --------------------------------- + --------------------------------------- (n + 19) (n + 18) (n + 21) (n + 19) (n + 18) (n + 21) 2 27 (n + 3) (23 n + 849 n + 2056) b(n + 2) + ------------------------------------------ (n + 19) (n + 18) (n + 21) 3 2 27 (169 n + 2622 n + 15223 n + 29566) b(n + 3) + ------------------------------------------------ (n + 19) (n + 18) (n + 21) 3 2 3 (4840 n + 102225 n + 640325 n + 1246386) b(n + 4) - ----------------------------------------------------- (n + 19) (n + 18) (n + 21) 3 2 3 (3385 n + 49481 n + 170144 n - 13430) b(n + 5) + -------------------------------------------------- (n + 19) (n + 18) (n + 21) 3 2 3 (3482 n + 154207 n + 1603453 n + 4856894) b(n + 6) + ------------------------------------------------------ (n + 19) (n + 18) (n + 21) 3 2 (59075 n + 1667001 n + 14921170 n + 43094853) b(n + 7) - 2/3 -------------------------------------------------------- (n + 19) (n + 18) (n + 21) 3 2 (48074 n + 1363311 n + 12792103 n + 39801840) b(n + 8) + -------------------------------------------------------- (n + 19) (n + 18) (n + 21) 3 2 (43339 n + 1821123 n + 23081162 n + 92066364) b(n + 9) - 1/3 -------------------------------------------------------- (n + 19) (n + 18) (n + 21) 3 2 (4670 n - 401523 n - 9543323 n - 50468514) b(n + 10) - 1/3 ------------------------------------------------------ (n + 19) (n + 18) (n + 21) 3 2 (17090 n + 588018 n + 6477682 n + 22737687) b(n + 11) - 2/3 ------------------------------------------------------- (n + 19) (n + 18) (n + 21) 3 2 (38125 n + 1064469 n + 8719772 n + 17173824) b(n + 12) + 1/3 -------------------------------------------------------- (n + 19) (n + 18) (n + 21) 3 2 (21473 n + 582618 n + 4189831 n + 3190524) b(n + 13) - 1/3 ------------------------------------------------------ (n + 19) (n + 18) (n + 21) 3 2 (20273 n + 736650 n + 8707345 n + 33158730) b(n + 14) + 1/3 ------------------------------------------------------- (n + 19) (n + 18) (n + 21) 3 2 (14969 n + 617205 n + 8422702 n + 38001030) b(n + 15) - 1/3 ------------------------------------------------------- (n + 19) (n + 18) (n + 21) 3 2 (1855 n + 76245 n + 1022525 n + 4442649) b(n + 16) + 2/3 ---------------------------------------------------- (n + 19) (n + 18) (n + 21) 3 2 (1571 n + 84051 n + 1489312 n + 8745672) b(n + 17) + 1/3 ---------------------------------------------------- (n + 19) (n + 18) (n + 21) 2 2 (n + 17) (224 n + 7929 n + 70035) b(n + 18) - ---------------------------------------------- (n + 19) (n + 18) (n + 21) 3 2 (130 n + 7019 n + 126201 n + 755696) b(n + 19) + ------------------------------------------------ (n + 19) (n + 18) (n + 21) 2 (18 n + 683 n + 6457) b(n + 20) - -------------------------------- + b(n + 21) = 0 (n + 21) (n + 19) Subject to the initial conditions b(1) = 0, b(2) = 0, b(3) = 1, b(4) = 6, b(5) = 26, b(6) = 100, b(7) = 359, b(8) = 1238, b(9) = 4151, b(10) = 13641, b(11) = 44156, b(12) = 141269, b(13) = 447790, b(14) = 1408770, b(15) = 4404804, b(16) = 13701992, b(17) = 42439052, b(18) = 130965283, b(19) = 402889009, b(20) = 1236068210, b(21) = 3783416048 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.9169 1/2 - ------ 1/2 n The probability of Bob winning the bet, as n grows larger is approximately 0.3527 1/2 - ------ 1/2 n You can see that indeed Bob has a better chance, but not significantly so. ----------------------------------------- This took, 33.064, seconds to generate ----------------------------------------------------------------------------\ ----------------------- Question Mumber, 3, : If Alice bets that there are more occurrences of consec\ utive substrings in, {[1, 1, 2]}, than in, {[1, 2, 3]}, and Bob, bets vice versa, who is more likely to win? Answer: They are equally likely to win ----------------------------------------------------------------------------\ ----------------------- Question Mumber, 4, : If Alice bets that there are more occurrences of consec\ utive substrings in, {[2, 1, 2]}, than in, {[1, 2, 3]}, and Bob, bets vice versa, who is more likely to win? Answer: Bob is more likely to win. Let's be more quantitative. We need the following two lemmas Lemma , 4.1, : Let a(n) be the number of words of length n in the alphabet , {1, 2, 3}, with more occurences of, {[2, 1, 2]}, then , {[1, 2, 3]} a(n) satisfies the following linear recurrence equation with polynomial coef\ ficients of order, 11 6 (n + 1) (n + 2) a(n) 2 (n + 2) (2 n - 19) a(n + 1) - ---------------------- + ----------------------------- (n + 11) (n + 8) (n + 11) (n + 8) 2 (313 n + 2331 n + 4130) a(n + 2) + 1/3 --------------------------------- (n + 11) (n + 8) 2 (193 n + 1831 n + 4226) a(n + 3) - --------------------------------- (n + 11) (n + 8) 2 (145 n + 1967 n + 6133) a(n + 4) + 2/3 --------------------------------- (n + 11) (n + 8) 2 (215 n + 1824 n + 3355) a(n + 5) + 2/3 --------------------------------- (n + 11) (n + 8) 2 (478 n + 5455 n + 15051) a(n + 6) - 2/3 ---------------------------------- (n + 11) (n + 8) 2 (460 n + 6009 n + 19055) a(n + 7) + 2/3 ---------------------------------- (n + 11) (n + 8) 2 (268 n + 3933 n + 14063) a(n + 8) - 2/3 ---------------------------------- (n + 11) (n + 8) 2 (95 n + 1544 n + 6129) a(n + 9) + 2/3 -------------------------------- (n + 11) (n + 8) 2 (37 n + 655 n + 2832) a(n + 10) - 1/3 -------------------------------- + a(n + 11) = 0 (n + 11) (n + 8) Subject to the initial conditions a(1) = 0, a(2) = 0, a(3) = 1, a(4) = 5, a(5) = 20, a(6) = 74, a(7) = 262, a(8) = 897, a(9) = 2997, a(10) = 9838, a(11) = 31867 Lemma , 4.2, : Let b(n) be the number of words of length n in the alphabet , {1, 2, 3}, with more occurences of, {[1, 2, 3]}, then , {[2, 1, 2]} b(n) satisfies the following linear recurrence equation with polynomial coef\ ficients of order, 26 2 3 (n + 3) (863 n + 6585 n + 11602) b(n + 2) -------------------------------------------- + b(n + 26) (n + 25) (n + 23) (n + 26) 2 2 (12 n + 559 n + 6500) b(n + 25) - ---------------------------------- (n + 26) (n + 23) 3 2 (40487 n + 641526 n + 3300433 n + 5414370) b(n + 5) + 1/3 ----------------------------------------------------- (n + 25) (n + 23) (n + 26) 3 2 (47623 n + 1281996 n + 11652263 n + 35078502) b(n + 6) + 1/3 -------------------------------------------------------- (n + 25) (n + 23) (n + 26) 3 2 2 (38409 n + 1058281 n + 9897652 n + 31085514) b(n + 7) - --------------------------------------------------------- (n + 25) (n + 23) (n + 26) 3 2 (95991 n + 3111206 n + 33834025 n + 122331090) b(n + 8) + --------------------------------------------------------- (n + 25) (n + 23) (n + 26) 3 2 (379 n - 2352882 n - 52225375 n - 285960150) b(n + 9) + 1/3 ------------------------------------------------------- (n + 25) (n + 23) (n + 26) 3 2 (111365 n + 2941650 n + 22480126 n + 39787728) b(n + 10) - 4/3 ---------------------------------------------------------- (n + 25) (n + 23) (n + 26) 3 2 (345359 n + 11397417 n + 118883746 n + 382910574) b(n + 11) + 2/3 ------------------------------------------------------------- (n + 25) (n + 23) (n + 26) 3 2 4 (50408 n + 2066441 n + 26821574 n + 110446560) b(n + 12) - ------------------------------------------------------------ (n + 25) (n + 23) (n + 26) 3 2 2 (50133 n + 3063451 n + 52794540 n + 277114886) b(n + 13) + ------------------------------------------------------------ (n + 25) (n + 23) (n + 26) 3 2 (34511 n - 2933169 n - 100226894 n - 730425552) b(n + 14) + 2/3 ----------------------------------------------------------- (n + 25) (n + 23) (n + 26) 3 2 (208945 n + 5226852 n + 16182563 n - 226800258) b(n + 15) - 2/3 ----------------------------------------------------------- (n + 25) (n + 23) (n + 26) 3 2 (334354 n + 12911949 n + 155919953 n + 558980190) b(n + 16) + 2/3 ------------------------------------------------------------- (n + 25) (n + 23) (n + 26) 3 2 (738307 n + 33716058 n + 505120349 n + 2470129938) b(n + 17) - 1/3 -------------------------------------------------------------- (n + 25) (n + 23) (n + 26) 3 2 (309590 n + 15642267 n + 261886087 n + 1451248614) b(n + 18) + 2/3 -------------------------------------------------------------- (n + 25) (n + 23) (n + 26) 3 2 (134769 n + 7332304 n + 132599749 n + 796766850) b(n + 19) - ------------------------------------------------------------ (n + 25) (n + 23) (n + 26) 3 2 (103240 n + 5965509 n + 114714473 n + 733978644) b(n + 20) + 2/3 ------------------------------------------------------------ (n + 25) (n + 23) (n + 26) 3 2 (81671 n + 4970460 n + 100720315 n + 679493694) b(n + 21) - 1/3 ----------------------------------------------------------- (n + 25) (n + 23) (n + 26) 3 2 (8147 n + 519242 n + 11021113 n + 77899666) b(n + 22) + ------------------------------------------------------- (n + 25) (n + 23) (n + 26) 3 2 (2662 n + 176919 n + 3916043 n + 28867230) b(n + 23) - 2/3 ------------------------------------------------------ (n + 25) (n + 23) (n + 26) 3 2 (793 n + 54774 n + 1259963 n + 9651702) b(n + 24) + 1/3 --------------------------------------------------- (n + 25) (n + 23) (n + 26) 3 2 3 (215 n + 3028 n + 11171 n + 10314) b(n + 3) - ----------------------------------------------- (n + 25) (n + 23) (n + 26) 3 2 2 (4950 n + 69425 n + 334997 n + 556476) b(n + 4) - --------------------------------------------------- (n + 25) (n + 23) (n + 26) 54 (n + 1) (n + 2) (n + 3) b(n) + ------------------------------- (n + 25) (n + 23) (n + 26) 18 (41 n + 155) (n + 3) (n + 2) b(n + 1) - ---------------------------------------- = 0 (n + 25) (n + 23) (n + 26) Subject to the initial conditions b(1) = 0, b(2) = 0, b(3) = 1, b(4) = 5, b(5) = 21, b(6) = 79, b(7) = 282, b(8) = 970, b(9) = 3252, b(10) = 10699, b(11) = 34703, b(12) = 111319, b(13) = 353924, b(14) = 1117121, b(15) = 3504958, b(16) = 10941581, b(17) = 34011526, b(18) = 105339081, b(19) = 325228983, b(20) = 1001395945, b(21) = 3076023894, b(22) = 9429035948, b(23) = 28849991275, b(24) = 88128475262, b(25) = 268817440700, b(26) = 818911493252 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.9235 1/2 - ------ 1/2 n The probability of Bob winning the bet, as n grows larger is approximately 0.7388 1/2 - ------ 1/2 n You can see that indeed Bob has a better chance, but not significantly so. ----------------------------------------- This took, 39.199, seconds to generate ----------------------------------------------------------------------------\ ----------------------- Question Mumber, 5, : If Alice bets that there are more occurrences of consec\ utive substrings in, {[2, 3, 1]}, than in, {[1, 2, 3]}, and Bob, bets vice versa, who is more likely to win? Answer: They are equally likely to win ----------------------------------------------------------------------------\ ----------------------- Question Mumber, 6, : If Alice bets that there are more occurrences of consec\ utive substrings in, {[3, 1, 1]}, than in, {[1, 2, 3]}, 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, 2, 1]}, than in, {[1, 2, 3]}, and Bob, bets vice versa, who is more likely to win? Answer: Bob is more likely to win. Let's be more quantitative. We need the following two lemmas Lemma , 7.1, : Let a(n) be the number of words of length n in the alphabet , {1, 2, 3}, with more occurences of, {[1, 2, 1]}, then , {[1, 2, 3]} a(n) satisfies the following linear recurrence equation with polynomial coef\ ficients of order, 10 2 54 (n + 3) (n + 1) a(n) 9 (7 n + 35 n + 40) a(n + 1) - ----------------------- + ----------------------------- (n + 10) (n + 7) (n + 10) (n + 7) 2 2 3 (3 n - 65 n - 224) a(n + 2) 2 (5 n + 253 n + 893) a(n + 3) - ------------------------------ - ------------------------------- (n + 10) (n + 7) (n + 10) (n + 7) 2 (17 n - 570 n - 3104) a(n + 4) - 2/3 ------------------------------- (n + 10) (n + 7) 2 (26 n + 883 n + 4164) a(n + 5) - 2/3 ------------------------------- (n + 10) (n + 7) 2 (128 n + 1829 n + 6420) a(n + 6) + 2/3 --------------------------------- (n + 10) (n + 7) 2 2 2 (47 n + 654 n + 2244) a(n + 7) (70 n + 1037 n + 3762) a(n + 8) - --------------------------------- + 2/3 -------------------------------- (n + 10) (n + 7) (n + 10) (n + 7) 2 (11 n + 175 n + 678) a(n + 9) - ------------------------------ + a(n + 10) = 0 (n + 10) (n + 7) Subject to the initial conditions a(1) = 0, a(2) = 0, a(3) = 1, a(4) = 6, a(5) = 25, a(6) = 93, a(7) = 327, a(8) = 1110, a(9) = 3678, a(10) = 11973 Lemma , 7.2, : Let b(n) be the number of words of length n in the alphabet , {1, 2, 3}, with more occurences of, {[1, 2, 3]}, then , {[1, 2, 1]} b(n) satisfies the following linear recurrence equation with polynomial coef\ ficients of order, 18 972 (n + 1) (n + 2) (n + 3) b(n) 648 (5 n + 17) (n + 3) (n + 2) b(n + 1) - -------------------------------- + --------------------------------------- (n + 15) (n + 18) (n + 17) (n + 15) (n + 18) (n + 17) 2 81 (n + 3) (83 n + 669 n + 1350) b(n + 2) - ------------------------------------------ (n + 15) (n + 18) (n + 17) 3 2 9 (1021 n + 12876 n + 53777 n + 74454) b(n + 3) + ------------------------------------------------- (n + 15) (n + 18) (n + 17) 3 2 6 (881 n + 3993 n - 33158 n - 155472) b(n + 4) - ------------------------------------------------ (n + 15) (n + 18) (n + 17) 3 2 36 (127 n + 6419 n + 64841 n + 185473) b(n + 5) - ------------------------------------------------- (n + 15) (n + 18) (n + 17) 3 2 (16303 n + 560382 n + 5471261 n + 16447734) b(n + 6) + ------------------------------------------------------ (n + 15) (n + 18) (n + 17) 3 2 (85597 n + 2716296 n + 26935529 n + 85555458) b(n + 7) - 1/3 -------------------------------------------------------- (n + 15) (n + 18) (n + 17) 3 2 2 (20484 n + 623465 n + 6207901 n + 20320182) b(n + 8) + -------------------------------------------------------- (n + 15) (n + 18) (n + 17) 3 2 (147427 n + 4481088 n + 45224207 n + 151630794) b(n + 9) - 1/3 ---------------------------------------------------------- (n + 15) (n + 18) (n + 17) 3 2 4 (11928 n + 376507 n + 3955674 n + 13831118) b(n + 10) + --------------------------------------------------------- (n + 15) (n + 18) (n + 17) 3 2 (111931 n + 3755328 n + 41945363 n + 155933490) b(n + 11) - 1/3 ----------------------------------------------------------- (n + 15) (n + 18) (n + 17) 3 2 (35105 n + 1261374 n + 15090541 n + 60094632) b(n + 12) + 2/3 --------------------------------------------------------- (n + 15) (n + 18) (n + 17) 3 2 2 (5747 n + 220751 n + 2823348 n + 12020700) b(n + 13) - -------------------------------------------------------- (n + 15) (n + 18) (n + 17) 3 2 (12737 n + 520392 n + 7078813 n + 32053638) b(n + 14) + 1/3 ------------------------------------------------------- (n + 15) (n + 18) (n + 17) 3 2 (3367 n + 145578 n + 2095205 n + 10036146) b(n + 15) - 1/3 ------------------------------------------------------ (n + 15) (n + 18) (n + 17) 3 2 (298 n + 13575 n + 205775 n + 1037790) b(n + 16) + 2/3 -------------------------------------------------- (n + 15) (n + 18) (n + 17) 2 (21 n + 647 n + 4966) b(n + 17) - -------------------------------- + b(n + 18) = 0 (n + 18) (n + 15) Subject to the initial conditions b(1) = 0, b(2) = 0, b(3) = 1, b(4) = 6, b(5) = 26, b(6) = 99, b(7) = 352, b(8) = 1202, b(9) = 3996, b(10) = 13032, b(11) = 41896, b(12) = 133213, b(13) = 419909, b(14) = 1314462, b(15) = 4091556, b(16) = 12676782, b(17) = 39124406, b(18) = 120357528 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.8144 1/2 - ------ 1/2 n The probability of Bob winning the bet, as n grows larger is approximately 0.6516 1/2 - ------ 1/2 n You can see that indeed Bob has a better chance, but not significantly so. ----------------------------------------- This took, 28.752, seconds to generate ----------------------------------------------------------------------------\ ----------------------- Question Mumber, 8, : If Alice bets that there are more occurrences of consec\ utive substrings in, {[2, 1, 1]}, than in, {[1, 2, 3]}, and Bob, bets vice versa, who is more likely to win? Answer: They are equally likely to win ----------------------------------------------------------------------------\ ----------------------- Question Mumber, 9, : If Alice bets that there are more occurrences of consec\ utive substrings in, {[1, 1, 3]}, than in, {[1, 2, 3]}, and Bob, bets vice versa, who is more likely to win? Answer: They are equally likely to win The best bet against, [1, 2, 3], is a member of, {[1, 1, 2], [1, 1, 3], [1, 2, 2], [1, 3, 2], [1, 3, 3], [2, 1, 1], [2, 1, 3], [2, 2, 1], [2, 2, 3], [2, 3, 1], [2, 3, 3], [3, 1, 1], [3, 1, 2], [3, 2, 1], [3, 2, 2], [3, 3, 1], [3, 3, 2]}, and then your edge, if you have n rolls, is exactly 0 The next best bet is a member of, {[1, 2, 1], [1, 3, 1], [3, 1, 3], [3, 2, 3]}, 0.1628 and then your edge is approximately, - ------ 1/2 n The next best bet is a member of, {[2, 1, 2], [2, 3, 2]}, 0.1847 and then your edge is approximately, - ------ 1/2 n The next best bet is a member of, {[2, 2, 2]}, 0.5420 and then your edge is approximately, - ------ 1/2 n The next best bet is a member of, {[1, 1, 1], [3, 3, 3]}, 0.5642 and then your edge is approximately, - ------ 1/2 n ----------------------- This ends this chapter that took, 141.490, seconds to generate. -------------------------------------------------------- This ends this book that took, 945.720, seconds to generate.