Question

Consider an infinite number of urns into which we toss balls independently, in such a way that a ball falls into the \(k\) th urn with probability \(1 / 2^{k}, k=1,2,3\). \(\ldots .\) For each positive integer \(N\), let \(Z_{N}\) be the number of urns which contain at least one ball after a total of \(N\) balls have been tossed. Show that $$ E\left(Z_{N}\right)=\sum_{\lambda=1}^{\infty}\left[1-\left(1-1 / 2^{k}\right)^{N}\right] $$ and that there exist constants \(C_{1}>0\) and \(C_{2}>0\) such that $$ C_{1} \log N \leq E\left(Z_{N}\right) \leq C_{2} \log N \quad \text { for all } N $$ Hint: Verify and use the facts: $$ E\left(Z_{N}\right) \geq \sum_{k=1}^{\log _{2}-N}\left[1-\left(1-\frac{1}{2^{k}}\right)^{N}\right] \geq C \log _{2} N $$ and $$ 1-\left(1-\frac{1}{2^{k}}\right)^{N} \leq N \frac{1}{2^{k}} \text { and } N \sum_{\log _{2}}^{\infty} \frac{1}{2^{k}} \leq C_{2} $$

Short answer

In conclusion, the expected value of the number of urns with at least one ball after \(N\) balls have been tossed is given by $$ E\left(Z_{N}\right) = \sum_{k=1}^{\infty}\left[1-\left(1-1 / 2^{k}\right)^{N}\right] $$ Moreover, there exist constants \(C_1 > 0\) and \(C_2 > 0\) such that $$ C_{1} \log N \leq E\left(Z_{N}\right) \leq C_{2} \log N \quad \text { for all } N $$

Step-by-step solution

Define the Indicator Variables

Define the indicator variable \(I_k\) for the \(k\)-th urn such that \(I_k=1\) if the urn contains at least one ball, and \(I_k=0\) otherwise. Observe that \(Z_N = \sum_{k=1}^{\infty} I_k\). Now, for each urn, we have the probability of having at least one ball as follows: $$ P(I_k = 1) = 1 - P(\text{No ball in the k-th urn after N tosses}) $$ Since the probability of a ball falling into the \(k\)-th urn is \(1/2^k\), the probability of not having a ball in a single toss is \((1 - 1/2^k)\). Therefore, the probability of not having a ball in the urn after N tosses is \((1 - 1/2^k)^N\). Thus, $$ P(I_k = 1) = \left[1 - \left(1 - \frac{1}{2^k}\right)^N\right] $$

Calculate Expected Value of \(Z_N\)

To find the expected value of \(Z_N\), we can use the linearity of expectation. Therefore, $$ E\left(Z_N\right) = E\left(\sum_{k=1}^{\infty} I_k \right) = \sum_{k=1}^{\infty} E(I_k) $$ Since the expectation of an indicator variable is equal to its probability, $$ E\left(Z_N\right) = \sum_{k=1}^{\infty} \left[1 - \left(1 - \frac{1}{2^k}\right)^N\right] $$ This proves the first part of the exercise. Now we need to find constants \(C_1\) and \(C_2\) such that the inequality holds for all \(N\).

Lower Bound by Using the Logarithm

Using the given hint, we need to find the lower bound of the expectation: $$ E\left(Z_N\right) \geq \sum_{k=1}^{\log_2 N}\left[1-\left(1-\frac{1}{2^{k}}\right)^{N}\right] $$ Since \(\log_2 N\) is increasing with N, we can define \(C_1\) as the sum of the terms from \(k=1\) to \(\log_2 N\). Thus, we have $$ C_{1} \log N \leq E\left(Z_{N}\right) $$

Upper Bound by Using the Logarithm

From the provided hint, we have the inequality for each term in the series: $$ 1 - \left(1-\frac{1}{2^k}\right)^N \leq N\frac{1}{2^k} $$ Now, we need to sum this inequality over the range from \(\log_2 N\) to \(\infty\). Thus, $$ N \sum_{k=\log_2 N + 1}^{\infty} \frac{1}{2^{k}} \leq C_2 $$ The series converges, and the sum is dominated by the first term. Therefore, we can define \(C_2\) as the sum of the series above, and we have the required inequality: $$ E\left(Z_{N}\right) \leq C_{2} \log N $$ Combining steps 3 and 4, we have proven the existence of constants \(C_1 > 0\) and \(C_2 > 0\) such that $$ C_{1} \log N \leq E\left(Z_{N}\right) \leq C_{2} \log N \quad \text { for all } N $$