A simple way of explaining the probability of finding x in y For some documentation, I need to express the probability of something happening in a way that is correct but easy to understand. I'm confused on the actual math for this. I'll simplify the numbers here.
Assume a system has 1,000 possible unique codes and I have used 10. I set a computer to search for the codes at a rate of one per hour. The computer will go through the 1,000 without repetition and the 10 have been chosen at random. How many hours statistically before I find a code ?
On the face of it, I am assuming 100 hours. But I have a feeling that this wouldn't be correct ?
 A: $100$ hours would be the right answer if the draws were with replacement, meaning if you found a "bad" piece, you put it back again randomly, so each time the probability of finding a "good" piece (a code) would remain constant at $\frac1{100}$
But here the number of "bad" pieces will go on reducing until you find a "good" piece, so the expected value of draws needed will be less.
With $B\;$"bad" pieces and $G\;$ "good" pieces totaling to  $N$
The formula is $\Bbb E[X] = \dfrac{N+1}{G+1} = \dfrac{1001}{11}= 91\;$

For coherent completeness, I am giving the formula  derivation here.
Let $Y_i$ be an indicator random variable that has a probability = $1$ if the $i_{th}$ "bad" piece comes before the first "good" piece, and $0$ otherwise.
Consider $Y_i$ together with the "good" pieces $G$, then the probablity that $Y_i$ comes before any "good" piece is $P(Y_i) = \frac{1}{G+1}$
Now the expectation of an indicator variable is just the probability of the event that it indicates, thus
$\Bbb E[Y_i] = P(Y_i)$,
and by linearity of expectation which applies even if the random variables are not independent,
$\Bbb E[Y] = \Bbb E[Y_1] + \Bbb E[Y_2] + .... = \dfrac{B}{G+1}$
The expected value $\Bbb E[X]$ of the first "good" piece is thus
$\Bbb E[X] =1 + \Bbb E[Y] = 1 + \dfrac{B}{G+1} = \dfrac{B+G+1}{G+1} = \dfrac{N+1}{G+1}$
A: Let $n$ codes $X_1,...,X_n$ be chosen at random from $\{1,2,...,N\}\ (n<N)$ without replacement (to guarantee the chosen codes differ from one another).
If $\{1,2,...,N\}$ is then searched in sequence, one per hour, until all the codes have been encountered, then the search time is $\text{MAX}:=\max(X_1,...,X_n)$. The expectation value of $\text{MAX}$ is then (see this post for derivations)
$$E(\text{MAX})={n\over n+1}(N+1).$$
If $\{1,2,...,N\}$ is then searched in sequence, one per hour, until the first code is encountered, then the search time is $\text{MIN}:=\min(X_1,...,X_n)$. The expectation value of $\text{MIN}$ is then
$$E(\text{MIN})={N+1\over n+1}$$
since by symmetry we have $N-E(\text{MAX})=E(\text{MIN})-1.$
NB: Comparing to the other answer (for searching by random sampling), the expected search times are the same for both random and sequential searching to the first encountered code!

An interesting fact:  Suppose we first sample in any order at all (random or nonrandom) $n<N$ distinct elements from $\{1,...,N\}$ and then we search distinct elements of $\{1,...,N\}$ in any order at all (random or nonrandom) until finding a sampled element. As long as at least one of these two procedures is random, the expected number of elements searched is the same, namely ${N+1\over n+1}.$ In one case we fix an arbitrary sample and randomize the search order, in the other case we randomize the sample and fix an arbitrary search order -- the two are equivalent.
A: My knowledge in statistics is very limited. So I've made a little program to check this question.
The program makes $100000$ rounds. In each round it randomly fills an array with $10$ codes (set as $1$). We are interested only in the first $1$. The position where it's found is the number of hours needed by the computer to find a good code. I don't care about the rest of codes.
Then it counts for each position in the array the number of "hits". For example hits[5]  (hits[4] in C++) is the number of rounds where the first code was found at position $5$.
Then $hits[i]/100000$ is the probably of take $i$ hours to find the first code.
You can get the program here
A typical output is:
Fist most probably at pos= 1  number of rounds with this hit= 1022
50% reached at pos =  68  50%= 50311
95% reached at pos =  258  95%= 95016

If you use a debugger (or add code to output hits[] to a file), you see the probably is decreasing with $i$. The best probably is to find the first code in the first chance (position= 1). This probably is closer to $hit/100000 = 1\%$
The program also calculates the sum of probablies to get $50\%$ and $95\%$
68 hours are needed to have $50\%$ of hiting the first code.
