# Sampling with replacement

Suppose you have 40 different books (20 math books, 15 history books, and 5 geography books).

Let M = math books, H = history books, G = geography books

You pick 5 books at random, with replacement, one at a time. What is the probability that you've picked books from at most two disciplines?

I know this is basic, but...

The way I have approached this problem is:

The only way you can have at most two disciplines is to have

1. { H H M M G }

2. { H H G G M }

3. { G G M M H }

so the answer I got is: $$\left(\left(\frac{15}{40}\right)^2\cdot\left(\frac{20}{40}\right)^2\cdot\left(\frac{5}{40}\right)\right) + \left(\left(\frac{15}{40}\right)^2\cdot\left(\frac{5}{40}\right)^2\cdot\left(\frac{20}{40}\right)\right) + \left(\left(\frac{5}{40}\right)^2\cdot\left(\frac{20}{40}\right)^2\cdot\left(\frac{15}{40}\right)\right)$$

I have a feeling I am doing this problem wrong. Is there an easier way to do this? I tried to do it with combinations, but the "with replacement" aspect threw me off a bit. I feel as though order should not matter here, but I do not know whether that is the case.

• The "with replacement" makes this a classical multinomial distribution problem. Is this homework? – Macro May 29 '12 at 15:40
• Yes, it is.. Not looking for the answer. Want intuition more than anything. I will add hw tag, only reason I didn't is because I feel like it makes people reticent in helping. – Avanish Giri May 29 '12 at 15:43
• In the three cases that you list you have three disciplines (and thus not at most two), so presumably you are trying to compute the probability of having three disciplines (the complement of which is the probability that you seek). You can solve this problem either by direct computation, as you've attempted to do, or by using random variables. Are you familiar with the binomial and/or multinomial distributions? Otherwise, try to think about whether there is more than one way to obtain the result { H H M M G }. – MånsT May 29 '12 at 16:18
• I think we should be asking Avanish what he means by "just two disciplines. The examples he chose all involve three disciplines history, math and geography. If he means that two disciplines are selected exactly twice, then his choices make sense. But that sounds like a completely different question. I will give an answer enumerating all the cases where only two disciplines are represented in the five but leave the probability calculations for him. – Michael R. Chernick May 29 '12 at 16:33
• (-1) Can somebody revert the question back? @AvanishGiri - deleting the body of your question is horrible practice and is sure to get you downvotes. Think about the purpose of a question and answer site - deleting your question is counter productive. – Dason May 30 '12 at 0:47

To have at most two disciplines occurring, one can have either only $1$ discipline or $2$ disciplines showing. Also, since this is sampling with replacement, we can consider the draws to be of three objects $(M, H, G)$ with probability $(\frac{4}{8}, \frac{3}{8}, \frac{1}{8})$ respectively.

For brevity, let's deal only with the numerators, as the denominator of the five draws will be $8^5$. Now the way to have only one discipline is relatively straightforward. It is a fivefold draw of the same value, so we can start with: $$M^5\Rightarrow 4^5 = 1024\\ H^5\Rightarrow 3^5 = 243\\ G^5\Rightarrow 1^5 = 1$$ Now the case of two disciplines can be broken into four classes. If $A$ is the first discipline and $B$ is the second, we can have patterns of the form $AAAAB$. We also need to consider the order in which these books were picked. For example, $AABAA \equiv AAAAB$ so we need to factor in the number of unique orders in which these patterns can occur. When we have $n$ elements which can be broken into $k$ distinct groups with size $n_i, \sum_k{n_i} = n$, the number of permutations is: $${n \choose {n_1, n_2, \ldots, n_k}} = \frac{n!}{n_1! n_2! \ldots n_k!}$$ The list of patterns and their permutations are $$AAAAB \Rightarrow A^4B^1; {5 \choose {4, 1}} = 5\\ AAABB \Rightarrow A^3B^2; {5 \choose {3, 2}} = 10\\ AABBB \Rightarrow A^2B^3; {5 \choose {2, 3}} = 10\\ ABBBB \Rightarrow A^1B^4; {5 \choose {1, 4}} = 5$$

