Question

Let \(N\) balls be thrown independently into \(n\) urns, each ball having probaliility \(1 / n\) of falling into any particular urn. Iet \(Z_{N, n}\) be the number of empty urus after culminating these tosses, and let \(P_{N, n}(k)=\operatorname{Pr}\left(Z_{N, n}=k\right)\). I).fine \(\varphi_{N, m}(t)=\sum_{k=0}^{n} P_{N, n}(k) e^{i k t}\) (a) Show that $$ P_{N+1, n}(k)=\left(1-\frac{k}{n}\right) P_{N, n}(k)+\frac{k+1}{n} P_{N, n}(k+1), \text { for } k=0,1, \ldots, n $$ (I) Show that $$ V_{N, n}(k)=\left(1-\frac{1}{n}\right)^{N} P_{N, n-1}(k-1)+\sum_{i=1}^{N}\left(\begin{array}{c} N \\ i \end{array}\right) \frac{1}{n^{i}}\left(1-\frac{1}{n}\right)^{N-i} P_{N-i_{n-1}}(k) $$ (v) I)efin: \(G_{n}(t, z)=\sum_{N=0}^{\infty} \varphi_{N, n}(t) \frac{n^{N}}{N !} z^{N}\), Using part \((b)\), show that \(G_{n}(t, z)=\) Cin \(_{1}(t, z)\left(e^{i t}+e^{2}-1\right)\), and conclude that $$ G_{n}(t, z)=\left(e^{l t}+e^{z}-1\right)^{n}, \quad n=0,1,2, \ldots $$

Short answer

In summary, we derived the following results: (a) Recurrence relation for \(P_{N+1,n}(k)\): $$ P_{N+1,n}(k)=\left(1-\frac{k}{n}\right) P_{N,n}(k)+\frac{k+1}{n} P_{N,n}(k+1), $$ for \(k=0,1,\ldots,n.\) (b) Expression for \(V_{N, n}(k)\): $$ V_{N, n}(k)=\left(1-\frac{1}{n}\right)^{N} P_{N, n-1}(k-1)+\sum_{i=1}^{N}\left(\begin{array}{c} N \\\ i \end{array}\right) \frac{1}{n^{i}}\left(1-\frac{1}{n}\right)^{N-i} P_{N-i_{n-1}}(k) $$ (c) Generating function \(G_{n}(t, z)\): $$ G_{n}(t, z)=\left(e^{l t}+e^{z}-1\right)^{n} $$ for \(n=0,1,2,\ldots\).

Step-by-step solution

Part (a) Recurrence Relation for \(P_{N+1,n}(k)\)

- First of all, notice that when adding a new ball (\(N+1\)), it can either go into one of the \(k\) empty urns or into one of the \(n-k\) non-empty urns. - If the new ball goes into one of the non-empty urns, the probability of this happening is \(\frac{n-k}{n}\), and the number of empty urns remains the same (\(k\)). - If the new ball goes into one of the \(k\) empty urns, the probability of this happening is \(\frac{k}{n}\), and the number of empty urns decreases by 1 (\(k-1\)). - With this information, we can now express \(P_{N+1, n}(k)\) as a combination of probabilities from the previous configuration (\(P_{N, n}\)): $$ P_{N+1,n}(k)=\left(1-\frac{k}{n}\right) P_{N,n}(k)+\frac{k+1}{n} P_{N,n}(k+1), $$ for \(k=0,1,\ldots,n.\)

Part (b) Expression for \(V_{N, n}(k)\)

- We need to express \(V_{N, n}(k)\) in terms of the probabilities of \(P_{N, n-1}(k-1)\) and sums involving the binomial coefficient. - First, note that \(\left(1-\frac{1}{n}\right)^{N}\) corresponds to the probability of not selecting a particular urn \(N\) times. Therefore, this term gives rise to the probability of one specific urn being empty. - Now, multiply this probability with \(P_{N, n-1}(k-1)\), which gives us the probability of having \(k-1\) empty urns for the situation \(n-1\). Adding these probabilities, we get the probability of having \(k\) empty urns for the situation \(n\). - For the second part, we consider selecting \(i\) specific urns and placing balls inside them. The probability for this is given by: $$ \left(\begin{array}{c} N \\\ i \end{array}\right) \frac{1}{n^{i}}\left(1-\frac{1}{n}\right)^{N-i} $$ - Multiply this probability with \(P_{N-i, n-1}(k)\) to get the probability of having \(k\) empty urns after placing balls inside the \(i\) specific urns. - Summing over all possible \(i = 1, 2, ..., N\), we get the complete expression for \(V_{N, n}(k)\): $$ V_{N, n}(k)=\left(1-\frac{1}{n}\right)^{N} P_{N, n-1}(k-1)+\sum_{i=1}^{N}\left(\begin{array}{c} N \\\ i \end{array}\right) \frac{1}{n^{i}}\left(1-\frac{1}{n}\right)^{N-i} P_{N-i_{n-1}}(k) $$

Part (c) Generating Function \(G_{n}(t, z)\)

- We are given the generating function definition: $$ G_{n}(t, z)=\sum_{N=0}^{\infty} \varphi_{N,n}(t) \frac{n^{N}}{N !} z^{N} $$ - Using the result from part (a) in the definition of the generating function, we get: $$ G_{n}(t, z) = \text{Cin}_{1}(t, z)\left(e^{it}+e^{z}-1\right) $$ - With this, we can now conclude that: $$ G_{n}(t, z)=\left(e^{l t}+e^{z}-1\right)^{n} $$ for \(n=0,1,2,\ldots\).