What is the probability of overflowing urns?

[ProbProblems]

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?

Homework Equations

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_i overflowing because a ball occupies the urn with P₁. The third ball has probability of (P₂+P₁). This continues until the Bth ball, which has a probability of overflowing of (P₁+P₂+P₃+...+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₁))^B + (1-(P₂+P₁))^B + ... + (1-(P₁+P₂+P₃+...+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!

 

[mighty2000]

Thank you for your question. It seems like you are on the right track with your thinking. To calculate the expected number of overflows, we need to consider the probability of each possible outcome (i.e. the number of overflows) and multiply it by the corresponding number of overflows. In this case, the possible outcomes are 0, 1, 2, ..., B overflows.

Based on your analysis, the probability of having k overflows when placing B balls can be represented as:

P(k overflows) = (1-(P1))^B + (1-(P2+P1))^B + ... + (1-(P1+P2+P3+...+PB-1))^B

To calculate the expected number of overflows, we would then multiply each possible outcome by its corresponding number of overflows and sum them up, giving us:

E(number of overflows) = 0*P(0 overflows) + 1*P(1 overflows) + 2*P(2 overflows) + ... + B*P(B overflows)

= 0*(1-(P1))^B + 1*(1-(P2+P1))^B + 2*(1-(P1+P2+P3+...+PB-1))^B + ... + B*(1-(P1+P2+P3+...+PB-1))^B

= (1-(P1))^B + (1-(P2+P1))^B + ... + (1-(P1+P2+P3+...+PB-1))^B

= P(0 overflows) + P(1 overflows) + ... + P(B overflows)

= 1

Therefore, the expected number of overflows is 1. This makes intuitive sense, as with B balls and B urns, it is expected that each urn will be filled with one ball, resulting in no overflows.

I hope this helps answer your question. If you have any further doubts or concerns, please feel free to ask. Keep up the good work in your studies!Scientist