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, 1, 1], Versus the number of occurences of all, 4, 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, 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, 2, : If Alice bets that there are more occurrences of consec\ utive substrings in, {[2, 3, 2, 3]}, 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 , 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, 2, 3]}, then , {[1, 1, 1, 1]} a(n) satisfies the following linear recurrence equation with polynomial coef\ ficients of order, 39 2 (n + 3) (2488 n + 4947 n - 29371) a(n + 2) ------------------------------------------- + a(n + 39) (n + 35) (n + 39) (n + 36) (n + 1) (n + 2) (n + 3) a(n) - 441/2 ---------------------------- (n + 35) (n + 39) (n + 36) (83 n - 2329) (n + 3) (n + 2) a(n + 1) + 3/2 -------------------------------------- (n + 35) (n + 39) (n + 36) 3 2 (2404289 n + 167360604 n + 3876426703 n + 29873715432) a(n + 24) - 1/6 ------------------------------------------------------------------ (n + 35) (n + 39) (n + 36) 3 2 (155932 n + 10077945 n + 212788100 n + 1458879009) a(n + 25) + -------------------------------------------------------------- (n + 35) (n + 39) (n + 36) 3 2 (52148 n + 2116965 n + 7144852 n - 327135951) a(n + 26) - 1/3 --------------------------------------------------------- (n + 35) (n + 39) (n + 36) 3 2 (116477 n + 8864028 n + 224710225 n + 1898708319) a(n + 27) + 2/3 ------------------------------------------------------------- (n + 35) (n + 39) (n + 36) 3 2 (54203 n + 3289746 n + 59897035 n + 289412976) a(n + 28) - 1/6 ---------------------------------------------------------- (n + 35) (n + 39) (n + 36) 3 2 2 (234 n + 16149 n + 266972 n - 157994) a(n + 29) - --------------------------------------------------- (n + 35) (n + 39) (n + 36) 3 2 (17049 n + 1557266 n + 47494803 n + 483678186) a(n + 30) - 1/2 ---------------------------------------------------------- (n + 35) (n + 39) (n + 36) 3 2 (4807 n + 499998 n + 17199032 n + 195842367) a(n + 31) + 1/3 -------------------------------------------------------- (n + 35) (n + 39) (n + 36) 3 2 (4591 n + 491724 n + 17327558 n + 201366549) a(n + 32) - 1/3 -------------------------------------------------------- (n + 35) (n + 39) (n + 36) 3 2 (13271 n + 1330596 n + 44424727 n + 493909530) a(n + 33) + 1/6 ---------------------------------------------------------- (n + 35) (n + 39) (n + 36) 3 2 (3248 n + 329235 n + 11121253 n + 125183436) a(n + 34) - 1/3 -------------------------------------------------------- (n + 35) (n + 39) (n + 36) 3 2 (514 n + 53187 n + 1833493 n + 21056110) a(n + 35) + ---------------------------------------------------- (n + 35) (n + 39) (n + 36) 3 2 3 (93 n + 9744 n + 340099 n + 3954528) a(n + 36) - -------------------------------------------------- (n + 35) (n + 39) (n + 36) 3 2 (187 n + 19874 n + 703573 n + 8297166) a(n + 37) + 1/2 -------------------------------------------------- (n + 35) (n + 39) (n + 36) 3 2 (77007 n + 1288438 n + 6010123 n + 7409268) a(n + 4) + 1/2 ------------------------------------------------------ (n + 35) (n + 39) (n + 36) 3 2 (218153 n + 5114912 n + 35009883 n + 72667208) a(n + 5) + 1/2 --------------------------------------------------------- (n + 35) (n + 39) (n + 36) 3 2 (314525 n + 10792352 n + 99564379 n + 274655340) a(n + 6) + 1/2 ----------------------------------------------------------- (n + 35) (n + 39) (n + 36) 3 2 (11257 n - 11080244 n - 170453369 n - 645131744) a(n + 7) - 1/2 ----------------------------------------------------------- (n + 35) (n + 39) (n + 36) 3 2 (2613287 n + 36547509 n + 43166587 n - 653743341) a(n + 8) - 1/3 ------------------------------------------------------------ (n + 35) (n + 39) (n + 36) 3 2 (2486676 n + 55785983 n + 378985352 n + 707044191) a(n + 9) - ------------------------------------------------------------- (n + 35) (n + 39) (n + 36) 3 2 (14220952 n + 385326603 n + 3344631332 n + 9144792183) a(n + 10) - 1/3 ------------------------------------------------------------------ (n + 35) (n + 39) (n + 36) 3 2 (20086838 n + 629250789 n + 6438931366 n + 21446106945) a(n + 11) - 1/3 ------------------------------------------------------------------- (n + 35) (n + 39) (n + 36) - 3 2 (44845865 n + 1565614452 n + 17987276971 n + 67986091452) a(n + 12) 1/6 --------------------------------------------------------------------- (n + 35) (n + 39) (n + 36) - 3 2 (40856815 n + 1600100652 n + 20703528293 n + 88595067204) a(n + 13) 1/6 --------------------------------------------------------------------- (n + 35) (n + 39) (n + 36) 3 2 (6819926 n + 297881157 n + 4318058116 n + 20821752042) a(n + 14) - 2/3 ------------------------------------------------------------------ (n + 35) (n + 39) (n + 36) 3 2 (5561530 n + 272788443 n + 4411417691 n + 23620071612) a(n + 15) - 1/3 ------------------------------------------------------------------ (n + 35) (n + 39) (n + 36) 3 2 (4253221 n + 165306852 n + 1959347789 n + 6326738922) a(n + 16) + 1/6 ----------------------------------------------------------------- (n + 35) (n + 39) (n + 36) 3 2 (15273763 n + 807434466 n + 14185203797 n + 82753633182) a(n + 17) + 1/6 -------------------------------------------------------------------- (n + 35) (n + 39) (n + 36) 3 2 (7400101 n + 414954150 n + 7731424109 n + 47844714024) a(n + 18) + 1/3 ------------------------------------------------------------------ (n + 35) (n + 39) (n + 36) 3 2 (3697654 n + 224267250 n + 4512057569 n + 30115052361) a(n + 19) + 2/3 ------------------------------------------------------------------ (n + 35) (n + 39) (n + 36) 3 2 (464768 n + 33341831 n + 778083920 n + 5938939833) a(n + 20) + -------------------------------------------------------------- (n + 35) (n + 39) (n + 36) 3 2 (445635 n + 29661026 n + 653814876 n + 4772119545) a(n + 21) + -------------------------------------------------------------- (n + 35) (n + 39) (n + 36) 3 2 (5139277 n + 327699618 n + 6942928553 n + 48866489124) a(n + 22) - 1/6 ------------------------------------------------------------------ (n + 35) (n + 39) (n + 36) 3 2 (129389 n + 13651148 n + 421662095 n + 4050078420) a(n + 23) - 1/2 -------------------------------------------------------------- (n + 35) (n + 39) (n + 36) 3 2 (3539 n + 32 n - 310222 n - 1017183) a(n + 3) + ----------------------------------------------- (n + 35) (n + 39) (n + 36) 2 (31 n + 2265 n + 41294) a(n + 38) - 1/2 ---------------------------------- = 0 (n + 39) (n + 36) Subject to the initial conditions a(1) = 0, a(2) = 0, a(3) = 0, a(4) = 1, a(5) = 6, a(6) = 26, a(7) = 102, a(8) = 376, a(9) = 1331, a(10) = 4586, a(11) = 15486, a(12) = 51491, a(13) = 169145, a(14) = 550200, a(15) = 1775240, a(16) = 5689035, a(17) = 18126188, a(18) = 57465954, a(19) = 181398588, a(20) = 570437139, a(21) = 1787821316, a(22) = 5586549635, a(23) = 17410151578, a(24) = 54127378577, a(25) = 167914037596, a(26) = 519875408400, a(27) = 1606680169948, a(28) = 4957284582176, a(29) = 15272181827467, a(30) = 46984332662604, a(31) = 144359721083427, a(32) = 443018004280838, a(33) = 1358051524296427, a(34) = 4158762701132235, a(35) = 12723170498476295, a(36) = 38889947046816584, a(37) = 118772299652630568, a(38) = 362452926861115463, a(39) = 1105267936569096096 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, 1, 1]}, then , {[2, 3, 2, 3]} b(n) satisfies the following linear recurrence equation with polynomial coef\ ficients of order, 36 (n + 1) (n + 2) (n + 3) b(n) (13 n + 751) (n + 3) (n + 2) b(n + 1) 1323/8 ---------------------------- + 9/2 ------------------------------------- (n + 34) (n + 32) (n + 36) (n + 34) (n + 32) (n + 36) 3 2 (17395 n + 209116 n + 646915 n + 349194) b(n + 3) - 3/8 --------------------------------------------------- (n + 34) (n + 32) (n + 36) 3 2 (13175 n + 238268 n + 1061691 n + 972990) b(n + 4) - 3/4 ---------------------------------------------------- + b(n + 36) (n + 34) (n + 32) (n + 36) 3 2 (294307 n + 7380210 n + 51852659 n + 108275136) b(n + 5) - 1/8 ---------------------------------------------------------- (n + 34) (n + 32) (n + 36) 3 2 (112687 n + 3747756 n + 34833060 n + 98434527) b(n + 6) - 3/4 --------------------------------------------------------- (n + 34) (n + 32) (n + 36) 3 2 (185231 n + 20481756 n + 290902591 n + 1105495986) b(n + 7) - 1/8 ------------------------------------------------------------- (n + 34) (n + 32) (n + 36) 3 2 (2172671 n + 36866886 n + 133201771 n - 194520360) b(n + 8) + 1/8 ------------------------------------------------------------- (n + 34) (n + 32) (n + 36) 3 2 (6122375 n + 157716930 n + 1327704565 n + 3641635206) b(n + 9) + 1/8 ---------------------------------------------------------------- (n + 34) (n + 32) (n + 36) 3 2 (807907 n + 24230977 n + 242010412 n + 807667516) b(n + 10) + 3/2 ------------------------------------------------------------- (n + 34) (n + 32) (n + 36) 3 2 (4307546 n + 141207594 n + 1541918593 n + 5634185907) b(n + 11) + 1/4 ----------------------------------------------------------------- (n + 34) (n + 32) (n + 36) 3 2 (577829 n + 20249296 n + 232213256 n + 875204265) b(n + 12) + 3/4 ------------------------------------------------------------- (n + 34) (n + 32) (n + 36) 3 2 (1638766 n + 65610513 n + 890570957 n + 4084079034) b(n + 13) - 1/4 --------------------------------------------------------------- (n + 34) (n + 32) (n + 36) 3 2 (3346891 n + 138727857 n + 1927156142 n + 8982084654) b(n + 14) - 1/4 ----------------------------------------------------------------- (n + 34) (n + 32) (n + 36) 3 2 (2171132 n + 95454444 n + 1391685865 n + 6732850947) b(n + 15) - 1/4 ---------------------------------------------------------------- (n + 34) (n + 32) (n + 36) 3 2 (73598 n + 2530863 n + 20421349 n - 18440832) b(n + 16) - 3/4 --------------------------------------------------------- (n + 34) (n + 32) (n + 36) 3 2 (1104125 n + 57224852 n + 999400151 n + 5881375512) b(n + 17) + 3/8 --------------------------------------------------------------- (n + 34) (n + 32) (n + 36) 3 2 (942153 n + 51345474 n + 931244095 n + 5621022594) b(n + 18) + 3/8 -------------------------------------------------------------- (n + 34) (n + 32) (n + 36) 3 2 (1502309 n + 91317834 n + 1849055659 n + 12477919950) b(n + 19) + 1/8 ----------------------------------------------------------------- (n + 34) (n + 32) (n + 36) 3 2 (77127 n + 4697567 n + 98484136 n + 709828686) b(n + 20) - 3/4 ---------------------------------------------------------- (n + 34) (n + 32) (n + 36) 3 2 (842321 n + 48906162 n + 931775827 n + 5799508194) b(n + 21) - 1/8 -------------------------------------------------------------- (n + 34) (n + 32) (n + 36) 3 2 (88991 n + 6725307 n + 167922970 n + 1388066370) b(n + 22) - 1/2 ------------------------------------------------------------ (n + 34) (n + 32) (n + 36) 3 2 (95275 n + 6240702 n + 133579465 n + 928903606) b(n + 23) - 3/8 ----------------------------------------------------------- (n + 34) (n + 32) (n + 36) 3 2 (222559 n + 15054282 n + 336639419 n + 2484374952) b(n + 24) + 1/4 -------------------------------------------------------------- (n + 34) (n + 32) (n + 36) 2 (n + 3) (7811 n + 33519 n - 13868) b(n + 2) - 3/8 -------------------------------------------- (n + 34) (n + 32) (n + 36) 3 2 (57761 n + 4085349 n + 95653645 n + 740237379) b(n + 25) - 1/2 ---------------------------------------------------------- (n + 34) (n + 32) (n + 36) 3 2 (76427 n + 5821344 n + 147411265 n + 1240626138) b(n + 26) + 1/2 ------------------------------------------------------------ (n + 34) (n + 32) (n + 36) 3 2 (61948 n + 4859676 n + 126876497 n + 1102295673) b(n + 27) - 1/2 ------------------------------------------------------------ (n + 34) (n + 32) (n + 36) 3 2 (37186 n + 3026535 n + 82024043 n + 740181714) b(n + 28) + 1/2 ---------------------------------------------------------- (n + 34) (n + 32) (n + 36) 3 2 (50093 n + 4234086 n + 119187973 n + 1117328412) b(n + 29) - 1/4 ------------------------------------------------------------ (n + 34) (n + 32) (n + 36) 3 2 (14120 n + 1229118 n + 35632807 n + 344027253) b(n + 30) + 1/2 ---------------------------------------------------------- (n + 34) (n + 32) (n + 36) 3 2 (6242 n + 560235 n + 16744924 n + 166664445) b(n + 31) - 1/2 -------------------------------------------------------- (n + 34) (n + 32) (n + 36) 3 2 (1747 n + 161994 n + 5002163 n + 51433824) b(n + 32) + 3/4 ------------------------------------------------------ (n + 34) (n + 32) (n + 36) 3 2 (967 n + 92226 n + 2929256 n + 30983133) b(n + 33) - 1/2 ---------------------------------------------------- (n + 34) (n + 32) (n + 36) 3 2 (485 n + 47382 n + 1541593 n + 16703388) b(n + 34) + 1/4 ---------------------------------------------------- (n + 34) (n + 32) (n + 36) 3 2 (34 n + 3396 n + 112955 n + 1251093) b(n + 35) - 1/2 ------------------------------------------------ = 0 (n + 34) (n + 32) (n + 36) Subject to the initial conditions b(1) = 0, b(2) = 0, b(3) = 0, b(4) = 1, b(5) = 5, b(6) = 21, b(7) = 81, b(8) = 295, b(9) = 1037, b(10) = 3557, b(11) = 11973, b(12) = 39726, b(13) = 130316, b(14) = 423521, b(15) = 1365834, b(16) = 4376200, b(17) = 13943914, b(18) = 44217070, b(19) = 139630469, b(20) = 439313691, b(21) = 1377704264, b(22) = 4308016374, b(23) = 13435965507, b(24) = 41806321489, b(25) = 129805351533, b(26) = 402257536011, b(27) = 1244370178601, b(28) = 3843198841278, b(29) = 11851970218913, b(30) = 36500004728993, b(31) = 112265099046573, b(32) = 344894446931690, b(33) = 1058408461110311, b(34) = 3244730326195241, b(35) = 9937830224398975, b(36) = 30410176931457688 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.634 1/2 - ----- 1/2 n The probability of Bob winning the bet, as n grows larger is approximately 1.38 1/2 - ---- 1/2 n You can see that indeed Alice has a better chance, but not significantly so. ----------------------------------------- This took, 93.760, seconds to generate ----------------------------------------------------------------------------\ ----------------------- 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, 3}, 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, 29 2 (17 n + 898 n + 11810) a(n + 28) - --------------------------------- (n + 29) (n + 26) 3 2 (313 n + 22617 n + 543488 n + 4343556) a(n + 25) + -------------------------------------------------- (n + 25) (n + 29) (n + 26) 3 2 (992 n + 73077 n + 1791577 n + 14619186) a(n + 26) - 1/3 ---------------------------------------------------- (n + 25) (n + 29) (n + 26) 3 2 (335 n + 25356 n + 638719 n + 5355360) a(n + 27) + 1/3 -------------------------------------------------- (n + 25) (n + 29) (n + 26) 3 2 18 (5665 n + 85899 n + 430610 n + 714024) a(n + 4) + ---------------------------------------------------- (n + 25) (n + 29) (n + 26) 3 2 (71141 n + 937077 n + 3181276 n + 765348) a(n + 5) + ---------------------------------------------------- (n + 25) (n + 29) (n + 26) 3 2 (22562 n + 2737563 n + 36463687 n + 128468634) a(n + 6) - 1/3 --------------------------------------------------------- (n + 25) (n + 29) (n + 26) 3 2 (278830 n + 9153057 n + 93289367 n + 302333358) a(n + 7) - 1/3 ---------------------------------------------------------- (n + 25) (n + 29) (n + 26) 3 2 (634019 n + 17973207 n + 165885808 n + 496002960) a(n + 8) - 1/6 ------------------------------------------------------------ (n + 25) (n + 29) (n + 26) 3 2 (296734 n + 4130961 n - 10296055 n - 222962670) a(n + 9) - 1/6 ---------------------------------------------------------- (n + 25) (n + 29) (n + 26) 3 2 (281690 n + 17192289 n + 277486147 n + 1347911286) a(n + 10) + 1/6 -------------------------------------------------------------- (n + 25) (n + 29) (n + 26) 3 2 (175684 n + 8065773 n + 117222507 n + 547732676) a(n + 11) + 1/2 ------------------------------------------------------------ (n + 25) (n + 29) (n + 26) 3 2 (624731 n + 24692478 n + 324251875 n + 1409543616) a(n + 12) + 1/6 -------------------------------------------------------------- (n + 25) (n + 29) (n + 26) 3 2 (186670 n + 6312267 n + 67622099 n + 219980766) a(n + 13) + 1/3 ----------------------------------------------------------- (n + 25) (n + 29) (n + 26) 3 2 (25926 n + 781145 n + 6086301 n + 3098842) a(n + 14) + ------------------------------------------------------ (n + 25) (n + 29) (n + 26) 3 2 (36613 n + 1664729 n + 25382656 n + 129527610) a(n + 15) - ---------------------------------------------------------- (n + 25) (n + 29) (n + 26) 3 2 (221081 n + 9801459 n + 143976838 n + 699965952) a(n + 16) - 1/6 ------------------------------------------------------------ (n + 25) (n + 29) (n + 26) 3 2 (126580 n + 6051039 n + 95067389 n + 489673194) a(n + 17) - 1/6 ----------------------------------------------------------- (n + 25) (n + 29) (n + 26) 3 2 (83738 n + 3984759 n + 62530621 n + 322856046) a(n + 18) + 1/6 ---------------------------------------------------------- (n + 25) (n + 29) (n + 26) 3 2 (55298 n + 3058341 n + 56337721 n + 345870300) a(n + 19) + 1/6 ---------------------------------------------------------- (n + 25) (n + 29) (n + 26) 3 2 (2479 n + 141038 n + 2651443 n + 16471588) a(n + 20) + 3/2 ------------------------------------------------------ (n + 25) (n + 29) (n + 26) 3 2 (12730 n + 685839 n + 12091595 n + 69479826) a(n + 21) - 1/3 -------------------------------------------------------- (n + 25) (n + 29) (n + 26) 3 2 (2054 n + 177051 n + 4733929 n + 40306710) a(n + 22) - 1/3 ------------------------------------------------------ (n + 25) (n + 29) (n + 26) 3 2 (23 n - 750 n - 70067 n - 934056) a(n + 23) - --------------------------------------------- (n + 25) (n + 29) (n + 26) 3 2 2 (155 n + 10406 n + 232270 n + 1723551) a(n + 24) + ---------------------------------------------------- + a(n + 29) (n + 25) (n + 29) (n + 26) 2916 (n + 4) (n + 2) (n + 1) a(n) + --------------------------------- (n + 25) (n + 29) (n + 26) 2 972 (n + 2) (16 n + 121 n + 221) a(n + 1) + ------------------------------------------ (n + 25) (n + 29) (n + 26) 2 108 (n + 3) (412 n + 3573 n + 7742) a(n + 2) + --------------------------------------------- (n + 25) (n + 29) (n + 26) 2 36 (n + 4) (2273 n + 22078 n + 53517) a(n + 3) + ----------------------------------------------- = 0 (n + 25) (n + 29) (n + 26) Subject to the initial conditions a(1) = 0, a(2) = 0, a(3) = 0, a(4) = 1, a(5) = 5, a(6) = 21, a(7) = 81, a(8) = 295, a(9) = 1039, a(10) = 3569, a(11) = 12035, a(12) = 40008, a(13) = 131493, a(14) = 428185, a(15) = 1383611, a(16) = 4441949, a(17) = 14181427, a(18) = 45058853, a(19) = 142567115, a(20) = 449423326, a(21) = 1412115618, a(22) = 4424007246, a(23) = 13823620949, a(24) = 43092241255, a(25) = 134042733765, a(26) = 416138113569, a(27) = 1289598089115, a(28) = 3989861441580, a(29) = 12325491796719 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, 1, 1]}, then , {[1, 1, 1, 2]} b(n) satisfies the following linear recurrence equation with polynomial coef\ ficients of order, 13 (n + 4) (n + 1) b(n) (n + 3) (5 n + 13) b(n + 1) -243/4 -------------------- - 27/2 --------------------------- (n + 13) (n + 9) (n + 13) (n + 9) 2 2 (15 n + 68 n + 72) b(n + 2) (27 n + 475 n + 1515) b(n + 3) - 9/2 ---------------------------- + 3/2 ------------------------------- (n + 13) (n + 9) (n + 13) (n + 9) 2 (17 n - 733 n - 4734) b(n + 4) - 1/4 ------------------------------- (n + 13) (n + 9) 2 2 (64 n + 918 n + 3461) b(n + 5) (6 n - 310 n - 2349) b(n + 6) + 1/2 ------------------------------- + 1/2 ------------------------------ (n + 13) (n + 9) (n + 13) (n + 9) 2 (120 n + 1453 n + 3835) b(n + 7) + 1/2 --------------------------------- (n + 13) (n + 9) 2 (137 n + 2081 n + 8108) b(n + 8) - 1/4 --------------------------------- (n + 13) (n + 9) 2 (35 n + 572 n + 2241) b(n + 9) - 1/2 ------------------------------- (n + 13) (n + 9) 2 (23 n + 404 n + 1608) b(n + 10) - 1/2 -------------------------------- (n + 13) (n + 9) 2 (47 n + 916 n + 4293) b(n + 11) + 1/2 -------------------------------- (n + 13) (n + 9) 2 (35 n + 729 n + 3672) 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) = 4, b(6) = 16, b(7) = 60, b(8) = 215, b(9) = 749, b(10) = 2552, b(11) = 8556, b(12) = 28321, b(13) = 92784 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.659 1/2 - ----- 1/2 n The probability of Bob winning the bet, as n grows larger is approximately 1.88 1/2 - ---- 1/2 n You can see that indeed Alice has a better chance, but not significantly so. ----------------------------------------- This took, 45.878, 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, 3}, 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 2409 (n + 1) (n + 2) (n + 3) a(n) - --------------------------------- (n + 20) (n + 19) (n + 23) (11975 n + 53597) (n + 3) (n + 2) a(n + 1) + 1/2 ------------------------------------------ (n + 20) (n + 19) (n + 23) 2 (n + 3) (207214 n + 2090259 n + 5334074) a(n + 2) - 1/6 -------------------------------------------------- (n + 20) (n + 19) (n + 23) 3 2 (567536 n + 9659889 n + 53106859 n + 94088352) a(n + 3) + 1/6 --------------------------------------------------------- (n + 20) (n + 19) (n + 23) 3 2 (169598 n + 3338735 n + 21493366 n + 45151075) a(n + 4) - --------------------------------------------------------- (n + 20) (n + 19) (n + 23) 3 2 (495695 n + 7474203 n + 28986046 n + 11327568) a(n + 5) + 1/6 --------------------------------------------------------- (n + 20) (n + 19) (n + 23) 3 2 (459245 n + 18718662 n + 215559613 n + 747685644) a(n + 6) + 1/6 ------------------------------------------------------------ (n + 20) (n + 19) (n + 23) 3 2 (215048 n + 5928773 n + 53697820 n + 159543259) a(n + 7) - ---------------------------------------------------------- (n + 20) (n + 19) (n + 23) 3 2 (871633 n + 24016272 n + 211343741 n + 592592205) a(n + 8) + 1/3 ------------------------------------------------------------ (n + 20) (n + 19) (n + 23) 3 2 3 (17990 n + 547931 n + 5145433 n + 14972243) a(n + 9) - -------------------------------------------------------- (n + 20) (n + 19) (n + 23) 3 2 (279901 n + 8668490 n + 89177295 n + 304229894) a(n + 10) - 1/2 ----------------------------------------------------------- (n + 20) (n + 19) (n + 23) 3 2 (676340 n + 20293365 n + 202776439 n + 679579206) a(n + 11) + 1/6 ------------------------------------------------------------- (n + 20) (n + 19) (n + 23) 3 2 (158776 n + 4265067 n + 38696339 n + 127739526) a(n + 12) - 1/6 ----------------------------------------------------------- (n + 20) (n + 19) (n + 23) 3 2 (217127 n + 6804912 n + 64832791 n + 171131118) a(n + 13) - 1/6 ----------------------------------------------------------- (n + 20) (n + 19) (n + 23) 3 2 (123095 n + 4038696 n + 41536693 n + 128730297) a(n + 14) + 1/3 ----------------------------------------------------------- (n + 20) (n + 19) (n + 23) 3 2 (14594 n + 511879 n + 5772913 n + 20773293) a(n + 15) - ------------------------------------------------------- (n + 20) (n + 19) (n + 23) 3 2 (1079 n + 50388 n + 833218 n + 4836135) a(n + 16) + --------------------------------------------------- (n + 20) (n + 19) (n + 23) 3 2 (1919 n + 32328 n - 468287 n - 7814820) a(n + 17) + 1/6 --------------------------------------------------- (n + 20) (n + 19) (n + 23) 3 2 (4711 n + 236595 n + 3969524 n + 22281480) a(n + 18) - 1/6 ------------------------------------------------------ (n + 20) (n + 19) (n + 23) 3 2 (2977 n + 161319 n + 2909591 n + 17471289) a(n + 19) + 1/3 ------------------------------------------------------ (n + 20) (n + 19) (n + 23) 3 2 (3146 n + 176127 n + 3280093 n + 20325576) a(n + 20) - 1/6 ------------------------------------------------------ (n + 20) (n + 19) (n + 23) 3 2 (832 n + 48147 n + 926489 n + 5929998) a(n + 21) + 1/6 -------------------------------------------------- (n + 20) (n + 19) (n + 23) 2 (37 n + 1513 n + 15366) a(n + 22) - 1/2 ---------------------------------- + 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) = 6, a(6) = 26, a(7) = 100, a(8) = 365, a(9) = 1288, a(10) = 4427, a(11) = 14921, a(12) = 49548, a(13) = 162629, a(14) = 528742, a(15) = 1705546, a(16) = 5465134, a(17) = 17413374, a(18) = 55213828, a(19) = 174328471, a(20) = 548363307, a(21) = 1719231328, a(22) = 5374307266, a(23) = 16755810534 Lemma , 4.2, : Let b(n) be the number of words of length n in the alphabet , {1, 2, 3}, 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 10659 (n + 1) (n + 2) (n + 3) b(n) - ---------------------------------- (n + 13) (n + 17) (n + 16) (35149 n + 147967) (n + 3) (n + 2) b(n + 1) + 1/2 ------------------------------------------- (n + 13) (n + 17) (n + 16) 2 (n + 3) (118069 n + 1298268 n + 3543344) b(n + 2) + 1/6 -------------------------------------------------- (n + 13) (n + 17) (n + 16) 3 2 (23722 n + 182133 n + 65930 n - 1162533) b(n + 3) - 1/3 --------------------------------------------------- (n + 13) (n + 17) (n + 16) 3 2 (15941 n + 382649 n + 2688686 n + 5848388) b(n + 4) - 1/2 ----------------------------------------------------- (n + 13) (n + 17) (n + 16) 3 2 (6412 n + 212507 n + 2023250 n + 5868709) b(n + 5) - ---------------------------------------------------- (n + 13) (n + 17) (n + 16) 3 2 (32473 n + 1315725 n + 13395074 n + 40339056) b(n + 6) + 1/6 -------------------------------------------------------- (n + 13) (n + 17) (n + 16) 3 2 (2801 n + 93910 n + 1220123 n + 5115690) b(n + 7) + 1/2 --------------------------------------------------- (n + 13) (n + 17) (n + 16) 3 2 (11168 n + 438009 n + 5115886 n + 18672162) b(n + 8) - 1/3 ------------------------------------------------------ (n + 13) (n + 17) (n + 16) 3 2 (6891 n + 213146 n + 2121077 n + 6820998) b(n + 9) + 1/2 ---------------------------------------------------- (n + 13) (n + 17) (n + 16) 3 2 (1963 n + 103371 n + 1488608 n + 6474432) b(n + 10) + 1/6 ----------------------------------------------------- (n + 13) (n + 17) (n + 16) 3 2 (7181 n + 236124 n + 2552476 n + 9047133) b(n + 11) - 1/3 ----------------------------------------------------- (n + 13) (n + 17) (n + 16) 3 2 (6785 n + 221139 n + 2365858 n + 8273532) b(n + 12) + 1/6 ----------------------------------------------------- (n + 13) (n + 17) (n + 16) 3 2 (413 n + 19272 n + 285166 n + 1354527) b(n + 13) + 1/3 -------------------------------------------------- (n + 13) (n + 17) (n + 16) 3 2 (563 n + 22753 n + 304426 n + 1346720) b(n + 14) - 1/2 -------------------------------------------------- (n + 13) (n + 17) (n + 16) 3 2 (201 n + 8432 n + 117233 n + 539622) b(n + 15) + 1/2 ------------------------------------------------ (n + 13) (n + 17) (n + 16) 2 (16 n + 447 n + 3085) 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) = 5, b(6) = 20, b(7) = 75, b(8) = 271, b(9) = 949, b(10) = 3240, b(11) = 10871, b(12) = 35992, b(13) = 117895, b(14) = 382757, b(15) = 1233495, b(16) = 3950408, b(17) = 12584214 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.611 1/2 - ----- 1/2 n The probability of Bob winning the bet, as n grows larger is approximately 1.59 1/2 - ---- 1/2 n You can see that indeed Alice has a better chance, but not significantly so. ----------------------------------------- This took, 42.956, seconds to generate ----------------------------------------------------------------------------\ ----------------------- Question Mumber, 5, : 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 , 5.1, : Let a(n) be the number of words of length n in the alphabet , {1, 2, 3}, 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, 38 3 2 (21923 n + 315369 n + 1521118 n + 2443260) a(n + 3) -9/2 ----------------------------------------------------- (n + 35) (n + 34) (n + 38) 3 2 (244697 n + 4301520 n + 25478389 n + 50469654) a(n + 4) - 3/2 --------------------------------------------------------- (n + 35) (n + 34) (n + 38) 3 2 (213299 n + 4376560 n + 30030873 n + 68757846) a(n + 5) - 9/2 --------------------------------------------------------- (n + 35) (n + 34) (n + 38) 3 2 (2508041 n + 58032774 n + 448691308 n + 1157979039) a(n + 6) - -------------------------------------------------------------- (n + 35) (n + 34) (n + 38) 3 2 (9590570 n + 244482591 n + 2079383761 n + 5900682858) a(n + 7) - 1/2 ---------------------------------------------------------------- (n + 35) (n + 34) (n + 38) 3 2 (18021329 n + 500756623 n + 4642896720 n + 14366075766) a(n + 8) - 1/2 ------------------------------------------------------------------ (n + 35) (n + 34) (n + 38) 3 2 (24670620 n + 737967071 n + 7358484803 n + 24469129518) a(n + 9) - 1/2 ------------------------------------------------------------------ (n + 35) (n + 34) (n + 38) 3 2 (16846771 n + 541343749 n + 5793535709 n + 20662151384) a(n + 10) - ------------------------------------------------------------------- - (n + 35) (n + 34) (n + 38) 3 2 (30391050 n + 1035881825 n + 11720750713 n + 44052971868) a(n + 11) 1/2 --------------------------------------------------------------------- (n + 35) (n + 34) (n + 38) - 3 2 (28879204 n + 1043520337 n + 12477907225 n + 49394342610) a(n + 12) 1/2 --------------------------------------------------------------------- (n + 35) (n + 34) (n + 38) 3 2 (8936015 n + 312741811 n + 3458106006 n + 11757370402) a(n + 13) - 1/2 ------------------------------------------------------------------ (n + 35) (n + 34) (n + 38) 3 2 (1291770 n + 27500903 n - 59900773 n - 2668307983) a(n + 14) - -------------------------------------------------------------- (n + 35) (n + 34) (n + 38) 3 2 (17049245 n + 816634620 n + 13106117963 n + 70369756962) a(n + 15) + 1/2 -------------------------------------------------------------------- (n + 35) (n + 34) (n + 38) 3 2 (10809769 n + 577150288 n + 10223105393 n + 60061201982) a(n + 16) + 1/2 -------------------------------------------------------------------- (n + 35) (n + 34) (n + 38) 3 2 (8589895 n + 449665907 n + 7851343553 n + 45712675051) a(n + 17) + ------------------------------------------------------------------ (n + 35) (n + 34) (n + 38) 3 2 (6524699 n + 471503049 n + 10561234138 n + 75252994920) a(n + 18) + 1/6 ------------------------------------------------------------------- (n + 35) (n + 34) (n + 38) 3 2 (13325698 n + 746865531 n + 13932378581 n + 86462695932) a(n + 19) + 1/6 -------------------------------------------------------------------- (n + 35) (n + 34) (n + 38) (n + 1) (n + 2) (n + 3) a(n) - 2997/2 ---------------------------- (n + 35) (n + 34) (n + 38) 27 (197 n + 689) (n + 3) (n + 2) a(n + 1) - ----------------------------------------- (n + 35) (n + 34) (n + 38) 2 (n + 3) (6649 n + 51147 n + 102446) a(n + 2) - 9/2 --------------------------------------------- + a(n + 38) (n + 35) (n + 34) (n + 38) 3 2 (4768053 n + 267644771 n + 5005279328 n + 31222183850) a(n + 20) - 1/2 ------------------------------------------------------------------ (n + 35) (n + 34) (n + 38) 3 2 (223736 n + 57445125 n + 2078527525 n + 20368619526) a(n + 21) - 1/6 ---------------------------------------------------------------- (n + 35) (n + 34) (n + 38) 3 2 (1323479 n + 83701866 n + 1763600834 n + 12384013195) a(n + 22) - ----------------------------------------------------------------- (n + 35) (n + 34) (n + 38) 3 2 (753042 n + 42600961 n + 775786499 n + 4478826942) a(n + 23) + 1/2 -------------------------------------------------------------- (n + 35) (n + 34) (n + 38) 3 2 (894539 n + 52893741 n + 1004735332 n + 6019403154) a(n + 24) - 1/6 --------------------------------------------------------------- (n + 35) (n + 34) (n + 38) 3 2 (1597328 n + 110625291 n + 2544453331 n + 19438401846) a(n + 25) + 1/6 ------------------------------------------------------------------ (n + 35) (n + 34) (n + 38) 3 2 (73904 n + 3037329 n + 11938186 n - 441921390) a(n + 26) - 1/3 ---------------------------------------------------------- (n + 35) (n + 34) (n + 38) 3 2 (32452 n + 1997271 n + 37509053 n + 195986520) a(n + 27) + 1/2 ---------------------------------------------------------- (n + 35) (n + 34) (n + 38) 3 2 (110260 n + 7890267 n + 184108511 n + 1390784238) a(n + 28) - 1/6 ------------------------------------------------------------- (n + 35) (n + 34) (n + 38) 3 2 (56423 n + 5337279 n + 166318438 n + 1710437910) a(n + 29) - 1/6 ------------------------------------------------------------ (n + 35) (n + 34) (n + 38) 3 2 (15889 n + 1463796 n + 44862575 n + 457394541) a(n + 30) + 1/3 ---------------------------------------------------------- (n + 35) (n + 34) (n + 38) 3 2 (13663 n + 1326198 n + 42692303 n + 455930610) a(n + 31) - 1/6 ---------------------------------------------------------- (n + 35) (n + 34) (n + 38) 3 2 (8089 n + 769584 n + 24376091 n + 257042562) a(n + 32) + 1/3 -------------------------------------------------------- (n + 35) (n + 34) (n + 38) 3 2 (3940 n + 379674 n + 12190553 n + 130416105) a(n + 33) - 1/3 -------------------------------------------------------- (n + 35) (n + 34) (n + 38) 3 2 (906 n + 90227 n + 2994031 n + 33104174) a(n + 34) + 1/2 ---------------------------------------------------- (n + 35) (n + 34) (n + 38) 3 2 (437 n + 44554 n + 1513189 n + 17120132) a(n + 35) - 1/2 ---------------------------------------------------- (n + 35) (n + 34) (n + 38) 3 2 (160 n + 16553 n + 570429 n + 6548040) a(n + 36) + 1/2 -------------------------------------------------- (n + 35) (n + 34) (n + 38) (29 n + 1077) (n + 34) a(n + 37) - 1/2 -------------------------------- = 0 (n + 38) (n + 35) Subject to the initial conditions a(1) = 0, a(2) = 0, a(3) = 0, a(4) = 1, a(5) = 6, a(6) = 26, a(7) = 101, a(8) = 371, a(9) = 1312, a(10) = 4514, a(11) = 15228, a(12) = 50606, a(13) = 166170, a(14) = 540368, a(15) = 1743218, a(16) = 5585881, a(17) = 17796839, a(18) = 56422330, a(19) = 178112587, a(20) = 560146682, a(21) = 1755746966, a(22) = 5486987387, a(23) = 17102216615, a(24) = 53178024997, a(25) = 164995597365, a(26) = 510926820828, a(27) = 1579305557304, a(28) = 4873719405300, a(29) = 15017575961807, a(30) = 46209962072966, a(31) = 142008303462810, a(32) = 435888374009409, a(33) = 1336463631567703, a(34) = 4093479132604509, a(35) = 12525979202441526, a(36) = 38294973446717364, a(37) = 116978944995571862, a(38) = 357052567841996541 Lemma , 5.2, : Let b(n) be the number of words of length n in the alphabet , {1, 2, 3}, 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, 35 2 27 (n + 3) (425 n + 4041 n + 9415) b(n + 2) -------------------------------------------- (n + 35) (n + 33) (n + 31) (n + 1) (n + 2) (n + 3) b(n) + 243/8 ---------------------------- (n + 35) (n + 33) (n + 31) 162 (n + 3) (n + 2) (19 n + 94) b(n + 1) + ---------------------------------------- + b(n + 35) (n + 35) (n + 33) (n + 31) 3 2 (14354 n + 219051 n + 1097083 n + 1802118) b(n + 3) + 27/8 ----------------------------------------------------- (n + 35) (n + 33) (n + 31) 3 2 (112739 n + 1983318 n + 11658817 n + 22803942) b(n + 4) + 9/8 --------------------------------------------------------- (n + 35) (n + 33) (n + 31) 3 2 (84666 n + 1694911 n + 11313233 n + 25161702) b(n + 5) + 27/8 -------------------------------------------------------- (n + 35) (n + 33) (n + 31) 3 2 (1366096 n + 29712735 n + 216317975 n + 527063952) b(n + 6) + 3/8 ------------------------------------------------------------- (n + 35) (n + 33) (n + 31) 3 2 (969775 n + 22843554 n + 178254713 n + 460992558) b(n + 7) + 3/4 ------------------------------------------------------------ (n + 35) (n + 33) (n + 31) 3 2 (2304371 n + 57211390 n + 469532955 n + 1273047390) b(n + 8) + 3/8 -------------------------------------------------------------- (n + 35) (n + 33) (n + 31) 3 2 (1754440 n + 43689293 n + 344192839 n + 832446432) b(n + 9) + 3/8 ------------------------------------------------------------- (n + 35) (n + 33) (n + 31) 3 2 (159851 n + 3862664 n + 28664392 n + 62033856) b(n + 10) + 9/4 ---------------------------------------------------------- (n + 35) (n + 33) (n + 31) 3 2 (283699 n + 12107770 n + 167382958 n + 748096491) b(n + 11) - 3/4 ------------------------------------------------------------- (n + 35) (n + 33) (n + 31) 3 2 (2879456 n + 89853669 n + 824373523 n + 1824215682) b(n + 12) - 1/8 --------------------------------------------------------------- (n + 35) (n + 33) (n + 31) 3 2 (959552 n + 22788585 n + 80649472 n - 718243473) b(n + 13) - 1/4 ------------------------------------------------------------ (n + 35) (n + 33) (n + 31) 3 2 (259860 n + 25954295 n + 621516715 n + 4356059172) b(n + 14) + 3/8 -------------------------------------------------------------- (n + 35) (n + 33) (n + 31) 3 2 (6077278 n + 301355991 n + 4964962337 n + 27173942796) b(n + 15) + 1/8 ------------------------------------------------------------------ (n + 35) (n + 33) (n + 31) 3 2 (935778 n + 51639743 n + 956198527 n + 5921687702) b(n + 16) + 3/8 -------------------------------------------------------------- (n + 35) (n + 33) (n + 31) 3 2 (1450526 n + 73231977 n + 1222723708 n + 6741066981) b(n + 17) + 1/2 ---------------------------------------------------------------- (n + 35) (n + 33) (n + 31) 3 2 (1678327 n + 85747884 n + 1453536089 n + 8172264924) b(n + 18) - 1/4 ---------------------------------------------------------------- (n + 35) (n + 33) (n + 31) 3 2 (2170450 n + 111637659 n + 1870060967 n + 10103963766) b(n + 19) + 1/8 ------------------------------------------------------------------ (n + 35) (n + 33) (n + 31) 3 2 (4628693 n + 265995042 n + 5081639743 n + 32270798262) b(n + 20) - 1/8 ------------------------------------------------------------------ (n + 35) (n + 33) (n + 31) 3 2 (854256 n + 49450239 n + 948426019 n + 6022748898) b(n + 21) + 3/8 -------------------------------------------------------------- (n + 35) (n + 33) (n + 31) 3 2 (2211970 n + 136916853 n + 2813261687 n + 19179863544) b(n + 22) - 1/8 ------------------------------------------------------------------ (n + 35) (n + 33) (n + 31) 3 2 (1007315 n + 65471958 n + 1414592749 n + 10159386954) b(n + 23) + 1/4 ----------------------------------------------------------------- (n + 35) (n + 33) (n + 31) 3 2 (1117975 n + 75014118 n + 1671919115 n + 12375127650) b(n + 24) - 1/8 ----------------------------------------------------------------- (n + 35) (n + 33) (n + 31) 3 2 (753062 n + 53319135 n + 1254896671 n + 9815602224) b(n + 25) + 1/8 --------------------------------------------------------------- (n + 35) (n + 33) (n + 31) 3 2 (81456 n + 6014084 n + 147661735 n + 1205477232) b(n + 26) - 3/4 ------------------------------------------------------------ (n + 35) (n + 33) (n + 31) 3 2 (39671 n + 3042356 n + 77592018 n + 657977739) b(n + 27) + 3/4 ---------------------------------------------------------- (n + 35) (n + 33) (n + 31) 3 2 (122318 n + 9812991 n + 261873655 n + 2324235054) b(n + 28) - 1/8 ------------------------------------------------------------- (n + 35) (n + 33) (n + 31) 3 2 (10287 n + 856612 n + 23736002 n + 218829129) b(n + 29) + 3/4 --------------------------------------------------------- (n + 35) (n + 33) (n + 31) 3 2 (24346 n + 2097429 n + 60147407 n + 574089108) b(n + 30) - 1/8 ---------------------------------------------------------- (n + 35) (n + 33) (n + 31) 3 2 (8842 n + 790905 n + 23555135 n + 233564940) b(n + 31) + 1/8 -------------------------------------------------------- (n + 35) (n + 33) (n + 31) 3 2 (3187 n + 294531 n + 9064148 n + 92886876) b(n + 32) - 1/8 ------------------------------------------------------ (n + 35) (n + 33) (n + 31) 3 2 (425 n + 40287 n + 1271758 n + 13369038) b(n + 33) + 1/4 ---------------------------------------------------- (n + 35) (n + 33) (n + 31) 3 2 (32 n + 3102 n + 100129 n + 1076220) b(n + 34) - 1/2 ------------------------------------------------ = 0 (n + 35) (n + 33) (n + 31) Subject to the initial conditions b(1) = 0, b(2) = 0, b(3) = 0, b(4) = 1, b(5) = 5, b(6) = 21, b(7) = 80, b(8) = 291, b(9) = 1022, b(10) = 3500, b(11) = 11772, b(12) = 39040, b(13) = 128013, b(14) = 415922, b(15) = 1341096, b(16) = 4296471, b(17) = 13689119, b(18) = 43408622, b(19) = 137080701, b(20) = 431313370, b(21) = 1352714382, b(22) = 4230263657, b(23) = 13194884235, b(24) = 41061116790, b(25) = 127508177583, b(26) = 395193716493, b(27) = 1222697289655, b(28) = 3776837428855, b(29) = 11649148430670, b(30) = 35881158619027, b(31) = 110379798686216, b(32) = 339159067941913, b(33) = 1040983358423816, b(34) = 3191853773165732, b(35) = 9777555870856011 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.642 1/2 - ----- 1/2 n The probability of Bob winning the bet, as n grows larger is approximately 1.40 1/2 - ---- 1/2 n You can see that indeed Alice has a better chance, but not significantly so. ----------------------------------------- This took, 95.364, seconds to generate ----------------------------------------------------------------------------\ ----------------------- Question Mumber, 6, : 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 , 6.1, : Let a(n) be the number of words of length n in the alphabet , {1, 2, 3}, 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 432 (2 n + 3) (n + 2) (n + 1) a(n) (31 n + 1955 n + 30744) a(n + 33) - ---------------------------------- - 1/2 ---------------------------------- (n + 30) (n + 34) (n + 31) (n + 34) (n + 31) 2 36 (n + 2) (77 n + 455 n + 612) a(n + 1) - ----------------------------------------- + a(n + 34) (n + 30) (n + 34) (n + 31) 3 2 12 (682 n + 9429 n + 38255 n + 48354) a(n + 2) + ------------------------------------------------ (n + 30) (n + 34) (n + 31) 3 2 3 (27713 n + 460149 n + 2416438 n + 4073376) a(n + 3) + ------------------------------------------------------- (n + 30) (n + 34) (n + 31) 3 2 9 (13891 n + 264399 n + 1625938 n + 3251384) a(n + 4) + ------------------------------------------------------- (n + 30) (n + 34) (n + 31) 3 2 2 (49067 n + 787056 n + 3615049 n + 3905394) a(n + 5) + ------------------------------------------------------- (n + 30) (n + 34) (n + 31) 3 2 (544623 n + 12053855 n + 90681674 n + 230320056) a(n + 6) + 1/2 ----------------------------------------------------------- (n + 30) (n + 34) (n + 31) 3 2 (391687 n + 7539239 n + 46858258 n + 93602256) a(n + 7) + 1/2 --------------------------------------------------------- (n + 30) (n + 34) (n + 31) 3 2 2 (84094 n + 2107407 n + 17032631 n + 44359878) a(n + 8) + ---------------------------------------------------------- (n + 30) (n + 34) (n + 31) 3 2 (483503 n + 21076995 n + 290851918 n + 1283053152) a(n + 9) - 1/2 ------------------------------------------------------------- (n + 30) (n + 34) (n + 31) 3 2 2 (91403 n + 4739429 n + 74666315 n + 369894902) a(n + 10) - ------------------------------------------------------------ (n + 30) (n + 34) (n + 31) 3 2 (2196107 n + 85656027 n + 1116857350 n + 4867402320) a(n + 11) - 1/6 ---------------------------------------------------------------- (n + 30) (n + 34) (n + 31) 3 2 (1340479 n + 43478865 n + 378215630 n + 512095416) a(n + 12) - 1/6 -------------------------------------------------------------- (n + 30) (n + 34) (n + 31) 3 2 (888230 n + 22922859 n + 86074348 n - 861960864) a(n + 13) - 1/3 ------------------------------------------------------------ (n + 30) (n + 34) (n + 31) 3 2 (371941 n + 19104425 n + 334080286 n + 1973607104) a(n + 14) + 1/2 -------------------------------------------------------------- (n + 30) (n + 34) (n + 31) 3 2 (1020061 n + 57049344 n + 1017534170 n + 5857359132) a(n + 15) + 1/3 ---------------------------------------------------------------- (n + 30) (n + 34) (n + 31) 3 2 (259699 n + 13265879 n + 220837242 n + 1193698888) a(n + 16) + 3/2 -------------------------------------------------------------- (n + 30) (n + 34) (n + 31) 3 2 (958909 n + 50060979 n + 886425122 n + 5302403760) a(n + 17) + 1/6 -------------------------------------------------------------- (n + 30) (n + 34) (n + 31) 3 2 (292721 n + 23696385 n + 566278366 n + 4214185776) a(n + 18) - 1/6 -------------------------------------------------------------- (n + 30) (n + 34) (n + 31) 3 2 (73664 n + 6629325 n + 172181464 n + 1376504784) a(n + 19) - 1/3 ------------------------------------------------------------ (n + 30) (n + 34) (n + 31) 3 2 (692251 n + 38504757 n + 719570462 n + 4531239504) a(n + 20) - 1/6 -------------------------------------------------------------- (n + 30) (n + 34) (n + 31) 3 2 (2805 n - 199136 n - 11823420 n - 133388556) a(n + 21) - -------------------------------------------------------- (n + 30) (n + 34) (n + 31) 3 2 (72382 n + 4790001 n + 102280280 n + 701587272) a(n + 22) - 1/3 ----------------------------------------------------------- (n + 30) (n + 34) (n + 31) 3 2 (119765 n + 7740717 n + 166108570 n + 1183254192) a(n + 23) + 1/3 ------------------------------------------------------------- (n + 30) (n + 34) (n + 31) 3 2 (27977 n + 1305039 n + 13946638 n - 28970616) a(n + 24) + 1/6 --------------------------------------------------------- (n + 30) (n + 34) (n + 31) 3 2 (10754 n + 422559 n + 1713082 n - 52725276) a(n + 25) - 1/3 ------------------------------------------------------- (n + 30) (n + 34) (n + 31) 3 2 (655 n + 93147 n + 3360368 n + 35859432) a(n + 26) - 2/3 ---------------------------------------------------- (n + 30) (n + 34) (n + 31) 3 2 (12062 n + 896289 n + 22061254 n + 179754300) a(n + 27) - 1/3 --------------------------------------------------------- (n + 30) (n + 34) (n + 31) 3 2 (13217 n + 967323 n + 23214178 n + 181845480) a(n + 28) + 1/6 --------------------------------------------------------- (n + 30) (n + 34) (n + 31) 3 2 (19 n + 5985 n + 291500 n + 3882444) a(n + 29) + 4/3 ------------------------------------------------ (n + 30) (n + 34) (n + 31) 3 2 (23 n + 1871 n + 50484 n + 451656) a(n + 30) + ---------------------------------------------- (n + 30) (n + 34) (n + 31) 3 2 (129 n + 11607 n + 347794 n + 3470656) a(n + 31) - 3/2 -------------------------------------------------- (n + 30) (n + 34) (n + 31) 3 2 2 (44 n + 4018 n + 122191 n + 1237562) a(n + 32) + -------------------------------------------------- = 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) = 6, a(6) = 27, a(7) = 105, a(8) = 386, a(9) = 1364, a(10) = 4697, a(11) = 15848, a(12) = 52668, a(13) = 172922, a(14) = 562257, a(15) = 1813483, a(16) = 5809750, a(17) = 18505442, a(18) = 58652948, a(19) = 185100716, a(20) = 581948632, a(21) = 1823517076, a(22) = 5696965992, a(23) = 17750937348, a(24) = 55177046697, a(25) = 171141208706, a(26) = 529780537253, a(27) = 1637034900902, a(28) = 5050175712458, a(29) = 15556072519170, a(30) = 47850894629699, a(31) = 147001873055609, a(32) = 451065487005418, a(33) = 1382538632111323, a(34) = 4233204752552730 Lemma , 6.2, : Let b(n) be the number of words of length n in the alphabet , {1, 2, 3}, 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 432 (2 n + 3) (n + 2) (n + 1) b(n) 36 (n + 2) (19 n + 73 n + 108) b(n + 1) ---------------------------------- - ---------------------------------------- (n + 20) (n + 19) (n + 16) (n + 20) (n + 19) (n + 16) 3 2 12 (94 n + 1473 n + 6839 n + 9834) b(n + 2) - --------------------------------------------- (n + 20) (n + 19) (n + 16) 3 2 3 (3371 n + 56199 n + 298162 n + 509088) b(n + 3) + --------------------------------------------------- (n + 20) (n + 19) (n + 16) 3 2 27 (67 n + 2179 n + 18966 n + 48680) b(n + 4) + ----------------------------------------------- (n + 20) (n + 19) (n + 16) 3 2 12 (904 n + 20079 n + 148409 n + 363342) b(n + 5) + --------------------------------------------------- (n + 20) (n + 19) (n + 16) 3 2 3 (3775 n + 90121 n + 709060 n + 1840420) b(n + 6) - ---------------------------------------------------- (n + 20) (n + 19) (n + 16) 3 2 (9233 n + 187861 n + 1121626 n + 1683656) b(n + 7) + 1/2 ---------------------------------------------------- (n + 20) (n + 19) (n + 16) 3 2 (15793 n + 472793 n + 4801838 n + 16451440) b(n + 8) - 1/2 ------------------------------------------------------ (n + 20) (n + 19) (n + 16) 3 2 (5555 n + 223205 n + 2820150 n + 11422224) b(n + 9) + ----------------------------------------------------- (n + 20) (n + 19) (n + 16) 3 2 2 (1991 n + 83234 n + 1086306 n + 4533972) b(n + 10) - ------------------------------------------------------ (n + 20) (n + 19) (n + 16) 3 2 12 (265 n + 11192 n + 154319 n + 699056) b(n + 11) + ---------------------------------------------------- (n + 20) (n + 19) (n + 16) 3 2 2 (651 n + 39535 n + 701125 n + 3862632) b(n + 12) - ---------------------------------------------------- (n + 20) (n + 19) (n + 16) 3 2 (2403 n + 143261 n + 2562782 n + 14404224) b(n + 13) + 1/2 ------------------------------------------------------ (n + 20) (n + 19) (n + 16) 3 2 (1755 n + 91433 n + 1539874 n + 8460000) b(n + 14) - 1/2 ---------------------------------------------------- (n + 20) (n + 19) (n + 16) 3 2 4 (81 n + 3214 n + 40637 n + 159006) b(n + 15) - ------------------------------------------------ (n + 20) (n + 19) (n + 16) 3 2 12 (63 n + 2917 n + 44716 n + 226636) b(n + 16) + ------------------------------------------------- (n + 20) (n + 19) (n + 16) 3 2 (427 n + 20741 n + 334290 n + 1786344) b(n + 17) - -------------------------------------------------- (n + 20) (n + 19) (n + 16) 3 2 (119 n + 6037 n + 101682 n + 568272) b(n + 18) + ------------------------------------------------ (n + 20) (n + 19) (n + 16) 2 (17 n + 576 n + 4840) 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) = 5, b(6) = 21, b(7) = 79, b(8) = 287, b(9) = 1005, b(10) = 3440, b(11) = 11554, b(12) = 38284, b(13) = 125437, b(14) = 407315, b(15) = 1312637, b(16) = 4203410, b(17) = 13387276, b(18) = 42436662, b(19) = 133969496, b(20) = 421406650 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.587 1/2 - ----- 1/2 n The probability of Bob winning the bet, as n grows larger is approximately 1.53 1/2 - ---- 1/2 n You can see that indeed Alice has a better chance, but not significantly so. ----------------------------------------- This took, 64.117, seconds to generate ----------------------------------------------------------------------------\ ----------------------- Question Mumber, 7, : 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 , 7.1, : Let a(n) be the number of words of length n in the alphabet , {1, 2, 3}, 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 (31 n + 1893 n + 28820) a(n + 32) -1/2 ---------------------------------- (n + 33) (n + 30) 2 (n + 3) (89 n + 977 n + 2664) a(n + 2) - 243/2 --------------------------------------- (n + 30) (n + 29) (n + 33) 3 2 (2795 n + 2039190 n + 78752965 n + 778767834) a(n + 21) - 1/6 --------------------------------------------------------- (n + 30) (n + 29) (n + 33) 3 2 (43355 n + 2668906 n + 54364277 n + 366251262) a(n + 22) + 1/2 ---------------------------------------------------------- (n + 30) (n + 29) (n + 33) 3 2 (20063 n + 1557048 n + 39470685 n + 328092100) a(n + 23) + 1/2 ---------------------------------------------------------- (n + 30) (n + 29) (n + 33) 3 2 (9614 n + 648063 n + 14606692 n + 110272119) a(n + 24) + 1/3 -------------------------------------------------------- (n + 30) (n + 29) (n + 33) 3 2 (26255 n + 1905798 n + 46229569 n + 374888370) a(n + 25) - 1/6 ---------------------------------------------------------- (n + 30) (n + 29) (n + 33) 3 2 (20323 n + 1505448 n + 37079465 n + 303715092) a(n + 26) - 1/6 ---------------------------------------------------------- (n + 30) (n + 29) (n + 33) 3 2 (3261 n + 241604 n + 5956995 n + 48914028) a(n + 27) + 1/2 ------------------------------------------------------ (n + 30) (n + 29) (n + 33) 3 2 (1625 n + 132738 n + 3595987 n + 32299182) a(n + 28) + 1/3 ------------------------------------------------------ (n + 30) (n + 29) (n + 33) 3 2 (967 n + 73026 n + 1809437 n + 14647218) a(n + 29) - 1/6 ---------------------------------------------------- (n + 30) (n + 29) (n + 33) 3 2 (983 n + 86790 n + 2550889 n + 24959298) a(n + 30) - 1/6 ---------------------------------------------------- (n + 30) (n + 29) (n + 33) 3 2 (517 n + 45720 n + 1346399 n + 13204476) a(n + 31) + 1/6 ---------------------------------------------------- + a(n + 33) (n + 30) (n + 29) (n + 33) (n + 1) (n + 2) (n + 3) a(n) + 729/2 ---------------------------- (n + 30) (n + 29) (n + 33) (n + 3) (n + 2) (19 n + 79) a(n + 1) - 243/2 ------------------------------------ (n + 30) (n + 29) (n + 33) 3 2 (65 n + 3756 n + 32967 n + 76108) a(n + 3) - 81/2 -------------------------------------------- (n + 30) (n + 29) (n + 33) 3 2 27 (1751 n + 20398 n + 54995 n - 17592) a(n + 4) + -------------------------------------------------- (n + 30) (n + 29) (n + 33) 3 2 (27093 n + 446210 n + 2302419 n + 3585286) a(n + 5) + 9/2 ----------------------------------------------------- (n + 30) (n + 29) (n + 33) 3 2 (431009 n + 8981094 n + 62227375 n + 143274834) a(n + 6) + 1/2 ---------------------------------------------------------- (n + 30) (n + 29) (n + 33) 3 2 (1639927 n + 38917176 n + 317335781 n + 888844932) a(n + 7) + 1/6 ------------------------------------------------------------- (n + 30) (n + 29) (n + 33) 3 2 3 (58718 n + 1225013 n + 8973836 n + 24659457) a(n + 8) + --------------------------------------------------------- (n + 30) (n + 29) (n + 33) 3 2 (89407 n + 7280814 n + 111881177 n + 475614546) a(n + 9) - 1/2 ---------------------------------------------------------- (n + 30) (n + 29) (n + 33) 3 2 (1491937 n + 63530064 n + 853033667 n + 3662759748) a(n + 10) - 1/6 --------------------------------------------------------------- (n + 30) (n + 29) (n + 33) 3 2 (1782419 n + 67837356 n + 873186493 n + 3773598132) a(n + 11) - 1/6 --------------------------------------------------------------- (n + 30) (n + 29) (n + 33) 3 2 (743629 n + 22109394 n + 208955171 n + 611346354) a(n + 12) - 1/3 ------------------------------------------------------------- (n + 30) (n + 29) (n + 33) 3 2 (1234885 n + 32392542 n + 197743199 n - 181613418) a(n + 13) - 1/6 -------------------------------------------------------------- (n + 30) (n + 29) (n + 33) 3 2 (93983 n + 920846 n - 35817279 n - 420471430) a(n + 14) - 1/2 --------------------------------------------------------- (n + 30) (n + 29) (n + 33) 3 2 (1152935 n + 52601544 n + 814586533 n + 4272524340) a(n + 15) + 1/6 --------------------------------------------------------------- (n + 30) (n + 29) (n + 33) 3 2 (925421 n + 41640735 n + 620412283 n + 3057395301) a(n + 16) + 1/3 -------------------------------------------------------------- (n + 30) (n + 29) (n + 33) 3 2 (1034593 n + 49821414 n + 784139579 n + 4013164302) a(n + 17) + 1/6 --------------------------------------------------------------- (n + 30) (n + 29) (n + 33) 3 2 (95321 n + 4306756 n + 63241275 n + 298271952) a(n + 18) - 1/2 ---------------------------------------------------------- (n + 30) (n + 29) (n + 33) 3 2 (206907 n + 10779700 n + 185378893 n + 1050260004) a(n + 19) - 1/2 -------------------------------------------------------------- (n + 30) (n + 29) (n + 33) 3 2 (57041 n + 3318314 n + 64183825 n + 413229580) a(n + 20) - ---------------------------------------------------------- = 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) = 6, a(6) = 26, a(7) = 102, a(8) = 376, a(9) = 1331, a(10) = 4586, a(11) = 15488, a(12) = 51507, a(13) = 169229, a(14) = 550584, a(15) = 1776861, a(16) = 5695488, a(17) = 18150828, a(18) = 57557162, a(19) = 181728023, a(20) = 571603701, a(21) = 1791885518, a(22) = 5600516970, a(23) = 17457598445, a(24) = 54286951368, a(25) = 168446062021, a(26) = 521635708016, a(27) = 1612465198878, a(28) = 4976182237375, a(29) = 15333581211609, a(30) = 47182852768178, a(31) = 144998760799021, a(32) = 445066835101732, a(33) = 1364596218057582 Lemma , 7.2, : Let b(n) be the number of words of length n in the alphabet , {1, 2, 3}, 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 2 (n + 3) (n + 1) b(n) (4 n + 23 n + 31) b(n + 1) -81/2 -------------------- - 27/2 --------------------------- (n + 13) (n + 9) (n + 13) (n + 9) 2 2 (6 n + 67 n + 145) b(n + 2) (22 n + 485 n + 1621) b(n + 3) + 9/2 ---------------------------- + 3/2 ------------------------------- (n + 13) (n + 9) (n + 13) (n + 9) 2 2 (59 n + 393 n + 172) b(n + 4) (9 n - 13 n - 314) b(n + 5) - 1/2 ------------------------------ + ---------------------------- (n + 13) (n + 9) (n + 13) (n + 9) 2 2 (80 n + 1083 n + 3651) b(n + 6) (18 n + 73 n - 611) b(n + 7) + -------------------------------- + ----------------------------- (n + 13) (n + 9) (n + 13) (n + 9) 2 (51 n + 830 n + 3559) b(n + 8) - 1/2 ------------------------------- (n + 13) (n + 9) 2 (56 n + 789 n + 2337) b(n + 9) - 1/2 ------------------------------- (n + 13) (n + 9) 2 2 (6 n + 193 n + 1279) b(n + 10) (6 n + 121 n + 593) b(n + 11) - 1/2 ------------------------------- + 7/2 ------------------------------ (n + 13) (n + 9) (n + 13) (n + 9) 2 (17 n + 357 n + 1818) b(n + 12) - 1/2 -------------------------------- + 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) = 5, b(6) = 20, b(7) = 76, b(8) = 275, b(9) = 961, b(10) = 3283, b(11) = 11021, b(12) = 36493, b(13) = 119529 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.571 1/2 - ----- 1/2 n The probability of Bob winning the bet, as n grows larger is approximately 1.63 1/2 - ---- 1/2 n You can see that indeed Alice has a better chance, but not significantly so. ----------------------------------------- This took, 52.417, 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, 3}, 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, 39 2 (31 n + 2265 n + 41294) a(n + 38) -1/2 ---------------------------------- (n + 39) (n + 36) 3 2 (472195 n + 8887088 n + 54674393 n + 110215684) a(n + 4) + 1/2 ---------------------------------------------------------- (n + 35) (n + 39) (n + 36) 3 2 (483936 n + 10124267 n + 69702295 n + 158225910) a(n + 5) + ----------------------------------------------------------- (n + 35) (n + 39) (n + 36) 3 2 (573981 n + 13171580 n + 100296599 n + 253414376) a(n + 6) + 3/2 ------------------------------------------------------------ (n + 35) (n + 39) (n + 36) 3 2 (2354987 n + 55703902 n + 435162003 n + 1121713132) a(n + 7) + 1/2 -------------------------------------------------------------- (n + 35) (n + 39) (n + 36) 3 2 (4259693 n + 101876682 n + 785858119 n + 1926544074) a(n + 8) + 1/3 --------------------------------------------------------------- (n + 35) (n + 39) (n + 36) 3 2 (8809039 n + 211399428 n + 1572053855 n + 3400384518) a(n + 9) + 1/6 ---------------------------------------------------------------- (n + 35) (n + 39) (n + 36) 3 2 (6274187 n + 118775646 n + 335769853 n - 2291699742) a(n + 10) + 1/6 ---------------------------------------------------------------- (n + 35) (n + 39) (n + 36) 3 2 (2653273 n + 4515342 n - 1009352587 n - 8108546604) a(n + 11) + 1/6 --------------------------------------------------------------- (n + 35) (n + 39) (n + 36) 3 2 (1375760 n + 83532081 n + 1454486428 n + 7764520179) a(n + 12) - 1/3 ---------------------------------------------------------------- (n + 35) (n + 39) (n + 36) 2 (n + 3) (23300 n + 239277 n + 586264) a(n + 2) + ----------------------------------------------- (n + 35) (n + 39) (n + 36) 2 (n + 4) (185727 n + 2297618 n + 6870783) a(n + 3) + 1/2 -------------------------------------------------- (n + 35) (n + 39) (n + 36) 3 2 (6845281 n + 316769832 n + 4811940029 n + 23962515234) a(n + 13) - 1/6 ------------------------------------------------------------------ (n + 35) (n + 39) (n + 36) 3 2 (3088373 n + 126258866 n + 1712396953 n + 7675336192) a(n + 14) - 1/2 ----------------------------------------------------------------- (n + 35) (n + 39) (n + 36) 3 2 (4595614 n + 185365881 n + 2425134797 n + 10166825172) a(n + 15) - 1/3 ------------------------------------------------------------------ (n + 35) (n + 39) (n + 36) 3 2 (1361504 n + 52880817 n + 597021625 n + 1581443862) a(n + 16) - 1/3 --------------------------------------------------------------- (n + 35) (n + 39) (n + 36) 3 2 (389417 n - 2517849 n - 455591033 n - 5091787347) a(n + 17) - 1/3 ------------------------------------------------------------- (n + 35) (n + 39) (n + 36) 3 2 (1381819 n + 83901213 n + 1698513665 n + 11430673839) a(n + 18) + 1/3 ----------------------------------------------------------------- (n + 35) (n + 39) (n + 36) 3 2 (1648624 n + 89602995 n + 1629404837 n + 9926345196) a(n + 19) + 2/3 ---------------------------------------------------------------- (n + 35) (n + 39) (n + 36) 3 2 (1390067 n + 100645734 n + 2318733733 n + 17207724642) a(n + 20) + 1/6 ------------------------------------------------------------------ (n + 35) (n + 39) (n + 36) 3 2 (1790143 n + 110174112 n + 2243745665 n + 15091613664) a(n + 21) + 1/6 ------------------------------------------------------------------ (n + 35) (n + 39) (n + 36) 3 2 (1136249 n + 67258008 n + 1310853979 n + 8397063516) a(n + 22) + 1/6 ---------------------------------------------------------------- (n + 35) (n + 39) (n + 36) 3 2 (2152481 n + 132728118 n + 2712341275 n + 18384297342) a(n + 23) - 1/6 ------------------------------------------------------------------ (n + 35) (n + 39) (n + 36) 3 2 (36293 n + 822358 n - 18419801 n - 413202978) a(n + 24) + 1/2 --------------------------------------------------------- (n + 35) (n + 39) (n + 36) 3 2 (87845 n + 8827422 n + 270630589 n + 2612445840) a(n + 25) - 1/6 ------------------------------------------------------------ (n + 35) (n + 39) (n + 36) 3 2 (272755 n + 19354044 n + 455332655 n + 3551568546) a(n + 26) - 1/3 -------------------------------------------------------------- (n + 35) (n + 39) (n + 36) 3 2 (456295 n + 33377874 n + 808535441 n + 6482321262) a(n + 27) + 1/6 -------------------------------------------------------------- (n + 35) (n + 39) (n + 36) 3 2 (5509 n + 1014792 n + 41481017 n + 486630210) a(n + 28) + 1/6 --------------------------------------------------------- (n + 35) (n + 39) (n + 36) 3 2 3 (3754 n + 283581 n + 7010959 n + 56445514) a(n + 29) - -------------------------------------------------------- (n + 35) (n + 39) (n + 36) 3 2 (23501 n + 1914292 n + 51715383 n + 463380408) a(n + 30) + 1/2 ---------------------------------------------------------- (n + 35) (n + 39) (n + 36) 3 2 (11133 n + 941168 n + 26411069 n + 245998326) a(n + 31) - 1/2 --------------------------------------------------------- (n + 35) (n + 39) (n + 36) 3 2 (3185 n + 299240 n + 9352783 n + 97278808) a(n + 32) - 1/2 ------------------------------------------------------ + a(n + 39) (n + 35) (n + 39) (n + 36) 72 (n + 1) (n + 2) (n + 3) a(n) + ------------------------------- (n + 35) (n + 39) (n + 36) 6 (n + 3) (n + 2) (559 n + 2737) a(n + 1) + ----------------------------------------- (n + 35) (n + 39) (n + 36) 3 2 (846 n + 71857 n + 1998755 n + 18122358) a(n + 33) + ---------------------------------------------------- (n + 35) (n + 39) (n + 36) 3 2 (453 n + 47866 n + 1676323 n + 19466130) a(n + 34) + ---------------------------------------------------- (n + 35) (n + 39) (n + 36) 3 2 (43 n + 4015 n + 123554 n + 1249712) a(n + 35) - ------------------------------------------------ (n + 35) (n + 39) (n + 36) 3 2 (379 n + 39854 n + 1395981 n + 16288146) a(n + 36) - 1/2 ---------------------------------------------------- (n + 35) (n + 39) (n + 36) 3 2 2 (44 n + 4678 n + 165671 n + 1954467) a(n + 37) + -------------------------------------------------- = 0 (n + 35) (n + 39) (n + 36) Subject to the initial conditions a(1) = 0, a(2) = 0, a(3) = 0, a(4) = 1, a(5) = 6, a(6) = 27, a(7) = 107, a(8) = 396, a(9) = 1406, a(10) = 4852, a(11) = 16401, a(12) = 54569, a(13) = 179316, a(14) = 583353, a(15) = 1882149, a(16) = 6030732, a(17) = 19210247, a(18) = 60883803, a(19) = 192116987, a(20) = 603894882, a(21) = 1891839298, a(22) = 5908786493, a(23) = 18405264103, a(24) = 57191790290, a(25) = 177326985812, a(26) = 548723407565, a(27) = 1694908981238, a(28) = 5226618478197, a(29) = 16092965162059, a(30) = 49481718179548, a(31) = 151947551816078, a(32) = 466041645080957, a(33) = 1427826354085962, a(34) = 4369981012482859, a(35) = 13361886803251904, a(36) = 40819516173317478, a(37) = 124596252379895222, a(38) = 380016267787374203, a(39) = 1158191919915824113 Lemma , 8.2, : Let b(n) be the number of words of length n in the alphabet , {1, 2, 3}, 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, 33 2 (13 n + 782 n + 11729) b(n + 32) 72 (n + 1) (n + 2) (n + 3) b(n) - --------------------------------- - ------------------------------- (n + 33) (n + 29) (n + 29) (n + 33) (n + 32) 6 (n + 3) (n + 2) (127 n + 577) b(n + 1) - ---------------------------------------- + b(n + 33) (n + 29) (n + 33) (n + 32) 2 (n + 3) (1324 n + 19059 n + 54824) b(n + 2) + -------------------------------------------- (n + 29) (n + 33) (n + 32) 2 (n + 4) (17577 n + 252142 n + 821337) b(n + 3) + 1/2 ----------------------------------------------- (n + 29) (n + 33) (n + 32) 3 2 (71589 n + 1470892 n + 9655923 n + 20452484) b(n + 4) + 1/2 ------------------------------------------------------- (n + 29) (n + 33) (n + 32) 3 2 (322853 n + 7425411 n + 55582936 n + 135892068) b(n + 5) + 1/3 ---------------------------------------------------------- (n + 29) (n + 33) (n + 32) 3 2 (1346023 n + 34714962 n + 292790123 n + 810079140) b(n + 6) + 1/6 ------------------------------------------------------------- (n + 29) (n + 33) (n + 32) 3 2 (1189912 n + 33558753 n + 311065265 n + 949765326) b(n + 7) + 1/3 ------------------------------------------------------------- (n + 29) (n + 33) (n + 32) 3 2 (1715953 n + 52697043 n + 532403882 n + 1773385998) b(n + 8) + 1/3 -------------------------------------------------------------- (n + 29) (n + 33) (n + 32) 3 2 (681388 n + 22953179 n + 254432302 n + 929816079) b(n + 9) + ------------------------------------------------------------ (n + 29) (n + 33) (n + 32) 3 2 (2045044 n + 74513367 n + 893514710 n + 3531855171) b(n + 10) + 1/3 --------------------------------------------------------------- (n + 29) (n + 33) (n + 32) 3 2 (1622105 n + 64976658 n + 851975803 n + 3666554538) b(n + 11) + 1/3 --------------------------------------------------------------- (n + 29) (n + 33) (n + 32) 3 2 (223601 n + 10089306 n + 147130715 n + 697838770) b(n + 12) + 3/2 ------------------------------------------------------------- (n + 29) (n + 33) (n + 32) 3 2 (189499 n + 10812934 n + 187308935 n + 1019277176) b(n + 13) + 1/2 -------------------------------------------------------------- (n + 29) (n + 33) (n + 32) 3 2 (122330 n + 2307711 n - 8781209 n - 232922592) b(n + 14) - 1/3 ---------------------------------------------------------- (n + 29) (n + 33) (n + 32) 3 2 (98204 n + 4132276 n + 57225769 n + 261554583) b(n + 15) - ---------------------------------------------------------- (n + 29) (n + 33) (n + 32) 3 2 (347438 n + 17236194 n + 283685569 n + 1551713751) b(n + 16) - 1/3 -------------------------------------------------------------- (n + 29) (n + 33) (n + 32) 3 2 2 (13783 n + 855328 n + 17000452 n + 109564527) b(n + 17) - ----------------------------------------------------------- (n + 29) (n + 33) (n + 32) 3 2 (51214 n + 3384519 n + 71937407 n + 496543824) b(n + 18) - 1/3 ---------------------------------------------------------- (n + 29) (n + 33) (n + 32) 3 2 (6133 n + 986280 n + 31378985 n + 281664474) b(n + 19) - 1/6 -------------------------------------------------------- (n + 29) (n + 33) (n + 32) 3 2 (82235 n + 4703280 n + 89333965 n + 563690352) b(n + 20) + 1/3 ---------------------------------------------------------- (n + 29) (n + 33) (n + 32) 3 2 (25943 n + 1246530 n + 18829897 n + 86204550) b(n + 21) - 1/6 --------------------------------------------------------- (n + 29) (n + 33) (n + 32) 3 2 (15667 n + 1140618 n + 27242777 n + 213743154) b(n + 22) + 1/6 ---------------------------------------------------------- (n + 29) (n + 33) (n + 32) 3 2 (4889 n + 328788 n + 7401451 n + 55802034) b(n + 23) + 2/3 ------------------------------------------------------ (n + 29) (n + 33) (n + 32) 3 2 2 (2647 n + 183013 n + 4209491 n + 32206401) b(n + 24) - -------------------------------------------------------- (n + 29) (n + 33) (n + 32) 3 2 (1513 n + 104652 n + 2398149 n + 18184378) b(n + 25) + ------------------------------------------------------ (n + 29) (n + 33) (n + 32) 3 2 (41 n + 4054 n + 124923 n + 1225470) b(n + 26) + ------------------------------------------------ (n + 29) (n + 33) (n + 32) 3 2 (623 n + 50036 n + 1333579 n + 11788710) b(n + 27) - ---------------------------------------------------- (n + 29) (n + 33) (n + 32) 3 2 (629 n + 51596 n + 1407503 n + 12766064) b(n + 28) + ---------------------------------------------------- (n + 29) (n + 33) (n + 32) 3 2 2 (68 n + 5535 n + 149784 n + 1347493) b(n + 29) - -------------------------------------------------- (n + 29) (n + 33) (n + 32) 3 2 2 (48 n + 4303 n + 128301 n + 1272234) b(n + 30) - -------------------------------------------------- (n + 29) (n + 33) (n + 32) 3 2 (61 n + 5514 n + 165931 n + 1662134) b(n + 31) + ------------------------------------------------ = 0 (n + 29) (n + 33) (n + 32) Subject to the initial conditions b(1) = 0, b(2) = 0, b(3) = 0, b(4) = 1, b(5) = 5, b(6) = 21, b(7) = 81, b(8) = 295, b(9) = 1037, b(10) = 3555, b(11) = 11963, b(12) = 39680, b(13) = 130118, b(14) = 422726, b(15) = 1362787, b(16) = 4364879, b(17) = 13902911, b(18) = 44071564, b(19) = 139122618, b(20) = 437565608, b(21) = 1371757661, b(22) = 4287990897, b(23) = 13369118554, b(24) = 41584891819, b(25) = 129076843463, b(26) = 399875205378, b(27) = 1236621762711, b(28) = 3818120395080, b(29) = 11771160083812, b(30) = 36240657107815, b(31) = 111435818770328, b(32) = 342251698657458, b(33) = 1050012648682487 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.573 1/2 - ----- 1/2 n The probability of Bob winning the bet, as n grows larger is approximately 1.49 1/2 - ---- 1/2 n You can see that indeed Alice has a better chance, but not significantly so. ----------------------------------------- This took, 90.037, seconds to generate ----------------------------------------------------------------------------\ ----------------------- Question Mumber, 9, : If Alice bets that there are more occurrences of consec\ utive substrings in, {[2, 1, 1, 3]}, 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 , 9.1, : Let a(n) be the number of words of length n in the alphabet , {1, 2, 3}, with more occurences of, {[2, 1, 1, 3]}, then , {[1, 1, 1, 1]} a(n) satisfies the following linear recurrence equation with polynomial coef\ ficients of order, 38 2 (31 n + 2203 n + 39060) a(n + 37) a(n + 38) - 1/2 ---------------------------------- (n + 38) (n + 35) 216 (n + 5) (n + 2) a(n + 1) + ---------------------------- (n + 35) (n + 34) (n + 38) 2 3 (n + 6) (389 n + 2901 n + 5188) a(n + 2) - ------------------------------------------- (n + 35) (n + 34) (n + 38) 3 2 (328046 n + 20263857 n + 414251905 n + 2802009129) a(n + 20) + 4/3 -------------------------------------------------------------- (n + 35) (n + 34) (n + 38) 3 2 (344965 n + 23902278 n + 545443613 n + 4105089024) a(n + 21) + 2/3 -------------------------------------------------------------- (n + 35) (n + 34) (n + 38) 3 2 (18785 n + 3213527 n + 115894434 n + 1193522016) a(n + 22) + 1/2 ------------------------------------------------------------ (n + 35) (n + 34) (n + 38) 3 2 (307889 n + 20313723 n + 442608994 n + 3179298864) a(n + 23) - 1/3 -------------------------------------------------------------- (n + 35) (n + 34) (n + 38) 3 2 (204435 n + 14942025 n + 362732878 n + 2924448792) a(n + 24) - 1/2 -------------------------------------------------------------- (n + 35) (n + 34) (n + 38) 3 2 (220103 n + 18065337 n + 489747418 n + 4390922760) a(n + 25) - 1/6 -------------------------------------------------------------- (n + 35) (n + 34) (n + 38) 3 2 (34919 n + 2389419 n + 52992274 n + 376153152) a(n + 26) + 1/3 ---------------------------------------------------------- (n + 35) (n + 34) (n + 38) 3 2 (142477 n + 11370603 n + 302015630 n + 2669572296) a(n + 27) + 1/6 -------------------------------------------------------------- (n + 35) (n + 34) (n + 38) 3 2 (11247 n + 961805 n + 27399074 n + 260059104) a(n + 28) + --------------------------------------------------------- (n + 35) (n + 34) (n + 38) 3 2 2 (1835 n + 141822 n + 3612763 n + 30257832) a(n + 29) - -------------------------------------------------------- (n + 35) (n + 34) (n + 38) 3 2 (7889 n + 698731 n + 20608134 n + 202409712) a(n + 30) - 1/2 -------------------------------------------------------- (n + 35) (n + 34) (n + 38) 3 2 2 (647 n + 61652 n + 1955133 n + 20641026) a(n + 31) - ------------------------------------------------------ (n + 35) (n + 34) (n + 38) 3 2 (2401 n + 219507 n + 6692018 n + 68058696) a(n + 32) + 1/2 ------------------------------------------------------ (n + 35) (n + 34) (n + 38) 3 2 (457 n + 45807 n + 1522646 n + 16788000) a(n + 33) + 1/2 ---------------------------------------------------- (n + 35) (n + 34) (n + 38) 3 2 (n + 703 n + 43272 n + 697740) a(n + 34) + ------------------------------------------ (n + 35) (n + 34) (n + 38) 3 2 (385 n + 39347 n + 1339406 n + 15187000) a(n + 35) - 1/2 ---------------------------------------------------- (n + 35) (n + 34) (n + 38) 3 2 2 (44 n + 4546 n + 156447 n + 1793430) a(n + 36) + -------------------------------------------------- (n + 35) (n + 34) (n + 38) 3 2 (4955 n + 87477 n + 506404 n + 943440) a(n + 3) - ------------------------------------------------- (n + 35) (n + 34) (n + 38) 3 2 (11191 n + 286761 n + 2283797 n + 5659128) a(n + 4) - 2/3 ----------------------------------------------------- (n + 35) (n + 34) (n + 38) 3 2 (51893 n + 116103 n - 6815678 n - 34058952) a(n + 5) + 1/6 ------------------------------------------------------ (n + 35) (n + 34) (n + 38) 3 2 (397583 n + 7195257 n + 36160810 n + 36360456) a(n + 6) + 1/6 --------------------------------------------------------- (n + 35) (n + 34) (n + 38) 3 2 (549451 n + 13027197 n + 96799250 n + 221229192) a(n + 7) + 1/3 ----------------------------------------------------------- (n + 35) (n + 34) (n + 38) 3 2 (652459 n + 18830529 n + 173137134 n + 507433400) a(n + 8) + 1/2 ------------------------------------------------------------ (n + 35) (n + 34) (n + 38) 3 2 (2588831 n + 91048209 n + 1008988954 n + 3565998648) a(n + 9) + 1/6 --------------------------------------------------------------- (n + 35) (n + 34) (n + 38) 3 2 (382485 n + 17456489 n + 236920210 n + 1000162712) a(n + 10) + -------------------------------------------------------------- (n + 35) (n + 34) (n + 38) 3 2 (711259 n + 71881557 n + 1360109066 n + 7167987960) a(n + 11) + 1/6 --------------------------------------------------------------- (n + 35) (n + 34) (n + 38) 3 2 (1069999 n + 12158997 n - 200317606 n - 2283608136) a(n + 12) - 1/3 --------------------------------------------------------------- (n + 35) (n + 34) (n + 38) 3 2 2 (440006 n + 13502073 n + 121792879 n + 271459128) a(n + 13) - --------------------------------------------------------------- (n + 35) (n + 34) (n + 38) 3 2 (7376933 n + 285388575 n + 3580681174 n + 14465647728) a(n + 14) - 1/6 ------------------------------------------------------------------ (n + 35) (n + 34) (n + 38) 3 2 (1844432 n + 82877181 n + 1227701569 n + 5997474006) a(n + 15) - 2/3 ---------------------------------------------------------------- (n + 35) (n + 34) (n + 38) 3 2 (1712059 n + 88157369 n + 1498655726 n + 8426053048) a(n + 16) - 1/2 ---------------------------------------------------------------- (n + 35) (n + 34) (n + 38) 3 2 (1776467 n + 114682389 n + 2366384626 n + 15819843312) a(n + 17) - 1/6 ------------------------------------------------------------------ (n + 35) (n + 34) (n + 38) 3 2 2 (109342 n + 4355492 n + 48278355 n + 94797090) a(n + 18) + ------------------------------------------------------------ (n + 35) (n + 34) (n + 38) 3 2 (934239 n + 51456637 n + 933050446 n + 5555350488) a(n + 19) + 1/2 -------------------------------------------------------------- (n + 35) (n + 34) (n + 38) 81 (n + 4) (n + 2) (n + 1) a(n) + ------------------------------- = 0 (n + 35) (n + 34) (n + 38) Subject to the initial conditions a(1) = 0, a(2) = 0, a(3) = 0, a(4) = 1, a(5) = 6, a(6) = 27, a(7) = 108, a(8) = 402, a(9) = 1433, a(10) = 4959, a(11) = 16794, a(12) = 55952, a(13) = 184040, a(14) = 599145, a(15) = 1934082, a(16) = 6199340, a(17) = 19752032, a(18) = 62610008, a(19) = 197578067, a(20) = 621068212, a(21) = 1945566064, a(22) = 6076120825, a(23) = 18924399615, a(24) = 58796804356, a(25) = 182274050163, a(26) = 563929898544, a(27) = 1741536721597, a(28) = 5369277031303, a(29) = 16528556825567, a(30) = 50809321270824, a(31) = 155987100929890, a(32) = 478314181521671, a(33) = 1465059225247587, a(34) = 4482793598969733, a(35) = 13703292240335204, a(36) = 41851573465731028, a(37) = 127712934689139615, a(38) = 389419305363501390 Lemma , 9.2, : Let b(n) be the number of words of length n in the alphabet , {1, 2, 3}, with more occurences of, {[1, 1, 1, 1]}, then , {[2, 1, 1, 3]} b(n) satisfies the following linear recurrence equation with polynomial coef\ ficients of order, 12 (n + 1) (n + 2) b(n) (n + 19) (n + 2) b(n + 1) -9/2 -------------------- - 3/2 ------------------------- (n + 12) (n + 8) (n + 12) (n + 8) 2 (23 n + 21 n - 158) b(n + 2) + 1/2 ----------------------------- (n + 12) (n + 8) 2 2 (131 n + 1057 n + 2082) b(n + 3) (52 n + 445 n + 894) b(n + 4) + 1/2 --------------------------------- + ------------------------------ (n + 12) (n + 8) (n + 12) (n + 8) 2 2 (41 n + 447 n + 1138) b(n + 5) (n - 31 n - 198) b(n + 6) + ------------------------------- - -------------------------- (n + 12) (n + 8) (n + 12) (n + 8) 2 2 (25 n + 395 n + 1582) b(n + 7) (33 n + 479 n + 1642) b(n + 8) - ------------------------------- - 1/2 ------------------------------- (n + 12) (n + 8) (n + 12) (n + 8) 2 (15 n + 263 n + 1074) b(n + 9) - 1/2 ------------------------------- (n + 12) (n + 8) 2 (43 n + 773 n + 3346) b(n + 10) + 1/2 -------------------------------- (n + 12) (n + 8) 2 (17 n + 323 n + 1478) b(n + 11) - 1/2 -------------------------------- + b(n + 12) = 0 (n + 12) (n + 8) Subject to the initial conditions b(1) = 0, b(2) = 0, b(3) = 0, b(4) = 1, b(5) = 5, b(6) = 21, b(7) = 81, b(8) = 295, b(9) = 1037, b(10) = 3555, b(11) = 11961, b(12) = 39668 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.541 1/2 - ----- 1/2 n The probability of Bob winning the bet, as n grows larger is approximately 1.55 1/2 - ---- 1/2 n You can see that indeed Alice has a better chance, but not significantly so. ----------------------------------------- This took, 58.942, seconds to generate ----------------------------------------------------------------------------\ ----------------------- Question Mumber, 10, : If Alice bets that there are more occurrences of conse\ cutive substrings in, {[1, 2, 1, 3]}, 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 , 10.1, : Let a(n) be the number of words of length n in the alphabet , {1, 2, 3}, with more occurences of, {[1, 2, 1, 3]}, then , {[1, 1, 1, 1]} a(n) satisfies the following linear recurrence equation with polynomial coef\ ficients of order, 30 2 (37 n + 2031 n + 27770) a(n + 29) -1/2 ---------------------------------- (n + 27) (n + 30) 2 (n + 3) (91 n + 1155 n + 3176) a(n + 2) - 81/2 ---------------------------------------- + a(n + 30) (n + 30) (n + 27) (n + 26) (n + 1) (n + 2) (n + 3) a(n) - 729/2 ---------------------------- (n + 30) (n + 27) (n + 26) (n + 4) (n + 3) (n + 2) a(n + 1) + 729/2 -------------------------------- (n + 30) (n + 27) (n + 26) 3 2 (1683 n + 126427 n + 3161758 n + 26325262) a(n + 26) + 1/2 ------------------------------------------------------ (n + 30) (n + 27) (n + 26) 3 2 (503 n + 38683 n + 990465 n + 8444286) a(n + 27) - -------------------------------------------------- (n + 30) (n + 27) (n + 26) 3 2 (275 n + 21682 n + 569075 n + 4972680) a(n + 28) + 1/2 -------------------------------------------------- (n + 30) (n + 27) (n + 26) 3 2 (913 n + 94614 n + 767417 n + 474771) a(n + 7) - ------------------------------------------------ (n + 30) (n + 27) (n + 26) 3 2 (8233 n - 28649 n - 1883954 n - 8408271) a(n + 8) + --------------------------------------------------- (n + 30) (n + 27) (n + 26) 3 2 (23641 n + 160044 n - 4775443 n - 39342936) a(n + 9) + 1/2 ------------------------------------------------------ (n + 30) (n + 27) (n + 26) 3 2 (34672 n + 538897 n - 229135 n - 21868636) a(n + 10) - 1/2 ------------------------------------------------------ (n + 30) (n + 27) (n + 26) 3 2 (95102 n + 2469663 n + 21370303 n + 65244534) a(n + 11) - 1/2 --------------------------------------------------------- (n + 30) (n + 27) (n + 26) 3 2 (211598 n + 8206971 n + 103831581 n + 429244146) a(n + 12) - 1/2 ------------------------------------------------------------ (n + 30) (n + 27) (n + 26) 3 2 (108908 n + 5175783 n + 79776577 n + 401112420) a(n + 13) + 1/2 ----------------------------------------------------------- (n + 30) (n + 27) (n + 26) 3 2 (30129 n + 299663 n - 8995384 n - 101530390) a(n + 14) + 1/2 -------------------------------------------------------- (n + 30) (n + 27) (n + 26) 3 2 3 (11382 n + 450434 n + 5702525 n + 22658436) a(n + 15) + --------------------------------------------------------- (n + 30) (n + 27) (n + 26) 3 2 (19530 n + 1203245 n + 23110412 n + 141431523) a(n + 16) + ---------------------------------------------------------- (n + 30) (n + 27) (n + 26) 3 2 (10230 n + 451172 n + 6139171 n + 24101664) a(n + 17) - ------------------------------------------------------- (n + 30) (n + 27) (n + 26) 3 2 (19970 n + 981733 n + 16013230 n + 86825325) a(n + 18) - -------------------------------------------------------- (n + 30) (n + 27) (n + 26) 3 2 (11641 n + 395678 n + 2577776 n - 13776236) a(n + 19) + ------------------------------------------------------- (n + 30) (n + 27) (n + 26) 3 2 (39007 n + 1898422 n + 29446063 n + 141949956) a(n + 20) - 1/2 ---------------------------------------------------------- (n + 30) (n + 27) (n + 26) 3 2 (29890 n + 1643701 n + 29754901 n + 176944506) a(n + 21) + 1/2 ---------------------------------------------------------- (n + 30) (n + 27) (n + 26) 3 2 (3361 n + 250229 n + 6011706 n + 46948832) a(n + 22) + 1/2 ------------------------------------------------------ (n + 30) (n + 27) (n + 26) 3 2 (3967 n + 249214 n + 5179818 n + 35588137) a(n + 23) - ------------------------------------------------------ (n + 30) (n + 27) (n + 26) 3 2 (911 n + 44988 n + 615041 n + 1449018) a(n + 24) + 1/2 -------------------------------------------------- (n + 30) (n + 27) (n + 26) 3 2 (678 n + 47893 n + 1125465 n + 8798288) a(n + 25) - 1/2 --------------------------------------------------- (n + 30) (n + 27) (n + 26) 3 2 (122 n + 1891 n + 10235 n + 18498) a(n + 3) - 81/2 --------------------------------------------- (n + 30) (n + 27) (n + 26) 3 2 (1862 n + 17913 n + 33211 n - 50334) a(n + 4) + 9/2 ----------------------------------------------- (n + 30) (n + 27) (n + 26) 3 2 (1119 n + 41105 n + 386386 n + 1081842) a(n + 5) + 9/2 -------------------------------------------------- (n + 30) (n + 27) (n + 26) 3 2 3 (6344 n + 171433 n + 1584753 n + 4871745) a(n + 6) + ------------------------------------------------------ = 0 (n + 30) (n + 27) (n + 26) Subject to the initial conditions a(1) = 0, a(2) = 0, a(3) = 0, a(4) = 1, a(5) = 6, a(6) = 27, a(7) = 107, a(8) = 397, a(9) = 1412, a(10) = 4878, a(11) = 16502, a(12) = 54938, a(13) = 180612, a(14) = 587784, a(15) = 1896998, a(16) = 6079739, a(17) = 19370043, a(18) = 61399782, a(19) = 193769676, a(20) = 609152729, a(21) = 1908470401, a(22) = 5961131965, a(23) = 18569309280, a(24) = 57703949032, a(25) = 178920638342, a(26) = 553667549158, a(27) = 1710206891884, a(28) = 5273839269417, a(29) = 16238408612534, a(30) = 49928814854557 Lemma , 10.2, : Let b(n) be the number of words of length n in the alphabet , {1, 2, 3}, with more occurences of, {[1, 1, 1, 1]}, then , {[1, 2, 1, 3]} b(n) satisfies the following linear recurrence equation with polynomial coef\ ficients of order, 15 (n + 1) (n + 2) b(n) (n + 5) (n + 2) b(n + 1) -81/4 -------------------- - 27/2 ------------------------ (n + 15) (n + 11) (n + 15) (n + 11) 2 (4 n + 11) (n + 2) b(n + 2) (43 n + 680 n + 2043) b(n + 3) - 9/2 --------------------------- + 3/2 ------------------------------- (n + 15) (n + 11) (n + 15) (n + 11) 2 (9 n + 29 n - 122) b(n + 4) - 15/4 ---------------------------- (n + 15) (n + 11) 2 (136 n + 2033 n + 7557) b(n + 5) + 1/2 --------------------------------- (n + 15) (n + 11) 2 2 (71 n + 859 n + 2594) b(n + 6) (142 n + 2118 n + 7769) b(n + 7) + 3/2 ------------------------------- + --------------------------------- (n + 15) (n + 11) (n + 15) (n + 11) 2 (39 n + 457 n + 746) b(n + 8) + 3/4 ------------------------------ (n + 15) (n + 11) 2 (65 n + 1294 n + 6768) b(n + 9) - 1/2 -------------------------------- (n + 15) (n + 11) 2 2 (46 n + 809 n + 3375) b(n + 10) (9 n + 26 n - 776) b(n + 11) - 3/2 -------------------------------- + 1/2 ----------------------------- (n + 15) (n + 11) (n + 15) (n + 11) 2 2 (19 n + 431 n + 2460) b(n + 12) (14 n + 342 n + 2047) b(n + 13) + 1/4 -------------------------------- + -------------------------------- (n + 15) (n + 11) (n + 15) (n + 11) 2 (15 n + 377 n + 2320) b(n + 14) - 1/2 -------------------------------- + b(n + 15) = 0 (n + 15) (n + 11) Subject to the initial conditions b(1) = 0, b(2) = 0, b(3) = 0, b(4) = 1, b(5) = 5, b(6) = 21, b(7) = 80, b(8) = 291, b(9) = 1021, b(10) = 3495, b(11) = 11749, b(12) = 38940, b(13) = 127614, b(14) = 414393, b(15) = 1335416 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.548 1/2 - ----- 1/2 n The probability of Bob winning the bet, as n grows larger is approximately 1.57 1/2 - ---- 1/2 n You can see that indeed Alice has a better chance, but not significantly so. ----------------------------------------- This took, 47.157, seconds to generate The best bet against, [1, 1, 1, 1], is a member of, {[1, 1, 1, 2], [1, 1, 1, 3], [2, 1, 1, 1], [3, 1, 1, 1]}, 1.221 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], [1, 1, 2, 3], [1, 1, 3, 2], [1, 1, 3, 3], [2, 2, 1, 1], [2, 3, 1, 1], [3, 2, 1, 1], [3, 3, 1, 1]}, 1.059 and then your edge is approximately, ----- 1/2 n The next best bet is a member of, {[1, 2, 1, 3], [1, 2, 2, 2], [1, 2, 2, 3], [1, 2, 3, 2], [1, 2, 3, 3], [1, 3, 1, 2], [1, 3, 2, 2], [1, 3, 2, 3], [1, 3, 3, 2], [1, 3, 3, 3], [2, 1, 3, 1], [2, 2, 2, 1], [2, 2, 3, 1], [2, 3, 2, 1], [2, 3, 3, 1], [3, 1, 2, 1], [3, 2, 2, 1], [3, 2, 3, 1], 1.022 [3, 3, 2, 1], [3, 3, 3, 1]}, and then your edge is approximately, ----- 1/2 n The next best bet is a member of, {[2, 1, 1, 3], [2, 1, 2, 3], [2, 1, 3, 3], [2, 2, 1, 3], [2, 2, 2, 3], [2, 2, 3, 3], [2, 3, 1, 3], [2, 3, 3, 3], [3, 1, 1, 2], [3, 1, 2, 2], [3, 1, 3, 2], [3, 2, 1, 2], [3, 2, 2, 2], [3, 3, 1, 2], [3, 3, 2, 2], [3, 3, 3, 2]}, 1.009 and then your edge is approximately, ----- 1/2 n The next best bet is a member of, {[1, 1, 2, 1], [1, 1, 3, 1], [1, 2, 1, 1], [1, 3, 1, 1]}, 0.979 and then your edge is approximately, ----- 1/2 n The next best bet is a member of, {[1, 2, 2, 1], [1, 2, 3, 1], [1, 3, 2, 1], [1, 3, 3, 1]}, 0.943 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, 1, 3, 2], [2, 2, 1, 2], [2, 2, 3, 2], [2, 3, 1, 2], [2, 3, 2, 2], [2, 3, 3, 2], [3, 1, 1, 3], [3, 1, 2, 3], [3, 1, 3, 3], [3, 2, 1, 3], [3, 2, 2, 3], [3, 2, 3, 3], [3, 3, 1, 3], [3, 3, 2, 3]}, 0.917 and then your edge is approximately, ----- 1/2 n The next best bet is a member of, {[1, 2, 1, 2], [1, 3, 1, 3], [2, 1, 2, 1], [3, 1, 3, 1]}, 0.758 and then your edge is approximately, ----- 1/2 n The next best bet is a member of, {[2, 3, 2, 3], [3, 2, 3, 2]}, 0.746 and then your edge is approximately, ----- 1/2 n The next best bet is a member of, {[2, 2, 2, 2], [3, 3, 3, 3]}, and then your edge is exactly 0 ----------------------- This ends this chapter that took, 592.236, seconds to generate.