Drexel dragonThe Math ForumDonate to the Math Forum

Ask Dr. Math - Questions and Answers from our Archives
_____________________________________________
Associated Topics || Dr. Math Home || Search Dr. Math
_____________________________________________

Probability of Random Samples by Complementarity, Inclusion, and Exclusion

Date: 08/09/2012 at 08:09:12
From: Abe
Subject: Probability of drawing random sample containing ...

Suppose you have a set S with N >= 2 different elements:

   S = {A_1, A_2, A_3, ..., A_N}.

From this set, you draw a random sample of size k, with replacement.

What is the probability that you draw a sample which at least contains A_1
and A_2?

Other elements may also be in the sample, but these two should at least be
in there.

I distinguish two cases: 

Case (1)

Only A_1 and A_2 occur in the sample.

In this case all the samples should be either A_1 or A_2, and each of
these elements should occur at least once. We therefore have to
"distribute" the samples over two bins -- A_1 and A_2 -- such that each
bin is non-empty. This requires Stirling numbers of the second kind. Since
the labels of the bins can also be switched, we have to multiply by 2! to
find the number of possible ways you can obtain a sample containing only
these two. This number is given by ...

   S(k, 2) * 2! 

... where S(k, 2) are Stirling numbers of the second kind.

Case (2)

Now I would tackle it the same way but with 3 bins:

   1. A_1
   2. A_2
   3. other elements

Again, Stirling numbers can be used: S(k, 3). From here on, I am stuck, as 
I am not able to figure out what to do with the "other elements" bin.

Once you find the number for case (2), you only need to add the number of
case (1) and divide by the total number of possibilities (N^k). 

But how do you calculate the probability if your sample does not contain
just A_1 and A_2?

Any help would be very much appreciated!



Date: 08/09/2012 at 12:12:59
From: Doctor Schwa
Subject: Re: Probability of drawing random sample containing ...

Hi Abe,

When you get stuck in some complicated casework like this, it's always a
good idea to look at the idea of complementary probability.

"Contains one or more A_1 and one or more A_2" gets tricky because of the
"or more" part.

"Contains no A_1, or contains no A_2" is a lot simpler, because the
probability of containing none is much more straightforward.

Is that enough of a hint to get you started?

There's still a little bit of complication here that you'll have to deal
with, because of potentially overcounting the things that contain no A_1
and also no A_2.

Feel free to write back if you still have questions!

- Doctor Schwa, The Math Forum
  http://mathforum.org/dr.math/ 



Date: 08/09/2012 at 18:18:40
From: Abe
Subject: Probability of drawing random sample containing ...

Dear Doctor Schwa,

Thank you for this valuable suggestion. In fact, it was also the first
thing that came to my mind!

In the case of a regular "at least" type of question, this would be easy:
say you want to know the probability that you draw A_1 at least once. This
would be equal to

   1 - probability of not drawing A_1 at all (which is the complement)

This is equal to 1 - (1 - (1/N))^k.

However, when you have 2 "at least" conditions, the probability of the
complement is not so easy to calculate. In my case, the complement of
drawing at least one A_1 AND at least one A_2, is given by drawing 

   (a) neither A_1 nor A_2
   
   OR 
   
   (b) at least one A_1 but not A_2 
   
   OR 
   
   (c) at least one A_2 but not A_1.

The probability of drawing neither A_1 or A_2 is again easy and is 
given by

   1 - (1 - (2/N))^k. 

However, the other two probabilities (which should be the same), I cannot
find. How do you find the probability of drawing at least one A_1 but not
A_2?

I hope I did not misinterpret your explanation or make any errors in mine.

Kind regards,

Abe



Date: 08/09/2012 at 22:28:32
From: Doctor Schwa
Subject: Re: Probability of drawing random sample containing ...

Hi Abe,

Sounds like you're on the right track here!

One technique here is to find the probability you describe as (b) by
finding the probability of at least one A_1 and subtracting the
probability of (at least one A_1 and at least one A_2), which you
conveniently found in part (a).

Once you do that, you'll see the Venn diagram shortcut -- also known as
the principle of inclusion and exclusion -- when you generalize it to more
than two sets. Your final answer is 

     (probability of at least one A_1) 
   + (probability of at least one A_2)
   - (probability of both)

- Doctor Schwa, The Math Forum
  http://mathforum.org/dr.math/ 



Date: 08/10/2012 at 03:57:17
From: Abe
Subject: Probability of drawing random sample containing ...

Dear Doctor Schwa,

I'm afraid there might be a mix up: Remember that I'm searching for the
probability of at least one A_1 and at least one A_2. What I found in (a)
was the probability of no A_1 and no A_2. Consequently, I cannot use it
here to calculate (b), so it looks like I'm back to square one. There does
not appear to be an easy way out. 

I guess I will need the Stirling numbers (second kind) after all.

Kind regards,

Abe



Date: 08/10/2012 at 04:43:48
From: Doctor Schwa
Subject: Re: Probability of drawing random sample containing ...

Hi Abe,

You can calculate P(no A_1) and P(no A_2).

You can also calculate P(no A_1 and no A_2).

My claim was that P(at least one A_1 and at least one A_2)

   = 1 - P(no A_1 and/or no A_2)
   = 1 - [P(no A_1) 
       + P(no A_2) 
       - P(no A_1 and no A_2)]

Here, the subtraction accounts for overcounting.

Am I making any sense?

- Doctor Schwa, The Math Forum
  http://mathforum.org/dr.math/ 



Date: 08/10/2012 at 05:59:08
From: Abe
Subject: Thank you (Probability of drawing random sample containing ...)

Dear Doctor Schwa,

You are making complete sense! This was indeed what I was looking for.

The probability is therefore given by:

   1 - 2(1 - (1/N))^k + (1 - (2/N))^k

Thank you very much for helping me out!
Associated Topics:
High School Probability
High School Sets

Search the Dr. Math Library:


Find items containing (put spaces between keywords):
 
Click only once for faster results:

[ Choose "whole words" when searching for a word like age.]

all keywords, in any order at least one, that exact phrase
parts of words whole words

Submit your own question to Dr. Math

[Privacy Policy] [Terms of Use]

_____________________________________
Math Forum Home || Math Library || Quick Reference || Math Forum Search
_____________________________________

Ask Dr. MathTM
© 1994-2013 The Math Forum
http://mathforum.org/dr.math/