We can solved this problem using matrices. Someone may have anywhere between 0 and 16 different toys. We may represent this by saying there are 17 states. If someone has
\[r\]
different toys. then the probability that he will find a toy he does not have in the next purchare, and move onto the state \[r+1\]
is \[\frac{16-r}{16}\]
. We can represent this my a square transition matrix with 17 rows and 17 columns.\[T=\frac{1}{16} \left( \begin{array}{ccccccc} 0 & 16 & 0 & 0 & \ldots & \ldots & \vdots \\ 0 & 1 & 15 & 0 & \ldots & \ldots & \vdots \\ 0 & 0 & 2 & 14 & \ldots & \ldots & \vdots \\ \vdots & \ldots & \ldots & 3 & \ldots & \ldots & \vdots \\ \vdots & \ldots & \dots & \dots & \ldots & 15 & 1 \\ \vdots & \ldots & \dots & \dots & \ldots & 0 & 1 \end{array} \right)\]
\[T=\frac{1}{16} \left( \begin{array}{ccccccc} 1 & -1 & 0 & 0 & \ldots & \ldots & \vdots \\ 0 & 15/16 & -15/16 & 0 \ldots & \ldots & \vdots \\ 0 & 0 & 14/16 & -14/16 & \ldots & \ldots & \vdots \\ \vdots & \ldots & \ldots & 13/16 & \ldots & \ldots & \vdots \\ \vdots & \ldots & \dots & \ldots & \ldots & 1/16 & -1/16 \\ \vdots & \ldots & \dots & \ldots & \ldots & 1 & 15/16 \end{array} \right)\]
This is an 'absorbing Markov chain'. A state in a Markov chain is an absorbing state if it is impossible to leave that state. A Markov chain is absorbing if
1. It has at least one absorbing state, and
2. From every state it is possible to go - possibly in several steps - to an absorbing state.
The absorbing state here is the final state with 16 different toys, and obviously from any state it is possible to reach that happy end state. The expected number of steps is the sum of the diagonal entries of the
\[(I-T)^{-1}\]
.\[(I-T)^{-1}=16 \frac{1}{16} \left( \begin{array}{ccccccc} 1/16 & 1/15 & 1/14 & \ldots & \ldots & \ldots & 1 \\ 0 & 1/15 & 1/14 & \ldots & \ldots & 1/2 & 1 \\ 0 & 0 & 1/14 & \ldots & \ldots & 1/2 & 1 \\ \vdots & \ldots & \ldots & \ldots & \ldots & \ldots & \vdots \\ \vdots & \ldots & \ldots & \ldots & \ldots & \ldots & \vdots \\ 0 & 0 & 0 & \ldots & \ldots & 0 & 1 & \end{array} \right)\]
The sum of the diagonal entries is
\[16(1/16+1/15+1/14+...+1) \simeq 54.09\]