There are also ${3 \choose 2} = 3$ ways to select $A$ and $B$ from $(M, H, G)$, so there will be $12$ cases for us to enumerate: $$MMMMH \Rightarrow 4^41^1\cdot 5 = 3840\\ MMMHH \Rightarrow 4^31^2\cdot 10 = 5760\\ MMHHH \Rightarrow 4^21^3\cdot 10 = 4320\\ MHHHH \Rightarrow 4^11^4\cdot 5 = 1620\\ MMMMG \Rightarrow 4^41^1\cdot 5 = 1280\\ MMMGG \Rightarrow 4^31^2\cdot 10 = 640\\ MMGGG \Rightarrow 4^21^3\cdot 10 = 160\\ MGGGG \Rightarrow 4^11^4\cdot 5 = 20\\ HHHHG \Rightarrow 3^41^1\cdot 5 = 405\\ HHHGG \Rightarrow 3^31^2\cdot 10 = 270\\ HHGGG \Rightarrow 3^21^3\cdot 10 = 90\\ HGGGG \Rightarrow 3^11^4\cdot 5 = 15$$ So we have a total of $19,688$ acceptable draws out of $32,768$ total, which simplifies to: $$\frac{2461}{4096} = 1 - \frac{1635}{4096}$$ Which matches what @whuber wrote. That highlights one of the beauties of combinatorics. It all boils down to counting so all the sophisticated methods, such as generating functions, must jibe with simple, but exhaustive, enumeration. Hope this helps.

One way to test if you answer is in the correct ballpark is to compare it to an estimate gained by simulation. Here is some sample code in R that takes a bunch of samples, calculates how many disciplines they come from, then calculates the proportion below 3:

> out <- replicate( 1000000, sample(1:3, 5, replace=TRUE, prob=c(20,15,5)),
+ simplify=FALSE)
> out[1:3]
[]
 1 2 1 1 1

[]
 2 1 1 2 1

[]
 1 2 2 1 1

> mean(  sapply( out, function(x) length(unique(x)) ) < 3 )
 0.601803


So while this does not give the exact answer and does not give the theoretical derivation, it does give a number to check against. Any solution whose value is not pretty close to 0.602 is probably wrong (being close does not guarantee correctness, but does give more confidence if everything else makes sense).

• Because we're statisticians, we can do better than "pretty close": we can estimate the standard error and check that the mean is within just two or three SEs of the correct value. Your simulation is 1.99 SEs higher than 2461/4096. This is big enough to make us uncomfortable but small enough to suggest that the simulation may have been conducted correctly :-). Replications tend to produce even smaller deviations, so I think you're ok. – whuber Sep 10 '13 at 20:55
• BTW, having motivated you to iterate the simulation, I should offer a way to do it quickly (because on my system, which isn't shabby, it takes 24 seconds). Here is a two order of magnitude speedup (0.5 seconds): n <- 10^6; system.time({ s <- matrix(sample(1:3, 5*n, replace=TRUE, prob=c(20,15,5)), ncol=5); f <- function(i) ((s[,1]-i)*(s[,2]-i)*(s[,3]-i)*(s[,4]-i)*(s[,5]-i) == 0); x <- f(1)+f(2)+f(3) < 3 }); x.bar <- mean(x); se <- sd(x) / sqrt(length(x)); (x.bar - 2461/4096) / se – whuber Sep 10 '13 at 20:59

To have just two disciplines represented,one must occur twice and the other three times. So you could have (1) history twice amd math 3 times, (2) math twice and history three times (3) history twice and geography three time (4) geography twice and history three times (5)math twice and geography three times and (6) geogrpahy twice and math three times. So the possibilities can be represented as {H H H M M}, {H H M M M} {H H H G G} {H H G G G} {M M M G G} and {M M G G G} each case involves 2 of 1 discipline and 3 of another. In each case there are 10 ways for this to occur. So for each sequence compute its probabuility, multiply by 10 and sum. Note a math occurrence in any place is 20/40 =1/2=0.5. History occurs with probability 15/40=3/8=0.375 on any occurrence and Geography occurs 5/40 =1/8 =0.125 on any occurrence.

• Thank you Michael. I get it now. Here is another sort of related question: Why can't I do it in a way which I treat the other two subjects that were not selected as one? For example, why couldn't I do : { H H H (NOT H) (NOT H) } * 10 so (15/40) * (15/40) * (15/40) * (25/40) * (25/40) Why must I enumerate the different cases, History and Math, AND History and Geography. Why can't I treat it like it is one. I tried this and it didn't work.. I know this is probably a stupid question but I think I will get it if it is explained – Avanish Giri May 29 '12 at 16:56
• The reason is that {H H H notH notH} includes {H H H M G}. This case does not satisfy the criteria for only two disciplines occurring. You are including too many cases and so yuor calculation will be wrong on the high side. – Michael R. Chernick May 29 '12 at 17:05
• (-1) This answer incorrectly addresses the question by misinterpreting "at most" as "equal." It is also incorrect in asserting that when two disciplines are represented they each must occur at least twice. The answer is $1-1635/4096$, obtained by summing the coefficients of all multiples of $mhg$ in the polynomial expansion of $((20m+15h+5g)/40)^5)$ to compute the chance that all three disciplines are sampled, and subtracting that chance from $1$. To find these multiples, $mhg$ can be multiplied by powers of $m,h,$ and $g$ summing to $2$, which are easily enumerated. – whuber Mar 1 '13 at 22:47