A store has 2 bins of balls. 1 bin is red, and contains 3 red balls. The other bin is gray and contains 2 gray balls. Every minute, on the minute, exactly one customer comes by the bins, picks up exactly one ball uniformly at random (of the 5 balls), and then puts the ball back in one of the two bins with a 50-50 chance of each bin (potentially putting a ball in the incorrect bin).

Describe the location of the red balls as a Markov Chain with states $\{0,1,2,3\}$ corresponding to the number of red balls in the red bin. Let $X_n$ denote the state of the system right after the $n$th customer has put down their ball. Compute the transition matrix $\mathbf P$ of the Markov Chain $\{X_n: n\geq 0\}$.

Attempt at a solution: I think I understand the problem, but my grasp of Markov Chains is weak since I just started studying them. I think I want to find all $16$ of the $p_{ij}$ for $i,j\in[0,3]$. First, I know that $p_{ij}=0$ when $i>j+1$ or $i<j-1$ since each customer only picks up a single ball. That is, $p_{02}=0, p_{20}=0$.

Next, I think $p_{00}=\Pr\{\text{someone picks any ball and puts in gray bin OR someone picks gray ball and puts in red bin}\}$=$(1*\frac{1}{2})+(\frac{2}{5}*\frac{1}{2})=.7$. And then so on for the remaining $p_{ij}$.

Is this correct?

  • $\begingroup$ What you have written so far is correct. $\endgroup$ – Gareth Feb 27 '14 at 18:18

Your Answer

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

Browse other questions tagged or ask your own question.