Convolution for Lattice Laws With Unequal Spans

Why Unequal Lattice Spans Require Care

When two independent discrete random variables are added, the probability at a sum comes from every pair of values that produces it. With different lattice spans, not every point on a tempting grid is attainable, and a single sum can have several representations. The reliable approach is to describe the supports first, then solve the equation that matches values from the two supports.

For example, if one variable takes values in multiples of 4 and another in multiples of 6, their sum lies on the grid of multiples of 2. But that grid is only a containing lattice: the value 2 cannot be formed from nonnegative multiples of 4 and 6. At other values, such as 12, more than one pair may contribute. Both facts matter when finding the distribution of the sum.

Definition: A discrete random variable \(X\) has a lattice representation with offset \(\alpha\) and span \(h>0\) if it takes values in \(\{\alpha+hi:i\in I\}\) with probability one, where \(I\) is a subset of the integers. Its support is the set of values having positive probability. For a lattice representation, write \(p_X(x)=P(X=x)\). The offset locates the grid; the span gives its spacing. A variable can have more than one lattice representation if the stated span is not the largest possible one.

Suppose \(X=\alpha+hI\) and \(Y=\beta+kJ\), where \(I\) and \(J\) take integer values and \(h,k>0\). For an observed value \(s\), a contribution to \(P(X+Y=s)\) is possible only if there are indices \(i,j\) in the respective supports satisfying \((\alpha+hi)+(\beta+kj)=s\). Thus it is not enough that \(s\) belongs to a broad grid containing the sums: there must be an actual compatible pair of support points.

The Convolution Formula on the Supports

The general discrete convolution formula makes this compatibility condition explicit. Its sum can be taken over the support of \(X\); terms for which \(s-x\) is outside the support of \(Y\) contribute zero.

Theorem: If \(X\) and \(Y\) are independent discrete random variables, then, for every real \(s\), \[ P(X+Y=s)=\sum_{x\in\operatorname{supp}(X)}p_X(x)p_Y(s-x), \] where \(p_Y(y)=0\) whenever \(y\) is not in the support of \(Y\). In particular, \(s\) is in the support of \(X+Y\) exactly when at least one \(x\in\operatorname{supp}(X)\) has \(s-x\in\operatorname{supp}(Y)\).

Proof. The event \(\{X+Y=s\}\) is the disjoint union, over \(x\in\operatorname{supp}(X)\), of the events \(\{X=x,Y=s-x\}\). Countable additivity and independence give

P(X+Y=s) =\sum_{x\in\operatorname{supp}(X)}P(X=x,Y=s-x) =\sum_{x\in\operatorname{supp}(X)}p_X(x)p_Y(s-x).

Each summand is nonnegative, so the sum is positive if and only if at least one compatible pair has positive probability. That is exactly the stated support condition. \(\square\)

The theorem applies whether the spans are equal or unequal, but lattice coordinates often make the support condition much easier to check. When the ratio of the spans is rational, the two lattices can be expressed using a common spacing.

Theorem: Suppose \(X=\alpha+hI\) and \(Y=\beta+kJ\) almost surely, with \(I,J\) integer-valued, and suppose \(h/k\) is rational. There are a \(d>0\) and relatively prime positive integers \(m,n\) such that \(h=dm\) and \(k=dn\). For \(S=X+Y\), every support point has the form \(s=\alpha+\beta+du\) for an integer \(u\). Its probability is \[ P(S=\alpha+\beta+du) =\sum_{\substack{i\in\operatorname{supp}(I)\\u-mi\in n\operatorname{supp}(J)}} p_I(i)\,p_J\!\left(\frac{u-mi}{n}\right), \] where \(n\operatorname{supp}(J)=\{nj:j\in\operatorname{supp}(J)\}\). The support consists exactly of those such points for which the sum has at least one term.

Proof. Write the positive rational ratio \(h/k\) as \(m/n\) with relatively prime positive integers \(m,n\), and set \(d=h/m=k/n\). For indices \(i,j\), the corresponding sum is

(\alpha+hi)+(\beta+kj)=\alpha+\beta+d(mi+nj).

Consequently, a sum can occur only at \(\alpha+\beta+du\) for an integer \(u=mi+nj\). For a fixed \(u\), an index \(i\) is compatible precisely when \(u-mi=nj\) for some \(j\in\operatorname{supp}(J)\). In that case the matching index is uniquely \(j=(u-mi)/n\). Substituting these compatible pairs into the discrete convolution formula gives the displayed probability. A sum has positive probability exactly when at least one such pair has positive mass, proving the support statement. \(\square\)

The integer equation is the key: a point on the common grid is not necessarily attainable. Even when it has integer solutions, index restrictions such as nonnegative indices or gaps in either support can rule out some or all of them. When several index pairs do work, all their probability products must be added.

Worked Example: Geometric Lattices With Different Spans

Let \(I\) and \(J\) be independent, with \(P(I=i)=\frac12(\frac12)^i\) and \(P(J=j)=\frac34(\frac14)^j\) for \(i,j=0,1,2,\ldots\). Set \(X=4I\) and \(Y=6J\). Find whether 2 is attainable and calculate \(P(X+Y=12)\).

The spans are 4 and 6, with common spacing \(d=2\): \(4=2(2)\) and \(6=2(3)\). Thus \(X+Y=2(2I+3J)\). For the value 2, the index equation is \(2i+3j=1\). Its left side is either zero or at least 2, so it has no nonnegative integer solutions. Therefore \(P(X+Y=2)=0\), even though 2 lies on the common grid.

For the value 12, solve \(2i+3j=6\) with \(i,j\geq0\). If \(j=0\), then \(i=3\), giving one pair. If \(j=1\), then \(2i=3\), which has no integer solution. If \(j=2\), then \(i=0\); larger \(j\) would make \(3j>6\). The only pairs are therefore \((3,0)\) and \((0,2)\). Independence gives

