Finding the number of non empty urns after 9 steps

Question

I'm trying to understand this example given in the book, "Introduction to probability models" by Sheldon Ross and am having trouble. The example (4.11) states:

"Suppose that balls are successively distributed among 8 urns, with each ball being equally likely to be put in any of these urns. What is the probability that there will be exactly 3 nonempty urns after 9 balls have been distributed?"

The one step transition matrix is given by

$p=\begin{bmatrix} 1/8 & 7/8 & 0 & 0 \\0 & 2/8 & 6/8 & 0 \\0 & 0 & 3/8&5/8 \\0 & 0 & 0 & 1\end{bmatrix}$

$p^{4}=\begin{bmatrix} 0.0002 & 0.0256 & 0.2563 & 0.7178 \\0 & 0.0039 & 0.0952 & 0.9009 \\0 & 0 & 0.0198&0.9802 \\0 & 0 & 0 & 1\end{bmatrix}$

The solution that is given is

$p^{8}_{1,3}= = 0.0002 × 0.2563 + 0.0256 × 0.0952 + 0.2563 × 0.0198 + 0.7178 × 0 = 0.00756$

I don't understand why the values 0.002 is multiplied by 0.2563 and 0.0256 is multiplied by 0.0952. Shouldn't the answer just be 0.2563?

Answer 1

Firstly, 9 balls have been distributed so the answer is an entry in the matrix of P to the power of 8 but not P to the power of 4. The state 1 in the one step transition matrix means one urn has been occupied so there are already one ball in one of these 8 urns. One step means a distribution of a ball. Hence we distribute 8 times from 1 ball to 9 balls and it is P to the power of 8.

Actually, the multiplication of P to the power of 4 is not a shortcut. It is an application of Chapman-Kolmogolov equations. In the discrete markov chain, this equation can be expressed in terms of matrix muliplication.the nth step transition matrix may be obtianed by multiplying the matrix P by itself n times

Answer 2

For reference, the book quoted by OP is "Introduction to probability models" by Sheldon Ross. In the 10th edition, the example referenced is example 4.11. All Ross is doing in that multiplication is raising the matrix, $P$ to the $8$-th power. I don't know why he didn't just say that instead of doing it this round-about way of first raising it to the power of $4$ and then getting the $1,3$ element of the square of that. To get the first row, third column of the product matrix, you take the first row of the first matrix and the third column of the second one and take their dot product. The .0002 is multiplied by .2563 because they are the first elements of respectively the first row and the third column of $P^4$

Answer 3

cHere is an approach without using Markov Chains.

For $1\leq i \leq 8$ let $A_i$ denote the event that at least one ball exists in urn $i$. Put $B=A_4\cup \dots \cup A_8$.

The probability that you seek equals ${8 \choose 3}\times \mathbb{P}(A_1\cap A_2\cap A_3\cap B^C)$ since any three of the eight urns are equally likely to be the non$-$empty urns. Let's take a close look at $\mathbb{P}(A_1\cap A_2\cap A_3\cap B^C)$. Using inclusion/exclusion we get

$$\begin{eqnarray*}\mathbb{P}(A_1\cap A_2\cap A_3\cap B^C)&=& 1-\mathbb{P}(A_1^C\cup A_2^C\cup A_3^C\cup B) \\ &=& 1- \Bigg[\mathbb{P}(A_1^C\cup A_2^C\cup A_3^C)+\mathbb{P}(B)-\mathbb{P}\big((A_1^C\cup A_2^C \cup A_3^C)\cap B\big)\Bigg] \\ &=&\mathbb{P}(B^C)+\mathbb{P}\big((A_1^C\cup A_2^C \cup A_3^C)\cap B\big)-\mathbb{P}(A_1^C\cup A_2^C\cup A_3^C) \\ &=&\left(\frac{3}{8}\right)^{9}+\sum_{k=1}^3{3 \choose k}(-1)^{k-1}\mathbb{P}(A_1^C\cap \dots \cap A_k^C\cap B)-\sum_{k=1}^3{3 \choose k}(-1)^{k-1}\mathbb{P}(A_1^C\cap \dots \cap A_k^C) \\ &=& \left(\frac{3}{8}\right)^9+\sum_{k=1}^3{3 \choose k}(-1)^{k-1}\Big(\frac{(8-k)^9-(3-k)^9}{8^9}\Big)-\sum_{k=1}^3{3 \choose k}(-1)^{k-1}\Big(\frac{8-k}{8}\Big)^9 \\ &=& \left(\frac{3}{8}\right)^{9}-\sum_{k=1}^{3}{3 \choose k}\left(-1\right)^{k-1}\left(\frac{3-k}{8}\right)^{9}\end{eqnarray*}$$

Multiply the above result by ${8 \choose 3}$ to get your answer of $0.00757$

Answer 4

Alternative approach:

Let $~A~$ denote the event that urns 1 thru 5 are empty.

Let $~B~$ denote the event that each of urns 6 thru 8 are non-empty, given that event A has occurred.

Then, the desired probability is

$$\binom{8}{5} \times p(A) \times p(B) ~: ~p(A) = \left[ ~\frac{3}{8} ~\right]^9. \tag1 $$

Therefore, the problem reduces to computing $~p(B),~$ which can be done via Inclusion-Exclusion. See this article for an introduction to Inclusion-Exclusion. Then, see this answer for an explanation of and justification for the Inclusion-Exclusion formula.

Let $~S~$ denote the collection of equally likely distributions where each of the 9 balls goes into one of urns 6 thru 8.

For $~k \in \{ ~6, ~7, ~8 ~\}, ~$ let $~S_k~$ denote the subset of $~S~$ where urn $~k~$ is empty. Then:

$$p(B) = \frac{|S| - |S_6 \cup S_7 \cup S_8|}{|S|} ~: ~|S| = 3^9. \tag2 $$

Let $~T_0 = |S|.$

Let $~T_1 = |S_6| + |S_7| + |S_8|.$

Let $~T_2 = |S_6 \cap S_7| + |S_6 \cap S_8| + |S_7 \cap S_8|.$

Let $~T_3 = |S_6 \cap S_7 \cap S_8|.$

Then, per Inclusion-Exclusion theory:

$$p(B) = \frac{T_0 - T_1 + T_2 - T_3}{|S|}. \tag3 $$

Then:

$$T_1 = \left[ ~3 \times 2^9 ~\right], ~T_2 = \left[ ~3 \times 1^9 ~\right], ~T_3 = \left[ ~1 \times 0^9 ~\right] = 0.$$

Therefore,

$$p(B) = \frac{3^9 - \left[ ~3 \times 2^9 ~\right] + \left[ ~3 \times 1^9 ~\right]}{3^9}.$$

Therefore, the desired computation is

$$\binom{8}{5} \times \left[ ~\frac{3}{8} ~\right]^9 \times \frac{3^9 - \left[ ~3 \times 2^9 ~\right] + \left[ ~3 \times 1^9 ~\right]}{3^9} \approx 0.00757.$$