What is the probability that, after 50 days, every person has their own hat back?

Question

Enzo, Rico and John each has a distinct hat. Every day, two of these three people, selected randomly, switch their hats. What is the probability that, after 50 days, every person has their own hat back?

Answer 1

Hint: Try proving that after an odd number of days there will always be exactly one person with the correct hat.

It is impossible for exactly two people to have the correct hat since that would imply that the third would also have the correct hat. It is impossible for all three to have the correct hat since that corresponds to the identity permutation which is an even permutation and cannot be represented as a product of an odd number of transpositions. How about zero?

Answer 2

Group the $50$ days into $25$ pairs. It is easy to verify manually that there is a $\frac13$ chance of each of the following outcomes for each pair of days:

• everyone keeps the hats they had before the pair of days elapsed
• everyone's hats shift one person right
• everyone's hats shift two persons right

Now suppose we have a column vector $(a_n,b_n,c_n)^T$ representing the probabilities of the hats being shifted $0,1,2$ places to the right respectively after $n$ pairs of days. We have $$\begin{bmatrix}a_n\\b_n\\c_n\end{bmatrix}=\begin{bmatrix}1/3&1/3&1/3\\ 1/3&1/3&1/3\\ 1/3&1/3&1/3\end{bmatrix}^n\begin{bmatrix}1\\0\\0\end{bmatrix}$$ But $(a_1,b_1,c_1)^T=(1/3,1/3,1/3)^T$ and left-multiplying this by the given square matrix gives back itself. Thus we must have $a_{25}=\frac13$, the final answer.

Answer 3

We can model the situation as a Markov process. The persons are (labels) 1, 2, 3. They stay always in thsi order. Their hats are also 1, 2, 3. The order of them is the one given by the person having it. Each possible permutation of the hats is possible. So we have six states, 123, 213, 132, 321, 231, 312. From each state there is in one step a join to exactly three other states (among the six). We assume (as specified in the OP) that the transition probabilities are $1/3$ from the state $s$ to the state $t$, if there is a transposition leading from $s$ to $t$. Else $0$. The chain is then in a raw picture:

123  231   312
 |\\/ | \//|
 | X  X  X |
 |//\ | /\\|
213  132  321

In words, from each even permutation there is exactly one path to each odd permutation, and conversely.

The transition matrix is thus $$ A=\frac 13 \begin{bmatrix} &&&1&1&1\\ &&&1&1&1\\ &&&1&1&1\\ 1&1&1&&&\\ 1&1&1&&&\\ 1&1&1&&& \end{bmatrix} \ , $$ (with zeros in the missing entries) Then $U:=A^2$ is $$ U:=A^2= \frac 13 \begin{bmatrix} 1&1&1&&&\\ 1&1&1&&&\\ 1&1&1&&&\\ &&&1&1&1\\ &&&1&1&1\\ &&&1&1&1 \end{bmatrix} \ , $$ And the powers of $U$ equal $U$, $U=U^2=U^3=\dots$ , so that $U=U^{25}=A^{50}$ gives the transition matrix for the $50$ days. The probability to land from $123$ in $123$ after $50$ days is thus $$\frac 13\ .$$