a) Finding $E[X_i]$ and $\text{Var}(X_i)$

Let $X_i$ be the number of balls thrown into bin $i$. There are $k$ balls and $n$ bins, and each ball is independently placed into one of the bins with equal probability.

• $E[X_i]$:

The expected value of $X_i$, the number of balls in bin $i$, follows a binomial distribution since each ball has a $\frac{1}{n}$ chance of being thrown into bin $i$.

$X_i \sim \text{Binomial}(k, \frac{1}{n})$

The expectation for a binomial distribution is:

$E[X_i] = k \cdot \frac{1}{n}$

• $\text{Var}(X_i)$:

The variance for a binomial distribution is given by:

$\text{Var}(X_i) = k \cdot \frac{1}{n} \cdot \left(1 - \frac{1}{n}\right)$

So,

$\text{Var}(X_i) = k \cdot \frac{1}{n} \cdot \frac{n-1}{n}$

b) Expected Number of Empty Bins

Let $I_i$ be an indicator random variable, which equals 1 if bin $i$ is empty, and 0 otherwise. The probability that a bin is empty is the probability that none of the $k$ balls landed in bin $i$, which is:

$P(\text{bin } i \text{ is empty}) = \left( 1 - \frac{1}{n} \right)^k$

Thus, the expected number of empty bins is:

[ E[\text{empty bins}] = \sum_{i=1}^{n} E[I_i] = n \cdot \left(1 - \frac{1}{n}\right)^k ]

c) Expected Number of Collisions

A collision occurs when a ball lands in a bin that already has at least one ball. Define $Y$ as the total number of collisions. If there are $X_i$ balls in bin $i$, then the number of collisions in bin $i$ is $X_i - 1$ for $X_i \geq 1$, and 0 otherwise. This can be expressed as $\sum_{i=1}^{n} \max(0, X_i - 1)$, but another way to express the total number of collisions is:

$Y = \sum_{i=1}^{n} \binom{X_i}{2}$

The expected number of collisions can be derived as:

[ E[Y] = \sum_{i=1}^{n} E\left[ \binom{X_i}{2} \right] = \sum_{i=1}^{n} \frac{k(k-1)}{2n^2} ]

So the expected number of collisions is:

$E[Y] = \frac{k(k-1)}{2n}$

d) Expected Value of the Total Score

The total score is defined as the sum of the squares of the number of balls in each bin, i.e., $\sum_{i=1}^{n} X_i^2$. We can compute $E[X_i^2]$ using the fact that:

[ E[X_i^2] = \text{Var}(X_i) + (E[X_i])^2 ]

From part (a), we know $E[X_i] = \frac{k}{n}$ and $\text{Var}(X_i) = k \cdot \frac{1}{n} \cdot \frac{n-1}{n}$. Therefore:

$E[X_i^2] = \frac{k}{n} \cdot \frac{n-1}{n} + \left( \frac{k}{n} \right)^2$

Thus, the total expected score is:

[ E[\text{total score}] = \sum_{i=1}^{n} E[X_i^2] = n \cdot \left( \frac{k}{n} \cdot \frac{n-1}{n} + \left( \frac{k}{n} \right)^2 \right) ]

Simplifying:

$E[\text{total score}] = n \cdot \left( \frac{k(n-1)}{n^2} + \frac{k^2}{n^2} \right) = n \cdot \frac{k(n-1) + k^2}{n^2}$

$E[\text{total score}] = \frac{k(n-1) + k^2}{n}$

This gives the expected value of the total score.

---

Let me know if you'd like further clarifications or details.

5 Follow-up Questions:

1. How does the expected number of empty bins change as $k$ increases?
2. What is the variance of the total score?
3. How would the results change if the balls were not thrown independently?
4. What happens to the number of collisions if $k = n$?
5. Can you derive the probability that exactly one bin contains all the balls?

Tip:

When dealing with binomial distributions, remember that as $n$ grows large, the distribution tends to a Poisson distribution, which can simplify certain calculations.