This task is a simplified form of the problem of probability of finding a target hash with provision for collisions.
Printer prints $N$ cards with numbers $[1, 100]$. On each iteration there is a $1\%$ chance to print duplicate. While printing duplicates, the $1\%$ chance remains.
The deck is shuffled. What is the $P$ (probabiltiy) to take at least one card from $[1, 10]$ if we pull out $50$ cards?
I thought it might be solved by hypergeometric distribution but the problem is that $\Omega$ (probability space) depends on the duplicate print and seems nonconstant. What $\Omega$ should I form for this task?
Which section of mathematics should I dig into?
Sample space: $\Omega$ here is the set of all non-decreasing sequences of integers, of finite length, starting at $1 $, ending with $\ldots, 99, 100.$ and incrementing by at most $1 $ at each step.
Probability measure: The probability of a given sequence is $\frac {99^{99}}{100^{N-1}} $ where $ N $ is the length of the sequence. [Proof: each increment comes with probability $\frac{99}{100}$ and there are $99$ of them, and each duplicate comes with probability $\frac{1}{100}$ and there are $N-100$ of them.]
Q: how many sequences of length $N$ contain $n$ elements in the interval $[1,10]$?
A: there are ${N-n-2\choose 88}{n-1\choose 9}$such sequences.
Each of them has probability $\frac {99^{99}}{100^{N-1}}$, so $$P(n\text{ elements in }[1,10]\text{ and }N\text{ elements in total})=\frac {99^{99}}{100^{N-1}}{N-n-2\choose 88}{n-1\choose 9}$$
Now given that there are $n$ elements in $[1,10]$ and $N$ elements in total, the probability that a random sample of $50$ cards does not contain any numbers in $[1,10]$ is $$\frac{N-n}{N}\ldots\frac{N-n-49}{N-49}=\frac{{N-n\choose 50}}{{N\choose 50}}$$
So the probability to have at least one card in $[1,10]$ by picking $50$ arbitrarily is $$\sum_{N=100}^{\infty}\sum_{n=10}^{N-90}\frac {99^{99}}{100^{N-1}}{N-n-2\choose 88}{n-1\choose 9}\left[1-\frac{{N-n\choose 50}}{{N\choose 50}}\right]$$