Convolution on Infinite Discrete Supports

Why Infinite Supports Require Careful Convolution

When two independent discrete random variables are added, a particular value of the sum can be produced by many pairs of values. The challenge is to identify exactly which pairs are possible and then add their probabilities. With variables whose supports extend without bound, the sum may have infinitely many contributing pairs, so the calculation becomes a series rather than a short table.

The key step is to express the target event as disjoint combinations of values of the two variables. Independence then lets us multiply the probabilities for each combination. The support determines whether the resulting sum has finitely or infinitely many terms.

Definition: Let $X$ and $Y$ be independent integer-valued random variables, with probability mass functions $p_X(k)=P(X=k)$ and $p_Y(k)=P(Y=k)$. For an integer $s$, the convolution formula is $$ P(X+Y=s)=\sum_{k\in\mathbb{Z}}p_X(k)p_Y(s-k). $$ Terms for which $k$ is outside the support of $X$, or $s-k$ is outside the support of $Y$, are zero. Thus the sum may be finite or infinite, depending on the supports.

Setting the Summation Range

The convolution formula can be written with $X=k$ and $Y=s-k$, or with the roles of $X$ and $Y$ reversed. Either form is valid, but the first is often easiest to interpret: list the possible values $k$ of $X$, then check whether $s-k$ is possible for $Y$.

For example, if both variables take nonnegative integer values, then a fixed sum $s\geq 0$ can be formed only with $0\leq k\leq s$. Its point probability is therefore a finite sum, even though each variable has an infinite support. In contrast, if one variable can be positive while the other can be negative, a fixed sum may be formed by infinitely many pairs.

Useful support check: If $X$ has support $A$ and $Y$ has support $B$, then a term contributes to $P(X+Y=s)$ only when $k\in A$ and $s-k\in B$. Determine both restrictions before evaluating the sum.

Worked Example: A Sum of a Geometric Variable and a Negative Geometric Variable

Let $X$ and $Z$ be independent. Suppose $X$ has a geometric distribution with success probability $1/2$, counting failures before the first success, so $P(X=k)=(1/2)(1/2)^k$ for $k=0,1,2,\ldots$. Let $Z$ also count failures before the first success, with success probability $1/3$, so $P(Z=k)=(1/3)(2/3)^k$. Set $Y=-Z$. Find $P(X+Y=0)$ and $P(X+Y=1)$.

Method and support. Since $X+Y=X-Z$, the target equation is $X-Z=s$. For $s=0$, the valid pairs are $X=k,\ Z=k$ for every integer $k\geq0$. There are infinitely many such pairs.

By independence and the geometric probability mass functions, $$ P(X-Z=0)=\sum_{k=0}^{\infty}\left(\frac12\left(\frac12\right)^k\right)\left(\frac13\left(\frac23\right)^k\right) =\frac16\sum_{k=0}^{\infty}\left(\frac13\right)^k. $$ The geometric series has first term $1$ and common ratio $1/3$, so its sum is $1/(1-1/3)=3/2$. Therefore $$ P(X-Z=0)=\frac16\cdot\frac32=\frac14=0.2500. $$

For $X-Z=1$, the valid pairs are $X=k+1,\ Z=k$, again for every $k\geq0$. Thus $$ P(X-Z=1)=\sum_{k=0}^{\infty}\left(\frac12\left(\frac12\right)^{k+1}\right)\left(\frac13\left(\frac23\right)^k\right) =\frac1{12}\sum_{k=0}^{\infty}\left(\frac13\right)^k =\frac1{12}\cdot\frac32 =\frac18=0.1250. $$

Check and common mistake avoided. Both probabilities are between zero and one, and each infinite series converges because its ratio is less than one. Keeping only the $k=0$ pair would give $1/6$ for the first probability, which omits all the other valid pairs; summing the full series gives $1/4$.

Why the Convolution Formula Holds

