Question: A string $s_1s_2\ldots s_n$ is a palindrome if $s_1s_2\ldots s_{n-1}s_n = s_ns_{n-1}…s_2s_1 $; i.e reading the string from left to right gives the same result as reading the string from right to left.
Let $n \ge 3$, be an odd integer. You are given a string of length $n$, in which each character is a uniformly random element of $\{a,b,c\}$. The characters are independent of each other. What is the probability that this bitstring is a palindrome?
Answer: $(1/3)^{(n-1)/2}$
Attempt:
I took $n=3$, with a string aba to make a palindrome. For the first character a, I have 3 options and must choose one of them. For b, I have 2 options and I must choose 1. And for a, I have 1 option and must pick 1 to make it a palindrome.
I used the binomial for all three cases and got
$$
Pr(A_1) = \binom{3}{1}*(1/3)^1*(1 – 1/3)^2 = 4/9\\
Pr(A_2) = \binom{2}{1}*(1/2)^1*(1-1/2)^1 = 1/2\\
Pr(A_3) = \binom{1}{1}*(1/2)^1*(1/2)^0 = 1/2
$$
Finally,
$$Pr(A) = (4/9)*(1/2)*(1/2) = 1/9 = (1/3)^{(n+1)/2}
\quad {\text for } \quad n=3$$
But according to the answer, it should be $Pr(A) = 1/3$. Where did I go wrong?
Best Answer
The idea is, out of $n = 2k+1$ positions, you pick the first $k+1$, then fix the last $k$ to be exactly like the first $k$ in reverse order. The number of such strings is $3^{k+1}$. The total number of string in question is $3^n=3^{2k+1}$, so the probability would be $$ 3^{k+1}/3^n = 3^{k+1-(2k+1)} = 3^{-k}. $$