Welcome to our community

Be a part of something great, join today!

A basic Problem with two boxes

Khelil

New member
Aug 1, 2013
8
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
 

Evgeny.Makarov

Well-known member
MHB Math Scholar
Jan 30, 2012
2,493
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.
 

chisigma

Well-known member
Feb 13, 2012
1,704
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$
 

Evgeny.Makarov

Well-known member
MHB Math Scholar
Jan 30, 2012
2,493
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.
 

Khelil

New member
Aug 1, 2013
8
Thank you for your answers

I never studied markov chains so I think I will need to do a course.


Sincerely yours
 

chisigma

Well-known member
Feb 13, 2012
1,704
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$
 

Opalg

MHB Oldtimer
Staff member
Feb 7, 2012
2,715
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$).
 

Khelil

New member
Aug 1, 2013
8
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.