Closure Rules for Sub-Gaussian Sums and Scaling

Why Closure Rules Matter

A useful concentration bound for one random variable becomes more useful when it can be carried through transformations and sums. Scaling changes the size of fluctuations, while adding independent variables combines their fluctuations. Sub-Gaussian variance proxies give a simple way to track both changes and then obtain an explicit tail bound for the sum.

The word proxy matters: a sub-Gaussian variance proxy is a parameter in an exponential-moment bound, and need not equal the variable's actual variance. We use the moment-generating-function definition below. It immediately supports the closure arguments needed here.

Definition and Basic Interpretation

Definition: A random variable $X$ with finite mean is sub-Gaussian with variance proxy $v$, where $v\geq 0$, if its moment-generating function satisfies $$ E\!\left[\exp\{\lambda(X-E[X])\}\right]\leq \exp\!\left(\frac{v\lambda^2}{2}\right) \quad\text{for every }\lambda\in\mathbb{R}. $$ The centered variable $X-E[X]$ is then called sub-Gaussian with proxy $v$. A variable may satisfy this inequality for more than one value of $v$; the smallest admissible value, when it exists, is its optimal variance proxy.

The centering is essential: the inequality controls fluctuations about $E[X]$, not the location of the distribution. The proxy $v$ has the units of a variance. It is not generally the variance itself, though in familiar cases such as a normal distribution the optimal proxy equals the variance.

Worked Example: Scaling and Translating a Normal Variable

Let $X\sim N(0,4)$, and define $Y=-3X+2$. Find a variance proxy for $Y$, and check it using the moment-generating function.

For $X\sim N(0,4)$, $E[X]=0$ and $E[e^{\lambda X}]=e^{4\lambda^2/2}$. Thus $X$ is sub-Gaussian with proxy $4$. The transformed variable has mean $E[Y]=-3E[X]+2=2$, so $Y-E[Y]=-3X$. Therefore $$ E[e^{\lambda(Y-E[Y])}] =E[e^{-3\lambda X}] =\exp\!\left(\frac{4(-3\lambda)^2}{2}\right) =\exp\!\left(\frac{36\lambda^2}{2}\right). $$ So $36$ is a proxy for $Y$. In fact $Y\sim N(2,36)$, whose variance is $36$, and its optimal proxy is $36$. The additive constant changes the mean but not the proxy; the factor $-3$ multiplies the proxy by $(-3)^2=9$.

Scaling and Translation

Theorem: If $X$ is sub-Gaussian with proxy $v$, and $a,b\in\mathbb{R}$, then $aX+b$ is sub-Gaussian with proxy $a^2v$.

To prove the claim, first compute the centered transform: $$ (aX+b)-E[aX+b]=a(X-E[X]). $$ For any $\lambda\in\mathbb{R}$, apply the defining inequality for $X$ with argument $a\lambda$: $$ E\!\left[e^{\lambda((aX+b)-E[aX+b])}\right] =E\!\left[e^{(a\lambda)(X-E[X])}\right] \leq \exp\!\left(\frac{v(a\lambda)^2}{2}\right) =\exp\!\left(\frac{a^2v\lambda^2}{2}\right). $$ This is the required bound. It also covers $a=0$: the transformed variable is constant, its centered transform is $1$, and proxy $0$ works. The translation $b$ disappears on centering, while a negative scaling is valid because the defining inequality holds for every real argument. $\square$

In particular, if $X$ has proxy $v$, then $c(X-E[X])$ has proxy $c^2v$. For a weighted sum, this rule explains why the square of each weight will appear in the resulting proxy.

Worked Example: A Weighted Sum of Rademacher Variables

Let $\varepsilon_1,\varepsilon_2$ be independent, each taking values $1$ and $-1$ with probability $1/2$. Find a proxy for $S=2\varepsilon_1-\varepsilon_2$, and give its two-sided tail bound at $t=3$.

For either Rademacher variable, $E[\varepsilon_i]=0$ and $$ E[e^{\lambda\varepsilon_i}] =\frac{e^\lambda+e^{-\lambda}}{2} =\cosh(\lambda) \leq e^{\lambda^2/2}. $$ For completeness, $\log\cosh(\lambda)\leq\lambda^2/2$: the difference $g(\lambda)=\lambda^2/2-\log\cosh(\lambda)$ is even, satisfies $g(0)=g'(0)=0$, and has $g''(\lambda)=\tanh^2(\lambda)\geq0$. Hence $g(\lambda)\geq0$. Each $\varepsilon_i$ therefore has proxy $1$.

Scaling gives proxy $2^2=4$ for $2\varepsilon_1$, and proxy $(-1)^2=1$ for $-\varepsilon_2$. Independence allows the proxies to add, so $S$ has proxy $5$. The concentration inequality proved below gives $$ P(|S|\geq3)\leq 2\exp\!\left(-\frac{3^2}{2(5)}\right) =2e^{-9/10}. $$ This is a valid upper bound; it need not equal the exact tail probability.

Adding Independent Variables

Theorem: Let $X_1,\ldots,X_n$ be independent random variables, each with finite mean, and suppose $X_i$ is sub-Gaussian with proxy $v_i\geq0$. Then $\sum_{i=1}^n X_i$ is sub-Gaussian with proxy $\sum_{i=1}^n v_i$.

