Skip to main content

Independent random variables and their sums

Two random variables are independent when every joint probability is a product. Then the PMF of their sum comes from adding products along the diagonals of a table, a discrete convolution: two dice again, and one more row of a Galton board, which is Pascal’s rule.
M06.5.4L1 Core25 minIn review

Before this lesson

M06.5.2 The probability mass function M06.3.4 Independence

After this lesson you can

  • State when two discrete random variables are independent, test a pair against the definition, and say what i.i.d. means.
  • Derive the PMF of the sum of two independent variables as a sum of products along the diagonals of a table.
  • Show that adding one row to a Galton board convolves its PMF with a fair coin, and that this is Pascal’s rule.
  • Compute a convolution with a double loop and with numpy.convolve, and explain why it fails for a dependent pair.

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.

The question

Each die on its own is flat: every face has probability \(1/6\). Yet their sum is a triangle that peaks at 7. Where does the triangle come from, and can we compute it from the two flat PMFs alone, without listing the 36 outcomes? The same question returns for every sum in machine learning: a total of many small errors, a count of correct answers, a mean over a batch.

From the last lesson

1. Write \({\Prob(a < X \leq b)}\) in terms of the CDF \(F\).

Show answer

\({F(b) - F(a)}\).

2. How does the inverse-CDF sampler turn a uniform \(U\) into a value?

Show answer

It returns the first value whose height \(F(x)\) is greater than \(U\); each value owns a slice of \({[0, 1)}\) as long as its probability.

Intuition

Lay the values of the first die along one side of a table and the values of the second along the other. Each cell is one pair \({(x, y)}\). If the dice do not influence each other, the chance of a pair is the chance of \(x\) times the chance of \(y\): \({1/6 \times 1/6 = 1/36}\) in every cell. The sum \({x + y}\) is the same along each diagonal, so the PMF of the sum adds up the cells of a diagonal.

On the left, a 6 by 6 table of pale cells, x the first die across and y the second die up. Above each column is a grey bar for p X of x equals 1/6, and to the left of each row a grey bar for p Y of y equals 1/6. The six cells on the diagonal where x plus y equals 7 are yellow. On the right, titled PMF of X plus Y, a grey bar chart over s equals 2 to 12 rising to a yellow bar at 7 labelled 6 cells times 1/36. A note reads: every cell: 1/6 times 1/6 equals 1/36; yellow diagonal: x plus y equals 7.
M06.5.4-F1

Two flat PMFs on the edges; each cell is the product of its row and column. Adding the cells of one diagonal gives one bar of the sum: the yellow diagonal makes the yellow bar.

Two ideas are in this picture, and the lesson takes them in turn. Independence is what lets each cell be a product. Adding along diagonals is what turns a table into the PMF of a sum, and it has a name: a convolution.

Build it up

Step 1. Independence for random variables. Lesson M06.3.4 called two events independent when the probability that both happen is the product of their probabilities. Two random variables are independent when every event about one is independent of every event about the other. For dice this means each cell is a product, as in the picture. A pair that fails: the first die \(D_1\) and the sum \({S = D_1 + D_2}\). Knowing \({S = 12}\) forces \({D_1 = 6}\), and indeed

\[ \begin{aligned} \Prob(D_1 = 1, S = 12) &= 0, \quad\text{but} \\ p_{D_1}(1)\, p_S(12) &= \tfrac{1}{6} \times \tfrac{1}{36} \neq 0. \end{aligned} \]

A comma inside \(\Prob\) means “and”. One failing cell is enough to show dependence.

Step 2. Pair each \(x\) with the \(y\) that completes the sum. For \({S = 5}\) the pairs are \({x = 1, 2, 3, 4}\) with \({y = 4, 3, 2, 1}\). Values \({x = 5}\) and 6 would need \({y = 0}\) or \({-1}\), which a die cannot show.

Two rows of bars. Top row, labelled p X of x: six bars of 1/6 at x equals 1 to 6, the first four yellow. Bottom row, labelled p Y of 5 minus x: under x equals 1 to 4 a yellow bar each, for y equals 4, 3, 2 and 1; under x equals 5 and 6, at y equals 0 and minus 1, no bar. Between the rows: 1/6 times 1/6 under each of the first four columns and times 0 under the last two. Title: pair each x with the y that makes x plus y equal 5, multiply, add. Bottom: p S of 5 equals 4 times 1/36 equals 4/36; a die has no 0 or minus 1.
M06.5.4-F2

One bar of the sum, built by pairing. Each \(x\) meets the one \(y\) that completes 5; the products of the pairs that exist add to \(4/36\).

