Tail Bounds from Shifted and Truncated Nonnegative Functions

Designing a Function for a Tail Event

Markov’s inequality turns the expectation of a nonnegative random variable into a bound on the probability that it is large. A useful way to apply it is to design the nonnegative random variable specifically for the event of interest. For a tail event, shifting the variable can remove values that contribute little to that event, and truncating the shifted variable can prevent very large values from dominating its expectation.

The basic principle does not require a particular distribution. It requires a measurable nonnegative function that is bounded below by a positive constant whenever the target event occurs.

Theorem: Let $A$ be an event, let $g(X)$ be a measurable nonnegative random variable, and suppose $g(X)\ge c$ on $A$, where $c>0$. If $E[g(X)]<\infty$, then $$ P(A)\le \frac{E[g(X)]}{c}. $$

Proof. The event condition gives the pointwise inequality $c\,1_A\le g(X)$, where $1_A$ is 1 on $A$ and 0 otherwise. Taking expectations preserves the inequality: $$ cP(A)=E[c\,1_A]\le E[g(X)]. $$ Dividing by $c>0$ proves the result. $\square$

Ordinary Markov’s inequality uses $g(X)=X$ for nonnegative $X$. The general form makes the design choice explicit: the function need only be large on the event being bounded; its values away from that event may be chosen to keep its expectation small.

Shifted and Truncated Upper-Tail Bounds

For a real number $u$, define its positive part by $u_+=\max(u,0)$. Fix a threshold $t$ and a shift $a<t$. If $X\ge t$, then $(X-a)_+\ge t-a$. The general theorem therefore gives a shifted upper-tail bound. A second choice caps the function at the threshold’s shifted height.

Theorem: Let $X$ be a real-valued random variable, and let $a<t$. If $E[(X-a)_+]<\infty$, then $$ P(X\ge t)\le \frac{E[(X-a)_+]}{t-a}. $$ Moreover, the truncated version always has a finite expectation and satisfies $$ P(X\ge t)\le \frac{E[\min\{(X-a)_+,\,t-a\}]}{t-a}. $$

Proof. On $\{X\ge t\}$, the positive part $(X-a)_+$ is at least $t-a$. Thus $$ (t-a)1_{\{X\ge t\}}\le (X-a)_+. $$ Taking expectations and dividing by $t-a>0$ proves the first bound. For the second, define $g(X)=\min\{(X-a)_+,t-a\}$. On the target event, $(X-a)_+\ge t-a$, so $g(X)=t-a$. Therefore $$ (t-a)1_{\{X\ge t\}}\le \min\{(X-a)_+,t-a\}. $$ This function is nonnegative and bounded by $t-a$, so its expectation is finite. Taking expectations proves the truncated bound. $\square$

The untruncated bound needs a finite positive-part expectation; the truncated bound does not, because its function is bounded. Also, the shift $a$ need not be a lower bound for $X$: the positive part makes the function nonnegative even when $X<a$. If $X\ge a$ almost surely, then $(X-a)_+=X-a$, giving the familiar shifted form $P(X\ge t)\le E[X-a]/(t-a)$.

Worked Example: Clipping Large Values in a Discrete Tail

Let $X$ take the values 0, 2, and 10 with probabilities 0.6, 0.3, and 0.1, respectively. Find bounds for $P(X\ge5)$ using ordinary Markov, then using shifted and truncated functions.

The exact probability is $P(X\ge5)=0.1$. The mean is $$ E[X]=0(0.6)+2(0.3)+10(0.1)=1.6. $$ Ordinary Markov gives $P(X\ge5)\le1.6/5=0.32$.

Now choose $a=0$ and truncate at $t=5$. The function $\min(X,5)$ takes values 0, 2, and 5 at the three support points, so $$ E[\min(X,5)]=0(0.6)+2(0.3)+5(0.1)=1.1. $$ Consequently $P(X\ge5)\le1.1/5=0.22$, an improvement over the ordinary Markov bound.

Choose instead $a=2$. The truncated function $\min\{(X-2)_+,3\}$ takes values 0, 0, and 3. Its expectation is $0.3$, and the bound is $0.3/3=0.1$, which equals the exact tail probability. Here the choice of shift makes the function vanish at both values below the threshold, while the cap makes its value constant at the value 10 above the threshold.

Truncation cannot increase the expectation relative to the corresponding untruncated positive part. It can therefore sharpen the bound when the relevant expectations are available. But a smaller function expectation is not automatically known just because $E[X]$ is known: calculating or bounding the truncated expectation may require additional information about the distribution.

Using Support Information

Support restrictions often suggest a useful shift. If $X\ge a$ almost surely, subtracting $a$ makes the variable nonnegative and measures distance above its lower support bound. For a lower-tail event, an almost-sure upper bound $X\le b$ suggests measuring distance below $b$.

Worked Example: A Uniform Variable With a Known Lower Bound

Suppose $X$ has the uniform distribution on $[2,8]$, and the target event is $X\ge6$. The exact probability is the length of the interval $[6,8]$ divided by the total interval length: $$ P(X\ge6)=\frac{8-6}{8-2}=\frac13. $$

