I am flipping a coin at least 3 times, and then until the sequence of coin flips is a palindrome. What is the mean number of flips I will perform? What is the probability I won't stop?
$\begingroup$
$\endgroup$
6
-
$\begingroup$ 11 or 00 are no palindromes, but 101, 111, 000, 010 are palindromes? I'm irritated. $\endgroup$– Dieter KadelkaCommented Jul 8, 2020 at 19:16
-
3$\begingroup$ @DieterKadelka Well, you have to require some minimum length, else you'll never get past one flip. $\endgroup$– Brian HopkinsCommented Jul 8, 2020 at 19:34
-
$\begingroup$ I'd keep this open. There are some subtle dependencies, e.g.: If the first three flips are not a palindrome, and the first four flips are not a palindrome, then the first four are either HHTH, HHTT, HTTT, THHH, TTHH, TTHT. So the conditional probability of getting a palindrome at the fifth throw is 1/3. $\endgroup$– user44143Commented Jul 8, 2020 at 19:40
-
2$\begingroup$ The unrestricted question was posed on Quora in 2016 and answers there suggest why the three flip minimum makes a more interesting question. $\endgroup$– Brian HopkinsCommented Jul 8, 2020 at 19:43
-
2$\begingroup$ The last section of Problems and Snapshots from the World of Probability could also be relevant; $\S$17.6 "Palindromes" starting on p244. The book is by Blom, Holst, and Sandell, published by Springer in 1994. $\endgroup$– Brian HopkinsCommented Jul 8, 2020 at 20:02
|
Show 1 more comment
2 Answers
$\begingroup$
$\endgroup$
Let's distinguish some cases. If the first two flips result in HT or TH then with probability 1 you will flip a palindrome. Indeed, this will happen at the time $n$ when the $n$-th flip coincides with the first one. You can easily calculate the expected value of $n$ to be 4.
If the first two flips result in HH or TT then we distinguish two more cases. Either the third flips coincides with the first two or it doesn't. In the former case then you get a palindrome and it happens with probability 1/4. All the intricacy of the problem is in the last case. Let's prove that with positive probability you won't stop (so in the end the expected value is infinity, as already discussed by mike).
WLOG, assume that the first three flips are TTH. The possible palindromes starting with TTH are of the form TTHTT or TTH$w$HTT where $w$ is a palindrome word (possibly empty). If $n=2k$ or $2k+1$ then the probability of flipping a palindrome word of length $n$ is $\frac{1}{2^k}$. Therefore, by a union bound, the probability of flipping a palindrome (given that the sequence starts with TTH) is less than
$$\frac{1}{4} + \left(2\sum_{k=0}^\infty \frac{1}{2^k}\right)\cdot\frac{1}{8}=\frac{3}{4}$$
All in all, with probability $>\frac{1}{16}$ you will not flip a palindrome (this lower bound is obviously not optimal).
$\begingroup$
$\endgroup$
Long comment: I think the expected number of tosses in $\infty$ and you can show it along the following lines: The probability of a palindrome of even length is the the same as the probablility that the sequence of flips exactly reverses the second half of the palindrome, i.e., HHTH HTHH is a palindrome of length 8 and HHTH THTT is the sequence that exactly reverses the second half , however, the reversed sequence will cause a random walk based on it to return to 0, and so occurs later than the first return time to 0, which has infinite expectation. Of course, you have to do something about odd ones.
