# Math Help - Sampling with replacement

1. ## Sampling with replacement

A = {1, 2, ..., N} is a set of N integers.

I'm sampling from A, one element each time, with replacement.

How many sampling may I expect to perform, in average, before obtaining one element that already came out?

I would appreciate some guidance. Thanks!

2. Originally Posted by paolopiace
A = {1, 2, ..., N} is a set of N integers.

I'm sampling from A, one element each time, with replacement.

How many sampling may I expect to perform, in average, before obtaining one element that already came out?

I would appreciate some guidance. Thanks!
There are $N^i$ possibilities for the first i samples; we assume these are all equally likely.

How many of the arrangements have a first duplication on sample number i? There are N ways to choose the ith sample. This element also appears exactly once in samples 1 through i-1, and disregarding order, there are $\binom{N-1}{i-2}$ possible choices for the other elements. Each set of elements in samples 1 through i-1 can be ordered in $(i-1)!$ ways. So altogether, there are

$N \binom{N-1}{i-2}(i-1)! = \frac{N! \; (i-1)}{(N-i+1)!}$

possible sequences of samples which have a first match on the ith sample.

So the probability that a first match happens on sample number i is

$p_i = \frac{N! \; (i-1)}{(N-i+1)! N^i}$,

and the expected number of samples required to achieve a match is

$\sum_{i=2}^N i \; p_i$.