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, 1, 1], Versus the number of occurences of all, 4, 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, {[1, 2, 2, 1]}, than in, {[1, 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}, with more occurences of, {[1, 2, 2, 1]}, then , {[1, 1, 1, 1]} a(n) satisfies the following linear recurrence equation with polynomial coef\ ficients of order, 34 (2 n + 3) (n + 2) (n + 1) a(n) -16/3 ------------------------------ (n + 30) (n + 34) (n + 31) 3 2 (2975 n + 436281 n + 11123722 n + 78229968) a(n + 16) - 1/6 ------------------------------------------------------- (n + 30) (n + 34) (n + 31) 3 2 (13735 n + 697197 n + 10973054 n + 51484680) a(n + 17) - 1/6 -------------------------------------------------------- (n + 30) (n + 34) (n + 31) 3 2 (1118 n + 38313 n + 42100 n - 5230272) a(n + 18) + 2/3 -------------------------------------------------- (n + 30) (n + 34) (n + 31) 3 2 (14267 n + 927903 n + 19842514 n + 139715520) a(n + 19) + 1/6 --------------------------------------------------------- (n + 30) (n + 34) (n + 31) 3 2 (2631 n + 138596 n + 2385021 n + 13351252) a(n + 20) - ------------------------------------------------------ (n + 30) (n + 34) (n + 31) 3 2 (14885 n + 805299 n + 14455690 n + 86469192) a(n + 21) + 1/6 -------------------------------------------------------- (n + 30) (n + 34) (n + 31) 3 2 (4261 n + 291675 n + 6633866 n + 50039184) a(n + 22) - 1/3 ------------------------------------------------------ (n + 30) (n + 34) (n + 31) 3 2 (3937 n + 280353 n + 6506858 n + 49185036) a(n + 23) + 1/3 ------------------------------------------------------ (n + 30) (n + 34) (n + 31) 3 2 (2003 n + 137130 n + 3106051 n + 23252124) a(n + 24) - 2/3 ------------------------------------------------------ (n + 30) (n + 34) (n + 31) 3 2 4 (51 n + 4648 n + 137189 n + 1319637) a(n + 25) + -------------------------------------------------- (n + 30) (n + 34) (n + 31) 3 2 (374 n + 18570 n + 226453 n - 77358) a(n + 26) + 2/3 ------------------------------------------------ (n + 30) (n + 34) (n + 31) 3 2 (191 n + 11160 n + 198013 n + 973926) a(n + 27) - 2/3 ------------------------------------------------- (n + 30) (n + 34) (n + 31) 3 2 2 (94 n + 7173 n + 181402 n + 1519660) a(n + 28) + -------------------------------------------------- (n + 30) (n + 34) (n + 31) 3 2 (379 n + 28815 n + 719120 n + 5867004) a(n + 29) - 1/3 -------------------------------------------------- (n + 30) (n + 34) (n + 31) 3 2 (3 n - 153 n - 16450 n - 274744) a(n + 30) + -------------------------------------------- (n + 30) (n + 34) (n + 31) 3 2 (13 n + 1211 n + 37562 n + 387944) a(n + 32) + ---------------------------------------------- (n + 30) (n + 34) (n + 31) 3 2 (4 n + 51 n + 164 n + 144) a(n + 2) + 16/3 ------------------------------------- (n + 30) (n + 34) (n + 31) 3 2 4 (75 n + 1279 n + 6884 n + 11844) a(n + 3) + --------------------------------------------- (n + 30) (n + 34) (n + 31) 3 2 2 (483 n + 9431 n + 59428 n + 121828) a(n + 4) - ------------------------------------------------ (n + 30) (n + 34) (n + 31) 3 2 (817 n + 24924 n + 232409 n + 673710) a(n + 5) - 2/3 ------------------------------------------------ (n + 30) (n + 34) (n + 31) 3 2 (3887 n + 105927 n + 955960 n + 2829660) a(n + 6) + 2/3 --------------------------------------------------- (n + 30) (n + 34) (n + 31) 3 2 (7343 n + 202983 n + 1846060 n + 5510940) a(n + 7) - 1/3 ---------------------------------------------------- (n + 30) (n + 34) (n + 31) 3 2 (4055 n + 250581 n + 3545446 n + 14583120) a(n + 8) + 1/6 ----------------------------------------------------- (n + 30) (n + 34) (n + 31) 3 2 (11537 n + 603975 n + 8721634 n + 38403600) a(n + 9) - 1/6 ------------------------------------------------------ (n + 30) (n + 34) (n + 31) 3 2 (12109 n + 445625 n + 5453630 n + 22179208) a(n + 10) + 1/2 ------------------------------------------------------- (n + 30) (n + 34) (n + 31) 3 2 (5995 n + 162805 n + 1274180 n + 2177776) a(n + 11) - 1/2 ----------------------------------------------------- (n + 30) (n + 34) (n + 31) 3 2 (2759 n + 83670 n + 1125721 n + 6572364) a(n + 12) + 1/3 ---------------------------------------------------- (n + 30) (n + 34) (n + 31) 3 2 (19345 n + 751587 n + 10410818 n + 51206568) a(n + 13) - 1/6 -------------------------------------------------------- (n + 30) (n + 34) (n + 31) 3 2 (39521 n + 1361697 n + 14068090 n + 37762584) a(n + 14) + 1/6 --------------------------------------------------------- (n + 30) (n + 34) (n + 31) 3 2 (3367 n + 70834 n - 142443 n - 6618800) a(n + 15) - --------------------------------------------------- + a(n + 34) (n + 30) (n + 34) (n + 31) 2 (7 n + 445 n + 7058) a(n + 33) - ------------------------------- (n + 34) (n + 31) 2 (n + 2) (2 n + 23 n + 33) a(n + 1) - 8/3 ----------------------------------- (n + 30) (n + 34) (n + 31) 2 2 (n + 32) (2 n + 113 n + 1591) a(n + 31) + ------------------------------------------ = 0 (n + 30) (n + 34) (n + 31) Subject to the initial conditions a(1) = 0, a(2) = 0, a(3) = 0, a(4) = 1, a(5) = 4, a(6) = 12, a(7) = 29, a(8) = 67, a(9) = 148, a(10) = 324, a(11) = 693, a(12) = 1468, a(13) = 3067, a(14) = 6372, a(15) = 13138, a(16) = 26985, a(17) = 55151, a(18) = 112401, a(19) = 228339, a(20) = 462949, a(21) = 936565, a(22) = 1891970, a(23) = 3816208, a(24) = 7689352, a(25) = 15476943, a(26) = 31127327, a(27) = 62555884, a(28) = 125644462, a(29) = 252220247, a(30) = 506092386, a(31) = 1015092415, a(32) = 2035362654, a(33) = 4079902625, a(34) = 8176228211 Lemma , 1.2, : Let b(n) be the number of words of length n in the alphabet , {1, 2}, with more occurences of, {[1, 1, 1, 1]}, then , {[1, 2, 2, 1]} b(n) satisfies the following linear recurrence equation with polynomial coef\ ficients of order, 20 2 (2 n + 3) (n + 2) (n + 1) b(n) (n + 2) (14 n + 65 n + 87) b(n + 1) 16/3 ------------------------------ - 8/3 ------------------------------------ (n + 20) (n + 19) (n + 16) (n + 20) (n + 19) (n + 16) 3 2 (4 n + 9 n - 64 n - 168) b(n + 2) + 16/3 ----------------------------------- (n + 20) (n + 19) (n + 16) 3 2 (119 n + 2055 n + 11056 n + 18972) b(n + 3) + 4/3 --------------------------------------------- (n + 20) (n + 19) (n + 16) 3 2 (431 n + 7515 n + 42076 n + 76452) b(n + 4) - 2/3 --------------------------------------------- (n + 20) (n + 19) (n + 16) 3 2 (401 n + 7632 n + 47701 n + 98502) b(n + 5) + 2/3 --------------------------------------------- (n + 20) (n + 19) (n + 16) 3 2 (653 n + 15417 n + 121300 n + 317772) b(n + 6) - 2/3 ------------------------------------------------ (n + 20) (n + 19) (n + 16) 3 2 (553 n + 14173 n + 119736 n + 333868) b(n + 7) + ------------------------------------------------ (n + 20) (n + 19) (n + 16) 3 2 (2591 n + 69597 n + 620134 n + 1836048) b(n + 8) - 1/6 -------------------------------------------------- (n + 20) (n + 19) (n + 16) 3 2 (723 n + 23717 n + 260806 n + 959120) b(n + 9) + 1/2 ------------------------------------------------ (n + 20) (n + 19) (n + 16) 3 2 (655 n + 26775 n + 350426 n + 1486440) b(n + 10) - 1/2 -------------------------------------------------- (n + 20) (n + 19) (n + 16) 3 2 (1553 n + 69303 n + 976744 n + 4431504) b(n + 11) + 1/6 --------------------------------------------------- (n + 20) (n + 19) (n + 16) 3 2 (339 n + 16075 n + 243732 n + 1198448) b(n + 12) - 1/2 -------------------------------------------------- (n + 20) (n + 19) (n + 16) 3 2 (89 n + 5233 n + 93432 n + 526884) b(n + 13) + ---------------------------------------------- (n + 20) (n + 19) (n + 16) 3 2 (403 n + 25317 n + 478562 n + 2845824) b(n + 14) - 1/6 -------------------------------------------------- (n + 20) (n + 19) (n + 16) 3 2 (85 n + 4993 n + 92794 n + 555648) b(n + 15) + 1/2 ---------------------------------------------- (n + 20) (n + 19) (n + 16) 3 2 (115 n + 4617 n + 58400 n + 222816) b(n + 16) + 1/6 ----------------------------------------------- (n + 20) (n + 19) (n + 16) 3 2 (33 n + 1605 n + 25876 n + 138144) b(n + 17) - 3/2 ---------------------------------------------- (n + 20) (n + 19) (n + 16) 3 2 (63 n + 3209 n + 54266 n + 304472) b(n + 18) + 1/2 ---------------------------------------------- (n + 20) (n + 19) (n + 16) 2 3 (3 n + 102 n + 860) b(n + 19) - -------------------------------- + b(n + 20) = 0 (n + 20) (n + 16) Subject to the initial conditions b(1) = 0, b(2) = 0, b(3) = 0, b(4) = 1, b(5) = 3, b(6) = 8, b(7) = 18, b(8) = 42, b(9) = 93, b(10) = 206, b(11) = 441, b(12) = 942, b(13) = 1981, b(14) = 4159, b(15) = 8648, b(16) = 17937, b(17) = 36978, b(18) = 76075, b(19) = 155897, b(20) = 318905 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.10664 1/2 - ------- 1/2 n The probability of Bob winning the bet, as n grows larger is approximately 0.7464 1/2 - ------ 1/2 n You can see that indeed Alice has a better chance, but not significantly so. ----------------------------------------- This took, 59.351, seconds to generate ----------------------------------------------------------------------------\ ----------------------- Question Mumber, 2, : If Alice bets that there are more occurrences of consec\ utive substrings in, {[2, 2, 2, 2]}, than in, {[1, 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, 1, 2]}, than in, {[1, 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}, with more occurences of, {[1, 1, 1, 2]}, then , {[1, 1, 1, 1]} a(n) satisfies the following linear recurrence equation with polynomial coef\ ficients of order, 26 2 (15 n + 707 n + 8292) a(n + 25) 32 (n + 4) (n + 2) (n + 1) a(n) -1/2 -------------------------------- - ------------------------------- (n + 26) (n + 23) (n + 23) (n + 22) (n + 26) 2 (n + 4) (65 n + 628 n + 1386) a(n + 3) - 8/3 --------------------------------------- (n + 23) (n + 22) (n + 26) 2 (n + 5) (29 n + 236 n + 108) a(n + 4) - 2/3 -------------------------------------- (n + 23) (n + 22) (n + 26) 2 16 (n + 2) (7 n + 53 n + 98) a(n + 1) - -------------------------------------- (n + 23) (n + 22) (n + 26) 2 (n + 3) (79 n + 648 n + 1340) a(n + 2) - 8/3 --------------------------------------- + a(n + 26) (n + 23) (n + 22) (n + 26) 3 2 (213 n + 4767 n + 36288 n + 91804) a(n + 5) + --------------------------------------------- (n + 23) (n + 22) (n + 26) 3 2 (81 n + 601 n - 10194 n - 72944) a(n + 6) + 1/2 ------------------------------------------- (n + 23) (n + 22) (n + 26) 3 2 (596 n + 24297 n + 291037 n + 1084080) a(n + 7) - 1/3 ------------------------------------------------- (n + 23) (n + 22) (n + 26) 3 2 (1645 n + 58343 n + 656286 n + 2383976) a(n + 8) - 1/2 -------------------------------------------------- (n + 23) (n + 22) (n + 26) 3 2 (331 n + 12714 n + 138155 n + 434718) a(n + 9) - 1/3 ------------------------------------------------ (n + 23) (n + 22) (n + 26) 3 2 (529 n + 42213 n + 734342 n + 3717216) a(n + 10) + 1/6 -------------------------------------------------- (n + 23) (n + 22) (n + 26) 3 2 (5591 n + 232575 n + 3158530 n + 14087568) a(n + 11) + 1/6 ------------------------------------------------------ (n + 23) (n + 22) (n + 26) 3 2 (1013 n + 39041 n + 503132 n + 2175120) a(n + 12) - 1/2 --------------------------------------------------- (n + 23) (n + 22) (n + 26) 3 2 (585 n + 19755 n + 216738 n + 758120) a(n + 13) + 1/2 ------------------------------------------------- (n + 23) (n + 22) (n + 26) 3 2 (345 n + 21595 n + 404428 n + 2372924) a(n + 14) - 1/2 -------------------------------------------------- (n + 23) (n + 22) (n + 26) 3 2 (3479 n + 158445 n + 2371504 n + 11660352) a(n + 15) + 1/6 ------------------------------------------------------ (n + 23) (n + 22) (n + 26) 3 2 (4733 n + 207999 n + 3010018 n + 14293800) a(n + 16) - 1/6 ------------------------------------------------------ (n + 23) (n + 22) (n + 26) 3 2 (157 n + 7761 n + 128012 n + 699980) a(n + 17) + 1/2 ------------------------------------------------ (n + 23) (n + 22) (n + 26) 3 2 (389 n + 17601 n + 266278 n + 1354848) a(n + 18) + 1/6 -------------------------------------------------- (n + 23) (n + 22) (n + 26) 3 2 (1261 n + 59337 n + 898610 n + 4320504) a(n + 19) + 1/6 --------------------------------------------------- (n + 23) (n + 22) (n + 26) 3 2 (817 n + 36609 n + 503048 n + 1961808) a(n + 20) - 1/6 -------------------------------------------------- (n + 23) (n + 22) (n + 26) 3 2 (179 n + 7533 n + 86686 n + 157152) a(n + 21) + 1/6 ----------------------------------------------- (n + 23) (n + 22) (n + 26) 3 2 (58 n + 3453 n + 68237 n + 447690) a(n + 22) - 1/3 ---------------------------------------------- (n + 23) (n + 22) (n + 26) 3 2 (35 n + 2403 n + 54634 n + 411528) a(n + 23) - 1/6 ---------------------------------------------- (n + 23) (n + 22) (n + 26) 3 2 (26 n + 1755 n + 39406 n + 294372) a(n + 24) + 2/3 ---------------------------------------------- = 0 (n + 23) (n + 22) (n + 26) Subject to the initial conditions a(1) = 0, a(2) = 0, a(3) = 0, a(4) = 1, a(5) = 3, a(6) = 8, a(7) = 20, a(8) = 46, a(9) = 105, a(10) = 233, a(11) = 508, a(12) = 1095, a(13) = 2332, a(14) = 4929, a(15) = 10345, a(16) = 21585, a(17) = 44824, a(18) = 92686, a(19) = 190975, a(20) = 392272, a(21) = 803553, a(22) = 1642148, a(23) = 3348847, a(24) = 6816665, a(25) = 13852607, a(26) = 28109365 Lemma , 3.2, : Let b(n) be the number of words of length n in the alphabet , {1, 2}, with more occurences of, {[1, 1, 1, 1]}, then , {[1, 1, 1, 2]} b(n) satisfies the following linear recurrence equation with polynomial coef\ ficients of order, 13 2 12 (n + 4) (n + 1) b(n) 6 (n + 5 n + 8) b(n + 1) - ----------------------- - ------------------------- (n + 13) (n + 9) (n + 13) (n + 9) 2 (n + 3) (5 n - 8) b(n + 2) (47 n + 451 n + 1092) b(n + 3) - -------------------------- + 1/2 ------------------------------- (n + 13) (n + 9) (n + 13) (n + 9) 2 2 (26 n + 261 n + 610) b(n + 4) (4 n - 3 n - 145) b(n + 5) - 1/2 ------------------------------ + 1/2 --------------------------- (n + 13) (n + 9) (n + 13) (n + 9) 2 (16 n + 343 n + 1632) b(n + 6) - 1/2 ------------------------------- (n + 13) (n + 9) 2 (40 n + 629 n + 2413) b(n + 7) + 1/2 ------------------------------- (n + 13) (n + 9) 2 2 (36 n + 547 n + 2054) b(n + 8) (2 n + 39 n + 219) b(n + 9) - 1/2 ------------------------------- + 1/2 ---------------------------- (n + 13) (n + 9) (n + 13) (n + 9) 2 2 (2 n + 37 n + 188) b(n + 10) (13 n + 252 n + 1163) b(n + 11) + 1/2 ----------------------------- + 1/2 -------------------------------- (n + 13) (n + 9) (n + 13) (n + 9) 2 (5 n + 104 n + 522) b(n + 12) - ------------------------------ + b(n + 13) = 0 (n + 13) (n + 9) Subject to the initial conditions b(1) = 0, b(2) = 0, b(3) = 0, b(4) = 1, b(5) = 2, b(6) = 5, b(7) = 12, b(8) = 27, b(9) = 62, b(10) = 136, b(11) = 296, b(12) = 638, b(13) = 1360 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.070537 1/2 - -------- 1/2 n The probability of Bob winning the bet, as n grows larger is approximately 1.058 1/2 - ----- 1/2 n You can see that indeed Alice has a better chance, but not significantly so. ----------------------------------------- This took, 37.410, seconds to generate ----------------------------------------------------------------------------\ ----------------------- Question Mumber, 4, : If Alice bets that there are more occurrences of consec\ utive substrings in, {[1, 1, 2, 1]}, than in, {[1, 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}, with more occurences of, {[1, 1, 2, 1]}, then , {[1, 1, 1, 1]} a(n) satisfies the following linear recurrence equation with polynomial coef\ ficients of order, 23 108 (n + 1) (n + 2) (n + 3) a(n) 18 (5 n - 8) (n + 3) (n + 2) a(n + 1) - -------------------------------- + ------------------------------------- (n + 20) (n + 19) (n + 23) (n + 20) (n + 19) (n + 23) 2 9 (n + 3) (3 n - 136 n - 486) a(n + 2) - --------------------------------------- (n + 20) (n + 19) (n + 23) 3 2 (929 n + 16728 n + 97195 n + 180384) a(n + 3) + 3/2 ----------------------------------------------- (n + 20) (n + 19) (n + 23) 3 2 (2919 n + 61069 n + 404414 n + 859080) a(n + 4) - 3/2 ------------------------------------------------- (n + 20) (n + 19) (n + 23) 3 2 3 (2503 n + 52430 n + 354549 n + 780372) a(n + 5) + --------------------------------------------------- (n + 20) (n + 19) (n + 23) 3 2 (11509 n + 196683 n + 912944 n + 716016) a(n + 6) - 1/2 --------------------------------------------------- (n + 20) (n + 19) (n + 23) 3 2 (6379 n + 274786 n + 3311107 n + 12129000) a(n + 7) - 1/2 ----------------------------------------------------- (n + 20) (n + 19) (n + 23) 3 2 (13231 n + 404682 n + 4028539 n + 13111554) a(n + 8) + ------------------------------------------------------ (n + 20) (n + 19) (n + 23) 3 2 (43571 n + 1340529 n + 13406095 n + 43661151) a(n + 9) - 1/3 -------------------------------------------------------- (n + 20) (n + 19) (n + 23) 3 2 (14137 n + 473355 n + 5062871 n + 17353992) a(n + 10) + 1/3 ------------------------------------------------------- (n + 20) (n + 19) (n + 23) 3 2 (31093 n + 962520 n + 9998447 n + 34970628) a(n + 11) + 1/6 ------------------------------------------------------- (n + 20) (n + 19) (n + 23) 3 2 (36862 n + 1204185 n + 13159061 n + 48384168) a(n + 12) - 1/6 --------------------------------------------------------- (n + 20) (n + 19) (n + 23) 3 2 (3277 n + 112227 n + 1345416 n + 5760706) a(n + 13) + 1/2 ----------------------------------------------------- (n + 20) (n + 19) (n + 23) 3 2 (11153 n + 365859 n + 3603832 n + 9419928) a(n + 14) + 1/6 ------------------------------------------------------ (n + 20) (n + 19) (n + 23) 3 2 (13609 n + 475785 n + 5208548 n + 17116026) a(n + 15) - 1/6 ------------------------------------------------------- (n + 20) (n + 19) (n + 23) 3 2 (2165 n + 81975 n + 999684 n + 3889716) a(n + 16) + 1/2 --------------------------------------------------- (n + 20) (n + 19) (n + 23) 3 2 (1358 n + 60405 n + 906109 n + 4615698) a(n + 17) - 1/6 --------------------------------------------------- (n + 20) (n + 19) (n + 23) 3 2 (9 n + 1382 n + 39477 n + 314290) a(n + 18) + 1/2 --------------------------------------------- (n + 20) (n + 19) (n + 23) 3 2 (293 n + 15630 n + 278767 n + 1664322) a(n + 19) + 1/6 -------------------------------------------------- (n + 20) (n + 19) (n + 23) 3 2 (133 n + 7577 n + 143668 n + 906828) a(n + 20) - 1/2 ------------------------------------------------ (n + 20) (n + 19) (n + 23) 3 2 (229 n + 13380 n + 260021 n + 1681086) a(n + 21) + 1/6 -------------------------------------------------- (n + 20) (n + 19) (n + 23) 2 (10 n + 411 n + 4198) a(n + 22) - -------------------------------- + a(n + 23) = 0 (n + 23) (n + 20) Subject to the initial conditions a(1) = 0, a(2) = 0, a(3) = 0, a(4) = 1, a(5) = 4, a(6) = 11, a(7) = 26, a(8) = 59, a(9) = 133, a(10) = 293, a(11) = 632, a(12) = 1340, a(13) = 2818, a(14) = 5888, a(15) = 12224, a(16) = 25228, a(17) = 51823, a(18) = 106094, a(19) = 216560, a(20) = 440879, a(21) = 895460, a(22) = 1815261, a(23) = 3673951 Lemma , 4.2, : Let b(n) be the number of words of length n in the alphabet , {1, 2}, with more occurences of, {[1, 1, 1, 1]}, then , {[1, 1, 2, 1]} b(n) satisfies the following linear recurrence equation with polynomial coef\ ficients of order, 17 180 (n + 1) (n + 2) (n + 3) b(n) 90 (7 n + 24) (n + 3) (n + 2) b(n + 1) - -------------------------------- + -------------------------------------- (n + 13) (n + 17) (n + 16) (n + 13) (n + 17) (n + 16) 2 9 (n + 3) (49 n + 284 n + 262) b(n + 2) - ---------------------------------------- (n + 13) (n + 17) (n + 16) 3 2 (301 n + 4620 n + 23243 n + 38016) b(n + 3) - 3/2 --------------------------------------------- (n + 13) (n + 17) (n + 16) 2 (n + 6) (301 n + 1657 n + 712) b(n + 4) + 3/2 ---------------------------------------- (n + 13) (n + 17) (n + 16) 3 2 (5 n + 332 n + 2795 n + 5840) b(n + 5) + 9/2 ---------------------------------------- (n + 13) (n + 17) (n + 16) 3 2 (196 n + 8592 n + 94925 n + 309540) b(n + 6) + ---------------------------------------------- (n + 13) (n + 17) (n + 16) 3 2 (657 n + 25940 n + 277927 n + 901404) b(n + 7) - 1/2 ------------------------------------------------ (n + 13) (n + 17) (n + 16) 3 2 (10 n + 709 n - 1971 n - 62124) b(n + 8) + 1/2 ------------------------------------------ (n + 13) (n + 17) (n + 16) 3 2 (492 n + 18831 n + 226801 n + 876098) b(n + 9) + 1/2 ------------------------------------------------ (n + 13) (n + 17) (n + 16) 3 2 (205 n + 7231 n + 82511 n + 306762) b(n + 10) - ----------------------------------------------- (n + 13) (n + 17) (n + 16) 3 2 (32 n + 1511 n + 21647 n + 97322) b(n + 11) - 1/2 --------------------------------------------- (n + 13) (n + 17) (n + 16) 3 2 (289 n + 10155 n + 117682 n + 448876) b(n + 12) + 1/2 ------------------------------------------------- (n + 13) (n + 17) (n + 16) 3 2 (168 n + 5893 n + 67995 n + 257178) b(n + 13) - 1/2 ----------------------------------------------- (n + 13) (n + 17) (n + 16) 3 2 (7 n + 472 n + 8779 n + 49522) b(n + 14) - 1/2 ------------------------------------------ (n + 13) (n + 17) (n + 16) 3 2 (21 n + 897 n + 12698 n + 59512) b(n + 15) + -------------------------------------------- (n + 13) (n + 17) (n + 16) 2 (8 n + 225 n + 1563) b(n + 16) - ------------------------------- + b(n + 17) = 0 (n + 17) (n + 13) Subject to the initial conditions b(1) = 0, b(2) = 0, b(3) = 0, b(4) = 1, b(5) = 3, b(6) = 7, b(7) = 16, b(8) = 37, b(9) = 85, b(10) = 186, b(11) = 400, b(12) = 852, b(13) = 1809, b(14) = 3810, b(15) = 7959, b(16) = 16538, b(17) = 34236 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.1152 1/2 - ------ 1/2 n The probability of Bob winning the bet, as n grows larger is approximately 0.8063 1/2 - ------ 1/2 n You can see that indeed Alice has a better chance, but not significantly so. ----------------------------------------- This took, 38.970, seconds to generate ----------------------------------------------------------------------------\ ----------------------- Question Mumber, 5, : If Alice bets that there are more occurrences of consec\ utive substrings in, {[1, 1, 2, 2]}, than in, {[1, 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}, with more occurences of, {[1, 1, 2, 2]}, then , {[1, 1, 1, 1]} a(n) satisfies the following linear recurrence equation with polynomial coef\ ficients of order, 33 2 (n + 28) (18 n + 941 n + 12001) a(n + 30) ------------------------------------------ (n + 30) (n + 29) (n + 33) 3 2 (193 n + 16188 n + 450299 n + 4152768) a(n + 29) - 1/6 -------------------------------------------------- (n + 30) (n + 29) (n + 33) 3 2 (67 n + 6120 n + 186029 n + 1881816) a(n + 31) + 1/6 ------------------------------------------------ (n + 30) (n + 29) (n + 33) 2 (n + 3) (65 n + 669 n + 1732) a(n + 2) - 16/3 --------------------------------------- (n + 30) (n + 29) (n + 33) (n + 1) (n + 2) (n + 3) a(n) 64 (n + 4) (n + 3) (n + 2) a(n + 1) + 64/3 ---------------------------- - ----------------------------------- (n + 30) (n + 29) (n + 33) (n + 30) (n + 29) (n + 33) 2 (7 n + 431 n + 6620) a(n + 32) - ------------------------------- (n + 33) (n + 30) 3 2 8 (n + 278 n + 2695 n + 6426) a(n + 3) - ---------------------------------------- (n + 30) (n + 29) (n + 33) 3 2 (761 n + 11448 n + 54721 n + 81822) a(n + 4) + 4/3 ---------------------------------------------- (n + 30) (n + 29) (n + 33) 3 2 (247 n + 3852 n + 15722 n + 8331) a(n + 5) + 4/3 -------------------------------------------- (n + 30) (n + 29) (n + 33) 3 2 (509 n - 9330 n - 196331 n - 740592) a(n + 6) - 1/3 ----------------------------------------------- (n + 30) (n + 29) (n + 33) 3 2 (9391 n + 313200 n + 3386945 n + 11842176) a(n + 7) + 1/6 ----------------------------------------------------- (n + 30) (n + 29) (n + 33) 3 2 (2435 n + 108000 n + 1210573 n + 3906660) a(n + 8) - 1/3 ---------------------------------------------------- (n + 30) (n + 29) (n + 33) 3 2 (24997 n + 941640 n + 11528759 n + 45957540) a(n + 9) - 1/6 ------------------------------------------------------- (n + 30) (n + 29) (n + 33) 3 2 (2605 n + 91980 n + 1433717 n + 8062158) a(n + 10) - 1/3 ---------------------------------------------------- (n + 30) (n + 29) (n + 33) 3 2 (17071 n + 698586 n + 9309011 n + 40493064) a(n + 11) + 1/3 ------------------------------------------------------- (n + 30) (n + 29) (n + 33) 3 2 (11120 n + 572733 n + 9495061 n + 50948760) a(n + 12) + 1/3 ------------------------------------------------------- (n + 30) (n + 29) (n + 33) 3 2 (37795 n + 1580868 n + 21677873 n + 97399968) a(n + 13) - 1/6 --------------------------------------------------------- (n + 30) (n + 29) (n + 33) 3 2 (5798 n + 340512 n + 6251734 n + 36722019) a(n + 14) - 2/3 ------------------------------------------------------ (n + 30) (n + 29) (n + 33) 3 2 (11355 n + 497904 n + 7225953 n + 34720196) a(n + 15) + 1/2 ------------------------------------------------------- + a(n + 33) (n + 30) (n + 29) (n + 33) 3 2 (28177 n + 1443462 n + 24234953 n + 133528728) a(n + 16) + 1/6 ---------------------------------------------------------- (n + 30) (n + 29) (n + 33) 3 2 (12379 n + 556902 n + 8324765 n + 41571546) a(n + 17) - 1/3 ------------------------------------------------------- (n + 30) (n + 29) (n + 33) 3 2 (5588 n + 282845 n + 4653937 n + 24693084) a(n + 18) - ------------------------------------------------------ (n + 30) (n + 29) (n + 33) 3 2 (13165 n + 630888 n + 9899243 n + 50748696) a(n + 19) + 1/6 ------------------------------------------------------- (n + 30) (n + 29) (n + 33) 3 2 (9901 n + 533307 n + 9345992 n + 52782168) a(n + 20) + 1/3 ------------------------------------------------------ (n + 30) (n + 29) (n + 33) 3 2 (343 n + 27765 n + 714818 n + 5873448) a(n + 21) - 1/3 -------------------------------------------------- (n + 30) (n + 29) (n + 33) 3 2 (2903 n + 137619 n + 1914142 n + 6453642) a(n + 22) - 1/3 ----------------------------------------------------- (n + 30) (n + 29) (n + 33) 3 2 (2851 n + 166890 n + 3109607 n + 18009588) a(n + 23) - 1/6 ------------------------------------------------------ (n + 30) (n + 29) (n + 33) 3 2 (1441 n + 44028 n - 272209 n - 11919144) a(n + 24) + 1/6 ---------------------------------------------------- (n + 30) (n + 29) (n + 33) 3 2 (59 n + 3244 n + 65273 n + 524304) a(n + 25) - 1/2 ---------------------------------------------- (n + 30) (n + 29) (n + 33) 3 2 (115 n + 13320 n + 454415 n + 4827444) a(n + 26) + 1/3 -------------------------------------------------- (n + 30) (n + 29) (n + 33) 3 2 (319 n + 23984 n + 600633 n + 5013848) a(n + 27) + 1/2 -------------------------------------------------- (n + 30) (n + 29) (n + 33) 3 2 2 (49 n + 3826 n + 99640 n + 866182) a(n + 28) - ------------------------------------------------ = 0 (n + 30) (n + 29) (n + 33) Subject to the initial conditions a(1) = 0, a(2) = 0, a(3) = 0, a(4) = 1, a(5) = 4, a(6) = 11, a(7) = 28, a(8) = 66, a(9) = 148, a(10) = 325, a(11) = 700, a(12) = 1484, a(13) = 3115, a(14) = 6483, a(15) = 13397, a(16) = 27540, a(17) = 56365, a(18) = 114934, a(19) = 233671, a(20) = 473895, a(21) = 959064, a(22) = 1937574, a(23) = 3908687, a(24) = 7875203, a(25) = 15850255, a(26) = 31872995, a(27) = 64044070, a(28) = 128603849, a(29) = 258100711, a(30) = 517749182, a(31) = 1038184358, a(32) = 2081036022, a(33) = 4170193503 Lemma , 5.2, : Let b(n) be the number of words of length n in the alphabet , {1, 2}, with more occurences of, {[1, 1, 1, 1]}, then , {[1, 1, 2, 2]} b(n) satisfies the following linear recurrence equation with polynomial coef\ ficients of order, 13 8 (n + 3) (n + 1) b(n) 2 (n + 4) (3 n + 7) b(n + 1) - ---------------------- - ---------------------------- (n + 13) (n + 9) (n + 13) (n + 9) 2 2 (17 n + 127 n + 226) b(n + 2) (11 n + 227 n + 748) b(n + 3) + ------------------------------ + 1/2 ------------------------------ (n + 13) (n + 9) (n + 13) (n + 9) 2 2 (83 n + 995 n + 2780) b(n + 4) (5 n + 175 n + 872) b(n + 5) - 1/4 ------------------------------- - 1/2 ----------------------------- (n + 13) (n + 9) (n + 13) (n + 9) 2 2 (44 n + 653 n + 2374) b(n + 6) (7 n + 157 n + 822) b(n + 7) + 1/2 ------------------------------- - 1/2 ----------------------------- (n + 13) (n + 9) (n + 13) (n + 9) 2 2 (23 n + 350 n + 1330) b(n + 8) (3 n + 8 n - 237) b(n + 9) - 1/2 ------------------------------- - 1/2 --------------------------- (n + 13) (n + 9) (n + 13) (n + 9) 2 (8 n + 109 n + 276) b(n + 10) + 1/2 ------------------------------ (n + 13) (n + 9) 2 (10 n + 211 n + 1083) b(n + 11) + 1/2 -------------------------------- (n + 13) (n + 9) 2 (19 n + 401 n + 2052) b(n + 12) - 1/4 -------------------------------- + b(n + 13) = 0 (n + 13) (n + 9) Subject to the initial conditions b(1) = 0, b(2) = 0, b(3) = 0, b(4) = 1, b(5) = 3, b(6) = 7, b(7) = 17, b(8) = 39, b(9) = 86, b(10) = 189, b(11) = 408, b(12) = 868, b(13) = 1835 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.0575832 1/2 - --------- 1/2 n The probability of Bob winning the bet, as n grows larger is approximately 0.8638 1/2 - ------ 1/2 n You can see that indeed Alice has a better chance, but not significantly so. ----------------------------------------- This took, 46.949, seconds to generate ----------------------------------------------------------------------------\ ----------------------- Question Mumber, 6, : If Alice bets that there are more occurrences of consec\ utive substrings in, {[1, 2, 1, 2]}, than in, {[1, 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}, with more occurences of, {[1, 2, 1, 2]}, then , {[1, 1, 1, 1]} a(n) satisfies the following linear recurrence equation with polynomial coef\ ficients of order, 34 2 1024 (n - 1) (n + 2) (n + 1) a(n) (6 n + 383 n + 6101) a(n + 33) a(n + 34) + --------------------------------- - ------------------------------- (n + 30) (n + 34) (n + 31) (n + 34) (n + 31) 3 2 (871 n + 43517 n + 538200 n - 100288) a(n + 26) - 1/2 ------------------------------------------------- (n + 30) (n + 34) (n + 31) 3 2 (455 n + 42942 n + 1309707 n + 13008736) a(n + 27) - 1/2 ---------------------------------------------------- (n + 30) (n + 34) (n + 31) 3 2 (127 n + 11570 n + 346983 n + 3431320) a(n + 28) + -------------------------------------------------- (n + 30) (n + 34) (n + 31) 3 2 (135 n + 11884 n + 347561 n + 3377250) a(n + 29) - -------------------------------------------------- (n + 30) (n + 34) (n + 31) 3 2 (195 n + 17003 n + 493770 n + 4775540) a(n + 30) + 1/2 -------------------------------------------------- (n + 30) (n + 34) (n + 31) 3 2 (27 n + 2507 n + 77524 n + 798392) a(n + 32) + 1/2 ---------------------------------------------- (n + 30) (n + 34) (n + 31) 3 2 (1897 n + 36201 n + 212672 n + 387678) a(n + 5) + 64/3 ------------------------------------------------- (n + 30) (n + 34) (n + 31) 3 2 (8275 n + 162849 n + 1036427 n + 2125953) a(n + 6) - 32/3 ---------------------------------------------------- (n + 30) (n + 34) (n + 31) 3 2 (25163 n + 588849 n + 4507570 n + 11257410) a(n + 7) + 16/3 ------------------------------------------------------ (n + 30) (n + 34) (n + 31) 3 2 4 (46913 n + 1176980 n + 9696507 n + 26200448) a(n + 8) - --------------------------------------------------------- (n + 30) (n + 34) (n + 31) 3 2 (218297 n + 5999796 n + 54649183 n + 164718012) a(n + 9) + 4/3 ---------------------------------------------------------- (n + 30) (n + 34) (n + 31) 3 2 (113102 n + 3395283 n + 33850909 n + 111989886) a(n + 10) - 8/3 ----------------------------------------------------------- (n + 30) (n + 34) (n + 31) 3 2 2 (190329 n + 6149140 n + 65959175 n + 234800892) a(n + 11) + ------------------------------------------------------------- (n + 30) (n + 34) (n + 31) 3 2 (416799 n + 14306784 n + 163382805 n + 620933612) a(n + 12) - ------------------------------------------------------------- (n + 30) (n + 34) (n + 31) 3 2 (1126037 n + 41435904 n + 507282943 n + 2066779500) a(n + 13) + 1/3 --------------------------------------------------------------- (n + 30) (n + 34) (n + 31) 3 2 (1180597 n + 46215282 n + 601105265 n + 2599177512) a(n + 14) - 1/3 --------------------------------------------------------------- (n + 30) (n + 34) (n + 31) 3 2 (2007365 n + 82194462 n + 1117457101 n + 5048723712) a(n + 15) + 1/6 ---------------------------------------------------------------- (n + 30) (n + 34) (n + 31) 3 2 (270460 n + 11797763 n + 170884771 n + 822548462) a(n + 16) - ------------------------------------------------------------- (n + 30) (n + 34) (n + 31) 3 2 (1375753 n + 63085542 n + 958637963 n + 4830201690) a(n + 17) + 1/6 --------------------------------------------------------------- (n + 30) (n + 34) (n + 31) 3 2 (315727 n + 15051437 n + 237325124 n + 1238045088) a(n + 18) - 1/2 -------------------------------------------------------------- (n + 30) (n + 34) (n + 31) 3 2 (671683 n + 34017654 n + 570293099 n + 3165613764) a(n + 19) + 1/6 -------------------------------------------------------------- (n + 30) (n + 34) (n + 31) 3 2 (225989 n + 11902635 n + 206915134 n + 1186535592) a(n + 20) - 1/3 -------------------------------------------------------------- (n + 30) (n + 34) (n + 31) 3 2 (61775 n + 3363747 n + 60279037 n + 354926412) a(n + 21) + 2/3 ---------------------------------------------------------- (n + 30) (n + 34) (n + 31) 3 2 (148669 n + 8583561 n + 163422170 n + 1024805400) a(n + 22) - 1/6 ------------------------------------------------------------- (n + 30) (n + 34) (n + 31) 3 2 (37105 n + 2186004 n + 42187625 n + 265650528) a(n + 23) + 1/3 ---------------------------------------------------------- (n + 30) (n + 34) (n + 31) 3 2 (9081 n + 537089 n + 10269924 n + 62726140) a(n + 24) - 1/2 ------------------------------------------------------- (n + 30) (n + 34) (n + 31) 3 2 (4321 n + 270334 n + 5492839 n + 35917878) a(n + 25) + 1/2 ------------------------------------------------------ (n + 30) (n + 34) (n + 31) 3 2 (n + 123 n + 461 n + 327) a(n + 2) - 512/3 ------------------------------------ (n + 30) (n + 34) (n + 31) 3 2 256 (17 n + 221 n + 760 n + 698) a(n + 3) + ------------------------------------------- (n + 30) (n + 34) (n + 31) 3 2 (514 n + 8733 n + 44492 n + 68445) a(n + 4) - 128/3 --------------------------------------------- (n + 30) (n + 34) (n + 31) 2 (n + 2) (2 n - 7 n - 3) a(n + 1) - 1024/3 --------------------------------- (n + 30) (n + 34) (n + 31) 2 (5 n + 149) (13 n + 777 n + 11596) a(n + 31) - 1/2 --------------------------------------------- = 0 (n + 30) (n + 34) (n + 31) Subject to the initial conditions a(1) = 0, a(2) = 0, a(3) = 0, a(4) = 1, a(5) = 4, a(6) = 11, a(7) = 27, a(8) = 63, a(9) = 142, a(10) = 310, a(11) = 665, a(12) = 1411, a(13) = 2958, a(14) = 6148, a(15) = 12708, a(16) = 26126, a(17) = 53466, a(18) = 109063, a(19) = 221850, a(20) = 450129, a(21) = 911492, a(22) = 1842745, a(23) = 3719991, a(24) = 7500406, a(25) = 15107538, a(26) = 30403345, a(27) = 61138743, a(28) = 122866932, a(29) = 246783216, a(30) = 495434834, a(31) = 994210356, a(32) = 1994420285, a(33) = 3999634122, a(34) = 8018744709 Lemma , 6.2, : Let b(n) be the number of words of length n in the alphabet , {1, 2}, with more occurences of, {[1, 1, 1, 1]}, then , {[1, 2, 1, 2]} b(n) satisfies the following linear recurrence equation with polynomial coef\ ficients of order, 28 192 (n - 2) (n + 2) (n + 1) b(n) b(n + 28) - -------------------------------- (n + 24) (n + 28) (n + 26) 3 2 (27888 n + 1315390 n + 20600541 n + 107124017) b(n + 17) - 3/4 ---------------------------------------------------------- (n + 24) (n + 28) (n + 26) 3 2 (35309 n + 1760115 n + 29146500 n + 160327752) b(n + 18) + 3/8 ---------------------------------------------------------- (n + 24) (n + 28) (n + 26) 3 2 (21759 n + 1151150 n + 20227143 n + 118023264) b(n + 19) - 3/8 ---------------------------------------------------------- (n + 24) (n + 28) (n + 26) 3 2 (19580 n + 1090473 n + 20172862 n + 123933744) b(n + 20) + 1/4 ---------------------------------------------------------- (n + 24) (n + 28) (n + 26) 3 2 (10061 n + 590118 n + 11500873 n + 74456964) b(n + 21) - 1/4 -------------------------------------------------------- (n + 24) (n + 28) (n + 26) 3 2 (1624 n + 100459 n + 2064841 n + 14097640) b(n + 22) + 3/4 ------------------------------------------------------ (n + 24) (n + 28) (n + 26) 3 2 (776 n + 50292 n + 1083505 n + 7758289) b(n + 23) - 3/4 --------------------------------------------------- (n + 24) (n + 28) (n + 26) 3 2 (627 n + 42463 n + 956416 n + 7163220) b(n + 24) + 3/8 -------------------------------------------------- (n + 24) (n + 28) (n + 26) 3 2 (108 n + 7651 n + 180316 n + 1413585) b(n + 25) - 3/4 ------------------------------------------------- (n + 24) (n + 28) (n + 26) 3 2 (221 n + 16323 n + 401218 n + 3281784) b(n + 26) + 1/8 -------------------------------------------------- (n + 24) (n + 28) (n + 26) 3 2 (61 n + 4650 n + 117959 n + 995754) b(n + 27) - 1/8 ----------------------------------------------- (n + 24) (n + 28) (n + 26) 3 2 8 (137 n + 135 n - 1076 n - 864) b(n + 2) - ------------------------------------------- (n + 24) (n + 28) (n + 26) 3 2 12 (33 n - 651 n - 3404 n - 1888) b(n + 3) + -------------------------------------------- (n + 24) (n + 28) (n + 26) 3 2 6 (133 n + 2383 n + 8758 n + 3768) b(n + 4) + --------------------------------------------- (n + 24) (n + 28) (n + 26) 3 2 3 (881 n + 17529 n + 102002 n + 172320) b(n + 5) - -------------------------------------------------- (n + 24) (n + 28) (n + 26) 3 2 (4643 n + 116301 n + 827704 n + 1702064) b(n + 6) + 3/2 --------------------------------------------------- (n + 24) (n + 28) (n + 26) 3 2 (24365 n + 588969 n + 4368488 n + 9846304) b(n + 7) - 3/4 ----------------------------------------------------- (n + 24) (n + 28) (n + 26) 3 2 (246851 n + 6359853 n + 52278442 n + 135988176) b(n + 8) + 1/8 ---------------------------------------------------------- (n + 24) (n + 28) (n + 26) 3 2 (145537 n + 4248183 n + 39717380 n + 118235304) b(n + 9) - 1/4 ---------------------------------------------------------- (n + 24) (n + 28) (n + 26) 3 2 (123979 n + 3888869 n + 39457580 n + 128934080) b(n + 10) + 3/8 ----------------------------------------------------------- (n + 24) (n + 28) (n + 26) 3 2 (149337 n + 4910546 n + 52980149 n + 186944708) b(n + 11) - 3/8 ----------------------------------------------------------- (n + 24) (n + 28) (n + 26) 3 2 (140573 n + 4957283 n + 57681086 n + 220857024) b(n + 12) + 3/8 ----------------------------------------------------------- (n + 24) (n + 28) (n + 26) 3 2 (67491 n + 2543602 n + 31702581 n + 130462510) b(n + 13) - 3/4 ---------------------------------------------------------- (n + 24) (n + 28) (n + 26) 3 2 (126101 n + 4992909 n + 65546788 n + 285136400) b(n + 14) + 3/8 ----------------------------------------------------------- (n + 24) (n + 28) (n + 26) 3 2 (292331 n + 12268212 n + 171003181 n + 791531604) b(n + 15) - 1/8 ------------------------------------------------------------- (n + 24) (n + 28) (n + 26) 3 2 (224545 n + 10049115 n + 149350280 n + 737012268) b(n + 16) + 1/8 ------------------------------------------------------------- (n + 24) (n + 28) (n + 26) 2 48 (n + 2) (17 n + 15 n - 48) b(n + 1) + --------------------------------------- = 0 (n + 24) (n + 28) (n + 26) Subject to the initial conditions b(1) = 0, b(2) = 0, b(3) = 0, b(4) = 1, b(5) = 3, b(6) = 8, b(7) = 19, b(8) = 44, b(9) = 99, b(10) = 216, b(11) = 466, b(12) = 994, b(13) = 2095, b(14) = 4386, b(15) = 9132, b(16) = 18905, b(17) = 38972, b(18) = 80083, b(19) = 164053, b(20) = 335175, b(21) = 683373, b(22) = 1390709, b(23) = 2825383, b(24) = 5732001, b(25) = 11614650, b(26) = 23508295, b(27) = 47534859, b(28) = 96036524 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.1496 1/2 - ------ 1/2 n The probability of Bob winning the bet, as n grows larger is approximately 0.6484 1/2 - ------ 1/2 n You can see that indeed Alice has a better chance, but not significantly so. ----------------------------------------- This took, 69.790, seconds to generate ----------------------------------------------------------------------------\ ----------------------- Question Mumber, 7, : If Alice bets that there are more occurrences of consec\ utive substrings in, {[1, 2, 2, 2]}, than in, {[1, 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 , 7.1, : Let a(n) be the number of words of length n in the alphabet , {1, 2}, with more occurences of, {[1, 2, 2, 2]}, then , {[1, 1, 1, 1]} a(n) satisfies the following linear recurrence equation with polynomial coef\ ficients of order, 30 3 2 8 (n + 164 n + 1169 n + 2126) a(n + 3) a(n + 30) + ---------------------------------------- (n + 30) (n + 27) (n + 26) 3 2 8 (53 n + 387 n - 26 n - 3270) a(n + 4) + ----------------------------------------- (n + 30) (n + 27) (n + 26) 3 2 (409 n - 2592 n - 74161 n - 265080) a(n + 5) - 2/3 ---------------------------------------------- (n + 30) (n + 27) (n + 26) 3 2 2 (314 n + 6981 n + 56431 n + 159980) a(n + 6) + ------------------------------------------------ (n + 30) (n + 27) (n + 26) 3 2 (3260 n + 89631 n + 819925 n + 2489706) a(n + 7) - 2/3 -------------------------------------------------- (n + 30) (n + 27) (n + 26) 3 2 (7795 n + 182184 n + 1465613 n + 4109280) a(n + 8) + 1/6 ---------------------------------------------------- (n + 30) (n + 27) (n + 26) 3 2 (11368 n + 348369 n + 3280997 n + 9399516) a(n + 9) + 1/6 ----------------------------------------------------- (n + 30) (n + 27) (n + 26) 3 2 (1247 n - 4025 n - 640508 n - 4869616) a(n + 10) - 1/2 -------------------------------------------------- (n + 30) (n + 27) (n + 26) 2 (n + 3) (43 n + 447 n + 1064) a(n + 2) - 16/3 --------------------------------------- (n + 30) (n + 27) (n + 26) 3 2 (4601 n + 197370 n + 2883557 n + 14111892) a(n + 11) - 1/2 ------------------------------------------------------ (n + 30) (n + 27) (n + 26) 3 2 (12215 n + 511107 n + 6362536 n + 23354688) a(n + 12) - 1/6 ------------------------------------------------------- (n + 30) (n + 27) (n + 26) 3 2 4 (1763 n + 78461 n + 1129606 n + 5285864) a(n + 13) + ------------------------------------------------------ (n + 30) (n + 27) (n + 26) 3 2 (4821 n + 250117 n + 4141498 n + 22161002) a(n + 14) - ------------------------------------------------------ (n + 30) (n + 27) (n + 26) 3 2 (12589 n + 717072 n + 12757523 n + 72383244) a(n + 15) + 1/6 -------------------------------------------------------- (n + 30) (n + 27) (n + 26) 3 2 (12616 n + 528843 n + 7104191 n + 30016968) a(n + 16) - 1/6 ------------------------------------------------------- (n + 30) (n + 27) (n + 26) 3 2 (2548 n + 101031 n + 1299495 n + 5466076) a(n + 17) + 1/2 ----------------------------------------------------- (n + 30) (n + 27) (n + 26) 3 2 (2509 n + 136215 n + 2678474 n + 18811068) a(n + 18) - 1/6 ------------------------------------------------------ (n + 30) (n + 27) (n + 26) 3 2 (1629 n + 73448 n + 1050327 n + 4647608) a(n + 19) + 1/2 ---------------------------------------------------- (n + 30) (n + 27) (n + 26) 3 2 (8971 n + 399351 n + 5313692 n + 18426312) a(n + 20) - 1/6 ------------------------------------------------------ (n + 30) (n + 27) (n + 26) 3 2 (1661 n + 84733 n + 1384546 n + 7105170) a(n + 21) + ---------------------------------------------------- (n + 30) (n + 27) (n + 26) 3 2 (1423 n + 79008 n + 1432511 n + 8435535) a(n + 22) - 2/3 ---------------------------------------------------- (n + 30) (n + 27) (n + 26) 3 2 (147 n + 5272 n + 19605 n - 548484) a(n + 23) + 1/2 ----------------------------------------------- (n + 30) (n + 27) (n + 26) 3 2 (259 n + 17651 n + 399308 n + 2997736) a(n + 24) + 1/2 -------------------------------------------------- (n + 30) (n + 27) (n + 26) 3 2 (7 n + 181 n - 3600 n - 93738) a(n + 25) - ------------------------------------------ (n + 30) (n + 27) (n + 26) 3 2 (13 n + 986 n + 24853 n + 208138) a(n + 26) + --------------------------------------------- (n + 30) (n + 27) (n + 26) 3 2 (55 n + 4285 n + 111140 n + 959716) a(n + 27) - ----------------------------------------------- (n + 30) (n + 27) (n + 26) 3 2 (37 n + 2936 n + 77563 n + 682240) a(n + 28) + ---------------------------------------------- (n + 30) (n + 27) (n + 26) (n + 1) (n + 2) (n + 3) a(n) - 64/3 ---------------------------- (n + 30) (n + 27) (n + 26) (n + 4) (n + 3) (n + 2) a(n + 1) + 320/3 -------------------------------- (n + 30) (n + 27) (n + 26) 2 (10 n + 551 n + 7565) a(n + 29) - -------------------------------- = 0 (n + 27) (n + 30) Subject to the initial conditions a(1) = 0, a(2) = 0, a(3) = 0, a(4) = 1, a(5) = 4, a(6) = 12, a(7) = 31, a(8) = 74, a(9) = 168, a(10) = 368, a(11) = 789, a(12) = 1663, a(13) = 3463, a(14) = 7147, a(15) = 14649, a(16) = 29869, a(17) = 60654, a(18) = 122782, a(19) = 247931, a(20) = 499667, a(21) = 1005458, a(22) = 2020775, a(23) = 4057448, a(24) = 8140568, a(25) = 16322685, a(26) = 32712777, a(27) = 65535263, a(28) = 131249786, a(29) = 262793810, a(30) = 526073271 Lemma , 7.2, : Let b(n) be the number of words of length n in the alphabet , {1, 2}, with more occurences of, {[1, 1, 1, 1]}, then , {[1, 2, 2, 2]} b(n) satisfies the following linear recurrence equation with polynomial coef\ ficients of order, 15 4 (n + 1) (n + 2) b(n) 2 (n + 2) (n - 3) b(n + 1) - ---------------------- + -------------------------- (n + 15) (n + 11) (n + 15) (n + 11) 2 (n + 7) (n + 2) b(n + 2) (33 n + 433 n + 1202) b(n + 3) + ------------------------ + 1/2 ------------------------------- (n + 15) (n + 11) (n + 15) (n + 11) 2 2 3 (10 n + 116 n + 319) b(n + 4) (29 n + 331 n + 938) b(n + 5) - -------------------------------- + 1/4 ------------------------------ (n + 15) (n + 11) (n + 15) (n + 11) 2 2 (19 n + 45 n - 598) b(n + 6) (47 n + 789 n + 3252) b(n + 7) + 1/4 ----------------------------- + 1/2 ------------------------------- (n + 15) (n + 11) (n + 15) (n + 11) 2 2 (25 n + 455 n + 2104) b(n + 8) (10 n + 175 n + 766) b(n + 9) - 1/2 ------------------------------- - ------------------------------ (n + 15) (n + 11) (n + 15) (n + 11) 2 (22 n + 391 n + 1620) b(n + 10) - 1/2 -------------------------------- (n + 15) (n + 11) 2 2 (24 n + 437 n + 1865) b(n + 11) (n + 30 n + 212) b(n + 12) + 1/2 -------------------------------- + 3/2 --------------------------- (n + 15) (n + 11) (n + 15) (n + 11) 2 2 (7 n + 183 n + 1164) b(n + 13) (5 n + 127 n + 790) b(n + 14) + 1/4 ------------------------------- - 3/4 ------------------------------ (n + 15) (n + 11) (n + 15) (n + 11) + b(n + 15) = 0 Subject to the initial conditions b(1) = 0, b(2) = 0, b(3) = 0, b(4) = 1, b(5) = 3, b(6) = 8, b(7) = 19, b(8) = 44, b(9) = 98, b(10) = 213, b(11) = 458, b(12) = 971, b(13) = 2041, b(14) = 4259, b(15) = 8837 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.053309 1/2 - -------- 1/2 n The probability of Bob winning the bet, as n grows larger is approximately 0.7997 1/2 - ------ 1/2 n You can see that indeed Alice has a better chance, but not significantly so. ----------------------------------------- This took, 44.987, seconds to generate ----------------------------------------------------------------------------\ ----------------------- Question Mumber, 8, : If Alice bets that there are more occurrences of consec\ utive substrings in, {[2, 1, 1, 2]}, than in, {[1, 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 , 8.1, : Let a(n) be the number of words of length n in the alphabet , {1, 2}, with more occurences of, {[2, 1, 1, 2]}, then , {[1, 1, 1, 1]} a(n) satisfies the following linear recurrence equation with polynomial coef\ ficients of order, 23 2 (n - 1) (n - 3) (n + 1) a(n) 32 (n - 2) (27 n + 57 n - 4) a(n + 1) 512/3 ---------------------------- + -------------------------------------- (n + 20) (n + 19) (n + 23) (n + 20) (n + 19) (n + 23) 2 (n - 1) (106 n + 523 n + 264) a(n + 2) + 16/3 --------------------------------------- (n + 20) (n + 19) (n + 23) 2 n (809 n + 3750 n + 3001) a(n + 3) - 8/3 ----------------------------------- (n + 20) (n + 19) (n + 23) 2 (n + 1) (263 n + 2176 n + 3621) a(n + 4) - 16/3 ----------------------------------------- (n + 20) (n + 19) (n + 23) 3 2 (2885 n + 17871 n + 2956 n - 36732) a(n + 5) + 2/3 ---------------------------------------------- (n + 20) (n + 19) (n + 23) 3 2 (3596 n + 46275 n + 199033 n + 290196) a(n + 6) - 1/3 ------------------------------------------------- (n + 20) (n + 19) (n + 23) 3 2 (141 n + 12350 n + 123373 n + 268116) a(n + 7) + 1/2 ------------------------------------------------ (n + 20) (n + 19) (n + 23) 3 2 (18607 n + 313029 n + 1622054 n + 2707140) a(n + 8) + 1/6 ----------------------------------------------------- (n + 20) (n + 19) (n + 23) 3 2 (13639 n + 244392 n + 1325123 n + 2166930) a(n + 9) - 1/6 ----------------------------------------------------- (n + 20) (n + 19) (n + 23) 3 2 (167 n - 4110 n - 119489 n - 543492) a(n + 10) - 1/3 ------------------------------------------------ (n + 20) (n + 19) (n + 23) 3 2 (2085 n + 46632 n + 317431 n + 654464) a(n + 11) + 1/2 -------------------------------------------------- (n + 20) (n + 19) (n + 23) 3 2 (2869 n + 82765 n + 770364 n + 2297612) a(n + 12) - 1/2 --------------------------------------------------- (n + 20) (n + 19) (n + 23) 3 2 (3163 n + 90240 n + 805451 n + 2194830) a(n + 13) + 1/6 --------------------------------------------------- (n + 20) (n + 19) (n + 23) 3 2 (305 n + 10793 n + 121000 n + 419206) a(n + 14) + ------------------------------------------------- (n + 20) (n + 19) (n + 23) 3 2 (1769 n + 60522 n + 655861 n + 2213700) a(n + 15) - 1/6 --------------------------------------------------- (n + 20) (n + 19) (n + 23) 3 2 (289 n + 11139 n + 140578 n + 583028) a(n + 16) + 1/2 ------------------------------------------------- (n + 20) (n + 19) (n + 23) 3 2 (41 n + 672 n - 11051 n - 184002) a(n + 17) - 1/6 --------------------------------------------- (n + 20) (n + 19) (n + 23) 3 2 (50 n + 2193 n + 31339 n + 146010) a(n + 18) - 2/3 ---------------------------------------------- (n + 20) (n + 19) (n + 23) 3 2 (11 n + 779 n + 17206 n + 121096) a(n + 19) - --------------------------------------------- (n + 20) (n + 19) (n + 23) 3 2 2 (5 n + 277 n + 5086 n + 30938) a(n + 20) + -------------------------------------------- (n + 20) (n + 19) (n + 23) 3 2 (8 n + 491 n + 10009 n + 67774) a(n + 21) + ------------------------------------------- (n + 20) (n + 19) (n + 23) 2 (6 n + 251 n + 2614) a(n + 22) - ------------------------------- + a(n + 23) = 0 (n + 23) (n + 20) Subject to the initial conditions a(1) = 0, a(2) = 0, a(3) = 0, a(4) = 1, a(5) = 4, a(6) = 12, a(7) = 31, a(8) = 73, a(9) = 164, a(10) = 357, a(11) = 762, a(12) = 1602, a(13) = 3332, a(14) = 6873, a(15) = 14090, a(16) = 28745, a(17) = 58422, a(18) = 118382, a(19) = 239313, a(20) = 482859, a(21) = 972776, a(22) = 1957357, a(23) = 3934549 Lemma , 8.2, : Let b(n) be the number of words of length n in the alphabet , {1, 2}, with more occurences of, {[1, 1, 1, 1]}, then , {[2, 1, 1, 2]} b(n) satisfies the following linear recurrence equation with polynomial coef\ ficients of order, 19 3 2 (n - 1) (n - 3) (n + 1) b(n) 32 (13 n + 5 n - 58 n + 8) b(n + 1) -512/3 ---------------------------- - ------------------------------------- (n + 15) (n + 19) (n + 18) (n + 15) (n + 19) (n + 18) 3 2 (68 n + 129 n - 77 n - 312) b(n + 2) + 16/3 -------------------------------------- (n + 15) (n + 19) (n + 18) 3 2 8 (61 n + 276 n + 211 n + 304) b(n + 3) + ----------------------------------------- (n + 15) (n + 19) (n + 18) 3 2 (239 n + 1353 n + 1240 n + 6) b(n + 4) - 8/3 ---------------------------------------- (n + 15) (n + 19) (n + 18) 3 2 2 (327 n + 3225 n + 9392 n + 8372) b(n + 5) + --------------------------------------------- (n + 15) (n + 19) (n + 18) 3 2 (406 n + 8373 n + 48773 n + 83460) b(n + 6) + 1/3 --------------------------------------------- (n + 15) (n + 19) (n + 18) 3 2 (4141 n + 57564 n + 228659 n + 246684) b(n + 7) - 1/6 ------------------------------------------------- (n + 15) (n + 19) (n + 18) 3 2 (1589 n + 27240 n + 150067 n + 275250) b(n + 8) + 1/3 ------------------------------------------------- (n + 15) (n + 19) (n + 18) 3 2 (556 n + 12879 n + 96668 n + 226989) b(n + 9) - 1/3 ----------------------------------------------- (n + 15) (n + 19) (n + 18) 3 2 (242 n + 5616 n + 41746 n + 100377) b(n + 10) - 2/3 ----------------------------------------------- (n + 15) (n + 19) (n + 18) 3 2 (234 n + 6360 n + 56059 n + 158767) b(n + 11) + ----------------------------------------------- (n + 15) (n + 19) (n + 18) 3 2 (749 n + 23580 n + 243163 n + 815100) b(n + 12) - 1/6 ------------------------------------------------- (n + 15) (n + 19) (n + 18) 3 2 (16 n + 475 n + 4511 n + 13856) b(n + 13) + ------------------------------------------- (n + 15) (n + 19) (n + 18) 3 2 (235 n + 9420 n + 122771 n + 516186) b(n + 14) + 1/6 ------------------------------------------------ (n + 15) (n + 19) (n + 18) 2 (227 n + 6051 n + 39190) b(n + 15) - 1/6 ----------------------------------- (n + 19) (n + 18) 3 2 (23 n + 994 n + 14247 n + 67728) b(n + 16) + 1/2 -------------------------------------------- (n + 15) (n + 19) (n + 18) 2 2 (11 n + 347 n + 2712) b(n + 17) (5 n + 164 n + 1331) b(n + 18) + 1/2 -------------------------------- - ------------------------------- (n + 18) (n + 15) (n + 19) (n + 15) + b(n + 19) = 0 Subject to the initial conditions b(1) = 0, b(2) = 0, b(3) = 0, b(4) = 1, b(5) = 3, b(6) = 8, b(7) = 20, b(8) = 46, b(9) = 103, b(10) = 225, b(11) = 484, b(12) = 1027, b(13) = 2159, b(14) = 4504, b(15) = 9341, b(16) = 19277, b(17) = 39625, b(18) = 81182, b(19) = 165868 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.099749 1/2 - -------- 1/2 n The probability of Bob winning the bet, as n grows larger is approximately 0.6982 1/2 - ------ 1/2 n You can see that indeed Alice has a better chance, but not significantly so. ----------------------------------------- This took, 40.461, seconds to generate The best bet against, [1, 1, 1, 1], is a member of, {[1, 1, 1, 2], [2, 1, 1, 1]}, 0.987463 and then your edge, if you have n rolls, is approximately, -------- 1/2 n The next best bet is a member of, {[1, 1, 2, 2], [2, 2, 1, 1]}, 0.8062168 and then your edge is approximately, --------- 1/2 n The next best bet is a member of, {[1, 2, 2, 2], [2, 2, 2, 1]}, 0.746391 and then your edge is approximately, -------- 1/2 n The next best bet is a member of, {[1, 1, 2, 1], [1, 2, 1, 1]}, 0.6911 and then your edge is approximately, ------ 1/2 n The next best bet is a member of, {[1, 2, 2, 1]}, 0.63976 and then your edge is approximately, ------- 1/2 n The next best bet is a member of, {[2, 1, 1, 2], [2, 1, 2, 2], [2, 2, 1, 2]}, 0.598451 and then your edge is approximately, -------- 1/2 n The next best bet is a member of, {[1, 2, 1, 2], [2, 1, 2, 1]}, 0.4988 and then your edge is approximately, ------ 1/2 n The next best bet is a member of, {[2, 2, 2, 2]}, and then your edge is exactly 0 ----------------------- This ends this chapter that took, 338.408, seconds to generate.