# 随机算法 (Fall 2011)/Markov's Inequality

When applying probabilistic analysis, we often want a bound in form of ${\displaystyle \Pr[X\geq t]<\epsilon }$ for some random variable ${\displaystyle X}$ (think that ${\displaystyle X}$ is a cost such as running time of a randomized algorithm). We call this a tail bound, or a tail inequality.

Besides directly computing the probability ${\displaystyle \Pr[X\geq t]}$, we want to have some general way of estimating tail probabilities from some measurable information regarding the random variables.

# Markov's Inequality

One of the most natural information about a random variable is its expectation, which is the first moment of the random variable. Markov's inequality draws a tail bound for a random variable from its expectation.

 Theorem (Markov's Inequality) Let ${\displaystyle X}$ be a random variable assuming only nonnegative values. Then, for all ${\displaystyle t>0}$, {\displaystyle {\begin{aligned}\Pr[X\geq t]\leq {\frac {\mathbf {E} [X]}{t}}.\end{aligned}}}
Proof.
 Let ${\displaystyle Y}$ be the indicator such that {\displaystyle {\begin{aligned}Y&={\begin{cases}1&{\mbox{if }}X\geq t,\\0&{\mbox{otherwise.}}\end{cases}}\end{aligned}}} It holds that ${\displaystyle Y\leq {\frac {X}{t}}}$. Since ${\displaystyle Y}$ is 0-1 valued, ${\displaystyle \mathbf {E} [Y]=\Pr[Y=1]=\Pr[X\geq t]}$. Therefore, ${\displaystyle \Pr[X\geq t]=\mathbf {E} [Y]\leq \mathbf {E} \left[{\frac {X}{t}}\right]={\frac {\mathbf {E} [X]}{t}}.}$
${\displaystyle \square }$

### Example (from Las Vegas to Monte Carlo)

Let ${\displaystyle A}$ be a Las Vegas randomized algorithm for a decision problem ${\displaystyle f}$, whose expected running time is within ${\displaystyle T(n)}$ on any input of size ${\displaystyle n}$. We transform ${\displaystyle A}$ to a Monte Carlo randomized algorithm ${\displaystyle B}$ with bounded one-sided error as follows:

${\displaystyle B(x)}$:
• Run ${\displaystyle A(x)}$ for ${\displaystyle 2T(n)}$ long where ${\displaystyle n}$ is the size of ${\displaystyle x}$.
• If ${\displaystyle A(x)}$ returned within ${\displaystyle 2T(n)}$ time, then return what ${\displaystyle A(x)}$ just returned, else return 1.

Since ${\displaystyle A}$ is Las Vegas, its output is always correct, thus ${\displaystyle B(x)}$ only errs when it returns 1, thus the error is one-sided. The error probability is bounded by the probability that ${\displaystyle A(x)}$ runs longer than ${\displaystyle 2T(n)}$. Since the expected running time of ${\displaystyle A(x)}$ is at most ${\displaystyle T(n)}$, due to Markov's inequality,

${\displaystyle \Pr[{\mbox{the running time of }}A(x)\geq 2T(n)]\leq {\frac {\mathbf {E} [{\mbox{running time of }}A(x)]}{2T(n)}}\leq {\frac {1}{2}},}$

thus the error probability is bounded.

This easy reduction implies that ZPP${\displaystyle \subseteq }$RP.

### Generalization

For any random variable ${\displaystyle X}$, for an arbitrary non-negative real function ${\displaystyle h}$, the ${\displaystyle h(X)}$ is a non-negative random variable. Applying Markov's inequality, we directly have that

${\displaystyle \Pr[h(X)\geq t]\leq {\frac {\mathbf {E} [h(X)]}{t}}.}$

This trivial application of Markov's inequality gives us a powerful tool for proving tail inequalities. With the function ${\displaystyle h}$ which extracts more information about the random variable, we can prove sharper tail inequalities.