# Calculating probability with n choose k

I'm trying to solve a problem two different ways, and I can'd seem to figure out where I'm going wrong.

I have 4 buckets (A,B,C,D), and 4 identical marbles. Each marble has an equal chance of being put in any of the 4 buckets, and each is placed independently (each bucket can have 0-4 marbles placed in it, with a total of 4 across all buckets)

I need to calculate the probability of bucket A being empty after the four marbles are placed.

My intuition says I can calculate the probability of the marble being placed in to any bucket except A as $\frac{3}{4}$. Then I can multiply the probabilities together since they are independent. So I can do $\left(\frac{3}{4}\right)^ 4$, which seems right.

But I think I should also be able to get the answer by calculating the number of ways that leaves A empty divided by the total number of ways the marbles can be placed in the 4 buckets. When I do that I get:

total ways: $\left(\dbinom{4}{4}\right)$ $\longrightarrow$ $\dbinom{7}{4}$ $\longrightarrow$ 35

ways with A empty: $\left(\dbinom{3}{4}\right)$ $\longrightarrow$ $\dbinom{6}{4}$ $\longrightarrow$ 15

But that gives me $\frac{15}{35}$, which is not the same as $\left(\frac{3}{4}\right)^ 4$

I'm guessing I am over counting or something else dumb, but I'm really stumped. Thanks for the help!

-

This is a Bernoulli process, a stochastic process which has two outcomes, success ("the marble is in $A$!") and failure ("the marble is not in $A$."). Let $s$ denote the probability of success and $f$ denote the probability of failure.

The formula for the probability of $k$ successes in $n$ trials is $$Pr[k\mbox{ successes in }n\mbox{ trials }] = \binom{n}{k}s^kf^{n-k}.$$

Where did this come from? There are $\binom{n}{k}$ different ways of arranging those $k$ successes among the $n$ tries. By independence, each of those different ways has probability $s^kf^{n-k}$ --- there are $k$ successes and the rest, all $n-k$ of them, are failures. Since we're not interested in the order of the successes, just the total number, we can add up the probabilities of all the different ways of getting $k$ successes in $n$ trials to arrive at the formula.

In your case, $s = \frac{1}{4}$, $f = \frac{3}{4}$, and $n=4$. Now we see that your first idea is correct: $$Pr[0\mbox{ successes }] = \binom{4}{0}\bigg(\frac{1}{4}\bigg)^0\bigg(\frac{3}{4}\bigg)^4 = bigg(\frac{3}{4}\bigg)^4.$$

What about your second idea? Let's think this through. For the denominator, we want to count the number of ways of distributing $4$ marbles among $4$ buckets. Let's think of this as a process: first we'll toss the first marble, then we'll toss the second marble, and so forth. How many options does the first marble have? $4$. The second? Again, $4$. So on. By the independence of the marble dropping, there are $4^4$ possible outcomes for this experiment. Repeating the argument, there are $3^4$ outcomes in which the $A$ bucket does not receive any marbles. Hence, $\frac{3^4}{4^4} = \big(\frac{3}{4}\big)^4$, just as we computed above.

Edit: After reading Andre Nicolas' answer, I want to add the following. One can only use counting to compute probability if all outcomes are equally likely. But as he notes, not all the multisets are equally likely! Some may be arrived at via multiple routes through the experiment's tree; for example, $\{A,A,A,A\}$ can only happen one way, while $\{A,B,C,D\}$ can happen $4!$ ways, since, e.g., $\{A,B,C,D\}=\{D,C,B,A\}$. So if you want to think in terms ofmultisets, you need to modify your counting. Take the different types of multisets (all one bucket, two buckets, three buckets, all four buckets), count the number of multisets in each type and multiply by the number of ways each multiset can occur, then add everything together.

-
Thank you! Your last paragraph helped a lot (as did Andre's). I appreciate it! –  kevin42 Mar 10 '12 at 4:02
You're welcome! :) –  Neal Mar 10 '12 at 13:03

There are indeed $\binom{7}{4}$ different ways to distribute $4$ identical balls between our $4$ buckets.

And there are indeed $\binom{6}{4}$ ways to distribute the $4$ balls between buckets B, C, and D.

So why can't we divide? Because the $35$ ways to distribute the $4$ balls among the $4$ buckets are not all equally likely. Is it obvious that they are not equally likely? Perhaps not, but it certainly is not obvious that they are equally likely!

Things may be intuitively clearer that if we distribute a large number of balls between $4$ buckets. Then a situation where A gets nothing, with the rest kind of evenly distributed between the other buckets, looks less likely than a situation in which the amounts in all the buckets are all roughly similar.

It is very convenient to have a sample space in which all outcomes are equally likely. For then to calculate a probability, we count and divide. That's why it is useful to imagine that the balls have $1$, $2$, $3$, $4$ written on them, perhaps with invisible ink, and are distributed in that order. Then the natural sample space is a record of which buckets the successive balls went into. So a typical element of the sample space is the sequence ACDC. By symmetry all elements of the sample space are equally likely. Now it is easy to count the possible "words" of length $4$, and the words that don't contain an A.

-
+1 for cutting straight to the heart of the problem. –  Neal Mar 10 '12 at 3:50

I think the problem is that you are neglecting order in the second method. That is, when we are counting the number of ways to distribute the balls, it matters which ball is in which bucket. Taking order into account, there are $4^4$ total ways to distribute the four balls into the four buckets (4 marbles, and each one has 4 choices, so $4*4*4*4$); and $3^4$ ways to distribute the balls into only the buckets B, C, D. This gives us a probability of $3^4/4^4 = (3/4)^4$, which matches the first method.

-

The problem seems to be in your second approach. The total number of ways (in your second solution) should be $4^4,$ as each marble has 4 choices of where to be put. And for the number of ways with A empty, each marble has 3 choices for where to be put, so $3^4$ ways. Which should give you $3^4/4^4,$ which is the same as your first solution.

-