ProbProblems
New member
- Joined
- Mar 18, 2011
- Messages
- 2
The Problem
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?
My Thoughts:
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!
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?
My Thoughts:
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!