I have an exam in a few hours and realized there's problems on practice problems that we didn't directly have to do for class. I know that the markov bound is:
$P(X \geq k) \leq E[X] / k$
and the chebyshev equation is:
$P(|X – E[X]| \geq k) \leq var(x) / k^2$
An example problem on a practice exam is of the following:
The students of cs245 are taking an exam. The exam lasts 120 minutes but if we pick a random student, the expected time to finish the exam is just 60 minutes. Let T be the time taken by the student. What is the best lower bound you can show for P(T < 90).
Can anyone explain to me how to do problems like these? I know its probably something simple but when I tried deriving it myself I ended up getting the wrong answer so I must've done something wrong.
Thanks.
Best Answer
"The students of CS245 are taking an exam. The exam lasts 120 minutes but if we pick a random student, the expected time to finish the exam is just 60 minutes.''
"Let $T$ be the time taken by the student.'' Information above implies $E(T) = 60.$ "What is the best lower bound you can show for $P(T < 90).$''
Here is a bound using Markov's Inequality: $P(T \ge k) \le E(T)/k,$ provided $P(T > 0) = 1$. The condition is satisfied because there are no negative exam times.
So $P(T < 90) = 1 - P(T \ge 90) \ge 1 - 60/90 = 1/3.$
Reality check: If $T \sim Unif(0, 120),$ then $E(T) = 60,$ and $P(X < 90) = 3/4 > 1/3.$ So Markov's Inequality makes a true statement, if not a particularly useful one. Because Markov's Inequality works for all non-negative random variables, it cannot possibly give the exact probability for all such random variables. However, Markov bounds are occasionally useful in practical situations and frequently used to prove limit theorems.