2
$\begingroup$

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?

2 Answers 2

2

There is no lower bound for the probability of a good result (except for the trivial lower bound 0), since what is given is consistent with the list being reduced by $n/2$ with probability 1.

  • 0
    @coffee_into_solutions: Perhaps we're misunderstanding each other. A lower bound on a quantity usually means that we can say for certain that the quantity is not lower than the lower bound. So a lower bound for the probability that the process is *good* would mean that that probability can't be lower than that lower bound. Since we can't, from what's given, exclude the possibility that that probability is $0$, it follows that we can't give a lower bound (other than $0$) for that probability. If you don't agree with that, please say specifically what part of the argument you don't agree with.2011-04-12
1

The wording "reduces the size of the list by at least $\frac{3}{4}ths$" is unclear. Suppose the original list was length $n$. The expectation of the reduced list is $\frac{n}{2}$. Are you asking for a lower bound on the probability that the reduced list is no more than $\frac{3n}{4}$, or no more than $\frac{n}{4}$? Joriki has answered as if it is $\frac{n}{4}$ (with answer 0). I will answer as if the question is for $\frac{3n}{4}$.

If a fraction $q=1-p$ of the distribution is above $\dfrac{3n}{4}$ and the remaining fraction $p$ of the distribution is non-negative then the expectation is greater than $\dfrac{3n(1-p)}{4}$. If the expectation is exactly $\dfrac{n}{2}$ then $\dfrac{3n(1-p)}{4} < \dfrac{n}{2}$ or simplified (using n>0)

$ p > \dfrac{1}{3}$

which is your lower bound.