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.

An Internet search engine looks for a keyword in 9 databases, searching them in random order. Only 5 of these databases contain the given keyword. What is the probability that it will be found in at least 2 of the first 4 searched databases?

What I tried is: Let X: the event that the keyword is to be found in at least 2 databases, and Y: the event that we search the first 4 databases, then we need to find a conditional probability $P(X\geq 2 | Y)=P(X= 2,3,\text{ or }4 | Y)=\frac{P(\{X\geq 2\} \cap Y)}{P(Y)}$ but then I don't know how to continue?

Any help...

share|improve this question
add comment

2 Answers

You are going to have to work out the probabilities of getting the keyword exactly $n$ times, and either add up the probabilities for $n=2$, $3$ or $4$, or subtract from $1$ the probabilities for $n=1$ or $0$.

If $N$ is the number of dictionaries where the keyword is found then $$\Pr(N=n) = \frac{{5 \choose n}{4 \choose 4-n}}{9 \choose 4}$$ since you have to choose $n$ dictionaries from $5$ with the keyword and $4-n$ from $4$ without, choosing $4$ from $9$ overall.

So for $n=0,1,2,3,4$ this gives probabilities $\frac{1}{126},\frac{20}{126},\frac{60}{126},\frac{40}{126},\frac{5}{126}$.

Add up the last three (and change to lowest terms) and you have your solution.

share|improve this answer
    
@Mike: I don't know: the value is the same but the words are not. You have ${5 \choose 3}$ where I have ${5 \choose 2}$, and you say "ways that 3 of the last 5 databases can contain the keyword" while I say "you have to choose 2 dictionaries from 5 with the keyword". Similarly you have ${9 \choose 5}$ where I have ${9 \choose 4}$, and you say "ways that 5 of the 9 total databases to contain the keyword" while I say "choosing 4 from 9 overall". –  Henry Sep 10 '11 at 21:23
    
Suppose there were only 2 databases (rather than 5) that contain the keyword. If I'm following your logic correctly, your answer to that modified problem would be $P(X = 2) = \binom{2}{2} \binom{7}{2}/\binom{9}{4}$ (2 from 2 with keyword, 2 from 7 without keyword, and 4 from 9 overall). The answer, though, is $\binom{4}{2}/\binom{9}{2}$ (the number of ways to distribute two keywords among a set of 4 divided by the number of ways to distribute two keywords among a set of 9). So I'm not sure that your logic works in general. (Or am I missing something?) –  Mike Spivey Sep 10 '11 at 21:48
    
So I guess it's not the same as my solution after all. (Deleting earlier comment to that effect.) –  Mike Spivey Sep 10 '11 at 21:53
    
In general, if there are $d$ dictionaries and $k$ of them have keywords, and you choose $m$ of them then $\Pr(N=n) = \dfrac{{k \choose n}{d-k \choose m-n}}{d \choose n}$. –  Henry Sep 10 '11 at 22:09
    
Huh. Even in the example I sort of picked at random, our logic still gives the same numerical answer! Perhaps our answers are equivalent after all, even when they don't look like it. Unfortunately, I don't have time right now to pursue this any further. +1 from me. –  Mike Spivey Sep 10 '11 at 22:09
show 1 more comment

Added: Henry's and my answers, while the approaches are different, actually give the same result! To see why, let's do the general case with $N$ databases, $M$ of which contain the keyword, and us choosing $K$ databases. Let $X$ be the number of the $K$ databases chosen that contain the keyword. For $P(X = x)$, Henry's and my logic give the following answers.

$$\text{ Henry: } P(X = x) = \frac{\binom{M}{x}\binom{N-M}{K-x}}{\binom{N}{K}}; \text{ me: } P(X = x) = \frac{\binom{K}{x} \binom{N-K}{M-x}}{\binom{N}{M}}.$$

But

$$\frac{\binom{M}{x}\binom{N-M}{K-x}}{\binom{N}{K}} = \frac{M!}{x! (M-x)!} \frac{(N-M)!}{(K-x)! (N-M-K+x)!} \frac{K! (N-K)!}{N!}$$ $$= \frac{K!}{x! (K-x)!} \frac{(N-K)!}{(M-x)! (N-K-M+x)!} \frac{M! (N-M)!}{N!} = \frac{\binom{K}{x} \binom{N-K}{M-x}}{\binom{N}{M}}.$$

Thus the two answers give the same result.


(Original answer.)

I would approach it differently. Let $X$ be the number of the first four databases in which the keyword is found. You want $P(X \geq 2)$.

$$P(X = 2) = \frac{\binom{4}{2} \binom{5}{3}}{\binom{9}{5}}$$ because there are $\binom{4}{2}$ ways that 2 of the first 4 databases can contain the keyword, $\binom{5}{3}$ ways that 3 of the last 5 databases can contain the keyword, and $\binom{9}{5}$ ways that 5 of the 9 total databases to contain the keyword.

I'll let you calculate $P(X = 3)$ and $P(X = 4)$.

(FYI, $X$ has what's called a hypergeometric distribution.)

share|improve this answer
    
So, in general: $P(X=k)=\frac{\binom{4}{k} \binom{5}{5-k}}{\binom{9}{5}} $ –  Kelly Sep 10 '11 at 16:56
    
@Jess: Yep. That's the form of the probability mass function for a hypergeometric distribution. –  Mike Spivey Sep 10 '11 at 17:05
    
I feel that there is something wrong above! Are we choosing 4 items and not 5?! –  Kelly Sep 10 '11 at 17:06
    
@Jess: I was looking at the problem from the point of view of placing 5 keywords into 9 databases. So we are choosing 5 items (databases) in which to place the keywords. –  Mike Spivey Sep 10 '11 at 20:31
add comment

Your Answer

 
discard

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

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