Counting & Probability Foundations

#Counting Is Where Probability Starts

You already know how to describe a dataset with a mean and a spread. Probability asks the forward question instead: before you see the data, how likely is each thing that could show up?

Here is the running example. All 200 users, split by plan, device, and outcome:

Hold on to these numbers. We will reuse them in every section: 100 Free users, 100 Pro users, 110 on Mobile, 90 on Desktop, 44 churned in total.

Counting a table like this is easy. Counting "how many ways could I pick 3 users out of 200" is not, and that is why we need counting rules.

#Sample Spaces and Events

Here is the same table with only two attributes, plan and device, so you can see the events as cells:

Now meet three ways of combining events and one special event, one symbol at a time. Each symbol is just a short way to write a word.

A shortcut for the union: if you add the Free row (100) and the Mobile column (110), the 70 users in the overlap get counted twice. Subtract them once and you get 100 + 110 - 70 = 140. Writing P(...) for "the chance of ...", that gives P(Free ∪ Mobile) = 140 / 200 = 0.70. The complement is just as direct: 44 users churned, so P(not churned) = 1 - 44/200 = 156/200 = 0.78.

Three names for the kinds of probability you can read off a table. They are used from here to the end of the lesson, so fix them now with the 200 users:

• Marginal means the chance of one attribute across everyone: P(Mobile) = 110 / 200 = 0.55.
• Joint means the chance of two attributes together: P(Free and Mobile) = 70 / 200 = 0.35.
• Conditional means the chance of one attribute inside a group: among Free users only, what fraction churned? It is written P(churned | Free), and the bar | is read "given". The group after the bar is the only part of the drawer you look at.

#The Three Axioms

All of probability theory follows from three rules. Every function that deserves the name "probability" must obey them. We meet them one at a time.

From these three rules you can derive everything else, including the complement rule above and the fact that no probability can exceed 1.

#Counting Rules

When the sample space is too big to list, counting rules do the listing for you. We build them in four small steps, each with one worked example, and then compare them side by side.

#Step 1: The multiplication principle

If one choice can be made in m ways and, independently of it, a second choice in n ways, the pair of choices can be made in m × n ways.

Worked: 2 plans and 2 devices give 2 × 2 = 4 combinations, which are exactly the four rows of our table: Free-Mobile, Free-Desktop, Pro-Mobile, Pro-Desktop. Add the outcome (churned or stayed) and each of the 4 rows splits in two, so there are 2 × 2 × 2 = 8 possible user profiles.

#Step 2: Factorials

Worked: for 4 users in a queue, there are 4 choices for the front spot, then 3 for the next, then 2, then 1, so 4! = 4 × 3 × 2 × 1 = 24 orders. Five users give 5! = 120, and ten users give 10! = 3,628,800, so factorials explode fast. By convention 0! = 1: there is exactly one way to line up nothing, which is to do nothing.

#Step 3: Permutations (order matters)

Worked: rank 3 users out of 5. There are 5 choices for first place, 4 left for second, 3 left for third, so 5 × 4 × 3 = 60 rankings. That is the same as 5! / 2! = 120 / 2 = 60: the 2! at the bottom cancels the part of the factorial for the 2 users you never place. This count is written P(n, k), here P(5, 3) = 60.

#Step 4: Combinations (order does not matter)

Worked: take the 60 rankings of 3 users out of 5 from step 3. Every group of 3 people appears in 3! = 6 different orders in that list, so the number of groups is 60 / 6 = 10. That is C(5, 3) = 10.

Now the numbers for our 200 users:

• A ranked top-3 of users: 200 × 199 × 198 = 7,880,400 permutations.
• An unranked panel of 3: 7,880,400 / 3! = 7,880,400 / 6 = 1,313,400 combinations. Each panel of 3 appears in 6 different orders in the ranked count, so dividing by 6 removes the duplicates.
• A case you can check by hand: C(5, 2) = 5! / (2! × 3!) = 120 / 12 = 10 ways to pick 2 users from 5.

#The four tools side by side

To choose between the last two, ask one question: would swapping two picked users give a different result? If yes, count permutations. If no, count combinations.

#Counting Rules: Quick Check

Run these in your head or in the playground below, then check yourself:

• How many ways can you order 4 different users in a queue? (4! = 24)
• How many 2-user panels from the 30 Free-Desktop users? (C(30, 2) = 435)
• If a registration form has 2 plan choices, 2 device choices, and 3 country choices, how many distinct profiles are there? (2 × 2 × 3 = 12)

#Classical Probability from Data Counts

When every outcome is equally likely, the probability of an event is favourable outcomes divided by total outcomes. This is the classical definition, and it is what we have been doing with the user table all along.

Pick one user uniformly at random from the 200. Then straight from the table, using the three names defined earlier:

• Marginal: P(churned) = 44 / 200 = 0.22, and P(Mobile) = 110 / 200 = 0.55.
• Joint: P(Free and Mobile) = 70 / 200 = 0.35.
• Conditional: among Free users only, 34 of 100 churned (28 + 6), so P(churned | Free) = 34 / 100 = 0.34. Among Pro users, 10 of 100 churned, so P(churned | Pro) = 0.10.

Conditioning is just shrinking the denominator: the drawer is restricted to the cards that satisfy the condition, and you count again. The new denominator is the size of the group after the bar, 100 Free users here, not 200.

