If I produce an alphanumeric string with length k, how many n strings must I produce to get a duplicate equal to a 1% chance? I'm terrible when it comes to probability.  The alphanumeric string consist of 'abcdefghijklmnopqrstuvwxyz0123456789' which is 36 possibilities.  If the string is k length (for example 8 alphanumeric chars long) how many n number of strings must I produce for a 1% chance of a duplicate?
Would the math look like this?
$$
\frac{n}{36^{k}} = \frac{0.01}{1}
$$
$$
n = 36^{k}(0.01)
$$
If so, then I'm sorry I wasted everyone's time, I just wanted to make sure and no this isn't homework or anything like that.
 A: This really depends on the way you produce the string, if it's randomly, then you would need to know the probability distribution. If we assume uniform distribution (each character is equally likely, which is common in practice in similar tasks), then for strings of length $k$ with $c$ possible characters on each position, we have total of $c\cdot c \cdots c=c^k$ of possibilities. Since the distribution is assumed uniform, each of the possibilities is equally likely, so $1/c^k$ of generating any specific string.  Now to calculate collision probabilities, it is basically a version of birthday problem (with really big numbers).
So suppose we want to generate $n$ of such strings, and see what is the probability there is not a duplicate. The first generated string can be any of $c^k$. The second must be just different from the previous one, so we have only $c^k-1$ possibilities. Similarly for third $c^k-2$, and so on. So probability there is no duplicate after generating $n$ strings this way is
$$
\frac{c^k}{c^k} \cdot \frac{c^k-1}{c^k}\cdots \frac{c^k-(n-1)}{c^k}=\frac{(c^k)!}{(c^k-n)!c^k}=\frac{n!\binom{c^k}{n}}{(c^k)^n}.
$$
Now the probability that there is a duplicate is simply the complement
$$
p=1-\frac{n!\binom{c^k}{n}}{(c^k)^n}.
$$
For numbers of the magnitude as in your problem, it is more practical to approximate the probability, for example as
$$
p \approx 1 - e^{-n^2/(2c^k)},
$$
or
$$
n \approx \sqrt{2c^k\ln \left(\frac{1}{1-p}\right)}.
$$
So for $c=36$, $k=8$ and $p=0.01$ we have $n \approx 238130$ of required strings (the exact value in this case is $n=238132$).
