• Support PF! Buy your school textbooks, materials and every day products Here!

What is the probability of overflowing urns?

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 pi overflowing because a ball occupies the urn with P1. The third ball has probability of (P2+P1). This continues until the Bth ball, which has a probability of overflowing of (P1+P2+P3+...+PB-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-(P1))B + (1-(P2+P1))B + ... + (1-(P1+P2+P3+...+PB-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!
 

Related Threads for: What is the probability of overflowing urns?

  • Last Post
Replies
6
Views
3K
Replies
2
Views
6K
Replies
1
Views
1K
Replies
1
Views
1K
Replies
3
Views
3K
Replies
1
Views
3K
Replies
1
Views
481
Replies
5
Views
5K
Top