Step 3. One more row of pegs. Let \(X_3\) be the bin after 3 rows of a fair Galton board and \(R\) be 1 if the next bounce goes right, 0 if left. After 4 rows the bin is \({X_4 = X_3 + R}\). A bounce does not remember the earlier ones, so \(R\) is independent of \(X_3\), with \({\Prob(R = 0)} = {\Prob(R = 1)} = {1/2}\).

Top: the PMF of a 3-row Galton board, bars of 1/8, 3/8, 3/8, 1/8 over bins 0 to 3, the middle two yellow. Grey arrows lead from each bar down-left and down-right to the PMF of a 4-row board below, bars of 1/16, 4/16, 6/16, 4/16, 1/16 over bins 0 to 4, with bin 2 yellow. On the right: R equals 1 if the last bounce is right, 0 or 1, each 1/2, independent of X3; bin 2 of row 4 gets half of bin 1 and half of bin 2: one half times 3/8 plus one half times 3/8 equals 6/16; in counts, 3 plus 3 equals 6, which is Pascal's rule. Labels: 3 rows: X3 at the top and 4 rows: X4 equals X3 plus R at the bottom.
M06.5.4-F3

Each bin of row 3 sends half its probability to the bin below it on the left and half to the bin below it on the right. Bin 2 of row 4 collects half of bin 1 and half of bin 2.

So \({\Prob(X_4 = 2)} = {\tfrac12 \cdot \tfrac38 + \tfrac12 \cdot \tfrac38} = {\tfrac{6}{16}}\): the bar of lesson M06.5.2, found without counting a single path.

The formal statement

NoteDefinition: independent random variables

Two discrete random variables \(X\) and \(Y\) on the same sample space are independent when, for every value \(x\) of \(X\) and every value \(y\) of \(Y\),

\[ \Prob(X = x, Y = y) = p_X(x)\, p_Y(y). \]

Random variables \({X_1, \dots, X_n}\) are independent when the probability of every list of values is the product of the \(n\) single probabilities. They are independent and identically distributed (i.i.d.) when, in addition, they all have the same PMF.

Repeated rolls of a die, repeated coin flips and the bounces of a Galton board are i.i.d. So are test examples drawn one at a time, with replacement, from the same pool, which is why accuracy on a test set behaves like a count of i.i.d. indicators (M06.11.1).

Products for any events. The definition talks about single values, but it gives products for any sets \(A\) and \(B\) of values. The event \({X \in A, Y \in B}\) is the disjoint union of the cells \({X = x, Y = y}\) with \(x\) in \(A\) and \(y\) in \(B\), so

\[ \begin{aligned} &\Prob(X \in A, Y \in B) \\ &= \sum_{x \in A} \sum_{y \in B} p_X(x)\, p_Y(y) \\ &= \Big(\sum_{x \in A} p_X(x)\Big) \Big(\sum_{y \in B} p_Y(y)\Big) \\ &= \Prob(X \in A)\, \Prob(Y \in B). \end{aligned} \]

The middle step takes the common factor \(p_X(x)\) out of each inner sum.

NoteThe PMF of a sum of independent variables

If \(X\) and \(Y\) are independent and take whole-number values, the PMF of \({S = X + Y}\) is

\[ p_S(s) = \sum_{x} p_X(x)\, p_Y(s - x), \]

the sum over all values \(x\) of \(X\). This is the convolution of \(p_X\) and \(p_Y\).

Why. Fix \(s\). If \({X = x}\), then \({S = s}\) exactly when \({Y = s - x}\). So the event \({\{S = s\}}\) is the union of the events \({\{X = x, Y = s - x\}}\), one for each \(x\). They are disjoint, because \(X\) has only one value on each outcome. Additivity gives

\[ p_S(s) = \sum_{x} \Prob(X = x,\; Y = s - x), \]

and independence turns each term into \({p_X(x)\, p_Y(s - x)}\). Where \({s - x}\) is not a value of \(Y\), the term is 0. In the table, the terms are the cells on the diagonal \({x + y = s}\).

The Galton board and Pascal’s rule. With \({X_{n+1} = X_n + R}\) as in Step 3, the formula with \({p_R(0) = p_R(1) = 1/2}\) has just two terms:

\[ p_{X_{n+1}}(k) = \tfrac12\, p_{X_n}(k) + \tfrac12\, p_{X_n}(k - 1). \]

Put in \({p_{X_n}(k)} = {\binom{n}{k}/2^n}\) from lesson M06.5.2 and multiply both sides by \({2^{n+1}}\). The left side becomes \({\binom{n+1}{k}}\), the paths to bin \(k\) of a board with \({n + 1}\) rows:

