Exercise 3: Discrete Distribution Sampling

Mathematical idea

Identify the unknown parameter from the normalization condition

Given PMF The probability mass function assigns probability kA to the value x = k, for k = 1, 2, 3, 4.

f X (1)=A, f X (2)=2A, f X (3)=3A, f X (4)=4A

Key principle A PMF must sum to 1 over its support.

Computation

A + 2A + 3A + 4A = 10A = 1 \Rightarrow A = 0.1

Python code

x   = np.array([1, 2, 3, 4])     # support of the distribution
# A + 2A + 3A + 4A = 10A = 1  =>  A = 1/10
f_X = np.array([1/10, 2/10, 3/10, 4/10])  # f_X(k) = k * A

Bar heights are A, 2A, 3A, 4A — a linearly increasing shape

The total area (sum of all bars) equals 1, confirming A = 0.1

PMF f_X(x)

f_X(1) = A

0.1

f_X(2) = 2A

0.2

f_X(3) = 3A

0.3

f_X(4) = 4A

0.4

Mathematical idea

Build the cumulative distribution as accumulated probability

Definition

F X (x) = P(X \leq x) = \sum x j \leq x f X (x j)

Geometric meaning For a discrete random variable, the CDF is a right-continuous step function: it stays constant between support points and jumps only at x_k.

Key takeaway

F X (x k) - F X (x k-1) = f X (x k)

Python code

# Cumulative sum: each entry adds the next PMF value
F_X = np.cumsum(f_X)     # [0.1, 0.3, 0.6, 1.0]

● = right-limit (value taken by the CDF at the jump point)

○ = left-limit (value just before the jump — not taken)

Jump size at x_k = F_X(x_k) − F_X(x_k−1) = f_X(x_k)

CDF F_X(t)

F_X(1) = 1/10

0.1

F_X(2) = 3/10

0.3

F_X(3) = 6/10

0.6

F_X(4) = 10/10

1.0

Mathematical idea

Sample by locating where the uniform draw falls on the CDF

Algorithm 1. Draw

ρ ~ U(0,1)

2. Return

x k = min{x : F X (x) \geq ρ}

Interpretation Each value x_k corresponds to the interval

(F X (x k-1), F X (x k)]

on the vertical probability axis.

Why it works

P(X = x k) = P(F X (x k-1) < ρ \leq F X (x k)) = F X (x k) - F X (x k-1) = f X (x k)

Python code

# Draw a uniform random number in [0, 1)
rho = np.random.rand()

# Return the smallest index where F_X[i] >= rho
sampleIndex = np.searchsorted(F_X, rho)  # quantile function
samples[i]  = x[sampleIndex]             # sampled value

ρ = 0.45

ρ (uniform draw)

0.45

Sampled x_k

—

F_X(x_k−1)

—

F_X(x_k)

—

→ Horizontal arrow: from the y-axis at height ρ rightward until the CDF step at x_k

↓ Vertical arrow: drops from the CDF step down to the x-axis — this is the sampled value

Mathematical idea

Verify the sampler by comparing empirical frequencies with the target PMF

Estimator

p̂ obs (x k) = #{i : X i = x k} / N

Interpretation This is the observed fraction of sampled values equal to x_k.

As N grows By the Law of Large Numbers,

p̂ obs (x k) \to f X (x k)

N \to \infty

N (samples): 1,000

Python code

# Count how many samples equal each value x_k
p_obs = np.zeros(len(x))
for i in range(len(x)):
    p_obs[i] = np.sum(samples == x[i]) / N

Theoretical f_X(x) Empirical p̂_obs(x)

N (samples)

—

Max |error|

—

Blue bars = theoretical PMF (target)

Red bars = empirical frequencies — converge to blue as N grows

Exercise 3: Sampling from a discrete distribution