The variable satisfies $X\ge2$ almost surely. Since $E[X]=(2+8)/2=5$, the shifted Markov bound is $$ P(X\ge6)\le\frac{E[X-2]}{6-2}=\frac{5-2}{4}=\frac34. $$ For the truncated version, $X-2$ is uniform on $[0,6]$, so $$ E[\min(X-2,4)] =\frac{1}{6}\left(\int_0^4 y\,dy+\int_4^6 4\,dy\right) =\frac{1}{6}(8+8)=\frac83. $$ Thus $P(X\ge6)\le(8/3)/4=2/3$. This is sharper than $3/4$, though still above the exact probability $1/3$.

The same idea gives a lower-tail bound. If $X\le b$ almost surely and $t<b$, then on $\{X\le t\}$, $b-X\ge b-t$. The shifted function $b-X$ is nonnegative under the support assumption. Capping it at $b-t$ gives a bounded alternative.

Theorem: Suppose $X\le b$ almost surely and $t<b$. Then $$ P(X\le t)\le\frac{E[b-X]}{b-t} $$ whenever the expectation is finite. The truncated bound is $$ P(X\le t)\le \frac{E[\min\{(b-X)_+,\,b-t\}]}{b-t}. $$

Justification. On $\{X\le t\}$, the support condition gives $b-X\ge b-t>0$. Hence $$ (b-t)1_{\{X\le t\}}\le b-X $$ and also $$ (b-t)1_{\{X\le t\}}\le\min\{(b-X)_+,b-t\}. $$ Taking expectations and dividing by $b-t$ yields the two bounds. The truncated function is bounded and nonnegative, so its expectation is finite. $\square$

Worked Example: A Lower Tail With an Upper Support Bound

Let $X$ take values 1, 4, 6, and 8 with probabilities 0.2, 0.3, 0.3, and 0.2. Its upper support bound is $b=8$. Bound $P(X\le5)$, whose exact value is $0.2+0.3=0.5$.

For the shifted bound, the expectation of the distance below 8 is $$ E[8-X]=7(0.2)+4(0.3)+2(0.3)+0(0.2)=3.2. $$ Since $b-t=8-5=3$, the shifted bound is $P(X\le5)\le3.2/3$. A probability cannot exceed 1, so this gives only the trivial bound 1.

For the truncated function $\min\{(8-X)_+,3\}$, the values at $X=1,4,6,8$ are 3, 3, 2, and 0. Therefore $$ E[\min\{(8-X)_+,3\}]=3(0.2)+3(0.3)+2(0.3)+0(0.2)=2.1. $$ The resulting bound is $P(X\le5)\le2.1/3=0.7$. It is nontrivial, although not as sharp as the exact probability $0.5$.

Choosing and Interpreting the Bound

A useful function is one that is small on much of the distribution but has a known positive lower bound on the target event. Shifting can suppress contributions from values on the uninteresting side of a threshold; truncating can suppress contributions from values far beyond it. For a lower tail, the same design can be applied to distance from an upper support bound. No independence assumption is involved: these are bounds for a single random variable.

The choice of shift and cap matters. A shift close to the threshold may make the target-event lower bound small, while a shift far below it may leave more irrelevant values contributing to the expectation. The resulting bound should be compared with 1, since any upper bound greater than 1 can be replaced by the trivial probability bound 1. The best choice depends on what is known about the distribution, not on a universal rule to shift or truncate as much as possible.

Common Mistake

Assuming a shift automatically improves a numerical bound. The shifted or truncated inequality is valid, but its usefulness depends on whether the corresponding expectation is smaller and can be evaluated or bounded. Knowing only $E[X]$ does not in general provide the value of $E[\min\{(X-a)_+,t-a\}]$.
Using a signed shift without checking nonnegativity. Markov’s inequality applies to nonnegative variables. Use $(X-a)_+$ if $X$ may fall below $a$, or verify that $X\ge a$ almost surely before replacing it by $X-a$.
Forgetting the cap height. On $X\ge t$, the capped function must reach its cap. For the upper-tail construction the cap is $t-a$; for the lower-tail construction it is $b-t$.

Key takeaway: To bound an event, construct a nonnegative function that is at least a known positive constant on that event, then divide its expectation by that constant. Shifts use threshold distance; truncation prevents values beyond the threshold from inflating the expectation.

Check Your Understanding

For each question, identify the function that would be useful before calculating its expectation.

If $X\ge a$ almost surely and $t>a$, write the shifted Markov bound for $P(X\ge t)$.
Why does $\min\{(X-a)_+,t-a\}$ equal $t-a$ whenever $X\ge t$?
Suppose $X\le b$ almost surely. Which shifted quantity can be used to bound $P(X\le t)$ for $t<b$?
In the discrete example with values 0, 2, and 10, why is the shift $a=2$ still valid even though $X$ can be below 2?
Does knowing only $E[X]$ necessarily determine the expectation of a truncated function of $X$? Explain.