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, 34.318, 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, 29.870, 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 2 2 (n + 3) (9968 n + 60609 n + 67768) a(n + 2) ---------------------------------------------- (n + 25) (n + 24) (n + 27) 12 (n + 3) (n + 2) (1327 n + 5881) a(n + 1) + ------------------------------------------- (n + 25) (n + 24) (n + 27) 1872 (n + 1) (n + 2) (n + 3) a(n) + --------------------------------- (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 -------------------------------------------------------- (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) + ------------------------------------------------ + 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 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 (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 ------------------------------------------------------ (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) 2 (13 n + 561 n + 6040) b(n + 23) - -------------------------------- + b(n + 24) = 0 (n + 24) (n + 21) 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.574, 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 (15 n + 752 n + 9409) a(n + 26) - -------------------------------- (n + 27) (n + 25) 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) 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 3 (n + 3) (529 n + 5115 n + 12782) a(n + 2) - -------------------------------------------- (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) + ------------------------------------------------------ (n + 25) (n + 24) (n + 27) 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) + --------------------------------------------------------- + a(n + 27) = (n + 25) (n + 24) (n + 27) 0 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, 37.411, 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.777, 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, 186.471, seconds to generate.