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.