Two players alternately flip coins into a row; the first player wins as soon as the whole row is a reflected sequence (a palindrome).
probability/flips/reflected.sequence New
New entry, edited from material collected for the archive and not yet in a released version.
Problem
Two players alternately flip coins into a row; the first player wins as soon as the whole row is a reflected sequence (a palindrome). What is the chance that this never happens? First my sister flips a coin and then I flip a coin. The two coins are put in a row (first hers then mine). If they match, she wins. If not, then two more are flipped, and placed in the row. Now, if they form a reflected sequence (HTTH or THHT) she wins. If not, the game continues with her winning once the coins that have been placed form a reflected sequence. If it never does, then I win. Obviously she has the advantage (50% chance of winning after only the first toss), but do I have any chance of winning? That is, as the number of coins grows without bound what is the likelihood that we never form a reflected sequence? -- Matthew Roozee <mroozee@math.uci.edu> [ Editor: the first paragraph is the editor's summary. ]
Show solution
With 2 coins there are 2 winning combinations out of 4 (AA and BB). With 4 coins there are 4 winning combinations out of 16 (AAAA, ABBA, BAAB and BBBB), but 2 of them (AAAA and BBBB) were already won with 2 coins, and thus never reached, leaving only 2 new winning combinations. With 2*n coins where n is odd the number of new winning combinations is twice the number for 2*(n-1) coins, as there is one 2*(n-1) coins winning combination wxyzzyxw for the two 2*n coins winning combinations wxyzAAzyxw and wxyzBBzyxw. No part of these combinations of less than n coins can be a winning combination, as it is already ruled out for 2*(n-1) coins. No part of these combinations of more than n coins can be a winning combination unless they are all the same, but this is ruled out after n = 1. With 2*n coins where n is even the number of new winning combinations is twice the number for 2*(n-1) coins minus the number of new winning combinations for n coins, as there is one 2*(n-1) coins winning combination vwxyzzyxwv for the two 2*n coins winning combinations vwxyzAAzyxwv and vwxyzBBzyxwv, but this winning combination is ruled out if vwxyzA or vwxyzB is a winning combination for n coins. There are no other partial winning combinations for the same reasons as above. This means that the number of winning combinations for 2*n coins is as follows: f(1) = 2 f(2) = 2 f(n) = 2 * f(n-1) for odd n f(n) = 2 * f(n-1) - f(n/2) for even n Thus f(3) = 4, f(4) = 6, f(5) = 12, f(6) = 20, f(7) = 40, f(8) = 74, etc. For 2*n coins the total number of combinations is 4^n, and thus the probability of a winning combination is p(n)=f(n)/4^n. Thus p(1) = 1/2, p(2) = 1/8, p(3) = 1/16, p(4) = 3/128, p(5) = 3/256, p(6) = 5/1024, p(7) = 5/2048, p(8) = 37/32768, etc. The sum of these probabilities quickly converges to 0.732213159... A computer simulation verifies this result. Thus the brother has roughly a 27% chance of winning, whereas the sister has roughly a 73% chance, when the number of coins is large (about 40 or more in practice). -- Ilan Mayer