Given a string, you keep swapping any two characters in the string randomly till the string becomes a palindrome. What is the expected number of swaps you will make? There will always be at least one palindrome which can be formed with the letters of the given string.
The length of the string will be at most 8 characters.
The string will consist of only lower-case letters ‘a’-‘z’.
How do I calculate this Expected value?
Best Answer
For any particular string, a Markov chain analysis can be done. But it will be complicated. I would be very surprised if there is a simple general formula.
EDIT: For example, consider the case $n=8$ with four distinct letters $abcd$, each occurring twice. Taking into account symmetries (permutations of the letters, and permutations of $1\ldots8$ that preserve the pairings $(1,8), (2,7), (3,6), (4,5)$, there are five states: $$ \eqalign{[a, b, c, d, a, b, c, d]\cr [a, b, c, d, a, b, d, c]\cr [a, b, c, d, a, c, b, d]\cr [a, b, c, d, a, c, d, b]\cr [a, b, c, d, d, c, b, a]\cr}$$ of which the last is a palindrome. I get a transition matrix of $$ P = \pmatrix{2/7 & 4/7 & 1/7 & 0 &0 \cr 1/7 & 4/7 & 0 & 2/7 & 0\cr 1/7 & 0 & 3/14 & 4/7 & 1/14 \cr 0 & 3/7 & 3/14 & 5/14 &0\cr 0 & 0 & 0 & 0 & 1\cr}$$ For example, the entry $P_{13} = 1/7 = 4/28$ because from state $1$, four of the $28$ possible transpositions go to state $3$: $(1,4)$, $(2,3)$, $(5,8)$, $(6,7)$. Thus $(1,4)$ takes $(a,b,c,d,a,b,c,d)$ to $(d,b,c,a,a,b,c,d)$, which becomes $(b,d,a,c,b,a,d,c]$ by interchanging positions $1$ with $2$, $3$ with $4$, $5$ with $6$, $7$ with $8$, and then $(a,b,c,d,a,c,b,d)$ by permuting the letters ($a \to c \to d \to b \to a$).
Writing $P$ in block-matrix form as $\pmatrix{A & B\cr 0 & 1\cr}$ where $A$ is the top left $4 \times 4$ block, the expected numbers of steps until absorption in state $5$, starting in each of the first four states, form the column vector $$ u = (I - A)^{-1}\pmatrix{1\cr 1\cr 1\cr 1\cr} = \pmatrix{5201/39 \cr 1750/13 \cr 364/3 \cr 5138/39\cr}$$