1. **Problem Statement:** We have 6 different prizes randomly distributed in cereal boxes, with an equal and very large number of each prize. We define states in a Markov Chain as $\{0,1,2,3,4,5,6\}$ representing the number of distinct prizes seen so far. We want to find the transition matrix $P$ where $P_{ij}$ is the probability of moving from state $i$ to state $j$ after buying one more box. 2. **Understanding the Markov Chain:** - State $i$ means we have seen $i$ distinct prizes. - When buying a new box, the prize is equally likely to be any of the 6 prizes. - The probability of getting a new distinct prize (moving from $i$ to $i+1$) is the number of unseen prizes divided by 6, i.e., $\frac{6 - i}{6}$. - The probability of getting a prize already seen (staying in state $i$) is $\frac{i}{6}$. 3. **Transition Matrix $P$:** - The matrix is $7 \times 7$ (states 0 to 6). - For $i = 0,1,2,3,4,5$: - $P_{i,i} = \frac{i}{6}$ (probability of no new prize) - $P_{i,i+1} = \frac{6 - i}{6}$ (probability of new prize) - For $i=6$ (all prizes collected), the chain stays in state 6 with probability 1. - All other entries are 0. 4. **Explicit Matrix $P$:** $$ P = \begin{bmatrix} 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ \frac{0}{6} & \frac{0}{6} & 1 & 0 & 0 & 0 & 0 \\ 0 & \frac{1}{6} & \frac{5}{6} & 0 & 0 & 0 & 0 \\ 0 & 0 & \frac{2}{6} & \frac{4}{6} & 0 & 0 & 0 \\ 0 & 0 & 0 & \frac{3}{6} & \frac{3}{6} & 0 & 0 \\ 0 & 0 & 0 & 0 & \frac{4}{6} & \frac{2}{6} & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 1 \end{bmatrix} $$ 5. **Correcting the matrix:** The first row corresponds to state 0, so from 0 distinct prizes: - Probability of staying at 0 distinct prizes is $\frac{0}{6} = 0$ (impossible, since first box always gives a new prize) - Probability of moving to 1 distinct prize is $\frac{6}{6} = 1$ So the matrix is: $$ P = \begin{bmatrix} 0 & 1 & 0 & 0 & 0 & 0 & 0 \\ 0 & \frac{1}{6} & \frac{5}{6} & 0 & 0 & 0 & 0 \\ 0 & 0 & \frac{2}{6} & \frac{4}{6} & 0 & 0 & 0 \\ 0 & 0 & 0 & \frac{3}{6} & \frac{3}{6} & 0 & 0 \\ 0 & 0 & 0 & 0 & \frac{4}{6} & \frac{2}{6} & 0 \\ 0 & 0 & 0 & 0 & 0 & \frac{5}{6} & \frac{1}{6} \\ 0 & 0 & 0 & 0 & 0 & 0 & 1 \end{bmatrix} $$ 6. **Explanation:** - Each row sums to 1. - The chain moves from $i$ to $i+1$ with probability $\frac{6 - i}{6}$. - The chain stays in $i$ with probability $\frac{i}{6}$. - State 6 is absorbing. This matrix fully describes the transition probabilities for the Cereal Box Problem.