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

From EtoneWiki
Jump to: navigation, search

When applying probabilistic analysis, we often want a bound in form of for some random variable (think that 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 , 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 be a random variable assuming only nonnegative values. Then, for all ,
Proof.
Let be the indicator such that

It holds that . Since is 0-1 valued, . Therefore,

Example (from Las Vegas to Monte Carlo)

Let be a Las Vegas randomized algorithm for a decision problem , whose expected running time is within on any input of size . We transform to a Monte Carlo randomized algorithm with bounded one-sided error as follows:

:
  • Run for long where is the size of .
  • If returned within time, then return what just returned, else return 1.

Since is Las Vegas, its output is always correct, thus only errs when it returns 1, thus the error is one-sided. The error probability is bounded by the probability that runs longer than . Since the expected running time of is at most , due to Markov's inequality,

thus the error probability is bounded.

This easy reduction implies that ZPPRP.

Generalization

For any random variable , for an arbitrary non-negative real function , the is a non-negative random variable. Applying Markov's inequality, we directly have that

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