Friday, May 10, 2013

Nine squares

If you are in Hong Kong and you need help for university mathematics courses, please visit  www.all-r-math.com.

Question: There are 9 squares, 3 black and 6 red. In each turn, a square is chosen randomly and its color is then switched. The process continues until all squares have the same color. What is the probability that all squares are red at the end?

REDREDBLACK
BLACKREDRED
REDREDBLACK


Answer: Let $P_k$ be the probability of all red at the end if currently there are $k$ red squares. Note in that turn, there are $\frac{k}9$ chance that a red square turns black and $\frac{9-k}9$ chance that a black square turns red. Therefore $$P_k=\frac{k}{9}P_{k-1}+\frac{k}{9}P_{k+1}, k=1,2,\ldots,8. P_0=0, P_9=1$$ Or in matrix notation, $$\begin{pmatrix}P_0\\P_1\\P_2\\P_3\\P_4\\P_5\\P_6\\P_7\\P_8\\P_9\end{pmatrix}= \begin{pmatrix}1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 1/9 & 0 & 8/9 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 2/9 & 0 & 7/9 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 3/9 & 0 & 6/9 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 4/9 & 0 & 5/9 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 5/9 & 0 & 4/9 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 6/9 & 0 & 3/9 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 7/9 & 0 & 2/9 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 8/9 & 0 & 1/9 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 \end{pmatrix} \begin{pmatrix}P_0\\P_1\\P_2\\P_3\\P_4\\P_5\\P_6\\P_7\\P_8\\P_9\end{pmatrix}$$ Hence $$\begin{pmatrix}P_0\\P_1\\P_2\\P_3\\P_4\\P_5\\P_6\\P_7\\P_8\\P_9\end{pmatrix} =\begin{pmatrix}0 \\ 35/83 \\ 315/664 \\ 325/664 \\ 165/332 \\ 167/332 \\ 339/664 \\ 349/664 \\ 48/83 \\ 1\end{pmatrix}.$$ Therefore the required probability is $P_6=\frac{339}{664}$ is just barely greater than $1/2$.