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], Versus the number of occurences of all, 2, 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, {[2, 2]}, than in, {[1, 1]}, and Bob, bets vice versa, who is more likely to win? Answer: They are equally likely to win ----------------------------------------------------------------------------\ ----------------------- Question Mumber, 2, : If Alice bets that there are more occurrences of consec\ utive substrings in, {[1, 2]}, than in, {[1, 1]}, and Bob, bets vice versa, who is more likely to win? Answer: Alice is more likely to win. Let's be more quantitative. We need the following two lemmas Lemma , 2.1, : Let a(n) be the number of words of length n in the alphabet , {1, 2, 3, 4, 5}, with more occurences of, {[1, 2]}, then , {[1, 1]} a(n) satisfies the following linear recurrence equation with polynomial coef\ ficients of order, 12 112500 (n + 1) (n + 2) (n + 3) a(n) ----------------------------------- (n + 10) (n + 12) (n + 11) 1875 (181 n + 833) (n + 3) (n + 2) a(n + 1) + ------------------------------------------- (n + 10) (n + 12) (n + 11) 2 375 (n + 3) (7 n - 1066 n - 4160) a(n + 2) + ------------------------------------------- (n + 10) (n + 12) (n + 11) 3 2 125 (1073 n + 15342 n + 78199 n + 135954) a(n + 3) - ---------------------------------------------------- (n + 10) (n + 12) (n + 11) 3 2 75 (1449 n + 14779 n + 32752 n - 23400) a(n + 4) - -------------------------------------------------- (n + 10) (n + 12) (n + 11) 3 2 25 (4387 n + 60336 n + 260495 n + 336762) a(n + 5) + ---------------------------------------------------- (n + 10) (n + 12) (n + 11) 3 2 15 (56 n + 11111 n + 130351 n + 392926) a(n + 6) + -------------------------------------------------- (n + 10) (n + 12) (n + 11) 3 2 5 (5843 n + 134013 n + 1016572 n + 2551500) a(n + 7) - ------------------------------------------------------ (n + 10) (n + 12) (n + 11) 3 2 2 (7007 n + 170754 n + 1386619 n + 3751800) a(n + 8) + ------------------------------------------------------ (n + 10) (n + 12) (n + 11) 2 6 (n + 9) (549 n + 9571 n + 41820) a(n + 9) - -------------------------------------------- (n + 10) (n + 12) (n + 11) 2 (439 n + 8180 n + 38181) a(n + 10) (32 n + 315) a(n + 11) + ----------------------------------- - ---------------------- + a(n + 12) (n + 12) (n + 11) n + 12 = 0 Subject to the initial conditions a(1) = 0, a(2) = 1, a(3) = 9, a(4) = 63, a(5) = 397, a(6) = 2356, a(7) = 13463, a(8) = 74957, a(9) = 409521, a(10) = 2205674, a(11) = 11748504, a(12) = 62027220 Lemma , 2.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]}, then , {[1, 2]} b(n) satisfies the following linear recurrence equation with polynomial coef\ ficients of order, 7 (n + 1) (n + 2) b(n) 125 (n + 8) (n + 2) b(n + 1) -625/2 -------------------- + ---------------------------- (n + 7) (n + 5) (n + 7) (n + 5) (n + 15) (n + 2) b(n + 2) 125 (n + 4) (n - 1) b(n + 3) - 25/2 ------------------------- + ---------------------------- (n + 7) (n + 5) (n + 7) (n + 5) 2 2 (15 n + 113 n + 202) b(n + 4) 5 (17 n + 163 n + 384) b(n + 5) - 25/2 ------------------------------ + -------------------------------- (n + 7) (n + 5) (n + 7) (n + 5) 2 (31 n + 339 n + 908) b(n + 6) - 1/2 ------------------------------ + b(n + 7) = 0 (n + 7) (n + 5) Subject to the initial conditions b(1) = 0, b(2) = 1, b(3) = 8, b(4) = 55, b(5) = 343, b(6) = 2025, b(7) = 11544 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.5643 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, 19.208, seconds to generate ----------------------------------------------------------------------------\ ----------------------- Question Mumber, 3, : If Alice bets that there are more occurrences of consec\ utive substrings in, {[2, 3]}, than in, {[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, {[2, 3]}, then , {[1, 1]} a(n) satisfies the following linear recurrence equation with polynomial coef\ ficients of order, 15 10000 (n + 1) (n + 2) (n + 3) a(n) 25 (59 n - 25) (n + 3) (n + 2) a(n + 1) ---------------------------------- - --------------------------------------- (n + 15) (n + 14) (n + 13) (n + 15) (n + 14) (n + 13) 2 10 (n + 3) (19931 n + 97599 n + 156280) a(n + 2) - ------------------------------------------------- (n + 15) (n + 14) (n + 13) 3 2 (87931 n + 639234 n + 824513 n - 1471710) a(n + 3) + ---------------------------------------------------- (n + 15) (n + 14) (n + 13) 3 2 4 (156053 n + 2169822 n + 9929212 n + 14904063) a(n + 4) + ---------------------------------------------------------- (n + 15) (n + 14) (n + 13) 3 2 3 (19497 n - 39122 n - 2067585 n - 6865390) a(n + 5) - ------------------------------------------------------ (n + 15) (n + 14) (n + 13) 3 2 2 (180865 n + 3444216 n + 21477233 n + 43755402) a(n + 6) - ----------------------------------------------------------- (n + 15) (n + 14) (n + 13) 3 2 9 (10035 n + 131462 n + 314625 n - 785818) a(n + 7) + ----------------------------------------------------- (n + 15) (n + 14) (n + 13) 3 2 24 (2495 n + 73374 n + 685912 n + 2059905) a(n + 8) + ----------------------------------------------------- (n + 15) (n + 14) (n + 13) 3 2 (13889 n + 317730 n + 2143471 n + 3596790) a(n + 9) - ----------------------------------------------------- (n + 15) (n + 14) (n + 13) 3 2 2 (7849 n + 266112 n + 2995019 n + 11196780) a(n + 10) - -------------------------------------------------------- (n + 15) (n + 14) (n + 13) 3 2 (9913 n + 339678 n + 3882731 n + 14805726) a(n + 11) + ------------------------------------------------------ (n + 15) (n + 14) (n + 13) 3 2 4 (659 n + 23706 n + 284536 n + 1139565) a(n + 12) - ---------------------------------------------------- (n + 15) (n + 14) (n + 13) 2 (383 n + 9559 n + 59742) a(n + 13) 30 (n + 13) a(n + 14) + ----------------------------------- - --------------------- + a(n + 15) (n + 14) (n + 15) n + 15 = 0 Subject to the initial conditions a(1) = 0, a(2) = 1, a(3) = 10, a(4) = 72, a(5) = 457, a(6) = 2713, a(7) = 15457, a(8) = 85664, a(9) = 465499, a(10) = 2492793, a(11) = 13200397, a(12) = 69289912, a(13) = 361161300, a(14) = 1871782257, a(15) = 9655467624 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]}, then , {[2, 3]} b(n) satisfies the following linear recurrence equation with polynomial coef\ ficients of order, 6 50 (n + 1) (n + 2) b(n) 5 (n + 2) (41 n + 58) b(n + 1) ----------------------- + ------------------------------ (n + 6) (n + 4) (n + 6) (n + 4) 2 2 (63 n + 406 n + 720) b(n + 2) 2 (63 n + 424 n + 700) b(n + 3) - ------------------------------ - -------------------------------- (n + 6) (n + 4) (n + 6) (n + 4) 2 2 (19 n + 86) (2 n + 7) b(n + 4) (15 n + 136 n + 300) b(n + 5) + -------------------------------- - ------------------------------ (n + 6) (n + 4) (n + 6) (n + 4) + b(n + 6) = 0 Subject to the initial conditions b(1) = 0, b(2) = 1, b(3) = 9, b(4) = 63, b(5) = 395, b(6) = 2332 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.5151 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, 20.203, seconds to generate The best bet against, [1, 1], is a member of, {[1, 2], [1, 3], [1, 4], [1, 5], [2, 1], [3, 1], [4, 1], [5, 1]}, 0.2821 and then your edge, if you have n rolls, is approximately, ------ 1/2 n The next best bet is a member of, {[2, 3], [2, 4], [2, 5], [3, 2], [3, 4], [3, 5], [4, 2], [4, 3], [4, 5], [5, 2], [5, 3], [5, 4]}, 0.2575 and then your edge is approximately, ------ 1/2 n The next best bet is a member of, {[2, 2], [3, 3], [4, 4], [5, 5]}, and then your edge is exactly 0 ----------------------- This ends this chapter that took, 39.785, seconds to generate.