How can I estimate a population size from the probability of randomly drawn members? I have a finite set $X$ of unknown size.  From that I independently draw a multiset of samples $S\subset X$.  For each sample $s\in S$ I can give the exact probability $p(s)$ with which it has been drawn from $X$ such that
$\sum_{x\in X}p(x)=1$ and how often it has been drawn.  I also have a lower bound $l\le p(s)$ for the probability of each sample.
Given this information, how can I estimate the size of $X$?
A mark and recapture approach is not going to work because $|S| \ll |X|$ by several orders of magnitude.  I have drawn about a billion of samples so far without encountering any duplicates.
 A: DISCLAIMER: Simulation has shown that this is not a good estimator but it might be helpful for further ideas
I propose the following estimator: With sample space $S$ and sample $s_1, ..., s_n$, we could use $\widehat{\#S}= n \times\frac{1}{\sum_{i=1}^np(s_i)}$ as an estimator for $\#S$
The theoretical idea is the following: 
We have a random Variable $X$ that has the probability values $p_s:=p(s)$ as the sample space and a distribution, such that $P(X=p_s)=p(s)$, i.e. the numeric value of the sample and its probability coincide.
We then estimate the mean of this Random Variable $X$, i.e. 
$E[X]=\sum_{s\in S}p(s)^2$ by taking the sample mean $\sum_{i=1}^np(s_i)$ In addition to that we use the fact that  $nE[X]=1 \iff n = \frac{1}{E[X]}$
So we use an unbiased estimator for $E[X]$ and plug it into the formula
$n=\frac{1}{E[X]}$ (which means that the estimator for $\#S$ is not necessarily unbiased anymore.
Maybe we could also estimate the distribution of $X$ in order to get a correction-factor of our estimate that takes into consideration how much $1/E[X]$ deviates from $E[1/X]=n$.
