# Estimate the number of elements by random sampling with replacement

## Setup:

1. $N$ numbered balls are in a bag. $N$ is unknown.
2. Pick a ball uniformly at random, record its number, replace it, shuffle.
3. After $M$ samples, of which we noticed $R$ repeated numbers, how can we estimate the value of $N$?

Clearly, after we've covered the set, only repeats will appear. However, there is a vanishingly small probability we've just missed one.

### Simplification:

Assume we know $N<n^\star$, which should make it easy to compute $P(N=n|R=r,M=m)$ for all $n<n^\star$.

## Application:

Estimating the number of webcomics when I'm pressing "random," assuming random is uniform over the comics.

The mean of the neg. binomial distribution is the number of successes before the Rth failure. In this case M-R. So M-R = pR/(1-p) with p being defined above. $$\ M-R = (1 - (M-R)/N))R / (M-R)/N$$ $$\ = (R - (M-R)R/N) * (N / (M-R)) = NR/(M-R) - R = M - R$$ $$\ = M = NR/(M-R) = M^2 - RM = NR --> N = (M^2/R) - M$$