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
    What? That's not true. The expected size is n/2. That's not every time..2011-04-12
  • 0
    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.2011-04-12
  • 0
    @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$.2011-04-12
  • 0
    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.2011-04-12
  • 0
    @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.2011-04-12
  • 0
    @coffee_into_solutions: To stay with your example: Let's say I told you the average grade of a student in a class is 73. Can you give me a lower bound for the number of people who got a grade of 79 or higher? You can't, since you can't exclude the possibility that everyone got a 73. That doesn't mean you can conclude that everyone got a 73.2011-04-12
  • 0
    It is a lower bound on the probability, so even if the probability stated is 75%, all possibilites still hold. Thanks for this though. It's clear that I need to spend some more time thinking about this!2011-04-12
  • 0
    @coffee_into_solutions: I don't understand that last comment. What is "the probability stated", and what does "all possibilities still hold" mean? And what's "It" in "It is a lower bound on the probability"?2011-04-12
  • 0
    I mean that a lower bound on the probability is what's being searched for. All possibilities still hold in the sense that even if the probability is 1/2, any one event of that random variable can occur.2011-04-12
  • 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.