Tutorials › Statistical Theory I - Probability and Distribution Theory › The Discrete Convolution Formula

Home  /  Tutorials  /  Joint Laws of Independent Variables

Joint Laws of Independent Variables · Tutorial 276 of 994

The Discrete Convolution Formula

Learn how independence turns the mass function of a sum into a sum of products, and how the supports determine which terms can contribute.

Intermediate 9 min read

What You'll Learn

  • Derive the discrete convolution formula from a disjoint partition of the event that a sum equals a given integer.
  • State the formula using the supports of both summands, including when the resulting probability is zero.
  • Distinguish possible sum values from values that actually have positive probability.
  • Evaluate convolution probabilities for finite and countably infinite supports.
  • Check that the resulting mass function is nonnegative and sums to one.

Why Sums Require a New Mass Function

Knowing the separate distributions of two random variables does not, by itself, tell us how to calculate the distribution of their sum. If \(X\) and \(Y\) are independent and integer-valued, the event \(X+Y=z\) can occur in several different ways: \(X\) might equal one value and \(Y\) the value that completes the sum, or the variables might take another pair of values with the same total. The probability of the sum must account for every such pair.

Independence supplies the probability of each pair as a product. Partitioning the event according to the value of one summand then gives the discrete convolution formula. The support conditions are essential: only pairs of values that are possible for both variables can contribute.

Definition: For an integer-valued random variable \(X\), its probability mass function is \(f_X(k)=P(X=k)\), for \(k\in\mathbb{Z}\). Its support is the set \(A=\{k\in\mathbb{Z}: f_X(k)>0\}\). For another integer-valued random variable \(Y\), write \(f_Y\) for its mass function and \(B=\{j\in\mathbb{Z}:f_Y(j)>0\}\) for its support.

The supports \(A\) and \(B\) may be finite or countably infinite. For any integer \(z\), a value \(k\) of \(X\) can contribute to the event \(X+Y=z\) only if \(z-k\) is a possible value of \(Y\). Thus the relevant \(k\)'s belong to \(A\) and also satisfy \(z-k\in B\).

The Discrete Convolution Formula

Theorem: Let \(X\) and \(Y\) be independent, integer-valued random variables with mass functions \(f_X\) and \(f_Y\). For \(S=X+Y\) and every integer \(z\), $$ f_S(z)=P(S=z)=\sum_{k\in\mathbb{Z}} f_X(k)f_Y(z-k) =\sum_{\substack{k\in A\\z-k\in B}} f_X(k)f_Y(z-k). $$ If there are no \(k\in A\) for which \(z-k\in B\), the sum is empty and \(f_S(z)=0\). The support of \(S\) is exactly $$ \{z\in\mathbb{Z}: f_S(z)>0\}=\{x+y:x\in A,\ y\in B\}. $$

The first sum can be written over all integers because any term with \(k\notin A\) or \(z-k\notin B\) is zero. The restricted version makes the support condition explicit. For fixed \(z\), there may be finitely or infinitely many contributing terms; in either case the sum is well-defined because its terms are nonnegative and its total is at most one.

To derive the formula, fix \(z\). The events \(\{X=k,Y=z-k\}\), as \(k\) ranges over the integers, are pairwise disjoint. Their union is exactly \(\{X+Y=z\}\): whenever the sum equals \(z\), the realized value \(k=X\) identifies one and only one event in the partition. Countable additivity and independence therefore give

$$ \begin{aligned} P(X+Y=z) &=\sum_{k\in\mathbb{Z}}P(X=k,Y=z-k)\\ &=\sum_{k\in\mathbb{Z}}P(X=k)P(Y=z-k)\\ &=\sum_{k\in\mathbb{Z}}f_X(k)f_Y(z-k). \end{aligned} $$

Each term is nonnegative. Consequently, the sum is positive if and only if at least one term is positive. A term is positive exactly when \(k\in A\) and \(z-k\in B\). This proves the stated description of the support.

Normalization: The convolution values form a probability mass function. Indeed, using nonnegativity to rearrange the countable sums, $$ \begin{aligned} \sum_{z\in\mathbb{Z}} f_S(z) &=\sum_{z\in\mathbb{Z}}\sum_{k\in\mathbb{Z}}f_X(k)f_Y(z-k)\\ &=\sum_{k\in\mathbb{Z}} f_X(k)\sum_{z\in\mathbb{Z}}f_Y(z-k)\\ &=\sum_{k\in\mathbb{Z}}f_X(k)\cdot 1=1. \end{aligned} $$ For fixed \(k\), as \(z\) ranges over the integers, \(z-k\) ranges over the integers, so the inner sum is one. This also verifies directly that no probability mass is lost by the formula.

Worked Applications

Worked Example: Two Finite Supports With a Shared Sum

Let \(X\) and \(Y\) be independent, with \(P(X=0)=1/2\), \(P(X=2)=1/3\), \(P(X=5)=1/6\), and \(P(Y=-1)=1/4\), \(P(Y=1)=3/4\). Find the support of \(S=X+Y\), and calculate \(P(S=1)\) and \(P(S=3)\).

The possible sums are obtained by pairing each value of \(X\) with each value of \(Y\): \(0+(-1)=-1\), \(0+1=1\), \(2+(-1)=1\), \(2+1=3\), \(5+(-1)=4\), and \(5+1=6\). Thus the support is \(\{-1,1,3,4,6\}\). In particular, the sum does not take every integer between its smallest and largest possible values.