\[ \binom{n+1}{k} = \binom{n}{k} + \binom{n}{k-1}. \]

That is Pascal’s rule (lesson M06.2.3), now read as “the last bounce went left, or it went right”.

Worked example

Heads in flips 1 and 2, plus heads in flips 3 and 4. Let \(X\) count heads in the first two of four fair flips and \(Y\) in the last two. They use different flips, so they are independent, and each has PMF \(1/4\), \(1/2\), \(1/4\) on 0, 1, 2. Find the PMF of \({X + Y}\).

The table. Each cell is a product. In sixteenths, \({p_X(x)\,p_Y(y)}\) is \({1 \times 1 = 1}\) in the corners, \({1 \times 2 = 2}\) on the edges and \({2 \times 2 = 4}\) in the middle.

A 3 by 3 table with x equals 0, 1, 2 across and y equals 0, 1, 2 up. Along the top p X of x is 1/4, 2/4, 1/4 and along the left p Y of y is 1/4, 2/4, 1/4. The cells read, from the top row down: 1/16, 2/16, 1/16; 2/16, 4/16, 2/16; 1/16, 2/16, 1/16. The three cells on the diagonal x plus y equals 2 are yellow and the other diagonals are shaded in alternate greys. On the right, under add each diagonal x plus y equals s: s equals 0: 1 equals 1/16; s equals 1: 2 plus 2 equals 4/16; s equals 2: 1 plus 4 plus 1 equals 6/16; s equals 3: 2 plus 2 equals 4/16; s equals 4: 1 equals 1/16. Below: X plus Y: 1, 4, 6, 4, 1 sixteenths.
M06.5.4-F4

The table of products for two independent counts, each over two flips. The five diagonals give the five bars of the sum.

The diagonals. Using the convolution formula for each \(s\):

\[ \begin{aligned} p_S(0) &= \tfrac14 \cdot \tfrac14 = \tfrac{1}{16}, \\ p_S(1) &= \tfrac14 \cdot \tfrac12 + \tfrac12 \cdot \tfrac14 = \tfrac{4}{16}, \\ p_S(2) &= \tfrac{1}{16} + \tfrac{4}{16} + \tfrac{1}{16} = \tfrac{6}{16}, \end{aligned} \]

and by symmetry \({p_S(3) = 4/16}\) and \({p_S(4) = 1/16}\).

Check. \({X + Y}\) counts heads in four fair flips, which is the bin of a 4-row Galton board, and lesson M06.5.2 found 1, 4, 6, 4, 1 sixteenths. The bars add to \({16/16 = 1}\).

Code

From scratch: a double loop over the two PMFs, adding each product to the bar of its sum.

from collections import defaultdict
from fractions import Fraction
import math

def convolve_pmf(p, q):
    """PMF of X + Y for independent X and Y, given as dicts value -> probability."""
    out = defaultdict(Fraction)
    for x, px in p.items():
        for y, qy in q.items():
            out[x + y] += px * qy          # cell (x, y) lies on the diagonal x + y
    return dict(sorted(out.items()))

die = {k: Fraction(1, 6) for k in range(1, 7)}
two_flips = {0: Fraction(1, 4), 1: Fraction(1, 2), 2: Fraction(1, 4)}
dice_sum = convolve_pmf(die, die)
four_flips = convolve_pmf(two_flips, two_flips)
print("two dice, p(5) and p(7):", dice_sum[5], dice_sum[7])
print("heads in four flips:", list(four_flips.values()))
two dice, p(5) and p(7): 1/9 1/6
heads in four flips: [Fraction(1, 16), Fraction(1, 4), Fraction(3, 8), Fraction(1, 4), Fraction(1, 16)]

numpy.convolve does the diagonal sums on plain arrays. The arrays carry no values, only positions: index 0 of the die’s array is the value 1, so index 0 of the result is the value \({1 + 1 = 2}\). Repeated convolution with the coin \({[1/2, 1/2]}\) grows a Galton board one row at a time.

import numpy as np

die_arr = np.full(6, 1 / 6)
sum_arr = np.convolve(die_arr, die_arr)       # values 2, 3, ..., 12
print("two dice x 36:", np.round(sum_arr * 36, 6))

board = np.array([1.0])                       # 0 rows: the ball is in bin 0
for row in range(10):
    board = np.convolve(board, [0.5, 0.5])    # one more independent bounce
