Discrete Convolution on Finite Supports

Why Enumerating Outcome Pairs Works

When two independent discrete measurements are added, a particular total can often be produced in several different ways. To find the probability of that total, list all the pairs that produce it, find the probability of each pair, and add those probabilities. This is the finite-support form of convolution: a practical method for turning two probability distributions into the distribution of their sum.

The method is useful whenever each variable has only finitely many possible values. It applies to counts, discrete uniform variables, and dice totals, including cases in which the variables have different supports or unequal probabilities. The key conditions are that the variables are independent and that their probability distributions are specified.

Definition: Let $X$ and $Y$ be independent discrete random variables with finite supports. Write $p_X(x)=P(X=x)$ and $p_Y(y)=P(Y=y)$, taking either probability to be zero when its argument is outside that variable's support. For $S=X+Y$, the probability mass function is $$ P(S=s)=\sum_x p_X(x)p_Y(s-x). $$ The sum is taken over the possible values $x$ of $X$. Equivalently, enumerate all pairs $(x,y)$ for which $x+y=s$, multiply $p_X(x)p_Y(y)$ for each pair, and add the products.

The formula relies on independence: it gives $P(X=x,Y=y)=p_X(x)p_Y(y)$. If the variables are dependent, the pair probability must instead come from their joint distribution; multiplying the marginal probabilities is generally incorrect. Also, different pairs may produce the same total, so the distribution of $S$ is not usually obtained by simply copying the probabilities of $X$ or $Y$.

A Reliable Enumeration Procedure

For modest supports, a pair table is often the clearest calculation. Put the possible values of one variable across the top and the values of the other down the side. Each cell records the sum for that pair, or its probability if you are tabulating probabilities directly. Then group cells with equal sums.

List the supports and probabilities.
Record every possible value and its probability for each variable. Check that each variable's probabilities sum to one.

Enumerate pairs.
Form every possible pair $(x,y)$. Under independence, assign that pair probability $p_X(x)p_Y(y)$.

Group by total.
For each value $s$, add the probabilities of all pairs satisfying $x+y=s$.

Check the result.
Verify that the resulting probabilities sum to one and that no possible pair has been omitted.

Deriving the Finite Convolution Formula

The formula follows by separating the event that the sum equals $s$ according to the value of $X$. For each possible $x$, the only value of $Y$ that makes $X+Y=s$ is $s-x$. These pair events cannot occur simultaneously for two different values of $X$, so their probabilities add.

\begin{aligned} \{S=s\} &=\bigcup_x \{X=x,\ Y=s-x\},\\ P(S=s) &=\sum_x P(X=x,\ Y=s-x)\\ &=\sum_x P(X=x)P(Y=s-x)\\ &=\sum_x p_X(x)p_Y(s-x). \end{aligned}

The second equality uses the fact that the events in the union are disjoint. The third uses independence. This also explains why the calculation has two distinct operations: multiply probabilities for a single pair, then add across all pairs producing the same total.

Worked Example: Combining Unequal Pair Probabilities

A hypothetical monitoring system records a count $X$ of minor alerts during one interval, with $P(X=0)=1/4$, $P(X=1)=1/2$, and $P(X=3)=1/4$. An independent system records a count $Y$ during the same interval, with $P(Y=0)=2/3$ and $P(Y=2)=1/3$. Find the distribution of $S=X+Y$ and $P(S\geq 3)$.

Method. Enumerate the six pairs and multiply their probabilities, since the two counts are independent. The pairs and their contributions are:

\begin{array}{c|c|c|c} X & Y & X+Y & P(X,Y)\\ \hline 0&0&0&(1/4)(2/3)=1/6\\ 0&2&2&(1/4)(1/3)=1/12\\ 1&0&1&(1/2)(2/3)=1/3\\ 1&2&3&(1/2)(1/3)=1/6\\ 3&0&3&(1/4)(2/3)=1/6\\ 3&2&5&(1/4)(1/3)=1/12 \end{array}

The total $3$ occurs in two different ways, so its probability is $1/6+1/6=1/3$. The complete distribution is therefore $P(S=0)=1/6$, $P(S=1)=1/3$, $P(S=2)=1/12$, $P(S=3)=1/3$, and $P(S=5)=1/12$. The value $4$ has probability zero because no pair produces it.

The requested tail probability is $$ P(S\geq 3)=P(S=3)+P(S=5)=1/3+1/12=5/12. $$ As a check, the distribution sums to $1/6+1/3+1/12+1/3+1/12=1$. Common mistake avoided: counting the two ways to obtain $3$ only once would omit one pair and understate its probability.

Sums of Discrete Uniform Variables

A discrete uniform variable assigns equal probability to each value in a finite set. When independent discrete uniform variables are added, every pair has the same probability, but the resulting sum is not generally uniform. Totals near the middle may have more representations than totals near the extremes.

Worked Example: Two Independent Discrete Uniform Measurements

Two independent hypothetical measurement offsets are recorded as integers. $X$ is uniform on $\{0,1,2,3\}$, and $Y$ is uniform on $\{1,2,3\}$. Find the distribution of $S=X+Y$, $P(S=4)$, and $P(S\geq 5)$.

