Conditional Markov and Chernoff Bounds

Why Condition Before Bounding a Tail?

A random variable can have different tail behavior in different settings. For example, a count may be Poisson with a rate that varies across groups, or a sum of Bernoulli variables may have a success probability determined by an unobserved environment. A single unconditional bound can conceal this structure. If an auxiliary variable $Z$ is observed, or is useful for describing the model, we can first bound the tail conditional on $Z$, then average those conditional bounds.

The key bookkeeping step is the tower property: the probability of an event is the expectation of its conditional probability. Thus, a valid conditional bound can be turned into an unconditional one by taking expectations. The resulting bound need not always be sharper than an unconditional bound, but it can preserve useful variation across the values of the auxiliary variable.

Conditional Markov and Exponential Bounds

Definition: Let $\mathcal G$ be a sigma-field representing the information on which we condition, and let $X$ be a nonnegative random variable. For $a>0$, the conditional Markov inequality is $$ P(X\ge a\mid\mathcal G)\le \frac{E[X\mid\mathcal G]}{a} \quad\text{almost surely}. $$ If $t>0$ and $E[e^{tX}\mid\mathcal G]$ is defined (possibly as an extended nonnegative conditional expectation), the conditional exponential Markov inequality is $$ P(X\ge a\mid\mathcal G)\le e^{-ta}E[e^{tX}\mid\mathcal G] \quad\text{almost surely}. $$

These statements require no independence between $X$ and $\mathcal G$. In applications, $\mathcal G$ is often the information generated by an auxiliary random variable $Z$. Then we write $P(X\ge a\mid Z)$ and $E[X\mid Z]$ as shorthand for conditioning on the sigma-field generated by $Z$.

Theorem: If $X\ge0$, $a>0$, and $E[X]<\infty$, then $$ P(X\ge a)\le E\!\left[\frac{E[X\mid\mathcal G]}{a}\right] =\frac{E[X]}{a}. $$ More generally, if for a fixed $t>0$ the conditional moment-generating function is finite almost surely, then $$ P(X\ge a)\le e^{-ta}E\!\left[E[e^{tX}\mid\mathcal G]\right] =e^{-ta}E[e^{tX}]. $$ The conditional versions are useful because they also give a bound before the final expectation is taken.

Proof. Since $X\ge0$, the indicator satisfies $1_{\{X\ge a\}}\le X/a$. Conditional expectation preserves inequalities, so $$ P(X\ge a\mid\mathcal G) =E[1_{\{X\ge a\}}\mid\mathcal G] \le \frac{E[X\mid\mathcal G]}{a} $$ almost surely. Taking expectations and applying the tower property gives the unconditional statement. For the exponential version, on $\{X\ge a\}$ we have $1\le e^{t(X-a)}$; outside that event the indicator is zero and the exponential is positive. Thus $1_{\{X\ge a\}}\le e^{t(X-a)}$ everywhere. Conditional expectation, followed by ordinary expectation, proves the result. $\square$

The same indicator argument gives the conditional exponential bound directly. When it is useful to choose $t$ after seeing the auxiliary variable, one can apply the inequality within each conditional model. For a finite-valued auxiliary variable, this amounts to applying the fixed-$t$ inequality separately in each stratum; the optimizing value may differ from stratum to stratum.

Worked Examples

Worked Example: A Mixed Poisson Count

Let $\Lambda$ equal 2 or 8 with probability $1/2$ each, and suppose $X\mid\Lambda=\lambda\sim\operatorname{Poisson}(\lambda)$. Bound $P(X\ge12)$ first by conditional Markov and then by a conditional Chernoff bound.

For a Poisson random variable with mean $\lambda$, $E[X\mid\Lambda=\lambda]=\lambda$. Conditional Markov gives $$ P(X\ge12\mid\Lambda=\lambda)\le\frac{\lambda}{12}. $$ The bound is $2/12=1/6$ when $\lambda=2$, and $8/12=2/3$ when $\lambda=8$. Averaging gives $$ P(X\ge12)\le\frac12\left(\frac16+\frac23\right)=\frac{5}{12}\approx0.4167. $$

For $t>0$, the conditional Poisson moment-generating function is $E[e^{tX}\mid\Lambda=\lambda]=\exp\{\lambda(e^t-1)\}$. Therefore $$ P(X\ge12\mid\Lambda=\lambda) \le \exp\{-12t+\lambda(e^t-1)\}. $$ When $\lambda<12$, differentiating the exponent gives $-12+\lambda e^t=0$, so the minimizing value is $t=\log(12/\lambda)>0$. Substitution yields the bound $$ \exp\left\{-12\log(12/\lambda)+12-\lambda\right\}. $$ For $\lambda=2$, this is $\exp(-12\log 6+10)\approx0.00001013$. For $\lambda=8$, it is $\exp(-12\log 1.5+4)\approx0.4207$. Averaging the conditional bounds gives approximately $(0.00001013+0.4207)/2=0.2104$. In this example, optimizing within each rate stratum gives a smaller bound than conditional Markov.

Worked Example: An Exponential Variable With a Random Rate

