An urn has 4 balls of 4 different colours Red,Blue,Green,Yellow.

An urn has $4$ balls of $4$ different colours; red, blue, green, and yellow. I pick one ball at random at first and if it is red, I paint it blue and return it to the urn. If it is blue, I paint it green. If it is green, I paint it yellow. If it is yellow, I paint it red. What is the expected number of trials to get all $4$ balls of the same colour?

Reminder:

$$\color{red}{red}\to \color{blue}{blue}$$ $$\color{blue}{blue}\to \color{green}{green}$$ $$\color{green}{green}\to \color{yellow}{yellow}$$ $$\color{yellow}{yellow}\to \color{red}{red}$$

I am really stuck with this problem. Help!

Solution 1:

This problem is equivalent to one in which there are four people in four rooms that are joined cyclically by corridors. Initially, each room has one of the four people, and at each turn, one person (not one room) is chosen at random, and this person moves counterclockwise. How long before they end up in the same room?

One can define a Markov chain that records the relative position of the four people. It will be easier to explain this first for the case of three people. There are only four possible states:

• One person in each of the three rooms, which we denote $111$.
• Two people in one room, and one person in the next room, which we denote $21$.
• One person in one room, and two people in the next room, which we denote $12$.
• All three people in one room, which we denote $3$.

The dynamics of the chain are also fairly simple:

• From $111$, we can only move to $21$. Because we only care about the relative positioning of the people, all three possible resulting arrangements are identical (up to rotation).

• From $21$, we can only move to $12$.

• From $12$, we move to $3$ with probability $1/3$, and to $111$ with probability $2/3$.

For any state $k$, let $t_k$ denote the expected time to reach state $3$. Then $t_3 = 0$, and

$$ t_{111} = 1+t_{21} \\ t_{21} = 1+t_{12} \\ t_{12} = 1+\frac{2t_{111}}{3} $$

This yields $t_{12} = 7$, $t_{21} = 8$, and in particular, $t_{111} = 9$.

With four people, we obtain the following equations:

$$ t_{1111} = 1+t_{211} \\ t_{211} = 1+\frac{3t_{121}}{4}+\frac{t_{202}}{4} \\ t_{121} = 1+\frac{3t_{112}}{4}+\frac{t_{31}}{4} \\ t_{31} = 1+\frac{3t_{22}}{4}+\frac{t_{103}}{4} \\ t_{202} = 1+t_{112} \\ t_{112} = 1+\frac{t_{1111}}{2}+\frac{t_{22}}{4}+\frac{t_{103}}{4} \\ t_{22} = 1+\frac{t_{211}}{2}+\frac{t_{13}}{2} \\ t_{103} = 1+\frac{3t_{211}}{4}+\frac{t_{13}}{4} \\ t_{13} = 1+\frac{3t_{121}}{4} $$

When one solves this stack of equations, one obtains $t_{1111} = \frac{1042}{15} = 69\frac{7}{15}$, well in line with Remy's simulation value.

Solution 2:

This is not a solution but rather an empirical simulation using R. Perhaps it could useful as a check of someone's work:

values=c() 
for(i in c(1:(10^5))){
count=0
urn<-c("red","blue","green","yellow")
while(length(unique(urn))!=1){ #while loop ends when the urn contains 1 unique element
u=floor(runif(1,1,5)) #random integer between 1 and 4, inclusive
urn[u]<-ifelse(urn[u]=="red","blue",ifelse(urn[u]=="blue","green",
ifelse(urn[u]=="green","yellow",ifelse(urn[u]=="yellow","red"))))
#changes the value at the randomly selected index to be the newly painted ball color
count=count+1}
i=i+1
values<-c(values,count)} #adds number of iterations needed in that trial to the vector
mean(values)

[1] 69.40828

The expected value should come out to be in the $65-75$ range. Again, this is not in any way a solution. It will be interesting to see how it compares to the analytical solution.

Solution 3:

Up to a cyclic permutation of the colors there are the ten states $$1234, \ 1123, \ 1223, \ 1233, \ 1122, \ 1133, \ 1222, 1333,\ 1112, \ 1111\ .$$ Denote by $t_\iota$ the expected number of moves to reach state $1111$ from state $\iota$. Then you have nine equations, whereby $$t_{1233}=1+{1\over4}t_{1122}+{1\over4} t_{1333}+{1\over2}t_{1234}$$ is one example. Solving these equations gives in particular $$t_{1234}={1042\over15}\approx69.4667\ ,$$ as in Brian Tung's answer.