There are $4$ possible values of $X$ and $3$ of $Y$, giving $4\cdot3=12$ equally likely pairs. Each pair has probability $(1/4)(1/3)=1/12$. Enumerating by the value of $X$:

\begin{array}{c|ccc} &Y=1&Y=2&Y=3\\ \hline X=0&1&2&3\\ X=1&2&3&4\\ X=2&3&4&5\\ X=3&4&5&6 \end{array}

Each cell shows the sum. Counting cells by total gives $1,2,3,3,2,1$ pairs for totals $1,2,3,4,5,6$, respectively. Thus the corresponding probabilities are $$ P(S=1,2,3,4,5,6)=\left(\frac{1}{12},\frac{2}{12},\frac{3}{12},\frac{3}{12},\frac{2}{12},\frac{1}{12}\right). $$ In particular, $P(S=4)=3/12=1/4$, and $P(S\geq5)=(2+1)/12=1/4$. The check is $(1+2+3+3+2+1)/12=12/12=1$. Common mistake avoided: the totals are not equally likely just because each variable is uniform; total $3$ has three representations, while total $1$ has only one.

Dice Totals with Different Supports

Dice calculations are the same finite-support problem. The sample space consists of ordered pairs of face values. If the dice are independent and fair, each ordered pair is equally likely. When the dice have different numbers of faces, use the product of those face counts for the number of pairs; do not assume a square sample space.

Worked Example: A Four-Faced Die and a Six-Faced Die

A hypothetical game uses one fair four-faced die numbered $1$ through $4$ and one independent fair six-faced die numbered $1$ through $6$. Find the distribution of their total $T$, the probability that $T=5$, and the probability that $T\geq7$.

There are $4\cdot6=24$ equally likely ordered pairs, each with probability $1/24$. Counting pairs for each possible total gives:

\begin{array}{c|ccccccccc} t&2&3&4&5&6&7&8&9&10\\ \hline \text{number of pairs}&1&2&3&4&4&4&3&2&1\\ P(T=t)&1/24&2/24&3/24&4/24&4/24&4/24&3/24&2/24&1/24 \end{array}

For example, total $7$ comes from $(1,6),(2,5),(3,4),(4,3)$, giving four pairs. Total $5$ also has four pairs, so $P(T=5)=4/24=1/6$. Totals at least $7$ have $4+3+2+1=10$ pairs, hence $P(T\geq7)=10/24=5/12$. The counts sum to $1+2+3+4+4+4+3+2+1=24$, as required. Common mistake avoided: using $36$ outcomes would treat the four-faced die as if it had six faces; the correct denominator is $24$.

Common Errors and a Final Check

A correct convolution is more than a list of possible totals. It must account for every pair, use the correct pair probabilities, and aggregate all pairs that yield the same sum. These checks are especially useful when supports have gaps or when probabilities are not equal.

Forgetting independence. Multiplying marginal probabilities is justified only when $X$ and $Y$ are independent. Otherwise use the joint probabilities.
Omitting a repeated total. If multiple pairs produce $s$, add every pair's probability to obtain $P(X+Y=s)$.
Assuming every total is possible. The sum's support consists of totals generated by at least one pair with positive probability. Gaps can occur.
Using the wrong number of equally likely pairs. For independent uniform variables with $m$ and $n$ possible values, there are $mn$ pairs, not necessarily $m^2$ or $n^2$.
Skipping the total-probability check. The probabilities of all possible sums must add to one. A failure usually indicates a missed pair, an incorrect product, or a grouping error.

For finite supports, enumeration is often safer than trying to infer the shape of a distribution. Once each pair has been assigned its probability, grouping by sum gives the complete distribution directly.

Check Your Understanding

For each problem, assume the stated variables are independent. Enumerate pairs where useful, combine equal totals, and check that the distribution is valid.

$X$ takes values $0$ and $2$ with probabilities $0.25$ and $0.75$. $Y$ takes values $1$ and $2$ with probabilities $0.4$ and $0.6$. Find the distribution of $X+Y$ and $P(X+Y\geq3)$. (Answer: $P(S=1,2,3,4)=(0.10,0.15,0.30,0.45)$; $P(S\geq3)=0.75$.)
$X$ is uniform on $\{1,2,3,4,5\}$ and $Y$ is uniform on $\{0,1,2\}$. Find $P(X+Y=5)$ and $P(X+Y\geq6)$. (Answer: $3/15=1/5$ and $3/15=1/5$.)
$X$ takes values $1,2,4$ with probabilities $0.2,0.5,0.3$; $Y$ takes values $0,1$ with probabilities $0.7,0.3$. Find the full distribution of $X+Y$. (Answer: $P(S=1,2,3,4,5)=(0.14,0.41,0.15,0.21,0.09)$.)
Two independent fair eight-sided dice are numbered $1$ through $8$. Find the probability their total is at least $10$, and the probability their total is even. (Answer: $28/64=7/16$ and $32/64=1/2$.)
$X$ takes values $-1,0,2$ with probabilities $0.2,0.5,0.3$; $Y$ takes values $0,2$ with probabilities $0.25,0.75$. Find the distribution of $X+Y$ and $P(X+Y=2)$. (Answer: $P(S=-1,0,1,2,4)=(0.05,0.125,0.15,0.45,0.225)$; $P(S=2)=0.45$.)

What You'll Learn