Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question
up vote 2 down vote accepted

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.

share|cite|improve this answer
What? That's not true. The expected size is n/2. That's not every time.. – user9497 Apr 12 '11 at 16:39
How do we know? Perhaps all the process does is reduce the length of the list to $n/2$. That's consistent with the information you've provided. – Yuval Filmus Apr 12 '11 at 16:55
@coffee_into_solutions: I didn't say it follows from what's given that the reduction length is always $n/2$; I just said that that's consistent with what's given, and hence it can't be possible to derive a lower bound from what's given. If you don't believe this, I suggest you point out what piece of information you've given is inconsistent with a probability of $1$ for a reduction length of $n/2$. – joriki Apr 12 '11 at 16:58
It's inconsistent to assume that, however. I'm not sure I understand your argument. You cannot generally assume that because the average grade of a student in a class is 73, every student in the class has a 73. – user9497 Apr 12 '11 at 16:58
@coffee_into_solutions: Again, I didn't assume that. All I said was that that's a possibility that's consistent with what's given. From this possibility alone we can deduce the impossibility of deducing a lower bound from what's given, since a lower bound must be valid in all possible scenarios. – joriki Apr 12 '11 at 17:00

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.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.