Distributing N balls in B baskets with equal probability.

[AntiElephant]

Homework Statement

I have N balls and B baskets. I look at each basket i in turn and decide with some probability P_i whether to insert one ball. After N balls are inserted, I stop. If I look through all the baskets B, I stop; I do not make a second run-through, even if all the balls haven't been inserted. Can I write P_i in such a way that, overall, each basket has an equal probability (which I'll call E_i) of obtaining a ball?

Homework Equations

The Attempt at a Solution

This isn't a homework question so I don't know how difficult this could get. I'm finding it hard to generalise P_i for all N and B. If N \geq B, then P_i can just be a constant number and all baskets have the same probability, because there are enough balls to supply for each basket and the chance isn't affected by whether balls have been inserted in previous baskets. So the assumption is that N < B

P_i seems like it depends on three variables:

N: The number of balls at the start.
B: The number of baskets.
R: The number of balls remaining when we reach i.

Obviously all P_i = 0 when R = 0. The problem would be easier if I could reason that maybe P_i doesn't depend on R when R>0, but I haven't been able to convince myself whether that's true.

The case where N = 1 is simple since I don't have to worry about the variable R:

E_1 = P_1
E_2 = (1-P_1)P_2
...
E_i = (1-P_1)(1-P_2)...(1-P_{i-1})P_i
...
E_B = (1-P_1)(1-P_2)...(1-P_{B-1})P_B

One can use this to notice:

(1): (1-P_i) = P_i/P_{i+1}

Our assumption:

E_1 = E_2 = ... = E_i = ... = E_B = 1/B

Therefore

P_1 = 1/B
P_2 = 1/(B-1)
P_3 = 1/(B-2)

Then use induction:

Assume

P_i = 1/(B-(i-1))

Show

P_{i+1} = 1/(B-i)

Which is easily shown with point (1) above. Leading me to the answer:

P_i=(1/(B−(i−1)))

The case for generalising this to any N seems very hard though, especially since the formula for each E_i isn't just one large multiplication like it was with N=1, and is instead an addition of probability of all the permutations in which i obtains a ball, and those permutations don't even have the same probability of occurring. For instance with N =2 for E_3 and P_i(R) I'm looking at:

E_3 = (1-P_1(2))(1-P_2(2))P_3(2) + P_1(2)(1-P_2(1))P_3(1) + (1-P_1(2))P_2(2)P_3(1)

It just becomes a mess to generalise. Is this possible? Can anyone provide some pointers for approaching this? Is there a name for this type of problem?

 

[Stephen Tashi]

Can I write P_i in such a way that, overall, each basket has an equal probability (I'll call E_i) of obtaining a ball?

Do you mean "exactly one ball" or "at least one ball" ?

E_1 = P_1
E_2 = (1-P_1)P_2

You haven't defined the variables $E_i$. It looks like you intend to go through the baskes in order. If no basket gets a ball, do you go through them again in the same order? It looks like $E_1$ is the probability that basket 1 gets a ball on the first attempt to put a ball in it. Is it possible that you'd make a second attempt ?

 

[AntiElephant]

Do you mean "exactly one ball" or "at least one ball" ?

You haven't defined the variables $E_i$. It looks like you intend to go through the baskes in order. If no basket gets a ball, do you go through them again in the same order? It looks like $E_1$ is the probability that basket 1 gets a ball on the first attempt to put a ball in it. Is it possible that you'd make a second attempt ?

Thanks for the reply. I mean exactly one ball. You're right, I wasn't clear enough about E_i. I want to adjust P_i so that, if an observer didn't see how the experiment took place, but repeated the experiment a number of times (and tabulated which baskets received a ball), he would conclude that the balls had been distributed randomly amongst the baskets (while making sure not to put more than one in a basket). So I'm aiming for each basket to have a N/B chance of receiving a ball, i.e. E_i = N/B.

I do intend to go through the baskets in order, from 1 to B and once having gone through all of them I stop. I do not make a second attempt. I'll edit my OP to be clearer.

 

[Ray Vickson]

Homework Statement

I have N balls and B baskets. I look at each basket i in turn and decide with some probability P_i whether to insert one ball. After N balls are inserted, I stop. If I look through all the baskets B, I stop; I do not make a second run-through, even if all the balls haven't been inserted. Can I write P_i in such a way that, overall, each basket has an equal probability (which I'll call E_i) of obtaining a ball?

