chisigma said:
Posted some years ago on an Italian math forum and not solved...
A maker for the promotion of his product includes in each pop corn pakage a prize [a colored pencil, a dummy animal, a pitcure card, etc...] randomly choosen among n different types. What is the expected number of pakages to be purchased if one wants to have the entire set of prizes?...
In the original post it has been proposed n=6, but it is better to try to analyse the general case. The failure of the attempts to solve the problem is probably due to the fact that nobody realized that in fact this is a Markov Chain problem with n states. In fact in the first purchase in any case one of the price is acquired and the missing prizes are n-1. At the second purchase or one finds the same price ad in the first and no progress is made, or one adds at his collection a new price and the missing prizes are n-2. Proceeding in this way the 'game' finish when the final state n is met. The state diagram is represented in figure...
The transition matrix is...
$\displaystyle P = \left | \begin{matrix} \frac{1}{n}& \frac{n-1}{n} & 0 & 0 & \cdot & \cdot & \cdot & 0 & 0 & 0 \\ 0& \frac{2}{n} & \frac{n-2}{n} & 0 & \cdot & \cdot & \cdot & 0 & 0 & 0 \\ 0 & 0 & \frac{3}{n} & \frac{n-3}{n} & \cdot & \cdot & \cdot & 0 & 0 & 0 \\ \cdot & \cdot & \cdot & \cdot & \cdot & \cdot & \cdot & \cdot & \cdot & \cdot \\ \cdot & \cdot & \cdot & \cdot & \cdot & \cdot & \cdot & \cdot & \cdot & \cdot \\ \cdot & \cdot & \cdot & \cdot & \cdot & \cdot & \cdot & \cdot & \cdot & \cdot \\ 0 & 0 & 0 & 0 & \cdot & \cdot & \cdot & \frac{3}{n} & 0 & 0 \\ 0 & 0 & 0 & 0 & \cdot & \cdot & \cdot & \frac {n-2}{n} & \frac{2}{n} & 0 \\ 0 & 0 & 0 & 0 & \cdot & \cdot & \cdot & 0 & \frac{n-1}{n} & \frac{1}{n} \\ 0& 0 & 0 & 0 & \cdot & \cdot & \cdot & 0 & 0 & 1\end{matrix} \right| $ (1)
Now we proceed as in...
http://mathhelpboards.com/basic-probability-statistics-23/expected-number-questions-win-game-4154.html#post18909
... starting by n=2 and finding A(n), i.e. the mean number of purchase necessary to acquire the entire set of prizes...
n=2
In this case is...
$\displaystyle Q = \frac{1}{2} \implies I - Q = \frac{1}{2} \implies (I_{1} - Q)^{- 1} = 2 \implies A(2)= 1 + 2 = 3$
n=3
In this case is...
$\displaystyle Q = \left | \begin{matrix} \frac{1}{3} & \frac{2}{3} \\ 0 & \frac{2}{3} \end{matrix} \right | \implies I - Q = \left | \begin{matrix} \frac{2}{3} & - \frac{2}{3} \\ 0 & \frac{1}{3} \end{matrix} \right | \implies (I - Q)^{-1} = \left | \begin{matrix} \frac{3}{2} & 3 \\ 0 & 3 \end{matrix} \right | \implies A(3) = 1 + 3 + \frac{3}{2} = \frac{11}{2}$
n=4
In this case is...
$\displaystyle Q = \left | \begin{matrix} \frac{1}{4} & \frac{3}{4} & 0 \\ 0 & \frac{1}{2} & \frac{1}{2} \\ 0 & 0 & \frac{3}{4} \end{matrix} \right | \implies I - Q = \left | \begin{matrix} \frac{3}{4} & - \frac{3}{4} & 0 \\ 0 & \frac{1}{2} & - \frac{1}{2} \\ 0 & 0 & \frac {1}{4} \end{matrix} \right | \implies (I - Q)^{-1} = \left | \begin{matrix} \frac{4}{3} & 2 & 4 \\ 0 & 2 & 4 \\ 0 & 0 & 4 \end{matrix} \right | \implies A(4) = 1 + 2 + 4 + \frac{4}{3} = \frac{25}{3}$
n=5
In this case is...
$\displaystyle Q = \left | \begin{matrix} \frac{1}{5} & \frac{4}{5} & 0 & 0 \\ 0 & \frac{2}{5} & \frac{3}{5} & 0 \\ 0 & 0 & \frac{3}{5} & \frac{2}{5} \\ 0 & 0 & 0 & \frac{4}{5} \end{matrix} \right | \implies I - Q = \left | \begin{matrix} \frac{4}{5} & - \frac{4}{5} & 0 & 0 \\ 0 & \frac{3}{5} & - \frac{3}{5} & 0 \\ 0 & 0 & \frac {2}{5} & - \frac{2}{5} \\ 0 & 0 & 0 & \frac{1}{5} \end{matrix} \right | \implies (I - Q)^{-1} = \left | \begin{matrix} \frac{5}{4} & \frac{5}{3} & \frac{5}{2} & 5 \\ 0 & \frac{5}{3} & \frac{5}{2} & 5 \\ 0 & 0 & \frac{5}{2} & 5 \\ 0 & 0 & 0 & 5 \end{matrix} \right | \implies $
$\displaystyle \implies A(5) = 1 + \frac{5}{4} + \frac{5}{3} + \frac{5}{2} + 5 = \frac{137}{12}$
n=6
In this case is...
$\displaystyle Q = \left | \begin{matrix} \frac{1}{6} & \frac{5}{6} & 0 & 0 & 0 \\ 0 & \frac{1}{3} & \frac{2}{3} & 0 & 0 \\ 0 & 0 & \frac{1}{2} & \frac{1}{2} & 0 \\ 0 & 0 & 0 & \frac{2}{3} & \frac{1}{3} \\ 0 & 0 & 0 & 0 & \frac{5}{6} \end{matrix} \right | \implies I - Q = \left | \begin{matrix} \frac{5}{6} & - \frac{5}{6} & 0 & 0 & 0 \\ 0 & \frac{2}{3} & - \frac{2}{3} & 0 & 0 \\ 0 & 0 & \frac {1}{2} & - \frac{1}{2} & 0 \\ 0 & 0 & 0 & \frac{1}{3} & - \frac{1}{3} \\ 0 & 0 & 0 & 0 & \frac{1}{6} \end{matrix} \right | \implies$
$\displaystyle \implies (I - Q)^{-1} = \left | \begin{matrix} \frac{6}{5} & \frac{3}{2} & 2 & 3 & 6 \\ 0 & \frac{3}{2} & 2 & 3 & 6\\ 0 & 0 & 2 & 3 & 6 \\ 0 & 0 & 0 & 3 & 6 \\ 0 & 0 & 0 & 0 & 6 \end{matrix} \right | \implies A(6) = 1 + \frac{6}{5} + \frac{3}{2} + 2 + 3 + 6 = \frac{147}{10}$
Observing the result we have obtained it seems not to be necessary to proceed with n>6 and with great probability we can conclude that the general result is...
$\displaystyle A(n) = n\ \sum_{k=1}^{n} \frac{1}{k} = n\ H_{n}\ (2)$
... and (2) is an interesting result which can be useful in many application fields...
Kind regards
$\chi$ $\sigma$
