What is the expected number of white balls, conditionally, in each row of this grid of white and black balls?

36 Views Asked by At

Suppose I have an $m\times n$ grid of black balls, $m,n \in \mathbb{N}$, and I randomly switch $k$ of them to white, where $1 \leq k \leq mn$. Every possible configuration of $k$ white balls is equally probable.

I want to compute the expected number of white balls in any row containing at least one white ball.

When $mn \gg k$, I can appeal to the fact that $p_0$, the probability that any given row contains no white balls, is approximately $\left(1-m^{-1}\right)^k$, hence the expected number of rows containing no white balls is $E[n_0] \approx mp_0 = m\left(1-m^{-1}\right)^k$, leaving $k$ white balls in the remaining $$E[n_{>0}] = m - E[n_0] = m - m\left(1-m^{-1}\right)^k$$ rows. The expected number of white balls in each of these rows can therefore be approximated $$E[n_{\text{white}}|n_{\text{white}} \geq 1] \approx k\left(m - m\left(1-m^{-1}\right)^k\right)^{-1}$$

However, as $\phi = \frac{k}{mn}$ increases towards $1$, this approximation becomes increasingly inadequate.

1

There are 1 best solutions below

2
On BEST ANSWER

There are $\binom{mn}{k}$ ways to select the cells with white balls, all of which we assume are equally likely.

First, what is the probability that row $i$ contains at least one white ball, for $1 \le i \le m$? It is $1$ minus the probability that the row contains no white balls, i.e. $$P(\text{at least one white ball}) = 1 - \frac{\binom{mn-n}{k}}{\binom{mn}{ k}}$$ Second, what is the probability that row $i$ contains at least one white ball and cell $i,j$ contains a white ball? This is the same as the probability that cell $i,j$ contains a white ball: $$\frac{k}{mn}$$ Let's define $X_{ij} = 1$ if cell $i,j$ contains a white ball, given that row $i$ contains at least one white ball, $0$ otherwise. Then $$E(X_{ij}) = P(X_{ij} =1) = \frac{k / mn}{1 - {\binom{mn-n}{k}} /{\binom{mn}{ k}}}$$ By linearity of expectation, the expected number of white balls in row $i$, given that the row contains at least one white ball, is $$\begin{align} E \left( \sum_{j=1}^n X_{ij} \right) &= \sum_{j=1}^n E(X_{ij}) \\ &= n E(X_{ij}) \\ & = \frac{k / m}{1 - {\binom{mn-n}{k}} /{\binom{mn}{ k}}} \end{align}$$