9
$\begingroup$

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!

$\endgroup$
  • $\begingroup$ Where are you stuck with this problem? What have you tried? How far have you gotten? What is the difficulty you encountered? $\endgroup$ – Graham Kemp Mar 23 '18 at 6:08
  • $\begingroup$ For one, two, and three colors, the expected times are $0$, $1$, and $9$ (the first two are deterministic). I'm working on four colors; the state diagram has ten states, so it may take a bit... $\endgroup$ – Brian Tung Mar 23 '18 at 16:25
  • $\begingroup$ OK, I've finished and added my answer. I think it's correct, though there seems to be some minor discrepancy between my result and that of a commenter on my answer. $\endgroup$ – Brian Tung Mar 23 '18 at 17:34
  • $\begingroup$ Update: Discrepancy resolved! $\endgroup$ – Brian Tung Mar 23 '18 at 18:02
4
$\begingroup$

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$.

enter image description here

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.

$\endgroup$
  • $\begingroup$ I also used the Markov chain approach, but went into rather "brute force" direction - I made a probability matrix for all 35 possible states, turned it into the fundamental matrix and obtained a probability of $69\frac{2}{3}$. I don't fully get your notation, so I cannot follow your calculations. Could you elaborate? $\endgroup$ – yassem Mar 23 '18 at 17:04
  • $\begingroup$ @yassem: Oh dear, that'll be difficult to distinguish. I've added an example for $n = 3$; does that help? $\endgroup$ – Brian Tung Mar 23 '18 at 17:11
  • $\begingroup$ There's not a ton of symmetry left in this reduced chain, so I might easily have made a typo entering this into my CAS. $\endgroup$ – Brian Tung Mar 23 '18 at 17:12
  • $\begingroup$ @yassem: Well, I did discover a typo, but rather annoyingly, it did not completely resolve the difference between our solutions, but only made it even harder to distinguish. $\endgroup$ – Brian Tung Mar 23 '18 at 17:22
  • $\begingroup$ I actually made a typo re-writting my answer, it's actually $69.4667$, not $69.6667$, so $69\frac{7}{15}$. What's you new answer? $\endgroup$ – yassem Mar 23 '18 at 17:56
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ I don't understand this language, it would be helpful if you use comments in your source code (I understand java). $\endgroup$ – Shubhashish Mar 23 '18 at 8:04
  • $\begingroup$ I will add that! $\endgroup$ – Remy Mar 23 '18 at 8:05
1
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

I have replaced the colors with numbers $1,2,3,4$ in the following java code. When I ran the code I got the expected value $70$ for 10000 iterations. enter image description here

import java.util.Scanner;

class prob1
{
 public static void main(String args[])
{Scanner s=new Scanner(System.in);
int n=s.nextInt();

int m=0;
for(int i=0;i<=n-1;i++)       
 {  int A[] ={1,2,3,4}; int c=0;        
  while((A[0]!=A[1])||(A[0]!=A[2])||(A[0]!=A[3]))
 {     
       c++;
     double ran= 4*Math.random();
int r=(int) ran;

  if(A[r]==1){A[r]=2;}
  else if(A[r]==2){A[r]=3;}
  else if(A[r]==3){A[r]=4;}
  else{A[r]=1;}

System.out.print(A[0]+"-"+A[1]+"-"+A[2]+"-"+A[3]);
}
m=m+c;
}
System.out.println((double) m/n);


}
}
$\endgroup$
  • $\begingroup$ Intuitively the process should take a while. For example, if you have 3 reds and another color, then chances are you'll select a red and the color will change. I don't know java but you might want to review it. $\endgroup$ – Remy Mar 23 '18 at 16:21
  • $\begingroup$ @Remy to calculate the expected value i just took the mean of no. of trials, maybe that doesn't give the expected value. $\endgroup$ – Shubhashish Mar 23 '18 at 17:00
  • $\begingroup$ No that should be right. I think after you found the desired ball's index, you changed the color of more than one ball, rather than going to the next iteration in your while loop. You need if else statements. $\endgroup$ – Remy Mar 23 '18 at 17:10
  • $\begingroup$ @Remy: I think the chain of if statements needs else statements. Otherwise, if (for instance) the $r$th ball is color $1$, then it will change color four times and return to color $1$ again, as each of the if statements is triggered in turn. I bet every run yields four balls of color $1$. $\endgroup$ – Brian Tung Mar 23 '18 at 17:15
  • $\begingroup$ Yeah I think so too. Shouldn't be a hard fix @ShubhashishChauhan $\endgroup$ – Remy Mar 23 '18 at 17:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.