Independence gives both the centering identity and factorization of the moment-generating function: $$ \sum_{i=1}^n X_i-E\!\left[\sum_{i=1}^n X_i\right] =\sum_{i=1}^n(X_i-E[X_i]), $$ and, for every real $\lambda$, $$ E\!\left[\exp\!\left\{\lambda\sum_{i=1}^n(X_i-E[X_i])\right\}\right] =\prod_{i=1}^n E[e^{\lambda(X_i-E[X_i])}]. $$ Applying each defining bound to its factor yields $$ \prod_{i=1}^n E[e^{\lambda(X_i-E[X_i])}] \leq \prod_{i=1}^n e^{v_i\lambda^2/2} =\exp\!\left(\frac{\lambda^2}{2}\sum_{i=1}^n v_i\right). $$ This is precisely the sub-Gaussian bound for the centered sum with proxy $\sum_i v_i$. $\square$

More generally, if $a_1,\ldots,a_n$ are fixed real numbers, the scaling theorem shows that $a_iX_i$ has proxy $a_i^2v_i$. The independent-sum theorem then gives proxy $\sum_i a_i^2v_i$ for $\sum_i a_iX_i$.

Worked Example: Summing Independent Normal Variables

Suppose $X_1\sim N(1,4)$ and $X_2\sim N(-2,9)$ are independent. Find a proxy for $T=X_1+X_2$, and bound $P(|T-E[T]|\geq5)$.

A normal variable with variance $\sigma^2$ has centered moment-generating function $e^{\sigma^2\lambda^2/2}$, so the proxies for $X_1$ and $X_2$ are $4$ and $9$. Independence gives $T$ proxy $4+9=13$. Its mean is $1+(-2)=-1$. Consequently, $$ P(|T+1|\geq5) \leq 2\exp\!\left(-\frac{5^2}{2(13)}\right) =2e^{-25/26}. $$ Numerically, this bound is about $0.765$, and in particular it is less than $0.766$. Since $T\sim N(-1,13)$, the proxy here equals the actual variance. The exponential bound is convenient, but can be looser than a calculation using the exact normal distribution.

Concentration for the Sum

Theorem: Under the hypotheses of the independent-sum theorem, let $S=\sum_{i=1}^n X_i$ and $V=\sum_{i=1}^n v_i$. For every $t>0$, $$ P(|S-E[S]|\geq t)\leq 2\exp\!\left(-\frac{t^2}{2V}\right) $$ when $V>0$. For $V=0$, $S=E[S]$ almost surely, so the probability on the left is zero.

For the upper tail, take any $\lambda>0$. On the event $S-E[S]\geq t$, the nonnegative random variable $e^{\lambda(S-E[S])}$ is at least $e^{\lambda t}$. Markov's inequality and the proxy bound therefore give $$ P(S-E[S]\geq t) \leq e^{-\lambda t}E[e^{\lambda(S-E[S])}] \leq \exp\!\left(-\lambda t+\frac{V\lambda^2}{2}\right). $$ For $V>0$, the exponent is minimized over $\lambda>0$ at $\lambda=t/V$. Substituting this value gives $$ P(S-E[S]\geq t)\leq \exp\!\left(-\frac{t^2}{2V}\right). $$ Apply the same argument to $-(S-E[S])$, which has the same proxy $V$, to obtain the identical bound for $P(S-E[S]\leq-t)$. The event $\{|S-E[S]|\geq t\}$ is the union of these two tail events. The union bound completes the proof. If $V=0$, each $v_i=0$, and its centered variable has zero proxy; the MGF bound for all real $\lambda$ implies it is zero almost surely. Thus the centered sum is zero almost surely as claimed. $\square$

For the weighted sum $S=\sum_i a_iX_i$, the same result yields $$ P\!\left(\left|S-E[S]\right|\geq t\right) \leq 2\exp\!\left(-\frac{t^2}{2\sum_{i=1}^n a_i^2v_i}\right), $$ provided the denominator is positive. This follows by using the weighted proxy $\sum_i a_i^2v_i$, not by treating the weights as if they were unsquared.

Common Pitfall: Adding Proxies Without Independence

The independent-sum proof uses factorization of the joint moment-generating function. Without independence, the step $$ E[e^{\lambda(X_1-E[X_1])}e^{\lambda(X_2-E[X_2])}] =E[e^{\lambda(X_1-E[X_1])}]E[e^{\lambda(X_2-E[X_2])}] $$ is not generally valid. Thus the conclusion that the sum has proxy $v_1+v_2$ cannot be asserted from the two individual proxy bounds alone.

For example, let $X_1=X_2=\varepsilon$, where $\varepsilon$ is Rademacher. Each variable has proxy $1$, but $X_1+X_2=2\varepsilon$ has proxy $4$, not $2$: its centered MGF is $\cosh(2\lambda)$, whose quadratic behavior near zero is that of variance $4$. The variables are perfectly dependent. By contrast, when they are independent the factorization proof justifies adding their proxies.

Key takeaway: Scaling by $a$ changes a sub-Gaussian proxy $v$ to $a^2v$; translating does not change it. For independent variables, proxies add. Optimizing the exponential Markov bound then gives a two-sided tail that decays as $\exp(-t^2/(2V))$, where $V$ is the sum of the proxies.

Check Your Understanding

Try these questions using the definitions and closure rules above.

If $X$ has proxy $7$, what proxy is guaranteed for $5X-3$? Explain why the constant $-3$ does not enter the answer.
Independent centered variables $X_1,X_2,X_3$ have proxies $1,4,9$. What proxy is guaranteed for $2X_1-X_2+3X_3$?
For an independent sum with total proxy $V=8$, write the bound for the probability that its centered value is at least $t>0$.
Which step in the independent-sum proof may fail when the summands are dependent?
Why does a variance proxy not always have to equal the actual variance?