Probability of sequence of coin flips palindrome 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?
 A: 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.
A: 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).
