The Relative Probablity of Winning a Daniel Litt style game when rolling a f\ air, 4, sides die marked with, {1, 2, 3, 4}, of number of occurrences of, [1, 1], Versus the number of occurences of all, 2, letter words in, {1, 2, 3, 4} 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}, with more occurences of, {[1, 2]}, then , {[1, 1]} a(n) satisfies the following linear recurrence equation with polynomial coef\ ficients of order, 12 12288 (n + 1) (n + 2) (n + 3) a(n) 256 (149 n + 761) (n + 3) (n + 2) a(n + 1) ---------------------------------- + ------------------------------------------ (n + 10) (n + 12) (n + 11) (n + 10) (n + 12) (n + 11) 2 64 (n + 3) (475 n + 5157 n + 12554) a(n + 2) - --------------------------------------------- (n + 10) (n + 12) (n + 11) 3 2 16 (377 n + 4944 n + 29083 n + 61140) a(n + 3) - ------------------------------------------------ (n + 10) (n + 12) (n + 11) 3 2 4 (2701 n + 15024 n - 81673 n - 441444) a(n + 4) - -------------------------------------------------- (n + 10) (n + 12) (n + 11) 3 2 4 (5608 n + 70383 n + 246599 n + 155988) a(n + 5) + --------------------------------------------------- (n + 10) (n + 12) (n + 11) 3 2 4 (1736 n + 20055 n + 44209 n - 83946) a(n + 6) - ------------------------------------------------- (n + 10) (n + 12) (n + 11) 3 2 2 (2077 n + 53706 n + 447581 n + 1213236) a(n + 7) - ---------------------------------------------------- (n + 10) (n + 12) (n + 11) 3 2 3 (1285 n + 31962 n + 264533 n + 728520) a(n + 8) + --------------------------------------------------- (n + 10) (n + 12) (n + 11) 2 3 (n + 9) (442 n + 7783 n + 34328) a(n + 9) - -------------------------------------------- (n + 10) (n + 12) (n + 11) 2 (244 n + 4565 n + 21393) a(n + 10) 3 (8 n + 79) 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) = 7, a(4) = 38, a(5) = 187, a(6) = 868, a(7) = 3886, a(8) = 16977, a(9) = 72879, a(10) = 308812, a(11) = 1295608, a(12) = 5393731 Lemma , 2.2, : Let b(n) be the number of words of length n in the alphabet , {1, 2, 3, 4}, with more occurences of, {[1, 1]}, then , {[1, 2]} b(n) satisfies the following linear recurrence equation with polynomial coef\ ficients of order, 7 128 (n + 1) (n + 2) b(n) 96 (n + 2) b(n + 1) - ------------------------ + ------------------- (n + 7) (n + 5) n + 7 2 2 8 (7 n + 59 n + 106) b(n + 2) 6 (11 n + 47 n + 10) b(n + 3) - ------------------------------ + ------------------------------ (n + 7) (n + 5) (n + 7) (n + 5) 2 2 2 (45 n + 331 n + 568) b(n + 4) (51 n + 485 n + 1130) b(n + 5) - -------------------------------- + ------------------------------- (n + 7) (n + 5) (n + 7) (n + 5) (4 n + 25) (3 n + 14) b(n + 6) - ------------------------------ + b(n + 7) = 0 (n + 7) (n + 5) Subject to the initial conditions b(1) = 0, b(2) = 1, b(3) = 6, b(4) = 32, b(5) = 156, b(6) = 721, b(7) = 3226 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.4232 1/2 - ------ 1/2 n The probability of Bob winning the bet, as n grows larger is approximately 0.7053 1/2 - ------ 1/2 n You can see that indeed Alice has a better chance, but not significantly so. ----------------------------------------- This took, 19.682, 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}, with more occurences of, {[2, 3]}, then , {[1, 1]} a(n) satisfies the following linear recurrence equation with polynomial coef\ ficients of order, 14 2592 (2 n + 1) (n + 2) (n + 1) a(n) ----------------------------------- (n + 14) (n + 13) (n + 12) 2 72 (n + 2) (232 n + 391 n + 165) a(n + 1) - ------------------------------------------ (n + 14) (n + 13) (n + 12) 3 2 12 (953 n + 14550 n + 57382 n + 68412) a(n + 2) - ------------------------------------------------- (n + 14) (n + 13) (n + 12) 3 2 2 (31319 n + 334527 n + 1161790 n + 1305624) a(n + 3) + ------------------------------------------------------- (n + 14) (n + 13) (n + 12) 3 2 4 (4246 n + 24009 n - 30406 n - 230172) a(n + 4) - -------------------------------------------------- (n + 14) (n + 13) (n + 12) 3 2 6 (7107 n + 115602 n + 606445 n + 1020554) a(n + 5) - ----------------------------------------------------- (n + 14) (n + 13) (n + 12) 3 2 (26167 n + 365445 n + 1471760 n + 1336260) a(n + 6) + ----------------------------------------------------- (n + 14) (n + 13) (n + 12) 3 2 (2443 n + 129345 n + 1414964 n + 4358304) a(n + 7) + ---------------------------------------------------- (n + 14) (n + 13) (n + 12) 3 2 (3359 n + 82887 n + 628852 n + 1419888) a(n + 8) - -------------------------------------------------- (n + 14) (n + 13) (n + 12) 3 2 (2333 n + 76497 n + 830320 n + 2984988) a(n + 9) - -------------------------------------------------- (n + 14) (n + 13) (n + 12) 3 2 (2599 n + 82719 n + 878786 n + 3116352) a(n + 10) + --------------------------------------------------- (n + 14) (n + 13) (n + 12) 3 2 4 (251 n + 8355 n + 92839 n + 344385) a(n + 11) - ------------------------------------------------- (n + 14) (n + 13) (n + 12) 2 6 (34 n + 787 n + 4564) a(n + 12) 2 (11 n + 133) a(n + 13) + ---------------------------------- - ------------------------ (n + 13) (n + 14) n + 14 + a(n + 14) = 0 Subject to the initial conditions a(1) = 0, a(2) = 1, a(3) = 8, a(4) = 45, a(5) = 222, a(6) = 1024, a(7) = 4539, a(8) = 19608, a(9) = 83223, a(10) = 348811, a(11) = 1448523, a(12) = 5973747, a(13) = 24505408, a(14) = 100111675 Lemma , 3.2, : Let b(n) be the number of words of length n in the alphabet , {1, 2, 3, 4}, with more occurences of, {[1, 1]}, then , {[2, 3]} b(n) satisfies the following linear recurrence equation with polynomial coef\ ficients of order, 5 2 36 (n + 1) (2 n + 1) b(n) 3 (12 n + 43 n + 47) b(n + 1) ------------------------- - ------------------------------ (n + 5) (n + 3) (n + 5) (n + 3) 2 (103 n + 303) (n + 2) b(n + 2) 4 (11 n + 67 n + 99) b(n + 3) - 1/2 ------------------------------ + ------------------------------ (n + 5) (n + 3) (n + 5) (n + 3) 2 (23 n + 163 n + 276) b(n + 4) - 1/2 ------------------------------ + b(n + 5) = 0 (n + 5) (n + 3) Subject to the initial conditions b(1) = 0, b(2) = 1, b(3) = 7, b(4) = 38, b(5) = 185 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.3785 1/2 - ------ 1/2 n The probability of Bob winning the bet, as n grows larger is approximately 0.6308 1/2 - ------ 1/2 n You can see that indeed Alice has a better chance, but not significantly so. ----------------------------------------- This took, 16.722, seconds to generate The best bet against, [1, 1], is a member of, {[1, 2], [1, 3], [1, 4], [2, 1], [3, 1], [4, 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], [3, 2], [3, 4], [4, 2], [4, 3]}, 0.2523 and then your edge is approximately, ------ 1/2 n The next best bet is a member of, {[2, 2], [3, 3], [4, 4]}, and then your edge is exactly 0 ----------------------- This ends this chapter that took, 36.727, seconds to generate.