Threshold Selection for Markov Bounds

Choosing a Markov Bound for a Tail Event

A Markov bound depends on more than the random variable: it depends on the nonnegative quantity to which the inequality is applied and on the threshold that quantity must exceed. For a specified tail event, several choices may be available. One moment can give the best bound at one tail threshold and a different moment can be better at another. A shifted or otherwise transformed random variable can also produce a useful comparison.

The aim is to compare valid bounds for the same event, not to assume that the highest available moment must be best. The resulting bound is guaranteed to be an upper bound, but it need not equal the tail probability or be the best bound obtainable from all information about the distribution.

Threshold comparison: If \(X\geq 0\), \(0<E[X^r]<\infty\), and \(x>0\), then for any \(r>0\), \(P(X\geq x)\leq E[X^r]/x^r\). When several such moments are available, calculate each bound at the specified \(x\) and use the smallest one. This selects the best bound among those candidates; it does not establish that the bound is optimal among all possible methods.

The inequality follows by comparing the event indicator with a nonnegative power of \(X\). More generally, if \(Y\geq 0\), \(c>0\), and an event \(A\) implies \(Y\geq c\), then \(1_A\leq Y/c\) pointwise. Taking expectations gives \(P(A)\leq E[Y]/c\), provided \(E[Y]\) is finite. The practical question is which \(Y\) and \(c\) give a useful comparison.

Compare Moment Orders at the Actual Tail Threshold

For a nonnegative \(X\), a moment of order \(r\) gives the candidate bound \(B_r(x)=E[X^r]/x^r\). Both the moment in the numerator and the tail threshold in the denominator matter. For two available orders \(0<r<s\), suppose their moments \(m_r=E[X^r]\) and \(m_s=E[X^s]\) are finite and positive. The bounds are equal when \(m_r/x^r=m_s/x^s\), or equivalently \(x^{s-r}=m_s/m_r\). Thus their crossover threshold is \(x_*=(m_s/m_r)^{1/(s-r)}\). Below or above this crossover, either order may be preferable; direct comparison determines which.

Worked Example: Two Moments and a Crossover Threshold

Let \(X=5\) with probability \(0.4\) and \(X=0\) with probability \(0.6\). Then \(E[X]=0.4(5)+0.6(0)=2\) and \(E[X^2]=0.4(25)+0.6(0)=10\). Compare the first- and second-moment bounds for \(P(X\geq x)\).

For \(x=4\), the first-moment bound is \(2/4=0.5\). The second-moment bound is \(10/4^2=10/16=0.625\). The first moment gives the smaller bound. In fact, \(P(X\geq4)=0.4\), so the first-moment bound is valid and the second-moment bound is also valid, though looser.

For \(x=6\), the first-moment bound is \(2/6=1/3\), while the second-moment bound is \(10/36=5/18\). Now the second moment gives the smaller bound. The actual tail probability is zero, since \(X\) never exceeds 5; neither positive bound captures that fact.

The crossover calculation gives \(x_*=10/2=5\). At \(x=5\), both bounds equal \(0.4\), which is also \(P(X\geq5)\). This example shows why moment order should be chosen for the threshold in the event, rather than chosen once and used automatically for every tail.

Shift the Threshold With a Positive-Part Moment

A further choice is to shift the random variable before applying Markov's inequality. For a real number \(a\), write \((X-a)_+=\max(X-a,0)\). If \(a<x\), then on \(X\geq x\), \((X-a)_+\geq x-a\). Consequently, for any \(r>0\) with \(E[(X-a)_+^r]<\infty\),

P(X\geq x)\leq \frac{E[(X-a)_+^r]}{(x-a)^r}.

This is a valid candidate for each \(a<x\); selecting \(a\) means comparing the resulting bounds. The shifted moment must actually be available or computable. It cannot be replaced by an assumed value based only on an unshifted moment.

Worked Example: Optimizing a Shift for a Uniform Tail

Let \(X\sim\operatorname{Uniform}(0,1)\), and bound \(P(X\geq0.8)\) using the first positive-part moment. For any \(a<0.8\), the candidate bound is \(b(a)=E[(X-a)_+]/(0.8-a)\).

If \(a\leq0\), then \(X-a\geq0\) everywhere and \(E[(X-a)_+]=E[X]-a=0.5-a\). Therefore \(b(a)=(0.5-a)/(0.8-a)\). Its derivative is \(-0.3/(0.8-a)^2<0\), so among \(a\leq0\) this bound is smallest at \(a=0\), where it is \(0.5/0.8=0.625\).

