The Relative Probablity of Winning a Daniel Litt style game when rolling a f\ air, 2, sides die marked with, {1, 2}, of number of occurrences of, [1, 1], Versus the number of occurences of all, 2, letter words in, {1, 2} 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}, with more occurences of, {[1, 2]}, then , {[1, 1]} a(n) satisfies the following linear recurrence equation with polynomial coef\ ficients of order, 10 2 48 (n + 4) (n + 2) (n + 1) a(n) 24 (n + 2) (9 n + 65 n + 108) a(n + 1) - ------------------------------- + --------------------------------------- (n + 10) (n + 9) (n + 8) (n + 10) (n + 9) (n + 8) 3 2 4 (95 n + 1059 n + 3766 n + 4344) a(n + 2) - -------------------------------------------- (n + 10) (n + 9) (n + 8) 2 2 (n + 3) (173 n + 1614 n + 3592) a(n + 3) + ------------------------------------------- (n + 10) (n + 9) (n + 8) 3 2 6 (35 n + 407 n + 1406 n + 1256) a(n + 4) - ------------------------------------------- (n + 10) (n + 9) (n + 8) 3 2 6 (21 n + 215 n + 434 n - 632) a(n + 5) + ----------------------------------------- (n + 10) (n + 9) (n + 8) 3 2 2 (31 n + 321 n + 422 n - 2352) a(n + 6) - ------------------------------------------ (n + 10) (n + 9) (n + 8) 2 2 3 (n + 7) (n - 46 n - 352) a(n + 7) 3 (5 n + 85 n + 354) a(n + 8) + ------------------------------------ + ------------------------------ (n + 10) (n + 9) (n + 8) (n + 9) (n + 10) (7 n + 58) a(n + 9) - ------------------- + a(n + 10) = 0 n + 10 Subject to the initial conditions a(1) = 0, a(2) = 1, a(3) = 3, a(4) = 6, a(5) = 13, a(6) = 28, a(7) = 56, a(8) = 113, a(9) = 231, a(10) = 464 Lemma , 2.2, : Let b(n) be the number of words of length n in the alphabet , {1, 2}, with more occurences of, {[1, 1]}, then , {[1, 2]} b(n) satisfies the following linear recurrence equation with polynomial coef\ ficients of order, 7 8 (n + 1) (n + 2) b(n) 4 (5 n + 13) (n + 2) b(n + 1) - ---------------------- + ----------------------------- (n + 7) (n + 5) (n + 7) (n + 5) 2 2 (13 n + 50) (n + 3) b(n + 2) (23 n + 183 n + 358) b(n + 3) - ------------------------------ + ------------------------------ (n + 7) (n + 5) (n + 7) (n + 5) 2 2 (15 n + 121 n + 236) b(n + 4) 2 (5 n + 46 n + 102) b(n + 5) - ------------------------------ + ------------------------------ (n + 7) (n + 5) (n + 7) (n + 5) 2 (5 n + 54 n + 142) b(n + 6) - ---------------------------- + b(n + 7) = 0 (n + 7) (n + 5) Subject to the initial conditions b(1) = 0, b(2) = 1, b(3) = 2, b(4) = 4, b(5) = 10, b(6) = 21, b(7) = 42 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.14105 1/2 - ------- 1/2 n The probability of Bob winning the bet, as n grows larger is approximately 0.42314 1/2 - ------- 1/2 n You can see that indeed Alice has a better chance, but not significantly so. ----------------------------------------- This took, 12.858, seconds to generate The best bet against, [1, 1], is a member of, {[1, 2], [2, 1]}, 0.28209 and then your edge, if you have n rolls, is approximately, ------- 1/2 n The next best bet is a member of, {[2, 2]}, and then your edge is exactly 0 ----------------------- This ends this chapter that took, 13.059, seconds to generate.