There are two contributing decompositions of 1: \((X,Y)=(0,1)\) and \((2,-1)\). By the convolution formula and independence, $$ P(S=1)=f_X(0)f_Y(1)+f_X(2)f_Y(-1) =\frac12\cdot\frac34+\frac13\cdot\frac14 =\frac38+\frac1{12}=\frac{11}{24}. $$

There is only one decomposition of 3: \((X,Y)=(2,1)\). Therefore, $$ P(S=3)=f_X(2)f_Y(1)=\frac13\cdot\frac34=\frac14. $$

Worked Example: A Sum With Infinite Supports

Suppose \(X\) and \(Y\) are independent and each has support \(\{0,1,2,\ldots\}\), with \(f_X(k)=f_Y(k)=1/((k+1)(k+2))\) for \(k\geq 0\). First check that this specifies a probability mass function, then find \(P(X+Y=2)\).

For every \(k\geq 0\), $$ \frac{1}{(k+1)(k+2)}=\frac{1}{k+1}-\frac{1}{k+2}. $$ Thus the partial sum through \(k=N\) is $$ \sum_{k=0}^{N} \left(\frac{1}{k+1}-\frac{1}{k+2}\right) =1-\frac{1}{N+2}, $$ which tends to 1 as \(N\) tends to infinity. The masses are positive and sum to one, so each is a valid probability mass function.

For the sum to equal 2, the only possible pairs are \((0,2)\), \((1,1)\), and \((2,0)\). The formula gives $$ \begin{aligned} P(X+Y=2) &=f_X(0)f_Y(2)+f_X(1)f_Y(1)+f_X(2)f_Y(0)\\ &=\frac12\cdot\frac1{12}+\frac16\cdot\frac16+\frac1{12}\cdot\frac12\\ &=\frac1{24}+\frac1{36}+\frac1{24} =\frac1{12}+\frac1{36} =\frac19. \end{aligned} $$ Only three terms contribute because both variables are nonnegative: any \(k<0\) or \(2-k<0\) has zero mass.

Worked Example: Support Gaps From an Even-Valued Summand

Let \(X\) have support \(\{0,2,4,\ldots\}\), with \(P(X=2m)=2^{-(m+1)}\) for \(m\geq0\). Independently, let \(Y\) take values \(-3\) and \(2\), with probabilities \(2/5\) and \(3/5\). Determine the support of \(S=X+Y\) and calculate \(P(S=1)\).

The masses of \(X\) sum to one because \(\sum_{m=0}^{\infty}2^{-(m+1)}=1\); the two stated probabilities for \(Y\) also sum to one. Pairing the possible values gives $$ \{x+y:x\in A,y\in B\} =\{-3+2m:m\geq0\}\ \cup\ \{2+2m:m\geq0\}. $$ The first set consists of \(-3,-1,1,3,\ldots\), and the second consists of \(2,4,6,\ldots\). Hence \(-2\) and 0, for example, are not in the support.

To obtain a sum of 1, the choice \(Y=-3\) requires \(X=4\), while the choice \(Y=2\) would require \(X=-1\), which is impossible. Since \(4=2m\) for \(m=2\), \(P(X=4)=2^{-(2+1)}=1/8\). Therefore, $$ P(S=1)=P(X=4)P(Y=-3)=\frac18\cdot\frac25=\frac1{20}. $$ The support condition removes the impossible decomposition before any probability is assigned to it.

Common Mistakes and Why the Formula Matters

A common mistake is to calculate \(P(X+Y=z)\) from only one pair of values, even when several pairs produce the same sum. For instance, in the first example, using only \((X,Y)=(0,1)\) would give \(3/8\), not the correct \(11/24\), because it omits \((2,-1)\). The correction is to list or characterize all \(k\) for which both \(f_X(k)\) and \(f_Y(z-k)\) are positive, and then add the corresponding products.

A related error is to assume that every integer between the smallest and largest possible sums belongs to the support. Supports can have gaps, as the first and third examples show. The precise test is not whether \(z\) lies between two endpoints; it is whether at least one pair \(x\in A\), \(y\in B\) satisfies \(x+y=z\). Independence is equally important: the product \(f_X(k)f_Y(z-k)\) follows from independence, and is not generally valid for dependent variables.

The convolution formula matters because it converts a joint probability calculation into a one-dimensional sum of products, while keeping track of every possible decomposition of the total. The same support-based reasoning also applies when there are infinitely many candidate values: zero-mass terms contribute nothing, and nonnegative terms make the countable sum well-defined.

Check Your Understanding

Use the support conditions as well as the products of masses when answering.

  1. If \(X\) has support \(\{0,2\}\) and \(Y\) has support \(\{1,3\}\), which values can \(X+Y\) take?
  2. For independent integer-valued \(X,Y\), explain why the events \(\{X=k,Y=z-k\}\) are disjoint as \(k\) varies.
  3. Suppose \(f_X(1)=1/4\), \(f_X(2)=3/4\), \(f_Y(-1)=2/5\), and \(f_Y(0)=3/5\), with \(X\) and \(Y\) independent. Calculate \(P(X+Y=1)\).
  4. Why does an empty sum in the convolution formula mean \(P(X+Y=z)=0\)?
  5. What part of the convolution formula would need to change if \(X\) and \(Y\) were dependent?

Previous

Next

Back to Tutorials