For a fixed integer $s$, the event $X+Y=s$ can be split according to the value of $X$. If $X=k$, the sum equals $s$ precisely when $Y=s-k$. These cases are mutually exclusive for different values of $k$, and together they cover every way the sum can equal $s$.

\begin{aligned} \{X+Y=s\} &=\bigcup_{k\in\mathbb{Z}}\{X=k,\ Y=s-k\},\\ P(X+Y=s) &=\sum_{k\in\mathbb{Z}}P(X=k,\ Y=s-k)\\ &=\sum_{k\in\mathbb{Z}}P(X=k)P(Y=s-k). \end{aligned}

The second line uses countable additivity for disjoint events. The final line uses independence. Without independence, the joint probabilities $P(X=k,Y=s-k)$ cannot in general be replaced by products of marginal probabilities. The series is well-defined: each term is nonnegative, and the sum is at most $\sum_k P(X=k)=1$, since $P(Y=s-k)\leq1$.

Evaluating Infinite Convolution Series

A frequent pattern is a Poisson variable combined with the negative of a geometric variable. The factorial in the Poisson probability mass function often turns the convolution into an exponential series. The support equation still comes first: solving it determines the index and the correct starting point of the sum.

Worked Example: A Poisson Variable Minus a Geometric Variable

Let $X\sim\operatorname{Poisson}(2)$, so $P(X=j)=e^{-2}2^j/j!$ for $j=0,1,2,\ldots$. Independently, let $Z$ be geometric with success probability $1/2$, counting failures before the first success, and set $Y=-Z$. Find $P(X+Y=1)$.

Method and valid range. The equation $X-Z=1$ requires $X=Z+1$. Write $Z=k$, where $k=0,1,2,\ldots$; then $X=k+1$. No negative values of $k$ are possible, and every nonnegative $k$ gives an admissible pair.

Using independence, $$ \begin{aligned} P(X-Z=1) &=\sum_{k=0}^{\infty}P(X=k+1)P(Z=k)\\ &=\sum_{k=0}^{\infty}\left(e^{-2}\frac{2^{k+1}}{(k+1)!}\right)\left(\frac12\left(\frac12\right)^k\right)\\ &=e^{-2}\sum_{k=0}^{\infty}\frac{1}{(k+1)!}. \end{aligned} $$

Set $j=k+1$. The series becomes $\sum_{j=1}^{\infty}1/j!=e-1$, because $e=\sum_{j=0}^{\infty}1/j!$. Therefore $$ P(X-Z=1)=e^{-2}(e-1)\approx 0.2325. $$ The probability is reported to four decimal places.

Check and common mistake avoided. The first term, corresponding to $k=0$, is $P(X=1)P(Z=0)=e^{-2}$, which agrees with the first term of $e^{-2}\sum_{j=1}^{\infty}1/j!$. Summing from $j=0$ instead would incorrectly add the term $e^{-2}$, which corresponds to no admissible pair in $X-Z=1$.

From Point Probabilities to Tail Probabilities

A tail probability such as $P(X+Y\geq r)$ can be found by summing the point probabilities for all integers $s\geq r$, provided those probabilities are known. When both variables are nonnegative, a fixed-sum convolution is finite, while the tail sum is infinite. It is often useful to simplify the point probability first and then sum the resulting series.

Worked Example: A Tail Probability for Two Nonnegative Geometric Variables

Let $X$ and $Y$ be independent geometric variables counting failures before the first success. Let $X$ have success probability $1/2$, and let $Y$ have success probability $1/4$. Find $P(X+Y\geq3)$.

