You are throwing k balls into n bins. Let Xi be the number of balls thrown into bin i. 
a) (2 points) What is E[Xi ] and Var(Xi)? 
b) (2 points) What is the expected number of empty bins? 
c) (2 points) Define a collision to occur when a ball lands in a non-empty bin (if there are n balls in a bin, count that as n − 1 collisions). What is the expected number of collisions? 
d) (4 points) Calculate the expected value of the ’total score’, defined as the sum of the squares of the number of balls in each bin. For example, if there are three bins with 2, 3, and 0 balls respectively, the total score would be calculated as: 22 + 32 + 02 = 4 + 9 + 0 = 13. Hint: E[X2 i ] = E[Xi ] 2 + Var(Xi).

### 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.

You are throwing k balls into n bins. Let Xi be the number of balls thrown into bin i. a) What is E[Xi] and Var(Xi)? b) What is the expected number of empty bins? c) Define a collision to occur when a ball lands in a non-empty bin (if there are n balls in a bin, count that as n − 1 collisions). What is the expected number of collisions? d) Calculate the expected value of the 'total score', defined as the sum of the squares of the number of balls in each bin.

Solve a problem involving k balls being thrown into n bins. Learn how to calculate the expected value, variance, number of empty bins, and expected number of collisions. Includes detailed steps for computing the total score using binomial distribution and combinatorics.

Math Problem Statement

Solution

Ask a new question for Free

By Image

Math Problem Analysis

Mathematical Concepts

Formulas

Theorems

Suitable Grade Level

Related Recommendation