Convolution Bounds For Independent Sums

Why convolution bounds matter

When \(Z=X+Y\), a candidate value of \(X\) contributes to the distribution of \(Z\) only if the corresponding value \(Y=Z-X\) is possible. Convolution is the process of combining the distributions of independent summands, but its limits are not arbitrary: they come from the supports of both variables. Omitting either support restriction can add impossible outcomes; applying only one can leave out valid ones.

This is especially important when the supports are shifted, have gaps, or have different endpoints. A reliable solution first identifies the possible values of each summand, then writes the convolution over their intersection. The same principle applies to probabilities such as \(P(X+Y\leq t)\): the region of integration must satisfy both support restrictions as well as the event.

Definition: The support of a random variable is the set of values that can occur with positive probability in a discrete model, or the region where its density can be nonzero in a continuous model. For independent \(X\) and \(Y\), the distribution of \(Z=X+Y\) is obtained by summing or integrating contributions only where both \(X=x\) and \(Y=z-x\) are possible.

Discrete convolution: intersect the supports

Suppose \(X\) and \(Y\) are independent discrete random variables with probability mass functions \(p_X\) and \(p_Y\). For any value \(z\),

P(X+Y=z)=\sum_{\substack{x\in\mathcal{S}_X\\z-x\in\mathcal{S}_Y}}p_X(x)p_Y(z-x),

where \(\mathcal{S}_X\) and \(\mathcal{S}_Y\) are their supports. Equivalently, the summation is over \(\mathcal{S}_X\cap(z-\mathcal{S}_Y)\), where \(z-\mathcal{S}_Y=\{z-y:y\in\mathcal{S}_Y\}\). If both supports are integer intervals, the restrictions can often be written as lower and upper bounds. For example, if \(X\) can be any integer from \(a\) to \(b\), and \(Y\) any integer from \(c\) to \(d\), then a contributing \(x\) must satisfy

\max(a,z-d)\leq x\leq\min(b,z-c),

with \(x\) restricted to integers. If the lower bound exceeds the upper bound, there are no contributing pairs and the probability is zero. If supports have gaps, the interval bounds alone are not enough: retain only values actually in both supports.

Worked Example: Convolving Discrete Supports With Gaps

Let \(X\) and \(Y\) be independent. The support and probabilities of \(X\) are \(0,1,2\) with probabilities \(0.2,0.5,0.3\), respectively. The support and probabilities of \(Y\) are \(0,2,4\) with probabilities \(0.25,0.50,0.25\), respectively. Find the distribution of \(Z=X+Y\), including \(P(Z=4)\).

Method. For each possible \(z\), retain only pairs \((x,y)\) in the two supports that sum to \(z\), and multiply the independent probabilities for each pair.

The smallest sum is \(0+0=0\), and the largest is \(2+4=6\). The possible sums are the integers from 0 through 6, although not every sum has the same contributing pairs. In particular, \(Z=4\) can occur as \((X,Y)=(0,4)\) or \((2,2)\). Thus

$$ P(Z=4)=(0.2)(0.25)+(0.3)(0.50)=0.05+0.15=0.20. $$

For the full distribution, list the valid pairs for each sum:

\begin{aligned} P(Z=0)&=(0.2)(0.25)=0.05,\\ P(Z=1)&=(0.5)(0.25)=0.125,\\ P(Z=2)&=(0.2)(0.50)+(0.3)(0.25)=0.10+0.075=0.175,\\ P(Z=3)&=(0.5)(0.50)=0.25,\\ P(Z=4)&=(0.2)(0.25)+(0.3)(0.50)=0.05+0.15=0.20,\\ P(Z=5)&=(0.5)(0.25)=0.125,\\ P(Z=6)&=(0.3)(0.25)=0.075. \end{aligned}

The probabilities sum to \(0.05+0.125+0.175+0.25+0.20+0.125+0.075=1.000\), as required. The gap in \(Y\)'s support matters: for \(Z=2\), for example, \(Y=1\) is not available, so the pair \((1,1)\) must not be counted. The common mistake this avoids is treating every integer in a support’s range as possible when the support actually has gaps.