\begin{aligned} P(X+Y=12) &=P(I=3)P(J=0)+P(I=0)P(J=2)\\ &=\left(\frac12\left(\frac12\right)^3\right)\left(\frac34\right) +\left(\frac12\right)\left(\frac34\left(\frac14\right)^2\right)\\ &=\frac{3}{64}+\frac{3}{128} =\frac{9}{128}. \end{aligned}

The two representations contribute separate masses; using only one would undercount the probability.

Offsets and Support Restrictions

Offsets shift the common grid but do not remove the need to solve the integer equation. The sum lies on the grid \(\alpha+\beta+d\mathbb{Z}\) when the spans are commensurable, yet its support may be a proper subset of that grid. Finite supports and restricted index sets make this especially visible.

Worked Example: An Offset Grid With an Unattainable Point

Let \(I\) and \(J\) be independent Bernoulli random variables with \(P(I=1)=1/3\) and \(P(J=1)=1/2\). Define \(X=1+4I\) and \(Y=2+6J\). Find the support and mass function of \(S=X+Y\).

Here \(S=3+4I+6J=3+2(2I+3J)\). The four possible index pairs give:

\((I,J)=(0,0)\): \(S=3\), with probability \((2/3)(1/2)=1/3\).
\((I,J)=(1,0)\): \(S=7\), with probability \((1/3)(1/2)=1/6\).
\((I,J)=(0,1)\): \(S=9\), with probability \((2/3)(1/2)=1/3\).
\((I,J)=(1,1)\): \(S=13\), with probability \((1/3)(1/2)=1/6\).

Thus the support is \(\{3,7,9,13\}\). The masses add to \(1/3+1/6+1/3+1/6=1\), as required. The common grid is \(3+2\mathbb{Z}\), but the point 5 is not attainable: it would require \(2I+3J=1\), which has no solution with \(I,J\in\{0,1\}\). The offsets determine the location of the grid, while the index equation determines which of its points actually occur.

When the Span Ratio Is Irrational

If \(h/k\) is irrational, there is no positive common spacing \(d\) and pair of integers \(m,n\) with \(h=dm\) and \(k=dn\). A sum is still formed by adding support points, and the discrete convolution formula still applies. Moreover, two distinct index pairs cannot yield the same sum: if \(hi+kj=hi'+kj'\), then \(h(i-i')=-k(j-j')\). Unless both differences are zero, this equality would make \(h/k\) rational. Thus every attainable sum has a unique representation when the ratio is irrational.

Worked Example: Irrational Spans Give Distinct Sums

Let \(I\) and \(J\) be independent Bernoulli random variables with \(P(I=1)=1/3\) and \(P(J=1)=2/5\). Set \(X=\sqrt{2}I\), \(Y=J\), and \(S=X+Y\). The ratio of the spans, \(\sqrt{2}/1\), is irrational. The four pairs produce the four distinct values below:

\((0,0)\) gives \(S=0\), with probability \((2/3)(3/5)=2/5\).
\((1,0)\) gives \(S=\sqrt{2}\), with probability \((1/3)(3/5)=1/5\).
\((0,1)\) gives \(S=1\), with probability \((2/3)(2/5)=4/15\).
\((1,1)\) gives \(S=1+\sqrt{2}\), with probability \((1/3)(2/5)=2/15\).

These values are distinct: an equality between two of them would imply that \(\sqrt{2}\) is rational. Hence each mass comes from exactly one pair. Their total is \(2/5+1/5+4/15+2/15=1\). In this example the sum support is not contained in any single lattice \(a+g\mathbb{Z}\) with \(g>0\), since the differences between support points include both 1 and \(\sqrt{2}\), whose ratio is irrational.

Common Mistakes and Why the Support Analysis Matters

A common mistake is to identify a common containing lattice and then treat every point on it as possible. In the first example, the common grid has spacing 2, but 2 itself has probability zero because the necessary equation has no nonnegative integer solution. The correction is to solve the support-matching equation, not just check grid membership.

Another error is to count only one representation of a sum. At 12 in the geometric example, both \((I,J)=(3,0)\) and \((0,2)\) produce the sum, so both products appear in the convolution. Conversely, when the span ratio is irrational, the uniqueness argument shows that no two distinct integer-index pairs collide. The appropriate calculation therefore depends on the relationship between the spans and on the actual index sets.

This support-first method prevents assigning positive mass to impossible values and prevents losing mass at collisions. It also gives a practical sequence for calculation:

Write each support in indexed form.
Record its offset, span, and allowed integer indices, including any restrictions such as nonnegativity.

Choose the appropriate support equation.
For rational span ratios, use the common spacing and solve \(mi+nj=u\). For an irrational ratio, distinct index pairs cannot collide.

Add the masses of all compatible pairs.
Use independence to multiply the two point masses for each pair, then sum those products.

Check Your Understanding

Use support matching before calculating any probability.

If \(X=5I\) and \(Y=8J\) for nonnegative integer-valued \(I,J\), what is a common spacing for the sum lattice, and what integer equation determines whether a proposed point is attainable?
Suppose \(X\) takes values 0 and 6 while \(Y\) takes values 0 and 10. List the four index-pair sums and identify any repeated value.
For offsets \(\alpha,\beta\) and spans \(h=dm\), \(k=dn\), explain why every sum lies on \(\alpha+\beta+d\mathbb{Z}\), but not necessarily at every point of that grid.
Why must all compatible pairs be included when computing a mass under the discrete convolution formula?
If two lattice spans have an irrational ratio, why can distinct integer-index pairs not produce the same sum?