How to bet against any given, 2, -letter word in the David Litt game with a fair die with, 3, faces By Shalosh B. Ekhad ----------------------------------------------------------------- ----------------------------------------------------------------- Chapter Number, 1 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], Versus the number of occurences of all, 2, 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, {[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, {[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 , 2.1, : Let a(n) be the number of words of length n in the alphabet , {1, 2, 3}, with more occurences of, {[2, 3]}, then , {[1, 1]} a(n) satisfies the following linear recurrence equation with polynomial coef\ ficients of order, 8 54 (n + 1) (n + 2) (n + 3) a(n) 9 (7 n - 11) (n + 3) (n + 2) a(n + 1) - ------------------------------- + ------------------------------------- (n + 8) (n + 7) (n + 6) (n + 8) (n + 7) (n + 6) 2 3 (n + 3) (19 n + 168 n + 224) a(n + 2) + ---------------------------------------- (n + 8) (n + 7) (n + 6) 3 2 3 (23 n + 136 n + 39 n - 522) a(n + 3) - ---------------------------------------- (n + 8) (n + 7) (n + 6) 2 3 (n + 3) (5 n + 128 n + 480) a(n + 4) - --------------------------------------- (n + 8) (n + 7) (n + 6) 3 2 2 (13 n + 144 n + 257 n - 762) a(n + 5) (11 n + 183 n + 718) a(n + 6) + --------------------------------------- + ------------------------------ (n + 8) (n + 7) (n + 6) (n + 7) (n + 8) (7 n + 53) a(n + 7) - ------------------- + a(n + 8) = 0 n + 8 Subject to the initial conditions a(1) = 0, a(2) = 1, a(3) = 6, a(4) = 24, a(5) = 83, a(6) = 269, a(7) = 845, a(8) = 2612 Lemma , 2.2, : Let b(n) be the number of words of length n in the alphabet , {1, 2, 3}, with more occurences of, {[1, 1]}, then , {[2, 3]} b(n) satisfies the following linear recurrence equation with polynomial coef\ ficients of order, 4 9 (n + 1) b(n) 3 (2 n - 1) b(n + 1) (8 n + 29) b(n + 2) - -------------- + -------------------- + ------------------- n + 4 n + 4 n + 4 3 (2 n + 7) b(n + 3) - -------------------- + b(n + 4) = 0 n + 4 Subject to the initial conditions b(1) = 0, b(2) = 1, b(3) = 5, b(4) = 19 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.24431 1/2 - ------- 1/2 n The probability of Bob winning the bet, as n grows larger is approximately 0.48861 1/2 - ------- 1/2 n You can see that indeed Alice has a better chance, but not significantly so. ----------------------------------------- This took, 11.972, seconds to generate ----------------------------------------------------------------------------\ ----------------------- Question Mumber, 3, : 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 , 3.1, : Let a(n) be the number of words of length n in the alphabet , {1, 2, 3}, with more occurences of, {[1, 2]}, then , {[1, 1]} a(n) satisfies the following linear recurrence equation with polynomial coef\ ficients of order, 12 486 (n + 1) (n + 2) (n + 3) a(n) 729 (3 n + 17) (n + 3) (n + 2) a(n + 1) -------------------------------- + --------------------------------------- (n + 10) (n + 12) (n + 11) (n + 10) (n + 12) (n + 11) 2 27 (n + 3) (211 n + 2082 n + 4784) a(n + 2) - -------------------------------------------- (n + 10) (n + 12) (n + 11) 3 2 27 (165 n + 2414 n + 11147 n + 16554) a(n + 3) + ------------------------------------------------ (n + 10) (n + 12) (n + 11) 3 2 3 (871 n + 10587 n + 35222 n + 21300) a(n + 4) - ------------------------------------------------ (n + 10) (n + 12) (n + 11) 3 2 9 (317 n + 3610 n + 8923 n - 7870) a(n + 5) + --------------------------------------------- (n + 10) (n + 12) (n + 11) 3 2 15 (140 n + 1821 n + 5785 n - 990) a(n + 6) - --------------------------------------------- (n + 10) (n + 12) (n + 11) 3 2 (337 n + 1023 n - 37828 n - 200052) a(n + 7) + ---------------------------------------------- (n + 10) (n + 12) (n + 11) 2 6 (n + 8) (79 n + 1566 n + 7455) a(n + 8) + ------------------------------------------ (n + 10) (n + 12) (n + 11) 2 4 (n + 9) (86 n + 1569 n + 7147) a(n + 9) - ------------------------------------------ (n + 10) (n + 12) (n + 11) 2 3 (35 n + 662 n + 3135) a(n + 10) (16 n + 159) 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) = 5, a(4) = 19, a(5) = 67, a(6) = 224, a(7) = 725, a(8) = 2301, a(9) = 7203, a(10) = 22330, a(11) = 68746, a(12) = 210560 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]}, then , {[1, 2]} b(n) satisfies the following linear recurrence equation with polynomial coef\ ficients of order, 7 (n + 1) (n + 2) b(n) 27 (2 n + 7) (n + 2) b(n + 1) -81/2 -------------------- + ----------------------------- (n + 7) (n + 5) (n + 7) (n + 5) 2 2 (11 n + 83 n + 146) b(n + 2) 3 (13 n + 83 n + 120) b(n + 3) - 9/2 ----------------------------- + ------------------------------- (n + 7) (n + 5) (n + 7) (n + 5) 2 2 (25 n + 183 n + 310) b(n + 4) 2 (13 n + 122 n + 279) b(n + 5) - 3/2 ------------------------------ + -------------------------------- (n + 7) (n + 5) (n + 7) (n + 5) 2 (17 n + 185 n + 492) 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) = 4, b(4) = 15, b(5) = 53, b(6) = 177, b(7) = 576 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.2821 1/2 - ------ 1/2 n The probability of Bob winning the bet, as n grows larger is approximately 0.56420 1/2 - ------- 1/2 n You can see that indeed Alice has a better chance, but not significantly so. ----------------------------------------- This took, 17.671, seconds to generate The best bet against, [1, 1], is a member of, {[1, 2], [1, 3], [2, 1], [3, 1]}, 0.28210 and then your edge, if you have n rolls, is approximately, ------- 1/2 n The next best bet is a member of, {[2, 3], [3, 2]}, 0.24430 and then your edge is approximately, ------- 1/2 n The next best bet is a member of, {[2, 2], [3, 3]}, and then your edge is exactly 0 ----------------------- This ends this chapter that took, 29.924, seconds to generate. ----------------------------------------------------------------- Chapter Number, 2 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, 2], Versus the number of occurences of all, 2, 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, {[2, 1]}, than in, {[1, 2]}, 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, {[3, 3]}, than in, {[1, 2]}, and Bob, bets vice versa, who is more likely to win? Answer: Bob 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}, with more occurences of, {[3, 3]}, then , {[1, 2]} a(n) satisfies the following linear recurrence equation with polynomial coef\ ficients of order, 4 9 (n + 1) a(n) 3 (2 n - 1) a(n + 1) (8 n + 29) a(n + 2) - -------------- + -------------------- + ------------------- n + 4 n + 4 n + 4 3 (2 n + 7) a(n + 3) - -------------------- + a(n + 4) = 0 n + 4 Subject to the initial conditions a(1) = 0, a(2) = 1, a(3) = 5, a(4) = 19 Lemma , 2.2, : Let b(n) be the number of words of length n in the alphabet , {1, 2, 3}, with more occurences of, {[1, 2]}, then , {[3, 3]} b(n) satisfies the following linear recurrence equation with polynomial coef\ ficients of order, 8 54 (n + 1) (n + 2) (n + 3) b(n) 9 (7 n - 11) (n + 3) (n + 2) b(n + 1) - ------------------------------- + ------------------------------------- (n + 8) (n + 7) (n + 6) (n + 8) (n + 7) (n + 6) 2 3 (n + 3) (19 n + 168 n + 224) b(n + 2) + ---------------------------------------- (n + 8) (n + 7) (n + 6) 3 2 3 (23 n + 136 n + 39 n - 522) b(n + 3) - ---------------------------------------- (n + 8) (n + 7) (n + 6) 2 3 (n + 3) (5 n + 128 n + 480) b(n + 4) - --------------------------------------- (n + 8) (n + 7) (n + 6) 3 2 2 (13 n + 144 n + 257 n - 762) b(n + 5) (11 n + 183 n + 718) b(n + 6) + --------------------------------------- + ------------------------------ (n + 8) (n + 7) (n + 6) (n + 7) (n + 8) (7 n + 53) b(n + 7) - ------------------- + b(n + 8) = 0 n + 8 Subject to the initial conditions b(1) = 0, b(2) = 1, b(3) = 6, b(4) = 24, b(5) = 83, b(6) = 269, b(7) = 845, b(8) = 2612 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.48861 1/2 - ------- 1/2 n The probability of Bob winning the bet, as n grows larger is approximately 0.24431 1/2 - ------- 1/2 n You can see that indeed Bob has a better chance, but not significantly so. ----------------------------------------- This took, 14.897, seconds to generate ----------------------------------------------------------------------------\ ----------------------- Question Mumber, 3, : If Alice bets that there are more occurrences of consec\ utive substrings in, {[1, 1]}, than in, {[1, 2]}, and Bob, bets vice versa, who is more likely to win? Answer: Bob 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]}, then , {[1, 2]} a(n) satisfies the following linear recurrence equation with polynomial coef\ ficients of order, 7 (n + 1) (n + 2) a(n) 27 (2 n + 7) (n + 2) a(n + 1) -81/2 -------------------- + ----------------------------- (n + 7) (n + 5) (n + 7) (n + 5) 2 2 (11 n + 83 n + 146) a(n + 2) 3 (13 n + 83 n + 120) a(n + 3) - 9/2 ----------------------------- + ------------------------------- (n + 7) (n + 5) (n + 7) (n + 5) 2 2 (25 n + 183 n + 310) a(n + 4) 2 (13 n + 122 n + 279) a(n + 5) - 3/2 ------------------------------ + -------------------------------- (n + 7) (n + 5) (n + 7) (n + 5) 2 (17 n + 185 n + 492) a(n + 6) - 1/2 ------------------------------ + a(n + 7) = 0 (n + 7) (n + 5) Subject to the initial conditions a(1) = 0, a(2) = 1, a(3) = 4, a(4) = 15, a(5) = 53, a(6) = 177, a(7) = 576 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, 2]}, then , {[1, 1]} b(n) satisfies the following linear recurrence equation with polynomial coef\ ficients of order, 12 486 (n + 1) (n + 2) (n + 3) b(n) 729 (3 n + 17) (n + 3) (n + 2) b(n + 1) -------------------------------- + --------------------------------------- (n + 10) (n + 12) (n + 11) (n + 10) (n + 12) (n + 11) 2 27 (n + 3) (211 n + 2082 n + 4784) b(n + 2) - -------------------------------------------- (n + 10) (n + 12) (n + 11) 3 2 27 (165 n + 2414 n + 11147 n + 16554) b(n + 3) + ------------------------------------------------ (n + 10) (n + 12) (n + 11) 3 2 3 (871 n + 10587 n + 35222 n + 21300) b(n + 4) - ------------------------------------------------ (n + 10) (n + 12) (n + 11) 3 2 9 (317 n + 3610 n + 8923 n - 7870) b(n + 5) + --------------------------------------------- (n + 10) (n + 12) (n + 11) 3 2 15 (140 n + 1821 n + 5785 n - 990) b(n + 6) - --------------------------------------------- (n + 10) (n + 12) (n + 11) 3 2 (337 n + 1023 n - 37828 n - 200052) b(n + 7) + ---------------------------------------------- (n + 10) (n + 12) (n + 11) 2 6 (n + 8) (79 n + 1566 n + 7455) b(n + 8) + ------------------------------------------ (n + 10) (n + 12) (n + 11) 2 4 (n + 9) (86 n + 1569 n + 7147) b(n + 9) - ------------------------------------------ (n + 10) (n + 12) (n + 11) 2 3 (35 n + 662 n + 3135) b(n + 10) (16 n + 159) b(n + 11) + ---------------------------------- - ---------------------- + b(n + 12) (n + 12) (n + 11) n + 12 = 0 Subject to the initial conditions b(1) = 0, b(2) = 1, b(3) = 5, b(4) = 19, b(5) = 67, b(6) = 224, b(7) = 725, b(8) = 2301, b(9) = 7203, b(10) = 22330, b(11) = 68746, b(12) = 210560 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.56420 1/2 - ------- 1/2 n The probability of Bob winning the bet, as n grows larger is approximately 0.2821 1/2 - ------ 1/2 n You can see that indeed Bob has a better chance, but not significantly so. ----------------------------------------- This took, 19.384, seconds to generate ----------------------------------------------------------------------------\ ----------------------- Question Mumber, 4, : If Alice bets that there are more occurrences of consec\ utive substrings in, {[1, 3]}, than in, {[1, 2]}, and Bob, bets vice versa, who is more likely to win? Answer: They are equally likely to win ----------------------------------------------------------------------------\ ----------------------- Question Mumber, 5, : If Alice bets that there are more occurrences of consec\ utive substrings in, {[2, 3]}, than in, {[1, 2]}, and Bob, bets vice versa, who is more likely to win? Answer: They are equally likely to win The best bet against, [1, 2], is a member of, {[1, 3], [2, 1], [2, 3], [3, 1], [3, 2]}, and then your edge, if you have n rolls, is exactly 0 The next best bet is a member of, {[3, 3]}, and then your edge is approximately, 0.24430 - ------- 1/2 n The next best bet is a member of, {[1, 1], [2, 2]}, 0.28210 and then your edge is approximately, - ------- 1/2 n ----------------------- This ends this chapter that took, 34.500, seconds to generate. -------------------------------------------------------- This ends this book that took, 64.516, seconds to generate.