print("10 rows, bin 5:", board[5], " = 252/1024:", 252 / 1024)
two dice x 36: [1. 2. 3. 4. 5. 6. 5. 4. 3. 2. 1.]
10 rows, bin 5: 0.24609375  = 252/1024: 0.24609375

Last, a simulation of two independent dice, and a warning. Below, \(X\) counts heads in flips 1 and 2 and \(Y\) in flips 2 and 3. They share flip 2, so they are not independent, and the convolution of their PMFs (the same 1, 4, 6, 4, 1 sixteenths as above) does not match their actual sum.

rng = np.random.default_rng(5)
d = rng.integers(1, 7, size=(100_000, 2))
sim = np.bincount(d.sum(axis=1), minlength=13)[2:] / len(d)
print("dice, largest gap to exact:", np.max(np.abs(sim - sum_arr)))

h = rng.integers(0, 2, size=(100_000, 3))     # three fair flips per row, 1 = heads
x_plus_y = (h[:, 0] + h[:, 1]) + (h[:, 1] + h[:, 2])
shared = np.bincount(x_plus_y, minlength=5) / len(h)
print("shared flip, simulated:", shared.round(3))
print("convolution would say: ", np.round(np.convolve([.25, .5, .25], [.25, .5, .25]), 3))
dice, largest gap to exact: 0.0016488888888888942
shared flip, simulated: [0.124 0.25  0.252 0.25  0.124]
convolution would say:  [0.062 0.25  0.375 0.25  0.062]

For the dice the simulated sums sit within a hundredth of the triangle. For the shared flip the middle bar is near \(0.25\), not the \(0.375\) that the convolution predicts.

Explore

The Galton board lives in lesson M06.5.2. Go from 4 rows to 5 and compare the exact bars: each new bar is half of the bar above-left plus half of the bar above-right, Step 3 of this lesson.

Pitfalls

Two bar charts of a PMF for X plus Y over the values 0 to 4, where X counts heads in flips 1 and 2 and Y heads in flips 2 and 3. Left, marked with a cross and titled convolve anyway: bars of 1/16, 4/16, 6/16, 4/16, 1/16 with the middle one yellow, and the note assumes X, Y independent. Right, marked with a tick and titled list the 8 outcomes: bars of 1/8, 2/8, 2/8, 2/8, 1/8 with the middle one yellow, and the note X plus Y equals H1 plus 2 H2 plus H3.
M06.5.4-F5

Wrong beside right. \(X\) and \(Y\) share flip 2, so the convolution gives the wrong PMF of their sum; listing the 8 outcomes gives the right one.

“The PMF of a sum is always the convolution of the two PMFs.”

Only when the two are independent. With \(X\) = heads in flips 1 and 2 and \(Y\) = heads in flips 2 and 3, each has PMF \(1/4\), \(1/2\), \(1/4\), but \({X + Y = H_1 + 2H_2 + H_3}\), where \(H_i\) is 1 if flip \(i\) is heads. Listing the 8 outcomes gives 1, 2, 2, 2, 1 eighths, while the convolution gives 1, 4, 6, 4, 1 sixteenths. The PMFs of \(X\) and \(Y\) alone cannot tell the two situations apart; the joint table of lesson M06.9.1 can.

“Independent means they cannot both happen.”

That is disjoint, nearly the opposite. Disjoint events with positive probability are never independent: if one happens, the other has probability 0 (lesson M06.3.4). Independent variables can take any pair of values; learning one leaves the chances of the other unchanged.

“Identically distributed means they take the same value.”

Two dice are identically distributed and usually show different faces. The other way round, \(X\) and \(X\) itself have the same PMF but are as dependent as two variables can be. In machine learning, “i.i.d. examples” means each example is a fresh, separate draw from the same source; duplicates leaked between a training set and a test set break the “independent” part.

Check yourself

Recall

1. When are two discrete random variables \(X\) and \(Y\) independent?

Show answer

When \({\Prob(X = x, Y = y)} = {p_X(x)\,p_Y(y)}\) for every value \(x\) of \(X\) and every value \(y\) of \(Y\).

2. What does i.i.d. mean?

Show answer

Independent and identically distributed: the variables are independent and all have the same PMF.

3. Write the PMF of \({S = X + Y}\) for independent whole-number variables.

Show answer

\({p_S(s)} = {\sum_x p_X(x)\,p_Y(s - x)}\), the convolution of \(p_X\) and \(p_Y\).

4. In the table of products, where are the cells that make up \(p_S(s)\)?

Show answer

On the diagonal \({x + y = s}\).

5. How does one more row of a fair Galton board change its PMF?

Show answer

