A question about balls-in-bins problem.

43 Views Asked by At

Drop $n$ balls into $k$ bins in an independently random way. Let $X_i$ be the number of balls in the bin with label $i$. Let $s\geq1$ be some integer. Let $Y_s=\sum_{i=1}^kX_i^s$.

It is clear that the expectation of $Y_1=n$. Are there any results in the other cases?

1

There are 1 best solutions below

0
On BEST ANSWER

The distribution of $X_i$ is Binomial with parameters $n$ and $p=1/k$. According to Wikipedia (Binomial distribution: Higher Moments), $$E(X_i^s) = \sum_{j=0}^s S(s,j)\; n^{\underline j} \; p^j.$$ where $S(s,j)$ is a Stirling number of the second kind and $n^{\underline j}$ is a falling factorial: $n^{\underline j} = n(n-1) \cdots (n-j+1)$.

So by linearity of expectation, $$E(Y_s) = k \; E(X_i^s) = k \sum_{j=0}^s S(s,j)\; n^{\underline j} \; (1/k)^j.$$