Surely many of these are coming now. I'm reviewing for final exams, and came across this problem.
I have a list of length $n$, and some process that reduces the length of the list by expected size $\frac{n}{2}$. I call this process $good$ if it reduces the size of the list by at least $\frac{3}{4}ths$. Give a lower bound on the probability that the call to the process is $good$.
So, I note that for it to be good, the value of the random variable must be $ \geq \frac{3}{2}$ times the expected value.
This seems like a clear cut place to use Markov's Inequality or Chernoff Bounds, but these both give upper bounds, and I'm looking for a lower bound. How would I approach this problem?