\({p_{n+1}(k)} = {\tfrac12 p_n(k) + \tfrac12 p_n(k - 1)}\): half of each bin moves one place right. In counts this is Pascal’s rule.

Exercises

1. ★ Roll a die (\(D\)) and flip a fair coin (\(C\) = 1 for heads, 0 for tails), independently. Find the PMF of \({D + C}\).

Show solution

\({D + C}\) runs from 1 to 7. Each cell of the 6 by 2 table is \({1/6 \times 1/2 = 1/12}\). The value 1 needs \({D = 1, C = 0}\): one cell, \(1/12\). Each value from 2 to 6 has two cells, \({(s, 0)}\) and \({(s - 1, 1)}\): \(2/12\). The value 7 needs \({D = 6, C = 1}\): \(1/12\). Check: \({1 + 5 \times 2 + 1 = 12}\) twelfths.

2. ★★ A fair Galton board with 4 rows has PMF 1, 4, 6, 4, 1 sixteenths. Use the rule for one more row to find the PMF for 5 rows, and check it against \(\binom{5}{k}/32\).

Show solution

In 32nds, \({p_5(k)} = {p_4(k) + p_4(k - 1)}\) counted in sixteenths, because halving sixteenths gives 32nds. So bin 0 gets \({1 + 0 = 1}\), bin 1 gets \({4 + 1 = 5}\), bin 2 gets \({6 + 4 = 10}\), bin 3 gets \({4 + 6 = 10}\), bin 4 gets \({1 + 4 = 5}\) and bin 5 gets \({0 + 1 = 1}\). These are \(\binom{5}{k}\) for \({k = 0, \dots, 5}\), and they add to 32.

3. ★★★ Let \(X\) be one roll of a die and set \({Y = X}\), the same roll. Show that \(X\) and \(Y\) are identically distributed but not independent, find the PMF of \({X + Y}\), and compare it with the convolution of the two PMFs.

Show solution

\(Y\) has the same PMF as \(X\), \(1/6\) on each face, so they are identically distributed. But \({\Prob(X = 1, Y = 2) = 0}\) while \({p_X(1)\,p_Y(2) = 1/36}\), so they are not independent. \({X + Y = 2X}\) takes the values 2, 4, 6, 8, 10, 12, each with probability \(1/6\), and never an odd value. The convolution would give the triangle of two independent dice, with \({p(7) = 6/36}\), a value \({2X}\) can never take. The convolution is only valid for independent variables.

Summary card

Independent: cells are products. Sum: add along the diagonals.

The anchor figure again: the 6 by 6 table of two dice with flat PMFs of 1/6 on its edges and the diagonal x plus y equals 7 in yellow, beside the triangular PMF of the sum with the bar at 7 in yellow.
M06.5.4-F1

Products in the cells, sums on the diagonals.

  • Independent. \({\Prob(X = x, Y = y)} = {p_X(x)\,p_Y(y)}\) for all \(x\), \(y\).
  • i.i.d. Independent, with one shared PMF.
  • Convolution. \({p_{X+Y}(s)} = {\sum_x p_X(x)\,p_Y(s - x)}\).
  • Galton board. One more row: \({p_{n+1}(k)} = {\tfrac12 p_n(k) + \tfrac12 p_n(k-1)}\).

Sources and next steps

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

  • Hossein Pishro-Nik, Introduction to Probability, Statistics, and Random Processes, Section 3.1.4. The definition of independent discrete random variables, \({P(X = x, Y = y)} = {P(X = x)P(Y = y)}\) for all \(x\) and \(y\), and its extension to \(n\) variables.
  • Charles M. Grinstead and J. Laurie Snell, Introduction to Probability, second edition, Section 7.1. The derivation of \({P(Z = z)} = {\sum_k P(X = k)\,P(Y = z - k)}\) from the disjoint events \({X = k}\), \({Y = z - k}\); Definition 7.1 of the convolution; and Example 7.1, the sum of two dice from 1/36 up to 6/36 and back.
  • NumPy documentation, numpy.convolve: “the sum of two independent random variables is distributed according to the convolution of their individual distributions”; the default mode 'full' returns \({N + M - 1}\) entries.

Next. This closes the module. Module M06.6 moves to random variables with densities, M06.7.2 uses independence to show that \({\E[XY] = \E[X]\,\E[Y]}\), M06.9 builds tables for dependent pairs, and M06.11.1 convolves dice again to watch a mean narrow.

This lesson unlocks

M06.7.2 Linearity of expectation M06.9.1 Joint distributions as tables M06.11.1 The sample mean is a random variable

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