# Sampling without replacement until object found

I'm wondering about sampling without replacement until an object is found. I can't seem to wrap my head around it.

The random variable I want to use is X which I let bet the number of objects examined until the object is found. So I'm interested in the probability mass function here.

My attempts so far are:

(i) Take one sample at a time. Then each sample is a Bernoulli trial with probability at the k-th sample = 1/(n-k+1), 1 <= k <= n

So to get P(X=x) I multiply each 1/(n-k+1) from 1 to k inclusive? i.e. P(X=x) = 1/(n-k+1)!

(ii) The problem looks kind of like a hypergeometric distribution with parameters: number of draws = k, pop. size = n, contains 1 success

But the hypergeometric pmf is constructed in terms of obtaining some number of successes from a potential group of successes within the population. For my problem however there is only one success in the potential success group and we want to stop when we get a success. So it's styled more in the way of a geometric distribution. Again, the random variable for a geometric dist. is number of trials needed to get a success.

I'm confused anyway, if anyone could shed some light on this I'd be very grateful, thanks

• Hi -- welcome to math.SE! Here's a reference and tutorial for typesetting math on this site. – joriki May 18 '16 at 10:41

We have $n$ objects, of which $n-1$ are bad and $1$ is good. We sample without replacement until the good object is found. Let $X$ be the number of trials needed.

Imagine that the objects have been lined up at random, with all orderings equally likely, and we choose the first, then the second, and so on.

The probability that the good object is in the $k$-th position is $\frac{1}{n}$. So $\Pr(X=k)=\frac{1}{n}$ for all $k$ such that $1\le k\le n$.

Remark: An approach like the one you began also works well, but takes a little longer. The probability that $X=1$ is clearly $\frac{1}{n}$.

For the success to occur on the second trial, we must have failure on the first trial, and success on the second. The probability of failure on the first trial is $\frac{n-1}{n}$. Given that we had failure on the first trial, the probability of success on the second trial is $\frac{1}{n-1}$. Thus $\Pr(X=2)=\frac{n-1}{n}\cdot\frac{1}{n-1}=\frac{1}{n}$.

It follows from our first two calculations that the probability of failure on the first two trials is $\frac{n-2}{n}$. Given that there was failure on the first $2$ trials, the probability of success on the third is $\frac{1}{n-2}$. Thus $\Pr(X=3)=\frac{n-2}{n}\cdot\frac{1}{n-2}=\frac{1}{n}$.

The pattern continues: For $1\le k\le n$, $\Pr(X=k)=\frac{1}{n}$.