The Relative Probablity of Winning a Daniel Litt style game when rolling a f\ air, 5, sides die marked with, {1, 2, 3, 4, 5}, of number of occurrences of, [1, 1, 1], Versus the number of occurences of all, 3, letter words in, {1, 2, 3, 4, 5} By Shalosh B. Ekhad ----------------------------------------------------------------------------\ ----------------------- Question Mumber, 1, : If Alice bets that there are more occurrences of consec\ utive substrings in, {[1, 2, 1]}, than in, {[1, 1, 1]}, and Bob, bets vice versa, who is more likely to win? Answer: Alice is more likely to win. Let's be more quantitative. We need the following two lemmas Lemma , 1.1, : Let a(n) be the number of words of length n in the alphabet , {1, 2, 3, 4, 5}, 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 (2 n + 3) (n + 2) (n + 1) a(n) -320000/3 ------------------------------ (n + 20) (n + 19) (n + 22) 2 (n + 2) (221 n + 1487 n + 2316) a(n + 1) + 56000/3 ----------------------------------------- (n + 20) (n + 19) (n + 22) 3 2 (3748 n - 17727 n - 294367 n - 624642) a(n + 2) + 800/3 ------------------------------------------------- (n + 20) (n + 19) (n + 22) 3 2 (44689 n - 35631 n - 1792366 n - 3791256) a(n + 3) + 100/3 ---------------------------------------------------- (n + 20) (n + 19) (n + 22) 3 2 (173711 n + 7234143 n + 62808862 n + 156339240) a(n + 4) + 20/3 ---------------------------------------------------------- (n + 20) (n + 19) (n + 22) 3 2 (996223 n + 24484524 n + 206399291 n + 571044450) a(n + 5) - 8/3 ------------------------------------------------------------ (n + 20) (n + 19) (n + 22) 3 2 (3781715 n + 1059351 n - 504490082 n - 2312792928) a(n + 6) + 1/3 ------------------------------------------------------------- (n + 20) (n + 19) (n + 22) 3 2 (5541601 n + 382572477 n + 5421090602 n + 21741328944) a(n + 7) + 1/3 ----------------------------------------------------------------- (n + 20) (n + 19) (n + 22) 3 2 (14807071 n + 465992115 n + 4867755500 n + 16876345992) a(n + 8) + 2/3 ------------------------------------------------------------------ (n + 20) (n + 19) (n + 22) 3 2 (9295161 n + 286811601 n + 2836760870 n + 8981801528) a(n + 9) + ---------------------------------------------------------------- (n + 20) (n + 19) (n + 22) 3 2 (587243 n + 21897564 n + 264184705 n + 1047078240) a(n + 10) - 8/3 -------------------------------------------------------------- (n + 20) (n + 19) (n + 22) 3 2 (6740119 n + 284398359 n + 3815823086 n + 16482831816) a(n + 11) - 1/3 ------------------------------------------------------------------ (n + 20) (n + 19) (n + 22) 3 2 (456575 n + 6009627 n - 40821626 n - 558128820) a(n + 12) - 2/3 ----------------------------------------------------------- (n + 20) (n + 19) (n + 22) 3 2 (596045 n + 15545937 n + 82210198 n - 250259184) a(n + 13) - 1/3 ------------------------------------------------------------ (n + 20) (n + 19) (n + 22) 3 2 (649181 n + 23411289 n + 274341364 n + 1035832236) a(n + 14) + 2/3 -------------------------------------------------------------- (n + 20) (n + 19) (n + 22) 3 2 (147397 n + 4968489 n + 53964482 n + 191060640) a(n + 15) - 1/3 ----------------------------------------------------------- (n + 20) (n + 19) (n + 22) 3 2 (61207 n + 2670795 n + 37891952 n + 173182464) a(n + 16) - 2/3 ---------------------------------------------------------- (n + 20) (n + 19) (n + 22) 3 2 (5177 n - 35943 n - 5662346 n - 60386424) a(n + 17) + 1/3 ----------------------------------------------------- (n + 20) (n + 19) (n + 22) 3 2 (2681 n + 147456 n + 2697004 n + 16406010) a(n + 18) + 8/3 ------------------------------------------------------ (n + 20) (n + 19) (n + 22) 3 2 (7721 n + 426465 n + 7846402 n + 48089832) a(n + 19) - 1/3 ------------------------------------------------------ (n + 20) (n + 19) (n + 22) 3 2 2 (203 n + 11551 n + 218890 n + 1381500) a(n + 20) + ---------------------------------------------------- (n + 20) (n + 19) (n + 22) 2 (19 n + 758 n + 7536) a(n + 21) - 5/3 -------------------------------- + a(n + 22) = 0 (n + 22) (n + 20) Subject to the initial conditions a(1) = 0, a(2) = 0, a(3) = 1, a(4) = 10, a(5) = 72, a(6) = 469, a(7) = 2885, a(8) = 17065, a(9) = 98256, a(10) = 554699, a(11) = 3084409, a(12) = 16946233, a(13) = 92203884, a(14) = 497657504, a(15) = 2667925277, a(16) = 14220426572, a(17) = 75421020644, a(18) = 398282902575, a(19) = 2095263996905, a(20) = 10985583550381, a(21) = 57425361437804, a(22) = 299374766650126 Lemma , 1.2, : Let b(n) be the number of words of length n in the alphabet , {1, 2, 3, 4, 5}, 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 n + 3) (n + 2) (n + 1) b(n) 320000/3 ------------------------------ (n + 15) (n + 14) (n + 12) 2 (n + 2) (53 n + 311 n + 348) b(n + 1) + 8000/3 -------------------------------------- (n + 15) (n + 14) (n + 12) 3 2 (3092 n + 39447 n + 160207 n + 208962) b(n + 2) + 800/3 ------------------------------------------------- (n + 15) (n + 14) (n + 12) 3 2 (34007 n + 546135 n + 2849662 n + 4835160) b(n + 3) + 100/3 ----------------------------------------------------- (n + 15) (n + 14) (n + 12) 3 2 (4355 n + 60123 n + 254446 n + 313176) b(n + 4) - 100/3 ------------------------------------------------- (n + 15) (n + 14) (n + 12) 3 2 (69103 n + 1690221 n + 13285472 n + 33789444) b(n + 5) - 20/3 -------------------------------------------------------- (n + 15) (n + 14) (n + 12) 3 2 (149497 n + 6508629 n + 67214378 n + 202512096) b(n + 6) + 1/3 ---------------------------------------------------------- (n + 15) (n + 14) (n + 12) 3 2 (42799 n + 2616099 n + 37800230 n + 156186096) b(n + 7) + 1/3 --------------------------------------------------------- (n + 15) (n + 14) (n + 12) 3 2 (3805 n + 598929 n + 9839804 n + 42777216) b(n + 8) - 4/3 ----------------------------------------------------- (n + 15) (n + 14) (n + 12) 3 2 4 (11683 n + 391041 n + 4237298 n + 14974768) b(n + 9) + -------------------------------------------------------- (n + 15) (n + 14) (n + 12) 3 2 2 (20817 n + 650927 n + 6743776 n + 23140140) b(n + 10) - --------------------------------------------------------- (n + 15) (n + 14) (n + 12) 3 2 (24721 n + 804087 n + 8685824 n + 31138548) b(n + 11) + 2/3 ------------------------------------------------------- (n + 15) (n + 14) (n + 12) 3 2 8 (454 n + 15649 n + 179260 n + 682056) b(n + 12) - --------------------------------------------------- (n + 15) (n + 14) (n + 12) 3 2 (175 n + 6408 n + 77978 n + 315222) b(n + 13) + 8/3 ----------------------------------------------- (n + 15) (n + 14) (n + 12) 2 3 (11 n + 273 n + 1684) 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) = 9, b(5) = 63, b(6) = 407, b(7) = 2488, b(8) = 14652, b(9) = 84123, b(10) = 473967, b(11) = 2631694, b(12) = 14443906, b(13) = 78530262, b(14) = 423633738, b(15) = 2270281933 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.15 1/2 - ---- 1/2 n The probability of Bob winning the bet, as n grows larger is approximately 1.73 1/2 - ---- 1/2 n You can see that indeed Alice has a better chance, but not significantly so. ----------------------------------------- This took, 45.413, seconds to generate ----------------------------------------------------------------------------\ ----------------------- Question Mumber, 2, : If Alice bets that there are more occurrences of consec\ utive substrings in, {[2, 2, 2]}, than in, {[1, 1, 1]}, and Bob, bets vice versa, who is more likely to win? Answer: They are equally likely to win ----------------------------------------------------------------------------\ ----------------------- Question Mumber, 3, : If Alice bets that there are more occurrences of consec\ utive substrings in, {[1, 1, 2]}, than in, {[1, 1, 1]}, and Bob, bets vice versa, who is more likely to win? Answer: Alice is more likely to win. Let's be more quantitative. We need the following two lemmas Lemma , 3.1, : Let a(n) be the number of words of length n in the alphabet , {1, 2, 3, 4, 5}, 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 (n + 1) (n + 2) (n + 3) a(n) 1000000/3 ---------------------------- (n + 19) (n + 18) (n + 21) 200000 (7 n + 20) (n + 3) (n + 2) a(n + 1) + ------------------------------------------ (n + 19) (n + 18) (n + 21) (7 n + 26) (n + 3) (107 n + 311) a(n + 2) + 10000/3 ----------------------------------------- (n + 19) (n + 18) (n + 21) 3 2 (2734 n + 21987 n + 36551 n - 30162) a(n + 3) + 2000/3 ----------------------------------------------- (n + 19) (n + 18) (n + 21) 3 2 (28009 n + 939858 n + 7443923 n + 17183490) a(n + 4) - 100/3 ------------------------------------------------------ (n + 19) (n + 18) (n + 21) 3 2 (14603 n + 299673 n + 1963666 n + 4124976) a(n + 5) - 500/3 ----------------------------------------------------- (n + 19) (n + 18) (n + 21) 3 2 (87053 n - 374274 n - 19208633 n - 86847450) a(n + 6) - 25/3 ------------------------------------------------------- (n + 19) (n + 18) (n + 21) 3 2 (1057616 n + 39501609 n + 430168861 n + 1454329854) a(n + 7) + 5/3 -------------------------------------------------------------- (n + 19) (n + 18) (n + 21) 3 2 (356192 n + 10351353 n + 99243547 n + 313698312) a(n + 8) + 25/3 ----------------------------------------------------------- (n + 19) (n + 18) (n + 21) 3 2 (2114283 n + 55478316 n + 474634421 n + 1308261800) a(n + 9) + -------------------------------------------------------------- (n + 19) (n + 18) (n + 21) 3 2 (14854 n + 826170 n + 12813092 n + 60613155) a(n + 10) - 20/3 -------------------------------------------------------- (n + 19) (n + 18) (n + 21) 3 2 (743644 n + 23869824 n + 254856575 n + 904650525) a(n + 11) - 4/3 ------------------------------------------------------------- (n + 19) (n + 18) (n + 21) 3 2 (372754 n + 14261601 n + 179509274 n + 743728311) a(n + 12) - 2/3 ------------------------------------------------------------- (n + 19) (n + 18) (n + 21) 3 2 2 (102112 n + 3900358 n + 49681324 n + 211074069) a(n + 13) + ------------------------------------------------------------- (n + 19) (n + 18) (n + 21) 3 2 (152930 n + 6467976 n + 90904480 n + 424598409) a(n + 14) + 2/3 ----------------------------------------------------------- (n + 19) (n + 18) (n + 21) 3 2 (84686 n + 3674217 n + 53173960 n + 256812705) a(n + 15) - 2/3 ---------------------------------------------------------- (n + 19) (n + 18) (n + 21) 3 2 4 (2267 n + 111651 n + 1817418 n + 9780104) a(n + 16) - ------------------------------------------------------- (n + 19) (n + 18) (n + 21) 3 2 4 (2845 n + 140375 n + 2305278 n + 12600296) a(n + 17) + -------------------------------------------------------- (n + 19) (n + 18) (n + 21) 3 2 (9743 n + 500472 n + 8559937 n + 48752904) a(n + 18) - 1/3 ------------------------------------------------------ (n + 19) (n + 18) (n + 21) 3 2 (1376 n + 73683 n + 1313587 n + 7797264) a(n + 19) + 1/3 ---------------------------------------------------- (n + 19) (n + 18) (n + 21) 2 (100 n + 3777 n + 35525) 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) = 9, a(5) = 65, a(6) = 423, a(7) = 2597, a(8) = 15353, a(9) = 88400, a(10) = 499171, a(11) = 2776781, a(12) = 15264349, a(13) = 83105281, a(14) = 448861685, a(15) = 2408126850, a(16) = 12845701436, a(17) = 68185017614, a(18) = 360369883829, a(19) = 1897415858917, a(20) = 9956777012089, a(21) = 52092452597812 Lemma , 3.2, : Let b(n) be the number of words of length n in the alphabet , {1, 2, 3, 4, 5}, with more occurences of, {[1, 1, 1]}, then , {[1, 1, 2]} b(n) satisfies the following linear recurrence equation with polynomial coef\ ficients of order, 10 2 (n + 3) (n + 1) b(n) (13 n + 55 n + 60) b(n + 1) -1250/3 -------------------- - 125/3 ---------------------------- (n + 10) (n + 7) (n + 10) (n + 7) 2 (2 n - 115 n - 369) b(n + 2) - 50/3 ----------------------------- (n + 10) (n + 7) 2 (20 n + 383 n + 1287) b(n + 3) + 20/3 ------------------------------- (n + 10) (n + 7) 2 (689 n + 6701 n + 17430) b(n + 4) + 1/3 ---------------------------------- (n + 10) (n + 7) 2 (92 n + 702 n + 903) b(n + 5) + 10/3 ------------------------------ (n + 10) (n + 7) 2 (167 n + 2025 n + 6513) b(n + 6) - 2/3 --------------------------------- (n + 10) (n + 7) 2 (451 n + 5813 n + 17742) b(n + 7) - 1/3 ---------------------------------- (n + 10) (n + 7) 2 2 (26 n + 379 n + 1341) b(n + 8) 2 (8 n + 127 n + 490) b(n + 9) + 10/3 ------------------------------- - ------------------------------- (n + 10) (n + 7) (n + 10) (n + 7) + b(n + 10) = 0 Subject to the initial conditions b(1) = 0, b(2) = 0, b(3) = 1, b(4) = 8, b(5) = 56, b(6) = 359, b(7) = 2183, b(8) = 12824, b(9) = 73513, b(10) = 413784 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.20 1/2 - ---- 1/2 n The probability of Bob winning the bet, as n grows larger is approximately 1.96 1/2 - ---- 1/2 n You can see that indeed Alice has a better chance, but not significantly so. ----------------------------------------- This took, 28.556, seconds to generate ----------------------------------------------------------------------------\ ----------------------- Question Mumber, 4, : If Alice bets that there are more occurrences of consec\ utive substrings in, {[2, 1, 2]}, than in, {[1, 1, 1]}, and Bob, bets vice versa, who is more likely to win? Answer: Alice is more likely to win. Let's be more quantitative. We need the following two lemmas Lemma , 4.1, : Let a(n) be the number of words of length n in the alphabet , {1, 2, 3, 4, 5}, with more occurences of, {[2, 1, 2]}, then , {[1, 1, 1]} a(n) satisfies the following linear recurrence equation with polynomial coef\ ficients of order, 27 3 2 (19087489 n + 934738240 n + 13914378903 n + 65323690812) a(n + 11) -------------------------------------------------------------------- (n + 25) (n + 24) (n + 27) 3 2 2 (23067647 n + 825627932 n + 9890266371 n + 39664514310) a(n + 12) + --------------------------------------------------------------------- (n + 25) (n + 24) (n + 27) 3 2 (4597981 n + 39568326 n - 1214537659 n - 12214271514) a(n + 13) - 2/3 ----------------------------------------------------------------- (n + 25) (n + 24) (n + 27) 3 2 (6406654 n + 236073009 n + 2840898404 n + 11088588183) a(n + 14) + 4/3 ------------------------------------------------------------------ (n + 25) (n + 24) (n + 27) 3 2 (14261809 n + 597815862 n + 8331358445 n + 38636260650) a(n + 15) - 2/3 ------------------------------------------------------------------- (n + 25) (n + 24) (n + 27) 3 2 (1601524 n + 61703772 n + 755651783 n + 2866178625) a(n + 16) + 4/3 --------------------------------------------------------------- (n + 25) (n + 24) (n + 27) 3 2 2 (938677 n + 44029896 n + 684376019 n + 3522973490) a(n + 17) - ---------------------------------------------------------------- (n + 25) (n + 24) (n + 27) 3 2 (1703531 n + 85090719 n + 1409425492 n + 7738908582) a(n + 18) + 2/3 ---------------------------------------------------------------- (n + 25) (n + 24) (n + 27) 3 2 (729805 n + 35461134 n + 561644489 n + 2879486232) a(n + 19) - 1/3 -------------------------------------------------------------- (n + 25) (n + 24) (n + 27) 3 2 (248467 n + 13114818 n + 227971259 n + 1302439740) a(n + 20) + 1/3 -------------------------------------------------------------- (n + 25) (n + 24) (n + 27) 3 2 (50717 n + 2855229 n + 53062048 n + 325029486) a(n + 21) - 2/3 ---------------------------------------------------------- (n + 25) (n + 24) (n + 27) 3 2 (9137 n + 695337 n + 17223466 n + 139624260) a(n + 22) - 2/3 -------------------------------------------------------- (n + 25) (n + 24) (n + 27) 3 2 2 (4303 n + 295877 n + 6775024 n + 51661610) a(n + 23) + -------------------------------------------------------- (n + 25) (n + 24) (n + 27) 3 2 (4043 n + 282963 n + 6598294 n + 51264750) a(n + 24) - 2/3 ------------------------------------------------------ (n + 25) (n + 24) (n + 27) 3 2 10 (41 n + 2946 n + 70519 n + 562370) a(n + 25) + ------------------------------------------------- (n + 25) (n + 24) (n + 27) 3 2 27 (3455359 n + 43191306 n + 179830259 n + 249151116) a(n + 3) + ---------------------------------------------------------------- (n + 25) (n + 24) (n + 27) 3 2 27 (3321323 n + 37659926 n + 120677531 n + 77634480) a(n + 4) + --------------------------------------------------------------- (n + 25) (n + 24) (n + 27) 3 2 18 (3801186 n + 44866625 n + 124058699 n - 45761460) a(n + 5) + --------------------------------------------------------------- (n + 25) (n + 24) (n + 27) 3 2 18 (160939 n - 30220595 n - 440373998 n - 1537908374) a(n + 6) + ---------------------------------------------------------------- (n + 25) (n + 24) (n + 27) 3 2 6 (8958704 n + 219596145 n + 1774568479 n + 4688767380) a(n + 7) - ------------------------------------------------------------------ (n + 25) (n + 24) (n + 27) 3 2 6 (7001633 n + 182630141 n + 1534617996 n + 4100567820) a(n + 8) - ------------------------------------------------------------------ (n + 25) (n + 24) (n + 27) 3 2 12 (3089771 n + 48897891 n + 66343427 n - 1142895914) a(n + 9) - ---------------------------------------------------------------- (n + 25) (n + 24) (n + 27) 3 2 3 (13784321 n + 475338736 n + 5554502707 n + 21880827500) a(n + 10) + --------------------------------------------------------------------- (n + 25) (n + 24) (n + 27) 2 810 (n + 3) (60820 n + 459709 n + 825048) a(n + 2) + --------------------------------------------------- (n + 25) (n + 24) (n + 27) 2 (19 n + 948 n + 11801) a(n + 26) - 5/3 --------------------------------- + a(n + 27) (n + 27) (n + 25) 3402000 (n + 1) (n + 2) (n + 3) a(n) + ------------------------------------ (n + 25) (n + 24) (n + 27) 72900 (331 n + 1389) (n + 3) (n + 2) a(n + 1) + --------------------------------------------- = 0 (n + 25) (n + 24) (n + 27) Subject to the initial conditions a(1) = 0, a(2) = 0, a(3) = 1, a(4) = 10, a(5) = 74, a(6) = 487, a(7) = 3008, a(8) = 17846, a(9) = 102966, a(10) = 582075, a(11) = 3239595, a(12) = 17809832, a(13) = 96941077, a(14) = 523346965, a(15) = 2805944601, a(16) = 14956230035, a(17) = 79318167694, a(18) = 418809040425, a(19) = 2202854049199, a(20) = 11547158909331, a(21) = 60345706504513, a(22) = 314511523033250, a(23) = 1635169451215824, a(24) = 8482536049051237, a(25) = 43914981389962672, a(26) = 226934161859159858, a(27) = 1170722744516596946 Lemma , 4.2, : Let b(n) be the number of words of length n in the alphabet , {1, 2, 3, 4, 5}, 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 3 2 27 (1050961 n + 16347674 n + 83052161 n + 137895364) b(n + 3) --------------------------------------------------------------- (n + 24) (n + 23) (n + 21) 3 2 9 (6372181 n + 116962902 n + 705099077 n + 1397884260) b(n + 4) + ----------------------------------------------------------------- (n + 24) (n + 23) (n + 21) 3 2 18 (4791094 n + 99627875 n + 682441501 n + 1542700080) b(n + 5) + ----------------------------------------------------------------- (n + 24) (n + 23) (n + 21) 3 2 72 (1317518 n + 31080254 n + 241553921 n + 619624820) b(n + 6) + ---------------------------------------------------------------- (n + 24) (n + 23) (n + 21) 3 2 15 (5122553 n + 134442300 n + 1162653475 n + 3317830704) b(n + 7) + ------------------------------------------------------------------- (n + 24) (n + 23) (n + 21) 3 2 3 (14836351 n + 440737264 n + 4290171921 n + 13717332384) b(n + 8) + -------------------------------------------------------------------- (n + 24) (n + 23) (n + 21) 3 2 12 (1058300 n + 36781233 n + 410945391 n + 1486952396) b(n + 9) + ----------------------------------------------------------------- (n + 24) (n + 23) (n + 21) 3 2 8 (121385 n + 83571 n - 36637391 n - 248433990) b(n + 10) - ----------------------------------------------------------- (n + 24) (n + 23) (n + 21) 3 2 2 (2919629 n + 100597276 n + 1155447611 n + 4433210784) b(n + 11) - ------------------------------------------------------------------- (n + 24) (n + 23) (n + 21) 3 2 2 (775931 n + 32286036 n + 439217589 n + 1962381032) b(n + 12) - ---------------------------------------------------------------- (n + 24) (n + 23) (n + 21) 3 2 (344366 n + 15187233 n + 220848304 n + 1060324782) b(n + 13) - 8/3 -------------------------------------------------------------- (n + 24) (n + 23) (n + 21) 3 2 (563686 n + 23060661 n + 314097527 n + 1425553656) b(n + 14) + 4/3 -------------------------------------------------------------- (n + 24) (n + 23) (n + 21) 3 2 2 (49965 n + 1920582 n + 24280013 n + 100842020) b(n + 15) - ------------------------------------------------------------ (n + 24) (n + 23) (n + 21) 3 2 2 (83081 n + 4077494 n + 66629533 n + 362409740) b(n + 16) + ------------------------------------------------------------ (n + 24) (n + 23) (n + 21) 3 2 (75851 n + 3835029 n + 64517470 n + 361084362) b(n + 17) - 4/3 ---------------------------------------------------------- (n + 24) (n + 23) (n + 21) 3 2 (46532 n + 2458131 n + 43181833 n + 252133584) b(n + 18) + 2/3 ---------------------------------------------------------- (n + 24) (n + 23) (n + 21) 3 2 (46387 n + 2639634 n + 49953263 n + 314280036) b(n + 19) - 1/3 ---------------------------------------------------------- (n + 24) (n + 23) (n + 21) 3 2 (7737 n + 460546 n + 9123709 n + 60144620) b(n + 20) + ------------------------------------------------------ (n + 24) (n + 23) (n + 21) 3 2 (3322 n + 204909 n + 4208639 n + 28780392) b(n + 21) - 2/3 ------------------------------------------------------ (n + 24) (n + 23) (n + 21) 3 2 (262 n + 16719 n + 355283 n + 2513976) b(n + 22) + 4/3 -------------------------------------------------- (n + 24) (n + 23) (n + 21) 2 (29 n + 1245 n + 13336) b(n + 23) - ---------------------------------- (n + 24) (n + 21) 2 270 (n + 3) (32200 n + 322053 n + 771176) b(n + 2) + --------------------------------------------------- + b(n + 24) (n + 24) (n + 23) (n + 21) 162000 (n + 1) (n + 2) (n + 3) b(n) - ----------------------------------- (n + 24) (n + 23) (n + 21) 8100 (221 n + 1219) (n + 3) (n + 2) b(n + 1) + -------------------------------------------- = 0 (n + 24) (n + 23) (n + 21) Subject to the initial conditions b(1) = 0, b(2) = 0, b(3) = 1, b(4) = 9, b(5) = 65, b(6) = 423, b(7) = 2595, b(8) = 15329, b(9) = 88184, b(10) = 497490, b(11) = 2764801, b(12) = 15183849, b(13) = 82586836, b(14) = 445628254, b(15) = 2388461851, b(16) = 12728503491, b(17) = 67498107927, b(18) = 356399712301, b(19) = 1874740222233, b(20) = 9828582371767, b(21) = 51374130776855, b(22) = 267815443182545, b(23) = 1392767269103835, b(24) = 7227227747143661 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.12 1/2 - ---- 1/2 n The probability of Bob winning the bet, as n grows larger is approximately 1.67 1/2 - ---- 1/2 n You can see that indeed Alice has a better chance, but not significantly so. ----------------------------------------- This took, 56.377, seconds to generate ----------------------------------------------------------------------------\ ----------------------- Question Mumber, 5, : If Alice bets that there are more occurrences of consec\ utive substrings in, {[1, 2, 2]}, than in, {[1, 1, 1]}, and Bob, bets vice versa, who is more likely to win? Answer: Alice is more likely to win. Let's be more quantitative. We need the following two lemmas Lemma , 5.1, : Let a(n) be the number of words of length n in the alphabet , {1, 2, 3, 4, 5}, 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 (n + 1) (n + 2) (n + 3) a(n) -390625/3 ---------------------------- (n + 19) (n + 18) (n + 21) (371 n - 370) (n + 3) (n + 2) a(n + 1) + 3125/3 -------------------------------------- (n + 19) (n + 18) (n + 21) 2 (n + 3) (4333 n + 28707 n + 42800) a(n + 2) + 625/3 -------------------------------------------- (n + 19) (n + 18) (n + 21) 3 2 125 (9547 n + 98378 n + 381821 n + 564530) a(n + 3) + ----------------------------------------------------- (n + 19) (n + 18) (n + 21) 3 2 125 (494 n - 64515 n - 573777 n - 1176698) a(n + 4) + ----------------------------------------------------- (n + 19) (n + 18) (n + 21) 3 2 (172031 n + 4252785 n + 32006866 n + 75439770) a(n + 5) - 25/3 --------------------------------------------------------- (n + 19) (n + 18) (n + 21) 3 2 (194068 n + 2630571 n + 10283555 n + 9124962) a(n + 6) - 25/3 -------------------------------------------------------- (n + 19) (n + 18) (n + 21) 3 2 (155807 n + 3238494 n + 22176055 n + 50190045) a(n + 7) - 50/3 --------------------------------------------------------- (n + 19) (n + 18) (n + 21) 3 2 5 (295916 n + 9026055 n + 90622441 n + 299153340) a(n + 8) + ------------------------------------------------------------ (n + 19) (n + 18) (n + 21) 3 2 (750779 n + 16894797 n + 118967188 n + 248942880) a(n + 9) + 5/3 ------------------------------------------------------------ (n + 19) (n + 18) (n + 21) 3 2 (3462388 n + 110402445 n + 1156461563 n + 3979884990) a(n + 10) + 1/3 ----------------------------------------------------------------- (n + 19) (n + 18) (n + 21) 3 2 (1205882 n + 35761530 n + 344898304 n + 1071318771) a(n + 11) - 2/3 --------------------------------------------------------------- (n + 19) (n + 18) (n + 21) 3 2 (53165 n + 4418019 n + 84218410 n + 466332344) a(n + 12) - ---------------------------------------------------------- (n + 19) (n + 18) (n + 21) 3 2 (235995 n + 8096868 n + 89858227 n + 318071584) a(n + 13) - ----------------------------------------------------------- (n + 19) (n + 18) (n + 21) 3 2 (805495 n + 31579434 n + 409629539 n + 1755764082) a(n + 14) + 1/3 -------------------------------------------------------------- (n + 19) (n + 18) (n + 21) 3 2 (171967 n + 6641577 n + 83491700 n + 338671230) a(n + 15) - 1/3 ----------------------------------------------------------- (n + 19) (n + 18) (n + 21) 3 2 (35951 n + 1810410 n + 30212776 n + 167179227) a(n + 16) - 2/3 ---------------------------------------------------------- (n + 19) (n + 18) (n + 21) 3 2 (15881 n + 792175 n + 13160258 n + 72814804) a(n + 17) + -------------------------------------------------------- (n + 19) (n + 18) (n + 21) 3 2 (5822 n + 300513 n + 5166394 n + 29585679) a(n + 18) - 2/3 ------------------------------------------------------ (n + 19) (n + 18) (n + 21) 3 2 (504 n + 27049 n + 483361 n + 2876336) a(n + 19) + -------------------------------------------------- (n + 19) (n + 18) (n + 21) 2 (104 n + 3933 n + 37045) 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) = 10, a(5) = 74, a(6) = 488, a(7) = 3017, a(8) = 17910, a(9) = 103379, a(10) = 584593, a(11) = 3254388, a(12) = 17894509, a(13) = 97416558, a(14) = 525977690, a(15) = 2820329894, a(16) = 15034144460, a(17) = 79736848424, a(18) = 421043932399, a(19) = 2214716171651, a(20) = 11609811353186, a(21) = 60675207260346 Lemma , 5.2, : Let b(n) be the number of words of length n in the alphabet , {1, 2, 3, 4, 5}, with more occurences of, {[1, 1, 1]}, then , {[1, 2, 2]} b(n) satisfies the following linear recurrence equation with polynomial coef\ ficients of order, 11 (n + 1) (n + 2) b(n) (n + 3) (n + 2) b(n + 1) -625/3 -------------------- - 1000/3 ------------------------ (n + 11) (n + 8) (n + 11) (n + 8) 2 (19 n + 393 n + 1010) b(n + 2) + 25/3 ------------------------------- (n + 11) (n + 8) 2 (13 n + 365 n + 1308) b(n + 3) + 25/3 ------------------------------- (n + 11) (n + 8) 2 (4 n + 41 n + 108) b(n + 4) + 500/3 ---------------------------- (n + 11) (n + 8) 2 (421 n + 4399 n + 11232) b(n + 5) + 5/3 ---------------------------------- (n + 11) (n + 8) 2 (281 n + 989 n - 8092) b(n + 6) + 1/3 -------------------------------- (n + 11) (n + 8) 2 (466 n + 5917 n + 18060) b(n + 7) - 2/3 ---------------------------------- (n + 11) (n + 8) 2 2 (19 n + 377 n + 1750) b(n + 8) 5 (13 n + 223 n + 940) b(n + 9) - 5/3 ------------------------------- + -------------------------------- (n + 11) (n + 8) (n + 11) (n + 8) 2 (22 n + 397 n + 1755) 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) = 9, b(5) = 64, b(6) = 415, b(7) = 2539, b(8) = 14971, b(9) = 86016, b(10) = 484809, b(11) = 2692440 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.10 1/2 - ---- 1/2 n The probability of Bob winning the bet, as n grows larger is approximately 1.79 1/2 - ---- 1/2 n You can see that indeed Alice has a better chance, but not significantly so. ----------------------------------------- This took, 29.641, seconds to generate ----------------------------------------------------------------------------\ ----------------------- Question Mumber, 6, : If Alice bets that there are more occurrences of consec\ utive substrings in, {[2, 1, 3]}, than in, {[1, 1, 1]}, and Bob, bets vice versa, who is more likely to win? Answer: Alice is more likely to win. Let's be more quantitative. We need the following two lemmas Lemma , 6.1, : Let a(n) be the number of words of length n in the alphabet , {1, 2, 3, 4, 5}, 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 (n + 1) (n + 2) (n + 3) a(n) 16000 (n + 4) (n + 3) (n + 2) a(n + 1) 2500/3 ---------------------------- + -------------------------------------- - (n + 25) (n + 24) (n + 27) (n + 25) (n + 24) (n + 27) 3 2 (79137941 n + 2423046582 n + 24590080987 n + 82843115730) a(n + 10) 1/3 --------------------------------------------------------------------- (n + 25) (n + 24) (n + 27) 3 2 (12699187 n + 463270896 n + 5587600733 n + 22366175124) a(n + 11) - 2/3 ------------------------------------------------------------------- (n + 25) (n + 24) (n + 27) 3 2 (10999955 n + 375825489 n + 4216448383 n + 15431086365) a(n + 12) + 2/3 ------------------------------------------------------------------- (n + 25) (n + 24) (n + 27) + 3 2 (34783283 n + 1394867136 n + 18529996405 n + 81471125472) a(n + 13) 1/3 --------------------------------------------------------------------- (n + 25) (n + 24) (n + 27) 3 2 (19512005 n + 886254468 n + 13309905463 n + 66107194224) a(n + 14) + 1/3 -------------------------------------------------------------------- (n + 25) (n + 24) (n + 27) 3 2 (1046461 n + 82303302 n + 1786189247 n + 11794831950) a(n + 15) + 1/3 ----------------------------------------------------------------- (n + 25) (n + 24) (n + 27) 3 2 (2870515 n + 138430863 n + 2212387355 n + 11709994107) a(n + 16) - 2/3 ------------------------------------------------------------------ (n + 25) (n + 24) (n + 27) 3 2 (1043693 n + 56138386 n + 1003318135 n + 5958568850) a(n + 17) - ---------------------------------------------------------------- (n + 25) (n + 24) (n + 27) 3 2 2 (71684 n + 3260009 n + 47089294 n + 209255929) a(n + 18) + ------------------------------------------------------------ (n + 25) (n + 24) (n + 27) 3 2 (850927 n + 49302546 n + 951398165 n + 6114683922) a(n + 19) + 1/3 -------------------------------------------------------------- (n + 25) (n + 24) (n + 27) 3 2 (20831 n + 1434082 n + 32377657 n + 240644070) a(n + 20) + ---------------------------------------------------------- (n + 25) (n + 24) (n + 27) 3 2 (95776 n + 5945121 n + 123035234 n + 849044949) a(n + 21) - 2/3 ----------------------------------------------------------- (n + 25) (n + 24) (n + 27) 3 2 (19087 n + 1109112 n + 21245621 n + 133899900) a(n + 22) + 1/3 ---------------------------------------------------------- (n + 25) (n + 24) (n + 27) 3 2 (19793 n + 1364232 n + 31305799 n + 239178840) a(n + 23) + 1/3 ---------------------------------------------------------- (n + 25) (n + 24) (n + 27) 3 2 (7613 n + 532800 n + 12423511 n + 96517476) a(n + 24) - 1/3 ------------------------------------------------------- (n + 25) (n + 24) (n + 27) 3 2 5 (81 n + 5820 n + 139311 n + 1110940) a(n + 25) + -------------------------------------------------- (n + 25) (n + 24) (n + 27) 3 2 (372877 n + 5746938 n + 28668191 n + 46582410) a(n + 3) + 5/3 --------------------------------------------------------- (n + 25) (n + 24) (n + 27) 3 2 40 (42829 n + 835491 n + 5189869 n + 10413091) a(n + 4) + --------------------------------------------------------- (n + 25) (n + 24) (n + 27) 3 2 4 (611606 n + 16470757 n + 131450167 n + 327645760) a(n + 5) + -------------------------------------------------------------- (n + 25) (n + 24) (n + 27) 3 2 (470383 n - 39841810 n - 613026003 n - 2173245210) a(n + 6) - ------------------------------------------------------------- (n + 25) (n + 24) (n + 27) 3 2 (10377007 n + 159648170 n + 602094717 n - 72901190) a(n + 7) - -------------------------------------------------------------- (n + 25) (n + 24) (n + 27) 3 2 (36985945 n + 816320631 n + 5797470449 n + 13070687043) a(n + 8) - 2/3 ------------------------------------------------------------------ (n + 25) (n + 24) (n + 27) 3 2 (98901049 n + 2619168684 n + 22857403547 n + 65734932240) a(n + 9) - 1/3 -------------------------------------------------------------------- (n + 25) (n + 24) (n + 27) 2 (19 n + 948 n + 11801) a(n + 26) - 5/3 --------------------------------- (n + 27) (n + 25) 2 (n + 3) (15995 n + 145257 n + 321610) a(n + 2) + 25/3 ----------------------------------------------- + a(n + 27) = 0 (n + 25) (n + 24) (n + 27) Subject to the initial conditions a(1) = 0, a(2) = 0, a(3) = 1, a(4) = 10, a(5) = 75, a(6) = 497, a(7) = 3082, a(8) = 18330, a(9) = 105933, a(10) = 599532, a(11) = 3339436, a(12) = 18369148, a(13) = 100025329, a(14) = 540144357, a(15) = 2896511746, a(16) = 15440515962, a(17) = 81889844708, a(18) = 432384854684, a(19) = 2274157088440, a(20) = 11920006427754, a(21) = 62287805474088, a(22) = 324592988512488, a(23) = 1687343169084717, a(24) = 8751809856617222, a(25) = 45301318254331893, a(26) = 234055758949935378, a(27) = 1207232428275346646 Lemma , 6.2, : Let b(n) be the number of words of length n in the alphabet , {1, 2, 3, 4, 5}, 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 (n + 1) (n + 2) b(n) (33 n + 79) (n + 2) b(n + 1) 100/3 -------------------- + 20/3 ---------------------------- (n + 9) (n + 6) (n + 9) (n + 6) 2 (1549 n + 8813 n + 12410) b(n + 2) + 1/3 ----------------------------------- (n + 9) (n + 6) 2 (1423 n + 10039 n + 16910) b(n + 3) + 1/3 ------------------------------------ (n + 9) (n + 6) 2 (31 n + 247 n + 362) b(n + 4) + 8/3 ------------------------------ (n + 9) (n + 6) 2 (175 n + 1861 n + 5090) b(n + 5) - 2/3 --------------------------------- (n + 9) (n + 6) 2 (187 n + 2165 n + 5978) b(n + 6) - 2/3 --------------------------------- (n + 9) (n + 6) 2 (61 n + 785 n + 2446) b(n + 7) + 4/3 ------------------------------- (n + 9) (n + 6) 2 (47 n + 657 n + 2218) 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) = 9, b(5) = 65, b(6) = 423, b(7) = 2595, b(8) = 15327, b(9) = 88160 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.08 1/2 - ---- 1/2 n The probability of Bob winning the bet, as n grows larger is approximately 1.76 1/2 - ---- 1/2 n You can see that indeed Alice has a better chance, but not significantly so. ----------------------------------------- This took, 38.026, seconds to generate The best bet against, [1, 1, 1], is a member of, {[1, 1, 2], [1, 1, 3], [1, 1, 4], [1, 1, 5], [2, 1, 1], [3, 1, 1], [4, 1, 1], [5, 1, 1]}, 0.76 and then your edge, if you have n rolls, is approximately, ---- 1/2 n The next best bet is a member of, {[1, 2, 2], [1, 2, 3], [1, 2, 4], [1, 2, 5], [1, 3, 2], [1, 3, 3], [1, 3, 4], [1, 3, 5], [1, 4, 2], [1, 4, 3], [1, 4, 4], [1, 4, 5], [1, 5, 2], [1, 5, 3], [1, 5, 4], [1, 5, 5], [2, 2, 1], [2, 3, 1], [2, 4, 1], [2, 5, 1], [3, 2, 1], [3, 3, 1], [3, 4, 1], [3, 5, 1], [4, 2, 1], [4, 3, 1], [4, 4, 1], [4, 5, 1], [5, 2, 1], [5, 3, 1], [5, 4, 1], [5, 5, 1] 0.69 }, and then your edge is approximately, ---- 1/2 n The next best bet is a member of, {[2, 1, 3], [2, 1, 4], [2, 1, 5], [2, 2, 3], [2, 2, 4], [2, 2, 5], [2, 3, 3], [2, 3, 4], [2, 3, 5], [2, 4, 3], [2, 4, 4], [2, 4, 5], [2, 5, 3], [2, 5, 4], [2, 5, 5], [3, 1, 2], [3, 1, 4], [3, 1, 5], [3, 2, 2], [3, 2, 4], [3, 2, 5], [3, 3, 2], [3, 3, 4], [3, 3, 5], [3, 4, 2], [3, 4, 4], [3, 4, 5], [3, 5, 2], [3, 5, 4], [3, 5, 5], [4, 1, 2], [4, 1, 3], [4, 1, 5], [4, 2, 2], [4, 2, 3], [4, 2, 5], [4, 3, 2], [4, 3, 3], [4, 3, 5], [4, 4, 2], [4, 4, 3], [4, 4, 5], [4, 5, 2], [4, 5, 3], [4, 5, 5], [5, 1, 2], [5, 1, 3], [5, 1, 4], [5, 2, 2], [5, 2, 3], [5, 2, 4], [5, 3, 2], [5, 3, 3], [5, 3, 4], [5, 4, 2], [5, 4, 3], [5, 4, 4], [5, 5, 2], [5, 5, 3], [5, 5, 4] 0.68 }, and then your edge is approximately, ---- 1/2 n The next best bet is a member of, {[1, 2, 1], [1, 3, 1], [1, 4, 1], [1, 5, 1]}, 0.58 and then your edge is approximately, ---- 1/2 n The next best bet is a member of, {[2, 1, 2], [2, 3, 2], [2, 4, 2], [2, 5, 2], [3, 1, 3], [3, 2, 3], [3, 4, 3], [3, 5, 3], [4, 1, 4], [4, 2, 4], [4, 3, 4], [4, 5, 4], [5, 1, 5], [5, 2, 5], [5, 3, 5], [5, 4, 5]}, 0.55 and then your edge is approximately, ---- 1/2 n The next best bet is a member of, {[2, 2, 2], [3, 3, 3], [4, 4, 4], [5, 5, 5]}, and then your edge is exactly 0 ----------------------- This ends this chapter that took, 199.807, seconds to generate.