# Sampling with replacement

• Jan 20th 2010, 08:45 PM
paolopiace
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!
• Jan 20th 2010, 10:19 PM
hatsoff
Quote:

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!

The probability of the $i$th trial failing given the failure of preceding trials is $\frac{N+1-i}{N}$. The probability of every trial failing up to and including the $y-1$th trial is therefore

$\sum_{i=1}^{y-1}\frac{N+1-i}{N}=\frac{N+1}{N}\sum_{i=1}^{y-1}-\frac{1}{N}\sum_{i=1}^{y-1}i$

$=\frac{(N+1)(y-1)}{N}-\frac{(y-1)(y-2)}{2N}$

$=\frac{(y-1)(2N+4-y)}{2N}$.

The probability of the $i$th trial succeeding given the failure of preceding trials is $\frac{i-1}{N}$. Let Y=y denote the event that every trial up to and including the $y-1$th trial fails and then the $y$th trial succeeds. Then

$p(y)=\frac{(y-1)(2N+4-y)}{2N}\left(\frac{y-1}{N}\right)=\frac{(y-1)^2(2N+4-y)}{2N^2}$.

Therefore $\mathbb{E}(Y)=\sum_{y=1}^{N}yp(y)=\sum_{y=1}^{N}\f rac{y(y-1)^2(2N+4-y)}{2N^2}$.

This can be simplified using common summation identities.