Homework Equations

The Attempt at a Solution

This isn't a homework question so I don't know how difficult this could get. I'm finding it hard to generalise P_i for all N and B. If N \geq B, then P_i can just be a constant number and all baskets have the same probability, because there are enough balls to supply for each basket and the chance isn't affected by whether balls have been inserted in previous baskets. So the assumption is that N < B

P_i seems like it depends on three variables:

N: The number of balls at the start.
B: The number of baskets.
R: The number of balls remaining when we reach i.

Obviously all P_i = 0 when R = 0. The problem would be easier if I could reason that maybe P_i doesn't depend on R when R>0, but I haven't been able to convince myself whether that's true.

The case where N = 1 is simple since I don't have to worry about the variable R:

E_1 = P_1
E_2 = (1-P_1)P_2
...
E_i = (1-P_1)(1-P_2)...(1-P_{i-1})P_i
...
E_B = (1-P_1)(1-P_2)...(1-P_{B-1})P_B

One can use this to notice:

(1): (1-P_i) = P_i/P_{i+1}

Our assumption:

E_1 = E_2 = ... = E_i = ... = E_B = 1/B

Therefore

P_1 = 1/B
P_2 = 1/(B-1)
P_3 = 1/(B-2)

Then use induction:

Assume

P_i = 1/(B-(i-1))

Show

P_{i+1} = 1/(B-i)

Which is easily shown with point (1) above. Leading me to the answer:

P_i=(1/(B−(i−1)))

The case for generalising this to any N seems very hard though, especially since the formula for each E_i isn't just one large multiplication like it was with N=1, and is instead an addition of probability of all the permutations in which i obtains a ball, and those permutations don't even have the same probability of occurring. For instance with N =2 for E_3 and P_i(R) I'm looking at:

E_3 = (1-P_1(2))(1-P_2(2))P_3(2) + P_1(2)(1-P_2(1))P_3(1) + (1-P_1(2))P_2(2)P_3(1)

It just becomes a mess to generalise. Is this possible? Can anyone provide some pointers for approaching this? Is there a name for this type of problem?

Thanks for the reply. I mean exactly one ball. You're right, I wasn't clear enough about E_i. I want to adjust P_i so that, if an observer didn't see how the experiment took place, but repeated the experiment a number of times (and tabulated which baskets received a ball), he would conclude that the balls had been distributed randomly amongst the baskets (while making sure not to put more than one in a basket). So I'm aiming for each basket to have a N/B chance of receiving a ball, i.e. E_i = N/B.

I do intend to go through the baskets in order, from 1 to B and once having gone through all of them I stop. I do not make a second attempt. I'll edit my OP to be clearer.

If $N \geq B$ then putting $P_i = p$ for all $i = 1,2,\ldots, N$ will result in equal occupancy probabilities for all baskets. Basically, when facing Basket $i$ with some balls remaining, pick a ball, then spin a roulette wheel (or whatever) to decide whether to fill Basket $i$. If you decide to fill it you place the selected ball in the basket; if you decide not to fill it, discard the ball (thus reducing the remaining balls by one.

If $N < B$ one way to achieve equal occupancy probability for each basket would be to first choose $N$ of the $B$ baskets at random (so that each basket has the same probability of being chosen). Then, among the chosen baskets, apply the equal-$P_i$ scheme to each in turn. Perhaps this scheme is not acceptable to you, because the process of picking $N$ baskets at random cannot easily be achieved by looking at the baskets sequentially, one-at-a-time.