Probability foundations: counting & 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} \le {}_{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(\varnothing) = 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(\lnot 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 $$\mathrm{ex}(E) = r\cdot p(E) + c\cdot\big(1 - p(E)\big),$$ 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.