For \(0\leq a<0.8\), use the uniform density, which is 1 on \((0,1)\): \(E[(X-a)_+]=\int_a^1(x-a)\,dx=(1-a)^2/2\). Hence \(b(a)=(1-a)^2/[2(0.8-a)]\). Differentiating gives \(b'(a)=(a-0.6)/[(1-a)(0.8-a)]\). The denominator is positive on this interval, so the bound decreases until \(a=0.6\) and increases after that. Its minimum is \(b(0.6)=0.4^2/[2(0.2)]=0.4\), better than the unshifted first-moment bound of \(0.625\).

The actual tail probability is \(P(X\geq0.8)=0.2\), from the interval length \(1-0.8\). Thus the optimized shifted bound is valid but not exact. It improves the candidate bound by using the location of the tail threshold while still leaving a gap to the true probability.

Shifted-threshold result: If \(X\) is real-valued, \(a<x\), \(r>0\), and \(E[(X-a)_+^r]<\infty\), then \(P(X\geq x)\leq E[(X-a)_+^r]/(x-a)^r\). Indeed, on \(X\geq x\), the quantity \((X-a)_+^r\) is at least \((x-a)^r\). Thus the event indicator satisfies

1_{\{X\geq x\}}\leq \frac{(X-a)_+^r}{(x-a)^r}.

Both sides are measurable and nonnegative, so taking expectations proves the result. \(\square\)

Transformations Can Make a Tail Bound More Useful

For a count-valued random variable, a useful nonnegative transformation may reflect the event threshold more closely than a raw power does. Consider the falling factorial \((k)_j=k(k-1)\cdots(k-j+1)\) for a nonnegative integer \(k\) and a positive integer \(j\). When \(k\geq j\), this is nonnegative and increases as the integer \(k\) increases. So on the event \(X\geq m\), for integers \(m\geq j\), \((X)_j\geq(m)_j\). If its expectation is finite, the event-indicator argument yields a bound using \(E[(X)_j]/(m)_j\).

Worked Example: Choosing a Factorial Moment for a Poisson Tail

Let \(X\sim\operatorname{Poisson}(2)\), and consider \(P(X\geq5)\). For an integer \(j\) between 1 and 5, the event implies \((X)_j\geq(5)_j\), so \(P(X\geq5)\leq E[(X)_j]/(5)_j\). The factorial moment can be computed directly:

E[(X)_j] =\sum_{k=j}^{\infty}\frac{k!}{(k-j)!}e^{-2}\frac{2^k}{k!} =2^j e^{-2}\sum_{\ell=0}^{\infty}\frac{2^\ell}{\ell!} =2^j.

For \(j=1\), the bound is \(2/5=0.4\). For \(j=2\), it is \(4/(5\cdot4)=0.2\). For \(j=3\), it is \(8/(5\cdot4\cdot3)=8/60=2/15\), approximately \(0.1333\). For \(j=4\), it is \(16/(5\cdot4\cdot3\cdot2)=16/120=2/15\). For \(j=5\), it is \(32/(5\cdot4\cdot3\cdot2\cdot1)=32/120=4/15\), approximately \(0.2667\). Among these candidates, orders 3 and 4 give the smallest bound.

The true probability can be checked from the Poisson probabilities: \(P(X\geq5)=1-P(X\leq4)=1-7e^{-2}\), approximately \(0.0527\). The selected bound \(2/15\) is larger, as required. The fifth factorial moment is available but gives a worse bound than the third or fourth; availability alone does not make an order preferable.

Common Mistakes and a Practical Selection Rule

A frequent mistake is to reason that higher moments always give tighter tail bounds. The Poisson calculation shows why that reasoning fails: increasing the order also changes the moment numerator and the event threshold denominator, and their ratio can increase. Another mistake is to choose a shift without checking the relevant positive-part moment. A shift is useful only when the bound it produces is valid and its numerator is known.

Keep the event fixed while comparing candidates. For each proposed moment order, shift, or transformation, verify that the event forces the transformed quantity to exceed the proposed cutoff. Then compute the expectation, divide by that cutoff, and compare the numerical bounds. A smaller bound is more informative among the candidates, but it is not proof that the actual tail probability is close to the bound.

State the tail event.
Record the event and its cutoff, including whether the variable is nonnegative or integer-valued.

List valid candidates.
Check which moments or transformed expectations are finite and which thresholds the event guarantees.

Calculate and compare.
Evaluate each upper bound for the specified event and retain the smallest valid candidate, while distinguishing it from the unknown true tail probability.

Check Your Understanding

For each question, justify the comparison using the event threshold and the candidate bound.

If \(E[X]=3\) and \(E[X^2]=15\) for a nonnegative random variable, compare the two moment bounds for \(P(X\geq4)\). Which is smaller?
For moments of orders \(r<s\), explain how the crossover threshold depends on the two moment values.
For the shifted bound, why must the shift \(a\) be strictly less than the event cutoff \(x\)?
In the Poisson example, why does the fifth factorial moment give a weaker candidate than the third?
Does selecting the smallest of several valid Markov bounds prove that the selected bound is the best possible upper bound from all distributional information? Explain.