If I throw N balls independently into M bins with uniform probability, the expected mean of the M bins is N/M balls.
What is the expected variance of the M bins?
I was thinking of what bin size I should use to reduce noise in image processing.
3
-
$\begingroup$ Just think about the first bin. You’re either in or out (binomial) $\endgroup$– Anthony QuasCommented Dec 3 at 13:39
-
$\begingroup$ I thought of this but then realized the number of balls in each bin is not independent of other bins. If one ball goes into the first bin, it means that ball is not going into the other bins. To clarify, I am not asking for the expected number of balls in one bin, but the variance across all the bins. I am sorry if I am not clear. $\endgroup$– rationalfreakCommented Dec 3 at 13:50
-
$\begingroup$ So are you asking for the variance of a multinomial random vector? $\endgroup$– Suhas VijaykumarCommented Dec 3 at 18:23
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
I think you are asking for the variance of a multinomial distribution.
Let $I_i\in[M]$ be selected independently and uniformly at random for each $i$ and let $e_{I_i}\in \mathbb{R}^M$ be a standard basis vector with a $1$ in position $I_i$ and zeros elsewhere. If I understand correctly, you are asking about the variance of the random vector $X = \sum_{i=1}^N e_{I_i}$, which is the total number of balls in each bin.
You noted that $\mathbb{E}X = (N/M, N/M, \ldots, N/M)$. By exchangeability, we only need to compute $$\mathbb{E}XX^\top = \sum_{i,j} \mathbb{E}e_{I_i}e_{I_j}^\top = N \mathbb{E}e_{I_1}e_{I_1}^\top + N(N-1)\mathbb{E}e_{I_1}e_{I_2}^\top = \left\{\delta_{ij}\frac{N}{M} + \frac{N(N-1)}{M^2}\right\}_{ij}.$$
So $\mathrm{Var}(X) = \mathbb{E}XX^\top - (\mathbb{E}X)(\mathbb{E}X)^\top$ is $$\left\{\delta_{ij}\frac{N}{M} - \frac{N}{M^2}\right\}_{ij}.$$
