0
$\begingroup$

Let $X$ be a random variable with mean, $E(X)=\mu$ and variance, $E(X-\mu)^2=\sigma^2$. Then Chebyshev's inequality asserts that $$ P\{|X-\mu|\geq k\sigma\} \leq \frac{1}{k^2} $$

Using this inequality, I have to show that $$e^{k+1} \geq k^2 \,\,\text{for}\,\, k>1$$ It is clear that if I can show that $$P\{|X-\mu|\geq k\sigma\}\geq \frac{1}{e^{k+1}}$$ for $k>1$, and any $\mu \in \mathbb{R}$ and any $\sigma>0$, then we are done. Thanks in advance.

Source : Rohatgi, Saleh-p.$98$-problem $6$.

$\endgroup$

2 Answers 2

2
$\begingroup$

Consider a random variable $X$ that follows the exponential distribution $\mathsf{Exp}(1)$. We have $$ \mathsf{E}(X) = 1, \quad\mathsf{Var}(X) = 1 $$ and for $x > 0$, $$ \Pr(X \geq x) = e^{-x} $$ implying $\Pr(X \geq k + 1) = 1/ e^{k+1}$. In addition, by Chebyshev's bound, we have $$ \Pr(X \geq 1 + k) \leq 1/k^2 $$ Therefore, $$ 1 / e^{k+1} \leq 1/k^2 $$

$\endgroup$
0
$\begingroup$

I agree to the above answer of using the Exponential distribution with mean = 1, but here is my approach using Markov's inequality. Please check if it makes any sense...

Let X be any random variable defined only for $x > 0$.

Then by Markov's Inequality

$P((X-1)^2 \ge K^2) \le \frac{E(X-1)^2}{K^2}$ which can be rewritten as $P(|X-1| \ge K) \le \frac{E(X-1)^2}{K^2}$. (Alternate derivation of the Chebyshev's inequality).

Now, for the negative case of the abs function, $P(X \le 1 - K) $ which is not possible, since $K > 1$ and X is defined only for positive values.

Thus, $P(X \ge K + 1) \le \frac{E(X-1)^2}{K^2}$ ---------------- (1)

Now, $P(X \ge K + 1)$ can also be written as $P(e^X \ge e^{K+1})$.

Applying the Markov's inequality again, we get

$P(e^X \ge e^{K+1}) \le \frac{Ee^X}{e^{K+1}}$, effectively stating that $P(X \ge K+1) \le \frac{Ee^X}{e^{K+1}}$ ----------------- (2). (Alternate derivation of the Chernoff's bounds)

Now, there are two ways to proceed from here. Either use the fact that the Chernoff's bounds are tighter than the Chebyshev's bounds, in which case the proof would be quite straighforward, or make use of the fact that both (1) and (2) are indeed the special case of the Markov's bound.

Chernoff's bound is tighter than Chebyshev's bound

In this case, $\frac{Ee^X}{e^{K+1}} \le \frac{E(X-1)^2}{K^2}$.

Now, in both the discrete as well as the continuous case, it is easier to show that $Ee^X \ge E(X-1)^2$.

Thus, $\frac{E(X-1)^2}{e^{K+1}} \le \frac{E(X-1)^2}{K^2}$ or $e^{K+1} > K^2$.

Both are derived from Markov's inequality

In the best case, one can assume both bounds may be equal in some case.

$\frac{Ee^X}{e^{K+1}} = \frac{E(X-1)^2}{K^2}$ or $\frac{E(X-1)^2}{e^{K+1}} \le \frac{E(X-1)^2}{K^2}$ using the fact that $Ee^X \ge E(X-1)^2$.

Thus, ${e^{K+1} \ge K^2}$

Please note, this is an individual answer and I'm in no way an "expert". Please let me know if the answer needs any modifications.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .