Distributing N balls in B baskets with equal probability.

[AntiElephant]

Homework Statement

I have [itex]N[/itex] balls and [itex]B[/itex] baskets. I look at each basket [itex]i[/itex] in turn and decide with some probability [itex]P_i[/itex] whether to insert one ball. After [itex]N[/itex] balls are inserted, I stop. If I look through all the baskets [itex] B [/itex], I stop; I do not make a second run-through, even if all the balls haven't been inserted. Can I write [itex]P_i[/itex] in such a way that, overall, each basket has an equal probability (which I'll call [itex]E_i[/itex]) 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 [itex]P_i[/itex] for all [itex]N[/itex] and [itex]B[/itex]. If [itex] N \geq B[/itex], then [itex]P_i[/itex] 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 [itex] N < B [/itex]

[itex]P_i[/itex] seems like it depends on three variables:

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

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

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

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

One can use this to notice:

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

Our assumption:

[itex]E_1 = E_2 = ... = E_i = ... = E_B = 1/B[/itex]

Therefore

[itex] P_1 = 1/B [/itex]
[itex] P_2 = 1/(B-1)[/itex]
[itex] P_3 = 1/(B-2)[/itex]

Then use induction:

Assume

[itex] P_i = 1/(B-(i-1)) [/itex]

Show

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

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

[itex] P_i=(1/(B−(i−1))) [/itex]

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

[itex]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) [/itex]

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 [itex]P_i[/itex] in such a way that, overall, each basket has an equal probability (I'll call [itex]E_i[/itex]) of obtaining a ball?

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

[itex]E_1 = P_1[/itex]
[itex]E_2 = (1-P_1)P_2[/itex]

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 [itex]E_i [/itex]. I want to adjust [itex]P_i[/itex] 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 [itex]N/B[/itex] chance of receiving a ball, i.e. [itex]E_i = N/B [/itex].

I do intend to go through the baskets in order, from [itex] 1 [/itex] to [itex]B[/itex] 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 [itex]N[/itex] balls and [itex]B[/itex] baskets. I look at each basket [itex]i[/itex] in turn and decide with some probability [itex]P_i[/itex] whether to insert one ball. After [itex]N[/itex] balls are inserted, I stop. If I look through all the baskets [itex] B [/itex], I stop; I do not make a second run-through, even if all the balls haven't been inserted. Can I write [itex]P_i[/itex] in such a way that, overall, each basket has an equal probability (which I'll call [itex]E_i[/itex]) 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 [itex]P_i[/itex] for all [itex]N[/itex] and [itex]B[/itex]. If [itex] N \geq B[/itex], then [itex]P_i[/itex] 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 [itex] N < B [/itex]

[itex]P_i[/itex] seems like it depends on three variables:

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

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

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

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

One can use this to notice:

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

Our assumption:

[itex]E_1 = E_2 = ... = E_i = ... = E_B = 1/B[/itex]

Therefore

[itex] P_1 = 1/B [/itex]
[itex] P_2 = 1/(B-1)[/itex]
[itex] P_3 = 1/(B-2)[/itex]

Then use induction:

Assume

[itex] P_i = 1/(B-(i-1)) [/itex]

Show

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

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

[itex] P_i=(1/(B−(i−1))) [/itex]

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

[itex]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) [/itex]

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 [itex]E_i [/itex]. I want to adjust [itex]P_i[/itex] 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 [itex]N/B[/itex] chance of receiving a ball, i.e. [itex]E_i = N/B [/itex].

I do intend to go through the baskets in order, from [itex] 1 [/itex] to [itex]B[/itex] 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.