Continuous convolution: derive the integral limits

Suppose \(X\) and \(Y\) are independent continuous random variables with densities \(f_X\) and \(f_Y\). For a fixed sum \(z\), a possible \(x\) must lie in the support of \(X\), and \(z-x\) must lie in the support of \(Y\). The density of \(Z=X+Y\) is therefore

f_Z(z)=\int_{\{x:x\in\mathcal{S}_X,\ z-x\in\mathcal{S}_Y\}} f_X(x)f_Y(z-x)\,dx.

If the supports are intervals \((a,b)\) and \((c,d)\), the restrictions \(a<x<b\) and \(c<z-x<d\) combine to give

\max(a,z-d)<x<\min(b,z-c).

Endpoints do not affect a continuous integral, so they can be included in the written integration limits. The density formula follows by conditioning on \(X\): for a small interval of possible sums near \(z\), the contribution from \(X\) near \(x\) is proportional to \(f_X(x)\,dx\), and the corresponding value of \(Y\) is near \(z-x\), contributing density \(f_Y(z-x)\). Independence makes the joint density the product \(f_X(x)f_Y(y)\); integrating over all compatible \(x\) gives the displayed formula. Without independence, that product is generally not the joint density, so this convolution formula need not apply.

Worked Example: Convolving Uniform Variables With Unequal Supports

Let \(X\sim\operatorname{Uniform}(0,2)\) and \(Y\sim\operatorname{Uniform}(1,4)\), independently. Find the density of \(Z=X+Y\), and then calculate \(P(Z\leq 3)\).

Step 1: Write the support restrictions. The densities are \(f_X(x)=1/2\) on \((0,2)\) and \(f_Y(y)=1/3\) on \((1,4)\). For a fixed \(z\), the requirements \(0<x<2\) and \(1<z-x<4\) imply \(z-4<x<z-1\). Thus the valid range is the intersection of these intervals:

\max(0,z-4)<x<\min(2,z-1).

The overlap changes at \(z=1,3,4,6\), the endpoints of the sum’s support and the points where the lower or upper limit changes. The overlap length is \(z-1\) for \(1<z<3\), \(2\) for \(3\leq z\leq4\), and \(6-z\) for \(4<z<6\). The product of the two densities is \(1/6\), so

f_Z(z)= \begin{cases} (z-1)/6,&1<z<3,\\ 1/3,&3\leq z\leq4,\\ (6-z)/6,&4<z<6,\\ 0,&\text{otherwise}. \end{cases}

Step 2: Integrate to obtain the requested probability. Since \(3\) is in the first rising section,

P(Z\leq3)=\int_1^3\frac{z-1}{6}\,dz =\left.\frac{(z-1)^2}{12}\right|_1^3 =\frac{4}{12}=\frac13=0.3333.

As a check, the three density areas are \(1/3\) on \((1,3)\), \(1/3\) on \((3,4)\), and \(1/3\) on \((4,6)\), for a total of 1. The key trap is to use the full support of \(X\) for every \(z\); for example, at \(z=2\), only \(0<x<1\) is valid, not all of \(0<x<2\).

Mixed sums: condition on the discrete variable

A sum can also combine a discrete variable and a continuous variable. If independent \(X\) is discrete and \(Y\) is continuous, conditioning on the value of \(X\) gives

f_{X+Y}(z)=\sum_{x\in\mathcal{S}_X}p_X(x)f_Y(z-x),

where each term is zero whenever \(z-x\) lies outside the support of \(Y\). This is a weighted sum of shifted densities. Each possible value of \(X\) shifts the support of \(Y\), and its probability weights that shift.

Worked Example: A Discrete Shift of a Continuous Distribution

A hypothetical device adds a random calibration offset \(X\), which is 0 with probability \(0.6\) and 2 with probability \(0.4\), to an independent random measurement error \(Y\sim\operatorname{Uniform}(0,3)\). Find the density of \(Z=X+Y\) and \(P(Z\leq3.5)\).

