Probability (n balls and n containers)

There are n balls and n containers. If the balls are distributed at random (Prob. 1/n for each container), what is the probability that exactly one container remains empty?

I just can’t seem to figure out an answer for this, and would surely love some help. Every path I’ve taken seems to be a dead end!
Any help would be much obliged.

-Captain Myrrh

If it’s any help to you, I believe this is referred to as an “occupancy problem”. I remember solving one but it had to do with ALL containers being filled. I had to use Stirling’s Numbers of the Second Kind. These are much tougher than they first appear.

For example, how many times do you have to roll a die until the probability is higher than 50% that all six numbers will have appeared at least once? For the 6 sided die problem, imagine it is 6 “containers” being “filled” with each of the 6 “containers” having an equal likelihood of being filled.

Maybe some of those terms will help you in a Google Search.

Well, first you start out with how many ways can you distribute n balls into n containers. You probably already know that it’s n[sup]n[/sup]. So that’s your denominator. The trick is the numerator.

You need to know:

How many ways you can pick 1 hole out of n to be the empty hole.
How many ways you can pick 1 hole out of n-1 to be the hole with 2 balls.
How many ways you can pick 2 balls out of n to be paired together.
How many ways you can distribute n-2 balls into n-2 holes with exactly one ball per hole.

Does that help?

I believe this to be the correct answer:

Say n = 5. Since there are n balls and n containers, every container must have one ball, except one container with two, and one container with zero.

Five balls, five empty containers

Status: ( ) ( ) ( ) ( ) ( )

You place one ball. Anywhere. 5/5 probability of picking an okay container.
Status: (X) ( ) ( ) ( ) ( )

Next place a ball in any of the empty containers. (Bear with me, I know you can pick the same one again, but I’ll get to that). 4/5 chance of being okay.
Status: (X) (X ) ( ) ( ) ( )

Again place a ball in an empty container. 3/5 chance.
Status: (X) (X) (X) ( ) ( )

Once more, ball in an empty container. 2/5 chance this time.
Status: (X) (X) (X) (X) ( )

Now, place a ball in one of the already-occupied containers. 4/5 chance.
Status: (XX) (X) (X) (X) ( )

This last step can occur at any time, but it doesn’t matter. You multiply the probabilities, so the order doesn’t matter.
Overall: (5/5) * (4/5) * (3/5) * (2/5) * (4/5) = 480 / 3125 = .1536
Now generalize it to the n case.
We have (n/n) * ((n-1)/n) * ((n-2)/n) * ((n-3)/n) * ((n-1)/n).
Simply: [n(n-1)^2(n-2)(n-3)] / n^n
Simply: [(n-1)^2(n-2)(n-3)] / n^(n-1)

There’s probably a better way of putting that. And maybe I made a mistake. ultrafilter?

If I made a mistake, it would be in assuming that it doesn’t matter when you double-fill one of the containers. If that’s the case, then the correct probability should be slightly higher than what I came up with.

I would suggest checking your equation to make sure it works for n = 2 and n = 3. That’s small enough that you can actually enumerate all the possible placements of balls and calculate the probability directly.

Here’s what I got—other Dopers are definitely encouraged to check and criticize.

Total number of ways the n balls could be distributed among n containers = n[sup]n[/sup] (as Punoqllads has pointed out).

Number of ways the n balls could be distributed among the containers #2 - #n (leaving only #1 empty) = number of ways to have two balls in one of these containers and one in each of the others.

