Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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|improve this question

2 Answers 2

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|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|improve this answer

Your Answer

 
discard

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