\( \newcommand{\vect}[1]{\mathbf{#1}} \newcommand{\mat}[1]{\mathbf{#1}} \newcommand{\R}{\mathbb{R}} \newcommand{\E}{\mathbb{E}} \newcommand{\Prob}{\mathbb{P}} \newcommand{\T}{^{\top}} \newcommand{\norm}[1]{\lVert #1 \rVert} \newcommand{\abs}[1]{\lvert #1 \rvert} \newcommand{\ihat}{\mkern1mu\hat{\boldsymbol{\imath}}\mkern2mu} \newcommand{\jhat}{\mkern1mu\hat{\boldsymbol{\jmath}}\mkern2mu} \newcommand{\pd}[2]{\frac{\partial #1}{\partial #2}} \newcommand{\argmax}{\operatorname*{arg\,max}} \newcommand{\argmin}{\operatorname*{arg\,min}} \newcommand{\cdata}[1]{\class{c-data}{#1}} \newcommand{\cmodel}[1]{\class{c-model}{#1}} \newcommand{\ctruth}[1]{\class{c-truth}{#1}} \newcommand{\cgrad}[1]{\class{c-grad}{#1}} \newcommand{\closs}[1]{\class{c-loss}{#1}} \newcommand{\cparam}[1]{\class{c-param}{#1}} \newcommand{\csecond}[1]{\class{c-second}{#1}} \renewcommand{\,}{\mkern3mu} \)

M06.2 · Counting and equally likely outcomes

A free, illustrated module of 4 lessons and one interactive in M06 Probability I: Equally likely outcomes; Ordered samples and the birthday problem; Unordered samples and binomial coefficients; Drawing without replacement.

M06.2 L1 · Core 4 lessons · about 100 min Live · in review

Part of M06 Probability I in the Mathematics track.

When every outcome is equally likely, a probability is a count: the outcomes in the event over all the outcomes. These four lessons derive that rule from the axioms and then learn to count the samples that machine learning draws: in order or not, with replacement or without. They answer the birthday problem, find that exactly 2 heads in 4 flips has probability 6/16 by way of a Galton board, and work out how often a random mini-batch misses a rare class.

What you need first. Sample spaces, events and the three axioms of probability (M06.1), and counting by the multiplication rule, permutations and n choose k (M01.8). The code uses Python sets, lists and loops (P01) and a first taste of NumPy’s random generator.

Lessons

1. Equally likely outcomes M06.2.1 25 min

   When every outcome is equally likely, a probability is a count: the outcomes in the event over all the outcomes. Derive that rule from the axioms, count sample spaces in stages with the multiplication rule, and see why the 11 sums of two dice are not equally likely.

2. Ordered samples and the birthday problem M06.2.2 25 min

   Draw k times from n things and keep the order: n^k ways with replacement and n!/(n - k)! without. Their ratio answers the birthday problem: among 23 people a shared birthday is more likely than not, the same sum that predicts hash collisions.

3. Unordered samples and binomial coefficients M06.2.3 25 min

   Choose k of n things when order does not matter: divide the ordered count by the k! orders of each choice to get n choose k. Prove Pascal’s rule on a Galton board, and find that exactly 2 heads in 4 fair flips has probability 6/16.

4. Drawing without replacement M06.2.4 25 min

   Find the chance of exactly j marked items in a sample drawn without replacement, by counting the two kinds separately. Worked on a mini-batch of 4 from 10 examples, 3 of them positive, checked by simulation and with scipy.stats.hypergeom.

The interactive

M06.2-X1 · Counting explorer. Draw k balls from a bag of n and switch “order matters” and “put back” on and off. Every ordered draw is a tile, the tiles that make the same sample share a box, and the read-out gives the count beside its formula and says whether the samples are equally likely. It lives in Unordered samples and binomial coefficients.