MHB A basic Problem with two boxes

  • Thread starter Thread starter Khelil
  • Start date Start date
AI Thread Summary
The discussion revolves around a probability problem involving two boxes, each containing one black ball and three white balls. Participants identify the problem as a Markov chain with three states, focusing on the transition matrix to determine the probability of achieving a specific configuration after N trials. The initial state can be any of the eight possible configurations, and the transition matrix must be established to analyze the system's behavior over time. Various calculations of transition probabilities are shared, highlighting the complexity of deriving an explicit formula for the probability of reaching the desired state. The conversation emphasizes the need for a solid understanding of Markov chains to solve the problem effectively.
Khelil
Messages
8
Reaction score
0
Dear Members, I really can't understand how to put this problem on equation

One black ball and three white balls (a total of four balls) are included in each X and Y
box. One ball is exchanged between these boxes in one trial. Obtain the probability
of a specific state in which each box has one black ball and three white balls after the $N^{th}$ trial.

Thank you
 
Mathematics news on Phys.org
This is a Markov chain with three states. If we associate states with pairs of numbers of white and black balls in the first box, then the states are (4, 0), (3, 1) and (2, 2). The problem then can be solved by writing the transition matrix and raising it to the $n$th power.
 
Khelil said:
Dear Members, I really can't understand how to put this problem on equation

One black ball and three white balls (a total of four balls) are included in each X and Y
box. One ball is exchanged between these boxes in one trial. Obtain the probability
of a specific state in which each box has one black ball and three white balls after the $N^{th}$ trial.

Thank you

Indicating with A and B the two boxes, it is enough to observe the state of A, that extablishes the state of B. The number of states of A is eight... 1) 0 W + 0 B

2) 0 W + 1 B

3) 1 W + 0 B

4) 1 W + 1 B

5) 2 W + 0 B

6) 2 w + 1 B

7) 3 W + 0 B

8) 3 W + 1 B

... and the problem can be treated as a Markov chain with adsorbing state 1 or 8. If the initial state is not specified then any state can be the initial state with probability $\frac{1}{8}$. The first step is of course to write the transition matrix... finding an explicit formula of the probability that the game ends at the n-th iteration as function of n seems in any case an hard task... Kind regards $\chi$ $\sigma$
 
Khelil said:
One black ball and three white balls (a total of four balls) are included in each X and Y box. One ball is exchanged between these boxes in one trial.
I understood this to mean that each box has one black and three white balls (8 balls total). Thus, the initial state is given. At each step, one ball is picked from each box and dropped into the other box, so the number of balls in each box stays the same. If a single ball changes the box at each step, it is not clear from which box it is chosen. In any case, the OP should say if this interpretation is correct.
 
Thank you for your answers

I never studied markov chains so I think I will need to do a course. Sincerely yours
 
chisigma said:
Indicating with A and B the two boxes, it is enough to observe the state of A, that extablishes the state of B. The number of states of A is eight... 1) 0 W + 0 B

2) 0 W + 1 B

3) 1 W + 0 B

4) 1 W + 1 B

5) 2 W + 0 B

6) 2 w + 1 B

7) 3 W + 0 B

8) 3 W + 1 B

... and the problem can be treated as a Markov chain with adsorbing state 1 or 8. If the initial state is not specified then any state can be the initial state with probability $\frac{1}{8}$. The first step is of course to write the transition matrix... finding an explicit formula of the probability that the game ends at the n-th iteration as function of n seems in any case an hard task...

If the colour of the balls is not important [we are searching the event of all balls in A or B] and at each iteration one ball change address with equal probability, the problem can be reduced to a five states Markov chain and each stated represents simply the number of balls in A. The transition matrix is...

$\displaystyle T = \left | \begin{matrix} 1 & 0 & 0 & 0 & 0 \\ \frac{1}{4} & 0 & \frac{3}{4} & 0 & 0 \\ 0 & \frac{1}{2} & 0 & \frac{1}{2} & 0 \\ 0 & 0 & \frac{3}{4} & 0 & \frac{1}{4} \\ 0 & 0 & 0 & 0 & 1 \end{matrix} \right| $ (1)

... that can be reduced in 'canonical form' as follows...

$\displaystyle P = \left | \begin{matrix} 0 & \frac{3}{4} & 0 & \frac{1}{4} & 0 \\ \frac{1}{2} & 0 & \frac{1}{2} & 0 & 0 \\ 0 & \frac{3}{4} & 0 & 0 & \frac{1}{4} \\ 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 1 \end{matrix} \right| $ (2)

The problem has two adsorbing states [0 and 4] and, if we assume that the initial state is a transient state [1, 2 or 3] with the same probability, the probability that the process terminates at the n-th iteration is...

$\displaystyle P_{n} = \frac{1}{5}\ (\sum_{i=1}^{3} p_{n,i,0} + \sum_{i=1}^{3} p_{n,i,4})\ (3)$

... where the terms p are the elements of the rows 0 and 4 of the matrix $P^{n}$.

The effective computation of (3) gives...

$\displaystyle P_{1}= \frac{2}{3}\ \frac{1}{4}= \frac{1}{6}$

$\displaystyle P_{2}= \frac{2}{3}\ (\frac{1}{4} + \frac{1}{8}) = \frac{2}{3}\ \frac{3}{8}= \frac{1}{4}$

$\displaystyle P_{3} = \frac{2}{3}\ (\frac{11}{32} + \frac{3}{32} + \frac{1}{8} ) = \frac{2}{3}\ \frac{9}{16}= \frac{3}{8}$

$\displaystyle P_{4} = \frac{2}{3}\ (\frac{11}{32} + \frac{7}{32} + \frac{3}{32} ) = \frac{2}{3}\ \frac{21}{32}= \frac{7}{16}$

$\displaystyle P_{5} = \frac{2}{3}\ (\frac{53}{128} + \frac{7}{32} + \frac{21}{128} ) = \frac{2}{3}\ \frac{102}{128}= \frac{34}{64}$


Of course more terms can be computed… the convergence to 1 of the $P_{n}$ if n tends to infinity is very slow, as expected…

Kind regards

$\chi$ $\sigma$
 
Following Evgeny.Makarov's method (comment #2 above, and assuming the interpretation of the problem that he gives in comment #4), the transition matrix is $M = \begin{bmatrix}\frac12 & \frac3{16} & 0 \\ \frac12 & \frac58 & \frac12 \\ 0 & \frac3{16} & \frac12 \end{bmatrix}$, with eigenvalues $1,\;\tfrac12,\;\tfrac18$. By diagonalising the matrix, you can find that $$M^n = \frac1{14}\begin{bmatrix}3+7*2^{-n}+4*2^{-3n} & 3(1-2^{-3n}) & 3-7*2^{-n}+4*2^{-3n} \\ 8(1-2^{-3n}) & 8+6*2^{-3n} & 8(1-2^{-3n}) \\ 3-7*2^{-n}+4*2^{-3n} & 3(1-2^{-3n}) & 3+7*2^{-n}+4*2^{-3n} \end{bmatrix} $$ (it's a fairly messy calculation). From that, you can read off all the transition probabilities after $n$ iterations. In particaular, starting from the initial state in which each box has one black ball and three white balls, the probability of being in that same state after $n$ iterations is $\dfrac{4 + 3*2^{-3n}}7$ (which converges very rapidly to $4/7$).
 
Thank you very much but I start to be confused. I can of course determine de matrix but I don't understand the Markov chain method.
 
Back
Top