December 2019
—————————
My December diary included the following brainteasers.
(1) Suppose n balls are randomly thrown into b boxes. What is the probability a given box contains exactly k balls?
If that's too easy, try this enhanced version:
(2) Suppose a box contains N balls, K of which are red. The remainder are blue. You draw n balls without replacement. What is the probability exactly k of them are red?
—————————
• Solutions
The logic is pretty much the same for all problems of this kind. I'll take the first one.
Fix your attention on some one particular box: Call it Ben.
(1) From Ben's point of view, what are the possible outcomes from one throw? That's easy: The ball lands in Ben with probability 1/b; the ball doesn't land in Ben with probability (1 − 1/b).
(2) Now construct a particular scenario for n ball throws. Here's a very simple one: The first k throws land in Ben, none of the other (n − k) throws do. What's the probability of this? Easy: You just multiply all the one-throw probabilities: the scenario has probability 1/b to the power k times (1 − 1/b) to the power (n − k). Let's call that probability P.
(3) But that's just one possible scenario for Ben getting k balls. Instead of getting the first k balls thrown, he might get the last k, or any k of the n. Any particular case has probability P, but how many cases are there?
(4) So I need to multiply P by something to get a bigger probability, to allow for all the different ways k balls could land in Ben. What's the number I need to multiply by? It's the number of ways of picking k items from a collection of n.
(5) That's a number well-known in math and basic to all problems like this. It has a name: "the binomial coefficient n, k." It has at least two notations, as described in the Mathworld link there. The "tall parentheses" is now standard, but Mathworld also allows nCk and I remember from my schooldays learning nCk.
So how do you work out nCk, the number of ways of picking k items from a collection of n?
First you need to recall the factorial of a positive whole number, written as N! and defined to be the product of all the positive whole numbers up to and including N. So factorial 5 is written 5! and is equal to 1×2×3×4×5, which works out to 120.
Now I can tell you that nCk is n!/((n − k)!×k!).
So if you have five items {apple, orange, pear, plum, kiwi}, the number of ways to select two of them is 5!/(3!×2!). Since 5! is 120, 3! is 6, and 2! is 2, that works out to ten. Sure enough: {apple, orange}, {apple, pear}, {apple, plum}, {apple, kiwi}, {orange, pear}, {orange, plum}, {orange, kiwi}, {pear, plum}, {pear, kiwi}, {plum, kiwi}. That's ten.
(I'm assuming here that we don't care about order of pick. {pear, plum} and {plum, pear} are the same thing for our purposes. If order of pick matters, the arithmetic is different. For the problems we're working on, order of pick doesn't matter.)
(6) So final answer: n!/((n − k)!×k!) times P, where P is 1/b to the power k times (1 − 1/b) to the power (n − k).
The second problem proceeds along similar lines, for a solution n!/((n − k)!×k!) times K/N to the power k times (1 − K/N) to the power (n − k).
[Added later. Wrong! I was lazy there, after dealing so briskly with Problem 1, in not thinking Problem 2 through, as I should have done. The probability here is actually the ratio of
• numerator: the number of ways of getting exactly k red balls from the K available,
• denominator: the number of ways of picking n balls from the N available.
That denominator is of course just NCn. The numerator is the number of ways of getting k red balls times the number of ways of getting (n − k) blue balls: KCk times (N − K)C(n − k).]