Let $Z$ equal 1 or 4 with probability $1/2$ each, and suppose $X\mid Z=z$ has an exponential distribution with rate $z$. Bound $P(X\ge2)$ using conditional Markov, and compare the result with the actual probability.

The conditional mean is $E[X\mid Z=z]=1/z$. Thus $$ P(X\ge2\mid Z=z)\le \frac{1}{2z}. $$ The bound is $1/2$ for $z=1$ and $1/8$ for $z=4$, so averaging gives $$ P(X\ge2)\le\frac12\left(\frac12+\frac18\right)=\frac{5}{16}=0.3125. $$

The exponential survival probability at 2 is $e^{-2z}$. Consequently the actual unconditional probability is $$ P(X\ge2)=\frac12(e^{-2}+e^{-8}) \approx\frac12(0.1353353+0.0003355) \approx0.06784. $$ The conditional Markov bound is valid but loose. Conditioning has not made Markov's inequality exact; it has simply produced a bound that respects the two different conditional means.

Worked Example: A Binomial Mixture and Conditional Chernoff Bounds

Let $P$ equal 0.1 or 0.4 with probability $1/2$ each. Conditional on $P=p$, let $S\sim\operatorname{Binomial}(20,p)$. Bound $P(S\ge12)$ using conditional Markov and conditional Chernoff bounds.

Since $E[S\mid P=p]=20p$, conditional Markov gives $P(S\ge12\mid P=p)\le20p/12$. The two bounds are $1/6$ and $2/3$, and their average is $5/12\approx0.4167$.

For $q=12/20=0.6$ and $t>0$, the conditional moment-generating function gives $$ P(S\ge12\mid P=p) \le \exp\{-20qt\}(1-p+pe^t)^{20}. $$ For $p<q$, differentiating the logarithm of the right-hand side gives the minimizing value $e^t=q(1-p)/(p(1-q))$. Substitution gives $\exp\{-20D(q\|p)\}$, where $$ D(q\|p)=q\log\left(\frac{q}{p}\right)+(1-q)\log\left(\frac{1-q}{1-p}\right). $$ When $p=0.1$, $$ D(0.6\|0.1)=0.6\log 6+0.4\log(4/9)\approx0.750684, $$ so the bound is $e^{-20(0.750684)}\approx3.0175\times10^{-7}$, or approximately $0.000000302$. When $p=0.4$, $$ D(0.6\|0.4)=0.6\log(1.5)+0.4\log(2/3)\approx0.081093, $$ giving $e^{-20(0.081093)}\approx0.1976$. The averaged conditional Chernoff bound is therefore approximately $$ \frac12(0.000000302+0.1976)\approx0.0988. $$ It is substantially below the conditional Markov bound for this mixture, though it remains an upper bound rather than the exact tail probability.

How Averaging and Optimization Fit Together

Suppose a conditional argument establishes $P(A\mid\mathcal G)\le B$ almost surely, where $B$ is a nonnegative, $\mathcal G$-measurable random variable. The tower property yields $$ P(A)=E[P(A\mid\mathcal G)]\le E[B]. $$ This is the central step in transferring a conditional tail bound to an unconditional one. If $B$ sometimes exceeds 1, replacing it by $\min(1,B)$ preserves validity and can improve the reported bound.

A Chernoff bound can be optimized separately in different strata when the auxiliary variable takes finitely many values. More generally, conditional bounds can be stated for each fixed $t>0$; one should not silently insert a random, data-dependent $t$ into a fixed-parameter inequality without justifying that step. In models with an explicitly specified conditional distribution, the bound can instead be derived within each conditional model, as in the binomial example.

Common Mistakes

Stopping at the conditional probability. $P(A\mid Z)$ is generally a random variable, not the unconditional answer. Take its expectation: $P(A)=E[P(A\mid Z)]$.
Averaging the auxiliary variable too early. Replacing $E[X\mid Z]$ by $E[X]$ before forming a conditional bound discards the variation across strata. This still gives ordinary Markov's inequality, but not the potentially more informative conditional bounds.
Assuming conditioning must improve every bound. The averaged conditional bound is valid, but it need not be smaller than every alternative unconditional bound. Compare actual numerical bounds rather than relying on a general claim of improvement.
Using an upper-tail Chernoff parameter with the wrong sign. For an event $X\ge a$, the exponential Markov argument uses $t>0$. A proposed optimizer must lie in the allowed parameter range and in the domain where the conditional moment-generating function exists.

Key takeaway: Bound the tail under the conditional law, retain its dependence on the auxiliary variable, and then average. The tower property makes this valid; the conditional model determines whether the resulting bound is useful.

Check Your Understanding

Try these questions without looking back at the worked examples.

State the conditional Markov inequality and its required conditions.
If $P(A\mid Z)\le B(Z)$ almost surely, what unconditional inequality follows, and why?
For a conditional Poisson model with rate $\lambda<a$, what value of $t$ minimizes the exponential Markov bound for $P(X\ge a\mid\Lambda=\lambda)$?
In the exponential-rate example, calculate the two conditional Markov bounds before averaging them.
Why is it not automatically valid to substitute a data-dependent random value of $t$ into a bound proved for fixed $t$?