2
$\begingroup$

This is a question from a homework assignment I am working on. I am using numbers in this example, although the question can and should be proven in the general case for n, m and k. New with mathjax so doing my best here.

There are $n = 1000$ cards, $m = 50$ cards are blue and $n - m = 950$ cards are red. We randomly draw, without replacement, $k = 25$ cards. Prove that the probability we draw no blue cards is at most $(\frac{(n-k)}{n})^m$.

My approach so far is using the fact that the probability of drawing no blue cards == the probability that the first card drawn is red, times the probability that the 2nd card is red, given the first card is red, times the probability that the 3rd card is red, given the first 2 cards were red, ..., times the probability that the $k^{th}$ card is red, given the first k-1 cards were red. I can clean up this product of probabilities using factorials, but am having trouble comparing it to the objective upper-bound for the proof.

Appreciate any thoughts on this.

Improve this question
$\endgroup$
  • 1
    $\begingroup$ Your approach looks right. I don't see how there can be an upper bound when there is only an exact bound? Are you sure that the question wasn't stated with replacement.because the answer looks. like what you would get if you sampled with replacement. $\endgroup$ – Michael R. Chernick Jan 18 '17 at 6:48
  • 1
    $\begingroup$ Since this is homework you need to use the self study tag. $\endgroup$ – Michael R. Chernick Jan 18 '17 at 6:49
  • $\begingroup$ tagged it self study, thanks. Yes I know my approach calculates an exact value, which is better than the bound, however for other aspects of the problem having the bound in this simple equation is useful. $\endgroup$ – Canovice Jan 18 '17 at 7:10
  • $\begingroup$ What is challenging to me is that my product of probabilities has k terms, whereas the bound is raised to the $m^{th}$ power $\endgroup$ – Canovice Jan 18 '17 at 7:10
  • 1
    $\begingroup$ That is because you are right. I will show you what I get $\endgroup$ – Michael R. Chernick Jan 18 '17 at 7:50
3
$\begingroup$

Presumably the idea is to have you bound the sampling without replacement by a calculation based on sampling with replacement.

As you note, this has $k$ and $m$ in the wrong places for the required bound.

However, also note that if we write a hypergeometric sampling problem out as a 2x2 table it immediately becomes obvious that we can interchange the roles of the number of draws and the number of successes in the population without changing the probability.

So just use that equivalent case to form the sampling-with-replacement bound.

I'll leave the few details (such as showing that it really is the same probability when you "flip the table", and demonstrating it's really a bound when you treat it as sampling with replacement) for you to sort out.

Note that this argument leaves us with two upper bounds -- both $(\frac{n-m}{n})^k$ and $(\frac{n-k}{n})^m$ are bounds, so the smaller of the two is also an upper bound. (You might like to see if you can show which will be smaller for given values of those parameters, though it presumably won't be needed for your work.)

Improve this answer
$\endgroup$
2
$\begingroup$

This is exactly the same as what you would get. On the first draw you have $(n-m)/n$ and then for the second draw you have only $n-m-1$ red balls left out of a total of $n-1$ balls remaining.

So multiplying these conditional probabilities gives you

$[(n-m)/n][(n-m-1)/(n-1)]...[(n-m-k+1)/(n-k+1)]$.

Improve this answer
$\endgroup$
  • $\begingroup$ Yes, so the question has essentially been reduced to showing that this is always less than $(\frac{(n-k)}{n})^m$ $\endgroup$ – Canovice Jan 18 '17 at 8:09
  • $\begingroup$ on its own, the question doesn't make a lot of sense because we can fairly easily calculate the exact answer. but for other parts of this question, having the bound is useful. $\endgroup$ – Canovice Jan 18 '17 at 8:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.