Say a coin has probability $p$ chance of heads (say $p=1/100$ for instance). A trial consists of $N$ coin flips. After $M$ trials, what is the expected number of unique trial sequences?
For example a trial with $N=10$ might be: TTTTHTTTHT
Another way of saying it is, take $M$ random binary numbers of length $N$, where each digit has a $p$ chance of being a 1. What is the expected number of unique binary numbers?
Follow up, given $M$ trials, and probability $p$ what should the length of trial be such that 99% of trials are unique sequences? (reason: to find a efficient way of generating unique sparse sequences up to a small error).
There are $2^N$ possible sequences. For each such sequence $s$ let $X_s$ be the indicator variable for $s$. Then of course the answer $E=\sum E[X_s]$
What is $E[X_s]$? Well, it depends on the number of Heads in $s$. If there are exactly $i$ Heads in $s$ then the probability that we see $s$ in any given trial is, of course, $p^i(1-p)^{N-i}$ from which it follows that $$ E[X_s]=1-\left(1-p^i(1-p)^{N-i}\right)^M$$
As there are exactly $\binom Ni$ sequences with exactly $i$ Heads we see that $$E=\sum_{i=0}^N \binom Ni \times \left(1-\left(1-p^i(1-p)^{N-i}\right)^M \right)$$
As a crude sanity check we remark that as $M\to \infty$ this becomes $E=\sum_0^N \binom Ni=2^N$, as of course it should.
As another, note that with $M=1$ we get $E=\sum_0^N \binom Ni p^i(1-p)^{N-i}=(p+1-p)^N=1$ as of course it should.