Step 1: Find each shifted support. If \(X=0\), then \(Z=Y\) has support \((0,3)\) and contributes \(0.6(1/3)=0.2\) to the density there. If \(X=2\), then \(Z=2+Y\) has support \((2,5)\) and contributes \(0.4(1/3)=0.1333\) there. The supports overlap on \((2,3)\), so the contributions must be added on that interval:

f_Z(z)= \begin{cases} 0.2,&0<z<2,\\ 0.2+0.4/3=1/3,&2<z<3,\\ 0.4/3=0.1333,&3<z<5,\\ 0,&\text{otherwise}. \end{cases}

Step 2: Calculate the probability. If \(X=0\), then \(Z\leq3.5\) always because \(Y<3\). If \(X=2\), the event requires \(Y\leq1.5\), which has probability \(1.5/3=0.5\). Hence

P(Z\leq3.5)=0.6(1)+0.4(0.5)=0.6+0.2=0.8000.

The density also checks: the first interval has area \(2(0.2)=0.4\), the overlap has area \(1(1/3)=1/3\), and the last interval has area \(2(0.4/3)=0.2667\). Their exact sum is \(0.4+1/3+4/15=1\). The trap avoided is using just one shifted density on the overlap, where both values of \(X\) can produce the same sum.

Common bounds errors and a practical method

Convolution is a bookkeeping problem as much as an integration or summation problem. Before calculating, state the supports and translate the second support condition into a restriction on the first variable. Then intersect the restrictions. This prevents several frequent errors:

Using only one support. A value of \(x\) may be possible for \(X\), while \(z-x\) is impossible for \(Y\); that \(x\) contributes nothing.
Assuming a continuous sum is uniform. Even when both summands are uniform, the overlap length changes with \(z\), so the sum density generally changes too.
Ignoring support gaps in a discrete model. Integer bounds do not imply that every integer inside them has positive probability.
Multiplying marginal probabilities without independence. For dependent variables, use the joint distribution or a conditional distribution; \(f_X(x)f_Y(y)\) is not generally valid.

A useful final check is to verify that the resulting sum distribution has total probability one. For a discrete convolution, add all the masses. For a continuous convolution, integrate the density over its support. Also check that the sum support is contained in the set of sums \(x+y\) formed from the two original supports.

State the model.
Confirm independence and write the support of each summand.

Translate both support conditions.
For a fixed sum \(z\), require \(x\in\mathcal{S}_X\) and \(z-x\in\mathcal{S}_Y\).

Form the convolution.
Sum over valid discrete values or integrate over the continuous intersection; for a mixed sum, weight the shifted density by each discrete probability.

Check the result.
Confirm the support, add or integrate to one, and compute any requested probability using the derived distribution.

Check Your Understanding

For each problem, first identify the values or interval that can contribute to the sum.

Independent \(X\) has probabilities \(0.2,0.5,0.3\) at \(0,1,2\), respectively. Independent \(Y\) has probabilities \(0.4,0.6\) at \(1,3\), respectively. Find \(P(X+Y=3)\). (Answer: 0.2400)
Independent \(X\sim\operatorname{Uniform}(0,1)\) and \(Y\sim\operatorname{Uniform}(0,3)\). Find the density of \(X+Y\) at \(z=2\). (Answer: \(1/3\), or 0.3333)
Independent \(X,Y\sim\operatorname{Uniform}(0,2)\). Find \(P(X+Y\leq0.5)\). (Answer: 0.0313 to four decimals)
Independent \(X\) equals 1 with probability 0.7 and 4 with probability 0.3; \(Y\sim\operatorname{Uniform}(0,2)\). Find the density of \(X+Y\) at \(z=4.5\). (Answer: 0.1500)
Independent \(X\) is uniform on the integer support \(\{0,1,2,3\}\), and \(Y\) equals 0 or 2 with probability \(1/2\) each. Find \(P(X+Y=4)\). (Answer: 0.1250)

What You'll Learn