Skip to content
Tutorials Center
My learning

Topics

Lesson 13 of 38 · Sampling Methods

Sampling Discrete Distributions

Draw from any discrete distribution with cumulative sums, build binomial and geometric samplers, and meet the fast alias method.

Many simulated quantities take only a few separate values: the outcome of a die, the number of customers arriving, which of several states a system moves to next. A discrete distribution assigns a probability p_i to each value i. This lesson shows how to sample from any such distribution, how to build the standard named ones from simple parts, and how to make sampling fast when there are many values.

The cumulative-sum method

Inverse transform sampling works for discrete variables too. List the probabilities p₀, p₁, …, p_{k−1} (they must sum to 1). Take cumulative sums:

Text
c₀ = p₀,  c₁ = p₀ + p₁,  …,  c_{k−1} = 1

These cut the interval [0, 1) into k pieces with lengths p_i. Draw U uniform and return the index of the piece that contains U, i.e. the smallest i with U < c_i. Each piece is hit with probability equal to its length.

Value Probability Cumulative U range
0 0.5 0.5 [0, 0.5)
1 0.3 0.8 [0.5, 0.8)
2 0.2 1.0 [0.8, 1.0)
Python Cumulative-sum sampler

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

np.searchsorted does a fast binary search. It handles a whole array of U values in one call, so the sampler is vectorized. NumPy's own rng.choice(values, size, p=probs) does essentially this.

Building a binomial from Bernoulli trials

A Bernoulli variable is 1 with probability p and 0 otherwise: 1 if U < p else 0. A binomial variable counts successes in n independent Bernoulli trials. The direct way is to add up n Bernoulli draws. Its mean is np and variance np(1−p).

Python Binomial by summing Bernoulli trials

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The geometric distribution by inversion

A geometric variable counts how many trials you need until the first success when each trial succeeds with probability p. It takes values 1, 2, 3, … with P(K = k) = (1−p)^(k−1) p. Its tail is P(K > k) = (1−p)^k, so inverting gives

Text
K = ceil( ln(U) / ln(1 − p) )

This produces a sample using one uniform number, no matter how large K is, instead of a slow loop of trials.

Python Geometric: one uniform per sample

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Poisson by counting arrivals

The Poisson distribution with mean λ counts events in a unit of time when events arrive independently at rate λ. The gaps between events are exponential(λ). So draw exponential gaps and count how many fit before time 1. This ties together two distributions from earlier lessons.

Python Poisson from exponential gaps

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

For a Poisson variable the mean and variance are both λ, a handy sanity check.

Many outcomes: the alias method

The cumulative method costs about log₂ k steps per sample (binary search) for k outcomes. If k is in the thousands or millions and you need billions of samples, that adds up. Walker's alias method prepares two tables in time proportional to k, after which every sample costs a constant number of steps: pick a column uniformly, then flip a biased coin to choose between that column's own value and its "alias". You do not need the details to use it; the key idea is that you can trade setup time for sampling speed. Libraries such as random.choices and some specialised packages use similar ideas.

For a handful of outcomes, rng.choice(values, size, p=probs) is the right tool. Reach for specialised methods only when profiling shows sampling is the bottleneck.

Check your understanding

Quick check · 4 questions

of 4 answered You scored / 4 · perfect!

  1. 1. Probabilities are 0.2, 0.5, 0.3 for values 0, 1, 2. The cumulative sums are 0.2, 0.7, 1.0. Which value does U = 0.65 select?

    0.65 lies in [0.2, 0.7), the piece for value 1.
  2. 2. A binomial(n, p) variable can be simulated by

    A binomial counts successes in n independent trials, so it is the sum of n Bernoulli variables.
  3. 3. What is the mean of a geometric variable with success probability p = 0.25 (counting trials until the first success)?

    The mean is 1/p = 4.
  4. 4. How can Poisson(λ) be sampled using exponentials?

    Poisson counts are the number of arrivals of a process with exponential inter-arrival times.

Summary

  • For any discrete distribution, cut [0, 1) by cumulative sums and find where U falls (np.searchsorted).
  • Binomial: sum of Bernoulli trials; geometric: ceil(ln U / ln(1−p)); Poisson: count exponential arrivals in one time unit.
  • Mean and variance checks (Poisson: both λ) catch many bugs.
  • The alias method gives constant-time sampling for large numbers of outcomes after a setup step.

Next: Sampling Points in Shapes and on Spheres