Probability foundations: counting & conditional probability

◈ 4 cards

Counting rules, permutations vs combinations, the sample-space definition of probability, Kolmogorov’s axioms, expectation, and conditional probability.

Why probability, and why here

Classical logic (Modules 1–6) reasons about what is provably true. Real agents — a physician, a diagnostic program, a self-driving car — must act on incomplete, noisy evidence. Stochastic methods (Luger Ch 5) attack uncertainty head-on: maintain explicit probability distributions over hypotheses and update them with evidence. The pay-off, in contrast to the heuristic confidence numbers of Module 4, is a mathematically principled framework. The cost is tractability — full probabilistic inference can be exponential, which is exactly why the later parts of this module (certainty factors, naive Bayes, belief networks) trade rigor for feasibility.

Counting: the two rules everything is built on

Probabilities of equally likely outcomes reduce to counting. Two rules generate the rest:

Addition rule — for sets $A$ and $C$ , $∣ A \cup C ∣ = ∣ A ∣ + ∣ C ∣ - ∣ A \cap C ∣$ . You subtract the overlap so shared elements are not double-counted (this is inclusion–exclusion).
Multiplication rule — if a first choice has $a$ options and a second has $b$ , there are $a \times b$ combined outcomes. This underlies the Cartesian product, permutations, and combinations.

Permutations vs combinations — the one distinction that trips people up: does order matter?

A permutation is an ordered arrangement. The number of permutations of $n$ items taken $r$ at a time is $_{n} P_{r} = \frac{n !}{( n - r )!} .$ Arranging books on a shelf is a permutation — a different order is a different arrangement.
A combination is an unordered subset: $_{n} C_{r} = \frac{n !}{( n - r )! r !} .$ Picking a committee is a combination — the same people in a different order are the same committee. Dividing by $r!$ collapses the $r!$ re-orderings of each chosen subset into one, so always $_{n} C_{r} \leq_{n} P_{r}$ .

Probability as a ratio, and Kolmogorov’s axioms

The sample space $S$ is the set of all outcomes of an experiment; an event $E$ is a subset of $S$ . For equally likely outcomes, $p (E) = \frac{∣ E ∣}{∣ S ∣} .$ All of probability theory follows from Kolmogorov’s three axioms: (1) every event’s probability lies in $[0, 1]$ ; (2) $p (S) = 1$ and $p (\emptyset) = 0$ ; (3) $p (A \cup B) = p (A) + p (B) - p (A \cap B)$ (the addition rule again, now over probabilities). The complement rule $p (\neg E) = 1 - p (E)$ falls straight out of these.

Expectation

The expectation (expected value) of an outcome with reward $r$ at probability $p$ and cost $c$ otherwise is $ex (E) = r \cdot p (E) + c \cdot (1 - p (E)),$ i.e. the probability-weighted average payoff. Worked example — roulette. A European wheel has 37 slots. Bet $\$1$ on one number: you win $\$35$ with probability $1/37$ and lose $\$1$ with probability $36/37$, so $$\mathrm{ex} = 35\cdot\tfrac{1}{37} + (-1)\cdot\tfrac{36}{37} \approx -\$0.027\text{ per play.} $The *negative* expectation is precisely why the house wins in the long run — and the same machinery (maximize expected reward) drives decision-theoretic planning and reinforcement learning later in AI. ## Conditional probability When we *know* event B occurred, the probability of A updates to the **conditional probability**$ p(A \mid B) = \frac{p(A \cap B)}{p(B)}.$$ Read it as: restrict the universe to the part where $B$ holds, then ask what fraction of that is also $A$. A fatal-but-common error is to assume $p(A\mid B) = p(B\mid A)$ — they are usually very different (the base-rate fallacy). Converting between the two is exactly the job of Bayes’ theorem in the next lesson.

The single question that separates the two counts is whether order matters. Dividing nPr by r! collapses the r! re-orderings of each chosen subset into one combination — which is why nCr is always the smaller number.