- 2

- 0

**1. Homework Statement**

Let's say we're placing balls in urns, and there are

*B*balls and

*U*urns. Each urn can only hold 1 ball. An overflow is when we try to place a ball in an urn that is already occupied. If

*B*<=

*U*and each urn has it's own probability of Pi of having a ball placed in the urn, where the sum of all Pi is 1, what is the expected number of overflows?

**2. Homework Equations**

**3. The Attempt at a Solution**

This is an expected value problem, meaning that we need to model the probability of overflowing. When the first ball is placed, it can't overflow. The next ball has probability

*p*overflowing because a ball occupies the urn with

_{i}*P*. The third ball has probability of (

_{1}*P*). This continues until the

_{2}+P_{1}*Bth*ball, which has a probability of overflowing of (

*P*).

_{1}+P_{2}+P_{3}+...+P_{B-1}Clearly you can't just sum these probabilities for each ball placement, so I'm thinking the right thing to do is take the compliment, putting those to the power of the number of balls you have and subtracting the whole thing from 1. So...

P(Overflowing) = 1 - ((1-(

*P*))

_{1}^{B}+ (1-(

*P*))

_{2}+P_{1}^{B}+ ... + (1-(

*P*))

_{1}+P_{2}+P_{3}+...+P_{B-1}^{B})

I'm not sure if this is right, but then we have to compute the expected value, and I'm unsure how to do that given the nature of the above probability.

I take it for the expected value you we take the sum of the following...

P(overflow 1 ball)*(1) + P(overflow 2 balls)*2 + ... + P(overflow B balls)*B. If this is correct, I don't really expect my above probability analysis is correct. Thoughts? Thanks!