Why it matters: Free users churn at 0.34 and Pro users at 0.10, a more-than-threefold gap that a single overall churn rate of 0.22 would hide completely.

Try the counting rules and the table yourself. This explorer runs on the StreamBox users, the 200-user table above that later lessons reuse: on the first tab pick a rule and watch the count and every arrangement, and on the second pick two events and compare P(A and B) with P(A) P(B).

#Independent vs Mutually Exclusive

Two ideas are constantly confused, so define them precisely.

• Mutually exclusive (disjoint): A and B can never happen together. Formally, P(A ∩ B) = 0.
• Independent: learning that A happened tells you nothing about B. Formally, P(A ∩ B) = P(A) × P(B), or equivalently P(B | A) = P(B).

• P(Free) × P(Mobile) = 0.5 × 0.55 = 0.275
• P(Free and Mobile) from the table = 70 / 200 = 0.35

#The Law of Total Probability

You can partition by device as well: P(churn | Mobile) = 34/110 ≈ 0.309 and P(churn | Desktop) = 10/90 ≈ 0.111, so 0.309 × 0.55 + 0.111 × 0.45 = 0.170 + 0.050 = 0.22 again. This law supplies the "evidence" denominator in Bayes' theorem, which is why it comes right before it.

#The Chain Rule: Probabilities of a Sequence

The product rule for a pair, from the conditional step above, says P(A and B) = P(A) × P(B | A). Apply it repeatedly and you get the chain rule of probability for any number of events:

Start: 200 cards (44 churned = C, 156 stayed = S)
+- Draw 1 is C  (44/200)
|  +- Draw 2 is C  (43/199)
|  |  +- Draw 3 is C  (42/198)    path CCC = 0.0101   <- all three churned
|  |  +- Draw 3 is S  (156/198)   path CCS = 0.0375
|  +- Draw 2 is S  (156/199)
|     +- Draw 3 is C  (43/198)    path CSC = 0.0375
|     +- Draw 3 is S  (155/198)   path CSS = 0.1350
+- Draw 1 is S  (156/200)
   +- Draw 2 is C  (44/199)
   |  +- Draw 3 is C  (43/198)    path SCC = 0.0375
   |  +- Draw 3 is S  (155/198)   path SCS = 0.1350
   +- Draw 2 is S  (155/199)
      +- Draw 3 is C  (44/198)    path SSC = 0.1350
      +- Draw 3 is S  (154/198)   path SSS = 0.4725

Follow the top path, the one where every draw is a churned user. The first card is churned with probability 44/200. If it was, 43 churned cards remain among 199, so the second is churned with probability 43/199. Then 42/198. Multiply along the path:

Every path through the tree is one of the 8 ways three draws can go, and the eight whole-path probabilities add up to 1 (apart from rounding), which is axiom 2 again. The tree's top path agrees with counting: C(44, 3) / C(200, 3) = 13,244 / 1,313,400 ≈ 0.01008. Two different routes, one number.

#Counting and Probability in ML

Explore how a probability distribution assigns weight to outcomes, and notice that the total always stays at 1:

#Verify by Simulation

A counted probability is a claim about the long run. A simulation lets you check the claim by brute force: build the 200 users, draw 3 at random many times, and see how often all three churned.

Try raising TRIALS to a million and watch the simulated value tighten around the counted one. The counting formula tells you the answer exactly; the simulation shows what that answer means as a long-run frequency.

#Try It Yourself

You have read the counts and run the simulation. Now build the same analysis from the raw table, one step at a time. Work through the TODOs in order, run your code, and only then open the solution.

Here is what the solution prints. P(churned) is 0.220 overall, but 0.340 among Free users and about 0.309 among Mobile users, so the condition moves the number a lot. Independence fails: P(Free and churned) is 0.170, while P(Free) x P(churned) = 0.5 x 0.22 = 0.110. Plan and churn are linked, which matches the 0.34 versus 0.10 gap you saw earlier.

There are C(200, 40) ways to pick a 40-user test set, and its log10 is 42.31, so the count is about 2 x 10^42. No program could list them, but math.comb counts them instantly. In the stretch, the chance that a random panel of 3 has no churned user is C(156, 3) / C(200, 3) = 0.4725 by counting, and the seeded simulation gives 0.4706 over 100,000 trials. They agree to about two decimal places, and a different seed will shift the simulated value slightly.

#Key Takeaways

• Probability starts as counting: favourable outcomes divided by total outcomes, when every outcome is equally likely. From our 200 users, P(churn) = 44 / 200 = 0.22
• The three axioms (non-negative, total of 1, additive for disjoint events) are all a valid probability needs, and they are the checks to run on any list of numbers you want to treat as probabilities
• Counting rules: the multiplication principle multiplies independent choices, n! orders n things (4! = 24, 0! = 1), permutations count ordered picks, and n choose k counts unordered picks. P(n,k) = C(n,k) x k!
• Mutually exclusive events cannot happen together, so they are dependent; independent events satisfy P(A and B) = P(A) P(B). The two ideas are close to opposites
• The law of total probability turns per-group rates into an overall rate (0.34 x 0.5 + 0.10 x 0.5 = 0.22), and the chain rule factors any joint probability into a product of conditionals, one fraction per step of a tree of draws (44/200 x 43/199 x 42/198 for three churned users)

#Quick Check