$ \newcommand{\vect}[1]{\boldsymbol{\mathbf{#1}}} \newcommand{\mat}[1]{\boldsymbol{\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} $

Drawing without replacement

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.

M06.2.4L1 Core25 min

In review

The maths and code on this page are checked by automated tests on every change, but an independent reader has not signed it off yet. Spot a mistake or a confusing step? Tell us.

Before this lesson: M06.2.3 Unordered samples and binomial coefficients

What you will be able to do

Derive the chance of exactly j marked items in a sample of k drawn without replacement from N items, K of them marked, by counting.
Compute the chance that a mini-batch of 4 from 10 examples holds no positive (1/6) and at least one (5/6).
Get the same answer with ordered counts, and explain why numerator and denominator must be both ordered or both unordered.
Check the result by simulation with rng.choice(replace=False) and with scipy.stats.hypergeom, naming its parameters M, n and N.

The question

A training set has 10 examples, and only 3 of them are positive. A mini-batch of 4 is drawn at random, with no example used twice. How likely is it that the batch holds no positive example at all, so that the model sees nothing of the rare class on that step?

From the last lesson

1. What is $\binom{n}{k}$, and how is it found from the ordered count?

Show answer

The number of unordered samples of $k$ different items from $n$. Each has $k!$ orders, so ${\binom{n}{k} = \dfrac{n!/(n-k)!}{k!}}$, which is ${\dfrac{n!}{k!\,(n-k)!}}$.

2. What is the probability of exactly 2 heads in 4 fair flips?

Show answer

${\binom{4}{2}/2^4 = 6/16 = 3/8}$.

Intuition

The ten examples come in two kinds: 3 positives and 7 negatives. A batch is an unordered sample of 4 of the 10. Drawn at random, every one of the $\binom{10}{4}$ batches is equally likely, so a probability about the batch is a count of batches over 210.

M06.2.4-F1

A batch with exactly $j$ positives is a choice of $j$ of the 3 positives together with a choice of ${4 - j}$ of the 7 negatives. The two choices are made separately, so their counts multiply.

The key move is to split one choice into two. Choosing a batch with $j$ positives is the same as choosing its positives and then choosing its negatives, and these are two stages of the multiplication rule.

Build it up

Step 1. The sample space. All batches: ${\binom{10}{4} = \dfrac{10 \cdot 9 \cdot 8 \cdot 7}{4!} = \dfrac{5040}{24} = 210}$.

Step 2. No positives. All 4 must be negatives: ${\binom{7}{4} = 35}$ batches. So ${\Prob(\text{no positive}) = 35/210 = 1/6}$.

Step 3. Exactly one positive. Choose the positive in ${\binom{3}{1} = 3}$ ways and the 3 negatives in ${\binom{7}{3} = 35}$ ways: ${3 \times 35 = 105}$ batches, a probability of ${105/210 = 1/2}$.

Step 4. Two and three. ${\binom{3}{2}\binom{7}{2} = 3 \times 21 = 63}$ and ${\binom{3}{3}\binom{7}{1} = 7}$. Check the total: ${35 + 105 + 63 + 7 = 210}$. Every batch has been counted exactly once.

M06.2.4-F2

Every one of the 210 batches as a cell, sorted by its number of positives. The yellow sixth of the block is the batches with no positive.

The formal statement

Exactly $j$ marked items, drawn without replacement

A sample of $k$ items is drawn without replacement from $N$ items, of which $K$ are marked, so that all $\binom{N}{k}$ samples are equally likely. Then the chance of exactly $j$ marked items is

\[ \Prob(j \text{ marked}) = \frac{\binom{K}{j}\binom{N-K}{k-j}}{\binom{N}{k}}. \]

These probabilities, over all $j$, are the hypergeometric distribution.

Proof. $\Omega$ is the set of unordered samples of size $k$, and it has $\binom{N}{k}$ equally likely members. A sample with exactly $j$ marked items is built in two stages: choose its $j$ marked items from the $K$ marked ones, in $\binom{K}{j}$ ways, then its ${k - j}$ unmarked items from the ${N - K}$ unmarked ones, in $\binom{N-K}{k-j}$ ways. Different choices at either stage give different samples, and every such sample arises once, so by the multiplication rule the event has ${\binom{K}{j}\binom{N-K}{k-j}}$ members. Divide by $|\Omega|$ (lesson M06.2.1).

A count is zero when it asks for more items than exist: a batch of 4 from our 10 can never hold 4 positives, because ${\binom{3}{4} = 0}$.

The same answer in order. Draw the batch one example at a time and keep the order. Now $\Omega$ has ${10 \cdot 9 \cdot 8 \cdot 7 = 5040}$ ordered lists, still equally likely, and the lists with no positive number ${7 \cdot 6 \cdot 5 \cdot 4 = 840}$. The ratio is ${840/5040 = 1/6}$ again: each unordered batch appears as ${4! = 24}$ lists, so the factor 24 cancels top and bottom. Either way works, as long as numerator and denominator are both ordered or both unordered.

With replacement it changes. If examples could repeat, each draw would be negative with chance 7/10 whatever came before, and the ordered count of all-negative lists would be ${7^4}$ out of ${10^4}$: ${2401/10000 = 0.2401}$. Drawing without replacement makes an all-negative batch less likely (1/6, about 0.167), because every negative drawn leaves fewer negatives behind.

M06.2.4-F4

Positives in a batch of 4, drawn without replacement (grey, exact) and with replacement (sky blue). Without replacement the counts bunch more tightly around one positive.

Worked example

At least one positive. “At least one” is the complement of “none”, so the complement rule of lesson M06.1.4 gives

\[ \begin{aligned} \Prob(\text{at least one}) &= 1 - \Prob(\text{none}) \\ &= 1 - \tfrac{1}{6} = \tfrac{5}{6}. \end{aligned} \]

Adding the three other cases gives the same: ${(105 + 63 + 7)/210 = 175/210 = 5/6}$. The complement needs one count instead of three.

M06.2.4-F3

The trace. Counting sets or counting lists gives the same 1/6, and the complement gives 5/6.

So about one batch in six leaves the model with no positive example. With 3 positives among 10 that is a real risk; with a rarer class it gets worse, which is one reason for stratified batches that guarantee each class a place.

Code

From scratch: the formula with math.comb, then a brute-force check that lists all 210 batches with itertools.combinations.

from fractions import Fraction
from itertools import combinations
import math

def exactly(j, N=10, K=3, k=4):
    """P(exactly j marked items in a sample of k drawn without replacement from N, K of them marked)."""
    return Fraction(math.comb(K, j) * math.comb(N - K, k - j), math.comb(N, k))

print([str(exactly(j)) for j in range(5)], 1 - exactly(0))

examples = range(10)                     # examples 0, 1, 2 are the positives
batches = list(combinations(examples, 4))
counts = [sum(1 for b in batches if sum(x < 3 for x in b) == j) for j in range(4)]
print(len(batches), counts)

['1/6', '1/2', '3/10', '1/30', '0'] 5/6
210 [35, 105, 63, 7]

Now the simulation: draw 100,000 batches with rng.choice(10, size=4, replace=False), which never repeats an example, and count the batches with no positive.

import numpy as np

rng = np.random.default_rng(42)
no_positive = 0
for _ in range(100_000):
    batch = rng.choice(10, size=4, replace=False)
    if not np.any(batch < 3):
        no_positive += 1
share = no_positive / 100_000
print(round(share, 4))

0.165

Last, the library. scipy.stats.hypergeom names its parameters differently from this lesson: M is the total number of items (our $N$), n the number of marked items (our $K$) and N the number drawn (our $k$). Read them off the documentation every time.

from scipy import stats

batch_dist = stats.hypergeom(M=10, n=3, N=4)
pmf = batch_dist.pmf([0, 1, 2, 3])
print(np.round(pmf, 4), round(float(batch_dist.sf(0)), 4))

[0.1667 0.5    0.3    0.0333] 0.8333

sf(0) is the chance of more than 0 positives, the 5/6 of the worked example.

Explore

The counting explorer lives in lesson M06.2.3. Set it to 5 balls and 3 draws without replacement, and switch “order matters” on and off: the count changes from 60 to 10, but each box holds the same 6 tiles, so the share of any event is the same either way. That is the rule of this lesson’s pitfall.

Pitfalls

$Two fractions side by side. Left, marked with a cross and titled mixed kinds: 35, tagged unordered, over 5040, tagged ordered, with the result equals 1/144, far too small. Right, marked with a tick and titled same kind on both lines: 840, tagged ordered, over 5040, tagged ordered, with the result equals 1/6, as 35/210 is.$

M06.2.4-F5

Wrong beside right. An unordered count over an ordered count is off by the factor ${4! = 24}$.

“There are 35 batches with no positive and 5040 ways to draw 4, so the chance is 35/5040.”

The 35 counts sets and the 5040 counts lists. Each set appears as 24 lists, so the answer is too small by a factor of 24. Put sets over sets (35/210) or lists over lists (840/5040).

“Each draw is negative with probability 7/10, so all four are negative with probability ${(7/10)^4}$.”

That is the answer with replacement. Without replacement the chance of a negative changes after every draw: 7/10, then 6/9, then 5/8, then 4/7. Their product is ${840/5040 = 1/6}$, the ordered count again. Lesson M06.3.2 will read this product as a chain of conditional probabilities.

“The answer must be the same as for drawing from a huge population.”

With replacement, or from a population so large that removing a few changes nothing, the all-negative chance is 0.2401. From only 10 examples it is 0.167. The difference matters for small data sets and for small classes; it shrinks as the population grows.

Check yourself

Recall

1. Write the chance of exactly $j$ marked items in a sample of $k$ drawn without replacement from $N$ items, $K$ of them marked.

Show answer

${\dfrac{\binom{K}{j}\binom{N-K}{k-j}}{\binom{N}{k}}}$.

2. A batch of 4 is drawn from 10 examples, 3 positive. What is the chance of no positive?

Show answer

${\binom{7}{4}/\binom{10}{4} = 35/210 = 1/6}$.

3. And of at least one positive?

Show answer

${1 - 1/6 = 5/6}$, by the complement rule.

4. Why may you count either ordered or unordered samples, and what must you never do?

Show answer

Both give equally likely outcomes, and each unordered sample of $k$ different items appears as $k!$ ordered ones in the event and in $\Omega$ alike, so the factor cancels. Never put an unordered count over an ordered one, or the reverse.

5. What do the parameters M, n and N of scipy.stats.hypergeom mean?

Show answer

M is the total number of items, n the number of marked items, and N the number drawn without replacement.

Exercises

1. ★ From the same 10 examples (3 positive), a batch of 4 is drawn without replacement. Find the probability that it holds exactly 2 positives.

Show solution

${\binom{3}{2}\binom{7}{2}/\binom{10}{4}}$, which is ${(3 \times 21)/210}$, or 63/210 = 3/10.

2. ★★ A box of 20 parts holds 4 faulty ones. An inspector tests 5 parts chosen at random without replacement. Find the probability that she finds no faulty part, and the probability that she finds at least one.

Show solution

${\binom{20}{5} = 15{,}504}$ samples in all, and ${\binom{16}{5} = 4{,}368}$ with no faulty part, so the chance of finding none is ${4368/15504 = 91/323 \approx 0.282}$. The chance of finding at least one is ${1 - 91/323 = 232/323 \approx 0.718}$.

3. ★★★ A lottery draws 6 numbers from 1 to 49 without replacement, and you choose 6. Find the probability of matching exactly 3 of them, and show that the ordered count gives the same answer.

Show solution

Your 6 numbers are the marked ones and the other 43 are unmarked. Unordered, the chance of exactly 3 matches is

\[ \begin{aligned} &\frac{\binom{6}{3}\binom{43}{3}}{\binom{49}{6}} \\ &\quad= \frac{20 \times 12{,}341}{13{,}983{,}816} \\ &\quad= \frac{246{,}820}{13{,}983{,}816} \\ &\quad\approx 0.0177. \end{aligned} \]

Ordered: $\Omega$ has ${49!/43!}$ lists. A list with exactly 3 matches chooses which 3 of the 6 draws match, in $\binom{6}{3}$ ways, fills those places in order from your 6 in ${6 \cdot 5 \cdot 4 = 120}$ ways and the other 3 from the 43 in ${43 \cdot 42 \cdot 41 = 74{,}046}$ ways, so the event has ${20 \times 120 \times 74{,}046}$ lists. Every ordered count is 720 (that is, $6!$) times its unordered partner: ${49!/43!}$ is 720 times 13,983,816, and ${120 \times 74{,}046}$ is 720 times 12,341, so the event’s lists are 720 times its ${20 \times 12{,}341}$ sets. The factor 720 cancels and the ordered ratio is the same 0.0177.

Summary card

Count the marked and the unmarked separately, multiply, and divide by all samples.

The anchor figure again: 3 blue positive balls and 7 sky-blue negative balls with a batch of 4 ringed, and the count 3 choose j times 7 choose 4 minus j over 10 choose 4, which is 35 over 210 equals 1 over 6 for no positives. — M06.2.4-F1
3 positives, 7 negatives, batches of 4.

Hypergeometric: ${\Prob(j) = \binom{K}{j}\binom{N-K}{k-j}\big/\binom{N}{k}}$.
Mini-batch: no positive 35/210 = 1/6; at least one 5/6.
Same kind top and bottom: sets over sets, or lists over lists.
In code: rng.choice(N, size=k, replace=False), then scipy.stats.hypergeom(M=N, n=K, N=k).

Sources and next steps

Sources. Each was opened and checked against this lesson on 14 November 2026.

Charles M. Grinstead and J. Laurie Snell, Introduction to Probability, second edition, Section 5.1, Important Distributions: the hypergeometric distribution, for $N$ balls of which $k$ are red, $n$ drawn without replacement, with ${h(N, k, n, x) = \binom{k}{x}\binom{N-k}{n-x}/\binom{N}{n}}$ derived by counting.
SciPy developers, scipy.stats.hypergeom, SciPy reference: M is the total number of objects, n the number of Type I objects and N the number drawn without replacement, with the probability mass function in that notation.
NumPy developers, numpy.random.Generator.choice, NumPy reference: with replace=False each element can be chosen at most once, and a sample larger than the population raises a ValueError.

Next. Module M06.3, Conditional probability and independence, redoes this mini-batch one draw at a time as a chain of conditional probabilities, and module M06.8 meets the binomial and hypergeometric families again as named distributions.

This lesson unlocks

M06.3 Conditional probability and independence M06.8 Common distributions and their stories

Your progress is saved in this browser only. No account, no tracking.