Markov Inequality

27 Feb 2018

Prologue To The Markov Inequality

On our way to the learning theorem, the sampling size and the confidence level are the major key factors that can lead your test result to a reject or still pondering. The Markov inequality is a rahter simple probabilistic inequality, that is also a preliminary to allow us to make very strong claims on sums of random variables.

Markov Inequality Theorem

Given that $Z$ is a non-negative random variable, then for all $t\ge 0$, we have $P(Z\ge t)\le \frac {E\lbrack Z\rbrack}{t}$

proof::mjtsai1974

➀let’s begin by the definition of expect value of a random variable.
$E\lbrack Z\rbrack$=$\sum(P(Z\ge t)\cdot\{Z\vert Z\ge t\}$+$P(Z<t)\cdot\{Z\vert Z<t\})$
, where we denote $\{Z\vert Z\ge t\}$=$1$,$\{Z\vert Z<t\}$=$1$
➁then:
$E\lbrack Z\rbrack\ge\sum P(Z\ge t)\cdot\{Z\vert Z\ge t\}$…this must hold
$\;\;\;\;\;\;\;$=$P(Z\ge t)\cdot\sum \{Z\vert Z\ge t\}$
➂choose $Q_t$=$\sum \{Z\vert Z\ge t\}$ to be the total number of events in $\{Z\vert Z\ge t\}$, then:
$\frac {E\lbrack Z\rbrack}{Q_t}\ge P(Z\ge t)$, where $Q_t$=$0$,$1$,$2$,…
➃take $Q_t=t$ could also hold to have $\frac {E\lbrack Z\rbrack}{t}\ge P(Z\ge t)$
We just prove that $P(Z\ge t)\le \frac {E\lbrack Z\rbrack}{t}$