# Thread: "Fun" problem using Markov and Chebyshev's inequality

1. ## "Fun" problem using Markov and Chebyshev's inequality

The question is as follows:

"The sum of a list of 1000 non-negative numbers is 9000 and the sum of the squares of the numbers is 91000. Let X represent a number picked at random from the list. What is the expected value of X and what is its variance? Using Markov's inequality, show that there cannot be more than 180 numbers greater than 50 in the list. What is the corresponding conclusion when Chebyshev's inequality is used?"

For the expectation and variance, we can easily find that these are 9 and 10 respectively. The deductions using the two inequalities are the cause of my problems. Firstly, the fact that there cannot be more than 180 numbers greater than 50 should be "obvious" because 180 x 50 = 9000, and all numbers are non-negative, so clearly the total will be more than 9000 if we have more than 180 numbers greater than 50.

But how do we use the Markov's inequality to obtain this result, and what is the corresponding result for Chebyshev's inequality? Presumably we have to use "an epsilon" to get that the probability is less than epsilon for all positive epsilon, but I can't see how to do this. Thanks very much.

2. Originally Posted by alakazam
The question is as follows:

"The sum of a list of 1000 non-negative numbers is 9000 and the sum of the squares of the numbers is 91000. Let X represent a number picked at random from the list. What is the expected value of X and what is its variance? Using Markov's inequality, show that there cannot be more than 180 numbers greater than 50 in the list. What is the corresponding conclusion when Chebyshev's inequality is used?"

For the expectation and variance, we can easily find that these are 9 and 10 respectively. The deductions using the two inequalities are the cause of my problems. Firstly, the fact that there cannot be more than 180 numbers greater than 50 should be "obvious" because 180 x 50 = 9000, and all numbers are non-negative, so clearly the total will be more than 9000 if we have more than 180 numbers greater than 50.

But how do we use the Markov's inequality to obtain this result, and what is the corresponding result for Chebyshev's inequality? Presumably we have to use "an epsilon" to get that the probability is less than epsilon for all positive epsilon, but I can't see how to do this. Thanks very much.
Let $\displaystyle X_1,\ldots,X_{1000}$ be the numbers in the list. Then $\displaystyle P(X\geq 50)=\frac{N}{1000}$, where $\displaystyle N$ is the number of items greater than $\displaystyle 50$ in the list. By Markov inequality, we get $\displaystyle \frac{N}{1000}=P(X\geq 50)\leq \frac{E[X]}{50}=\frac{9}{50},$ so that $\displaystyle N\leq\frac{9000}{50}=180$.

For Chebyshev, by doing the same, we can get an upper bound for the number $\displaystyle N$ of items lying in $\displaystyle [9-a,9+a]$ for some $\displaystyle a>0$.