Basic Counting Rules
  |   Source

Basic counting rules

AKA this is harder than it looks, and I'm not a great teacher some days.

I was helping my youngest (who isn't that young any more) with his math homework the other night, and we were learning about combinations and permutations. Some of these problems are fun, and some are depressingly difficult to sort out, and most of them make you facepalm once you learn the solution to a wrong answer. How hard can it be?! Page 1 of "A First Course in Probability" begins with "The Basic Principle of Counting" (Ross, 2010). The rules themselves are straightforward. Most of us are familiar with counting the possible number of license plates given some collection of available letters and numbers. Things get trickier, though, when we mix and match and when we consider dependent and independent probabilities.

A bag of balls, queue up AC⚡️DC

My son was working with a problem involving a bag of colored balls. There were some green, some red, and one gold; a total of ten balls in a bag. I don't recall what the original problem was because I saw a squirrel and chased it. I have had more than one semester of statistics classes, this can't be that hard! I blurted out the first question that came to mind, "What is the probability of pulling out a gold ball if you draw a ball out ten times?".

So far, so good.

We immediately discussed how important it is to quantify the problem. Details matter! We can't tell same-colored balls apart, so this isn't a permutation problem (order doesn't matter). What if we don't replace the balls? The probability of pulling a gold ball in ten trials is 100%, easy! 🎉 I am really interested in the situation with replacement, though. I thought the answer would be super easy, and I grabbed a calculator and started scratching my chin. "Oh, that's not right." "Hrm, neither is that." "Oh, oh, I see, but why???" His mother immediately scolded me for chasing a squirrel and they returned to their homework while I tried to sort out the problem in my own pea brain.

The chances of pulling a gold ball out of the bag of ten balls is 10% for any trial. We can all agree that this is an independent event, considered on its own. If you take my initial, naïve approach, you end up with in a dead end. By the rules of independent trials, you simply multiply the probabilities together.

$$ 0.1^{10} = 1.0\times10^{-10} $$

Oh, snap, that is a really small number.

Even worse, it gets smaller the more trials we do; that can't be right! Astute readers (or anyone with more brain cells than me) will quickly spot the solution, but is it clear why? Maybe this problem is a consequence of the subtlety of language. At any rate, we have to consider that if we pull out a gold ball, the game is over. It doesn't matter if that is on the first or the tenth trial. This problem is a really good example of when it is more useful to consider the compliment of the probability.

$$ p + q = 1 $$

Where p is the probability of our event and q is the compliment. Another way to ask our burning question is, "What is the likelihood of not drawing a gold ball in ten trials?" This is straightforward, and our independent trial formula works just fine.

$$ 0.9^{10} \approx 0.35 $$

This should calm our intuition. It gets smaller with more trials as one would expect.

Why doesn't it work the other way around? (keep reading!)

I'll admit; I didn't earn a great score in probability theory. I may be showing my ignorance, but I have a soft spot for the struggle my own child is experiencing at the moment.

Another look

Consider it this way, "What is the probability of drawing a gold ball on the first trial?" Easy-peasy, 10%. "What is the probability of pulling out a gold ball in two trails?" A ball, any, it doesn't matter, we just want a gold ball. There is a ten percent chance on the first draw, and a success there eliminates the need to draw a second time. Think about the space of all possible outcomes; the cardinality is $10^2$ for two trials. There is one happy outcome and 9 sad ones on the first draw. The pattern repeats for each possible outcome of the first trial. Out of 100 possibilities in the second trial, 19 of them contain a gold ball.

The probability of drawing a gold ball in two trials is:

  • the probability of drawing a gold ball on the first trial plus
  • the probability of not drawing a gold ball in the first trial multiplied
    • by the probability of drawing a gold ball during an independent, second trial.
$$ 0.1 + (0.9 * 0.1) = 0.19 $$

The probability of drawing a gold ball in three trials is:

  • the probability of drawing a gold ball on the first trial plus
  • the probability of not drawing a gold ball in the first trial multiplied
    • by the probability of drawing a gold ball during an independent, second trial plus
  • the probability of not drawing a gold ball in the previous two trails multiplied
    • by the probability of not drawing a gold ball during an indpendent, third trial.
$$ (0.1 + (0.9 * 0.1)) + (0.9*0.9*0.1) = 0.271 $$

This is quickly turning into a mess, but do you see the pattern? The probability of each trial is dijoint and independent from the previous trials, so we use the addition rule. The probability of getting a gold ball on this trial is dependent on the chances of getting here without a gold ball multiplied by the probability of drawing a gold ball right now (10%). There is a great article that summarizes this on Lumen Learning.

Another way to look at it is that 10 percent of the possibilities of any round are ancestors of the first possible gold ball. Add this 10 percent to 9 times the previous number of success, and you have the number of gold paths to this point.

In [17]:
acc = 1
for i in range(1, 10):
    acc = (acc * 9) + 10**i
    p = acc / 10**(i + 1)
    print(p)

0.19
0.271
0.3439
0.40951
0.468559
0.5217031
0.56953279
0.612579511
0.6513215599

We can extrapolate that out to ten trials, but isn't it a lot easier to subtract one from the compliment?!

$$ 1 - 0.9^{10} \approx 0.65 $$

There is a 65% chance of drawing a gold ball in ten trials with replacement.

I hope this shows how a simple problem can become overly complex if you approach it in a suboptimal way. How often do we do this when writing code?

Takeaways

  • Don't get too creative and deviate away from the learning material when a student is involved unless the material is really fresh in your mind.
  • I love playing with numbers, but probability problems require a lot of careful consideration. Be especially considerate of students who may not be native speakers. Word problems are evil enough for those of use who grew up speaking English.
  • Draw pictures! I have a notebook littered with tree diagrams from my own probability class.
  • It's okay to make mistakes in front of your kids. But don't give up; be a model of resourcefulness and calm determination (ok, ok, maybe I struggle with the calm part 😜).

References