This would = (# of ways to pick the container that gets 2 balls) * (number of ways to pick these two balls) * (number of ways to arrange the remaining n-2 balls into n-2 containers)

which would = (n-1) * ([sub]n[/sub]C[sub]2[/sub] or (n)*(n-1)/2 ) * (n-2)!

We’ve just calculated the number of ways that only the first container could be empty. By symmetry, multiply this by n to get the number of ways exactly one of the containers could be empty.

Here are the numbers for the first few n’s:

n = 2: P = 1 / 4 = 0.25
n = 3: P = 6 / 27 = 0.2222
n = 4: P = 36/256 = 0.1406
n = 5: P = 240/3125 = 0.0768
n = 6: P = 1800/46656 = 0.0386

On preview, I see that iwakura43 has come up with a different answer. I’m going to have to stare at it for a while to see if I can find where one of us made a mistake.

Here’s a way to think about it: you have n balls, two of which are paired together. You also have one “non-ball” that will go in one of the slots. This means that you can think of things as a permutation of n objects: one pair of balls, (n-2) single balls, and a non-ball. Multiply this by the number of ways to create one pair out of n balls (i.e. n(n-1)/2) and you’ve got the result.

Bottom line: N = (permutations)*(pairings) = n! * n(n-1)/2.

This gives N = 0 for n = 1 (which is pretty obviously true), and N = 1 for n = 2 (also pretty obvious.) I don’t think I’ve over- or under-counted here, but I could be wrong.

Also, this method doesn’t generalize easily to an arbitrary number of empty slots without getting into partitions of integers.

iwakura43: I think we’re solving different problems. Are the balls distinguishable? In other words, does “Ball 1 and Ball 2 in slot 1” count as the same thing as “Ball 2 and Ball 3 in slot 1”? I think my method is correct only if they don’t count as the same thing, but the OP isn’t clear. Yours is closer to correct if they don’t count as distinct (although your product should probably be (n-1)(n-2)32 instead of terminating at n-3.)

Thudlow Boink: You and I agree as long as you remember to throw that factor of n in there. :slight_smile:

Well, there’s one mistake: when I calculated my actual numbers, I left out the part at the end where you multiply by n. With this correction,

n = 2: P = 2/4 = 0.5
n = 3: P = 18/27 = 0.6667
n = 4: P = 144/256 = 0.5625
n = 5: P = 1200/3125 = 0.3840
n = 6: P = 10800/46656 = 0.2315

Wow I should have read the problem more carefully. I was thinking in terms of m balls filling up ***n ** * containers, where m is a number greater than or equal to n. Sorry.

n(n-1) ways to choose the empty and the doubly-filled container. n(n-1)/2 ways to pick the two balls in the doubly-filled container. (n-2)! ways to arrange the remaining balls in the remaining containers. So I get n(n-1)n!/(2n^n). I haven’t checked this carefully, but it gives the right answers for n=1 and n=2, and a numerical check for n=4 seems to confirm it.

It’s not at all obvious to me that the total number of ways to distribute n balls into n containers is n[sup]n[/sup]. That requires making assumptions that may be incorrect.

CaptainMyrrh, are the balls distinct or indistinct? Are the containers distinct or indistinct?

Oh, meant to put this into the last post. Here are the numbers you should get for n = 2 and n = 3.



b[sub]1[/sub] 1 b[sub]2[/sub] 1 => 1 hole empty
b[sub]1[/sub] 1 b[sub]2[/sub] 2 => 0 holes empty
b[sub]1[/sub] 2 b[sub]2[/sub] 1 => 0 holes empty
b[sub]1[/sub] 2 b[sub]2[/sub] 2 => 1 hole empty


2/4 => p = 0.5



b[sub]1[/sub] 1 b[sub]2[/sub] 1 b[sub]3[/sub] 1 => 2 holes empty
b[sub]1[/sub] 1 b[sub]2[/sub] 1 b[sub]3[/sub] 2 => 1 hole empty
b[sub]1[/sub] 1 b[sub]2[/sub] 1 b[sub]3[/sub] 3 => 1 hole empty

b[sub]1[/sub] 1 b[sub]2[/sub] 2 b[sub]3[/sub] 1 => 1 hole empty
b[sub]1[/sub] 1 b[sub]2[/sub] 2 b[sub]3[/sub] 2 => 1 hole empty
b[sub]1[/sub] 1 b[sub]2[/sub] 2 b[sub]3[/sub] 3 => 0 holes empty

b[sub]1[/sub] 1 b[sub]2[/sub] 3 b[sub]3[/sub] 1 => 1 hole empty
b[sub]1[/sub] 1 b[sub]2[/sub] 3 b[sub]3[/sub] 2 => 0 holes empty
b[sub]1[/sub] 1 b[sub]2[/sub] 3 b[sub]3[/sub] 3 => 1 hole empty

b[sub]1[/sub] 2 b[sub]2[/sub] 1 b[sub]3[/sub] 1 => 1 hole empty
b[sub]1[/sub] 2 b[sub]2[/sub] 1 b[sub]3[/sub] 2 => 1 hole empty
b[sub]1[/sub] 2 b[sub]2[/sub] 1 b[sub]3[/sub] 3 => 0 holes empty

b[sub]1[/sub] 2 b[sub]2[/sub] 2 b[sub]3[/sub] 1 => 1 hole empty
b[sub]1[/sub] 2 b[sub]2[/sub] 2 b[sub]3[/sub] 2 => 2 holes empty
b[sub]1[/sub] 2 b[sub]2[/sub] 2 b[sub]3[/sub] 3 => 1 hole empty

b[sub]1[/sub] 2 b[sub]2[/sub] 3 b[sub]3[/sub] 1 => 0 holes empty
b[sub]1[/sub] 2 b[sub]2[/sub] 3 b[sub]3[/sub] 2 => 1 hole empty
b[sub]1[/sub] 2 b[sub]2[/sub] 3 b[sub]3[/sub] 3 => 1 hole empty

b[sub]1[/sub] 3 b[sub]2[/sub] 1 b[sub]3[/sub] 1 => 1 hole empty
b[sub]1[/sub] 3 b[sub]2[/sub] 1 b[sub]3[/sub] 2 => 0 holes empty
b[sub]1[/sub] 3 b[sub]2[/sub] 1 b[sub]3[/sub] 3 => 1 hole empty

b[sub]1[/sub] 3 b[sub]2[/sub] 2 b[sub]3[/sub] 1 => 0 holes empty
b[sub]1[/sub] 3 b[sub]2[/sub] 2 b[sub]3[/sub] 2 => 1 hole empty
b[sub]1[/sub] 3 b[sub]2[/sub] 2 b[sub]3[/sub] 3 => 1 hole empty

b[sub]1[/sub] 3 b[sub]2[/sub] 3 b[sub]3[/sub] 1 => 1 hole empty
b[sub]1[/sub] 3 b[sub]2[/sub] 3 b[sub]3[/sub] 2 => 1 hole empty
b[sub]1[/sub] 3 b[sub]2[/sub] 3 b[sub]3[/sub] 3 => 2 holes empty


18/27 => 0.666…

On preview, Thudlow’s numbers match up with these. His equation also happens to map to mine. The equation I came up with is:
[sub]n[/sub]C[sub]2[/sub] * n! / n[sup]n[/sup]

I wrote a quick and dirty program to simulate this, and the numbers it spit out very closely agree with yours. On the last trial, it gave me:



2        .50667
3        .66773
4        .56326
5        .38268
6        .27162
7        .12766
8        .06719
9        .03354
10       .01591


The balls are not distinct.

Sorry, forgot to put in everything I wanted to on that last one. So no, the balls are not distinct, but yes, the containers are distinct. This is basically the root of my torubles with the problem. The N=2… 2/4 is only true for distinct balls. Without that, its is 2/3 for N=2.

Container 1: XX Container 2:
Container 1: X Container 2: X
Container 1: Container 2: XX

This leaves me with (If I’m counting right, I believe I am)
N=2 2/3
N=3 6/10
N=4 12/34

and thats as far as I cared to count. The number of solutions (cases where only one container has no balls) seems to follow Solutions=N((N-1)combination(N-2)), but I can’t figure out a good way to find the possible number of solutions.

If the balls are indistinct and the containers are distinct, the number of ways to distribute n balls into n containers is C(2n-1,n). Let me know if you don’t see where that comes from.

If we want exactly one container to be empty, then exactly one container will have two balls (the rest will have exactly one ball).

Count the number of ways this can happen as follows:

Pick two of the n containers to be the “special” ones (i.e., one is empty, and one has two balls in it). There are C(n,2) ways to do this.

Having picked these two containers, pick the one of the two that is to be empty. There are C(2,1)=2 ways to do this.

And so there are 2C(n,2) ways of distributing the balls with exactly one container empty. Therefore, the probability of this event happening is

2C(n,2) / C(2n-1,n).

The answer to the OP doesn’t depend on whether we distinguish between balls or not. The number of ways to put n balls into n containers, not distinguishing between balls, is indeed C(2n-1,n). However, these outcomes are not equally probable under the conditions in the OP.

Consider the case of n=2. Not distinguishing between balls, there are three outcomes, which we might designate (2, 0), (1, 1), and (0, 2). Two of these three have exactly one empty container. Yet it is not the case, if the balls were put into containers independently with probabilities of 1/2, that 2/3 of the time there will be one empty container. (1, 1) is twice as likely as either of the other possibilities, and the true probability is 1/2.

That’s a good point, Josh_dePlume, I had overlooked that. However, it’s still not entirely clear to me what the OP intended–whether the distribution of the balls is uniform, as CaptainMyrrh asked in the OP, or perhaps the distribution of arrangements of the balls is instead intended to be uniform, as CaptainMyrrh’s last post implies (to me, anyway).

Does it simplify the problem any if you start from the premise that in order to have exactly one container empty exactly one ball must be out of place? Figure out the odds of each ball randomly ending up in a seperate container. Then once you’ve got the odds of that happening there are exactly n different possiblities from there of having one of the balls out of place.