Method and point-probability range. Both supports are $0,1,2,\ldots$. For a fixed $n\geq0$, the equation $X+Y=n$ allows $X=k$ only for $k=0,\ldots,n$, with $Y=n-k$. Hence $$ \begin{aligned} P(X+Y=n) &=\sum_{k=0}^{n}\left(\frac12\left(\frac12\right)^k\right) \left(\frac14\left(\frac34\right)^{n-k}\right)\\ &=\frac18\sum_{k=0}^{n}\left(\frac12\right)^k\left(\frac34\right)^{n-k}\\ &=\frac12\left[\left(\frac34\right)^{n+1}-\left(\frac12\right)^{n+1}\right]. \end{aligned} $$ The last step uses the finite geometric-sum identity; the denominator in that identity is $3/4-1/2=1/4$.

Now sum over all integers $n\geq3$: $$ \begin{aligned} P(X+Y\geq3) &=\frac12\sum_{n=3}^{\infty}\left[\left(\frac34\right)^{n+1}-\left(\frac12\right)^{n+1}\right]\\ &=\frac12\left[ \frac{(3/4)^4}{1-3/4} -\frac{(1/2)^4}{1-1/2} \right]\\ &=\frac12\left(\frac{81}{64}-\frac18\right) =\frac{73}{128} =0.5703. \end{aligned} $$ The probability is reported to four decimal places.

Check and common mistake avoided. The complementary probability is $P(X+Y\leq2)$. From the same point formula, the probabilities at $n=0,1,2$ are $1/8,\ 5/32,\ 19/128$, respectively. Their sum is $16/128+20/128+19/128=55/128$, and $1-55/128=73/128$, confirming the result. The tail begins at $n=3$, not $n=4$: “at least 3” includes 3.

Common Convolution Traps

Convolution errors usually come from the support or the event equation rather than from difficult algebra. Before evaluating any sum, write the equation relating the component values to the target sum and use it to establish the index range.

Using an invalid range. For nonnegative $X$ and $Y$, a fixed sum $n$ permits only $0\leq X\leq n$. For $X-Z=s$ with nonnegative $Z$, the range may instead extend infinitely.
Dropping valid infinite terms. A fixed target value does not guarantee a finite number of pairs. If one variable can increase while the other decreases, infinitely many pairs may still have the same sum.
Multiplying without independence. The product $P(X=k)P(Y=s-k)$ is valid only when $X$ and $Y$ are independent. Otherwise use the joint probability.
Reversing the event equation. From $X-Z=s$, one obtains $X=Z+s$, not $Z=X+s$. Solving this relation carefully also reveals the correct starting index.
Misreading the geometric convention. Here a geometric variable counts failures before the first success and has support $0,1,2,\ldots$. A convention that counts the trial of the first success has a different support and probability mass function.

Key takeaway: For an independent discrete sum, identify all pairs satisfying the target equation, restrict the index to the supports, and only then apply independence. Evaluate any infinite series using a justified convergence formula, and check that the final probability is in $[0,1]$.

Check Your Understanding

For each problem, state the valid summation range before evaluating the probability. Geometric variables count failures before the first success.

Independent $X$ and $Z$ are geometric with success probabilities $1/2$ and $1/2$, respectively. Set $Y=-Z$. Find $P(X+Y=0)$. (Answer: $1/3=0.3333$)
Let $X\sim\operatorname{Poisson}(1)$, and independently let $Z$ be geometric with success probability $1/2$. Set $Y=-Z$. Find $P(X+Y=0)$. (Answer: $\frac12e^{-1/2}=0.3033$)
Independent $X$ and $Y$ are geometric with success probabilities $1/3$ and $1/2$, respectively. Find $P(X+Y=2)$. (Answer: $37/216=0.1713$)
Let $X\sim\operatorname{Poisson}(2)$, and independently let $Z$ be geometric with success probability $1/3$. Set $Y=-Z$. Find $P(X+Y=-1)$. (Answer: $\frac29e^{-2/3}=0.1141$)
Independent $X$ and $Y$ are geometric with success probabilities $1/2$ and $1/4$, respectively. Find $P(X+Y\geq2)$. (Answer: $23/32=0.7188$)

What You'll Learn