9
$\begingroup$

Assuming "complete randomness" and given a string with a length of 20 characters where each character may be one of 62 possible characters:

  • What are the total number of combinations possible? (Guessing 20 to the power of 62.)
  • Also, if new strings are randomly selected one after another and added to a list of strings selected so far, how many strings must be selected before the chance of selecting a string that has already been selected is below 1-in-100000 ($10^{-5}$)?

Note: 62 comes from: numeric digits (0-9), uppercase letters (A-Z), and lowercase letters (a-z).

$\endgroup$
10
  • 2
    $\begingroup$ Your second bullet point can be read in (at least) two possible ways. I'm wondering which you're interested in. (1) The probability that the $n$th string matches one of the previous strings or (2) The probability that by the time the $n$th string is selected there exists some duplicate within the collection of strings drawn so far. The answers to these two questions will be very different. :) $\endgroup$ – cardinal Mar 25 '12 at 16:17
  • 1
    $\begingroup$ Perhaps considering a two-character alphabet will make the difference clear. Let the letters be $H$ and $T$. We can ask: (1) For what $n$ do we have at least a 99% chance of the $n$th string being a duplicate of a previous string? The $n$ here is 8 since the only way we fail is if our sequence is either $TTT \cdots TH$ or $HHH\cdots HT$, which has total probability $2^{-(n-1)}$. Or, we ask (2) For what $n$ do we have at least a 99% chance of seeing some duplicate? In this case $n = 3$ since by the time we've seen three strings either $H$ or $T$ has been repeated at least once. $\endgroup$ – cardinal Mar 25 '12 at 16:38
  • 1
    $\begingroup$ Matt's answer handles (1), which essentially answers the question about whether "my" string matches somebody else's. But, if you are worried about some other two people's strings also potentially matching, then you are interested in (2). It comes down to whether you have a particular string of interest that you're comparing all others to or whether you are comparing all strings to each other. I'm not sure if I'm making that any clearer, though. (Your problem boils down to one of two variants of the famous so-called "birthday problem".) $\endgroup$ – cardinal Mar 25 '12 at 16:41
  • 1
    $\begingroup$ Cardinal is, as usual, correct. I assumed you had one "target" string, for which you were generating a list of guesses. If instead, you're generating strings at random and want to know the number it's safe to generate before any two strings match, then the answer is very different indeed. I'll amend my answer to address that case, if it's okay with you. $\endgroup$ – Matt Krause Mar 25 '12 at 17:12
  • 1
    $\begingroup$ I didn't make my previous example completely clear. Sorry about that. I was thinking of a two-letter alphabet $\{H,T\}$ and drawing strings of length one. Hence, when I wrote $HHH\cdots HT$, that stood for $s_1 = H$, $s_2 = H$, ..., $s_{n-1} = H$, $s_n = T$. $\endgroup$ – cardinal Mar 25 '12 at 18:00
12
$\begingroup$

Total number of possibilities

1) Close! You've got 62 choices for the first character, 62 for the 2nd, etc, so you end up with $62 \cdot 62 \cdot 62 \cdot \cdots 62 = 62^{20}$, which is an absurdly huge number.

Collision with a "Target" String

2) As we established above, there are $62^{20}$ potential strings. You want to know how many you'd need to guess to have better than 1 in 100,000 odds of guessing the "target" string. Essentially, you're asking what $$\frac{x}{62^{20}} \ge \frac{1}{10^5}$$To get it spot on, you'd have to round x up (or add one, if they're precisely equal), but as you'll see in a second, it doesn't really matter.

Through basic algebra, we can rearrange that as $$\begin{aligned} 10^5x &\ge 62^{20}\\ 10^5{x} &\ge (6.2 \cdot 10)^{20}\\ 10^5x &\ge 6.2^{20} \cdot 10^{20}\\ x &\ge 6.2^{20} \cdot 10^{15} \end{aligned}$$

Doing the math, $6.2^{20}$ is about $7 \cdot 10^{15}$, so let's call the whole thing $7 \cdot 10^{30}$ or, more succinctly, a whole heck of a lot.

This is, of course, why long passwords work really well :-) For real passwords, of course, you have to worry about strings of length less than or equal to twenty, which increases the number of possibilities even more.

Duplicates in the list

Now, let's consider the other scenario. Strings are generated at random and we want to determine how many can be generated before there's a 1:100,000 chance of any two strings matching. The classic version of this problem is called the Birthday Problem (or 'Paradox') and asks what the probability that two of n people have the same birthday. The wikipedia article[1] looks decent and has some tables that you might find useful. Nevertheless, I'll try to give you the flavor for the answer here too.

Some things to keep in mind:

-The probability of a match and of not having a match must sum to 1, so $P(\textrm{match}) = 1 - P(\textrm{no match})$ and vice versa.

-For two independent events $A$ and $B$, the probability of $P(A \& B) = P(A) \cdot P(B)$.

To get the answer, we're going to start by calculating the probability of not seeing a match for a fixed number of strings $k$. Once we know how to do that, we can set that equation equal to the threshold (1/100,000) and solve for $k$. For convenience, let's call $N$ the number of possible strings ($62^{20}$).

We're going to 'walk' down the list and calculate the probability that the $k$^{th} string matches any of the strings "above" it in the list. For the first string, we've got $N$ total strings and nothing in the list, so $P_{k=1}(\textrm{no match}) = \frac{N}{N} = 1$. For the second string, there are still $N$ total possibilities, but one of those has been "used up" by the first string, so the probability of a match for this string is $P_{k=2}(\textrm{no match}) = \frac{N-1}{N}$ For the third string, there are two ways for it a match and therefore $N-2$ ways not to, so $P_{k=3}(\textrm{no match}) = \frac{N-2}{N}$ and so on. In general, the probability of the $k$th string not matching the others is $$P_{k}(\textrm{no match})= \frac{N-k+1}{N}$$

However, we want the probability of no matches between any of the $k$ strings. Since all of the events are independent (per the question), we can just multiply these probabilities together, like this: $$P(\textrm{No Matches}) = \frac{N}{N} \cdot \frac{N-1}{N} \cdot \frac{N-2}{N} \cdots \frac{N-k+1}{N}$$ That can be simplified a little bit: $$\begin{aligned} P(\textrm{No Matches}) &= \frac{N \cdot (N-1) \cdot (N-2) \cdots (N-k+1)}{N^k} \\ P(\textrm{No Matches}) &= \frac{N!}{N^k \cdot (N-k)!} \\ P(\textrm{No Matches}) &= \frac{k! \cdot \binom{N}{k}}{N^k} \\ \end{aligned} $$ The first step just multiplies the fractions together, the second uses the definition of factorial ($k! = (k) \cdot (k-1) \cdot (k-2) \cdots 1$) to replace the products of $N-k+1 \cdots N$ with something a little more manageable, and the final step swaps in a binomial coefficient. This gives us an equation for the probability of having no matches at all after generating $k$ strings. In theory, you could set that equal to $\frac{1}{100,000}$ and solve for $k$. In practice, it's going to be difficult to an answer since you'll be multiplying/dividing by huge numbers--factorials grow really quickly ($100!$ is more than 150 digits long).

However, there are approximations, both for computing the factorial and for the whole problem. This paper[2] suggests $$ k = 0.5 + \sqrt{0.25 - 2N\ln(p)}$$ where p is the probability of not seeing a match. His tests max out at $N=48,000$, but it's still pretty accurate there. Plugging in your numbers, I get approximately $3.7 \cdot 10^{15}$.

References

[1] http://en.wikipedia.org/wiki/Birthday_problem

[2] Mathis, Frank H. (June 1991). "A Generalized Birthday Problem". SIAM Review (Society for Industrial and Applied Mathematics) 33 (2): 265–270. JSTOR Link

$\endgroup$
3
  • $\begingroup$ +1 Awesome, given clearly my poor math skills resulted in asking the question, so I'll leave the question unanswered for a day, but looks good to me, and is way more clear of an answer than I expected - thank you! $\endgroup$ – blunders Mar 25 '12 at 2:59
  • 1
    $\begingroup$ Glad to help! Let me know if anything's unclear. For kicks, I ran the numbers. You'll need 7044234255469980229683302646164 guesses; like I said--a lot! $\endgroup$ – Matt Krause Mar 25 '12 at 3:11
  • $\begingroup$ +1 @Matt Krause: +1 to your comment below the answer; your answer and commitment to giving the best answer possible is exemplary, worthy of note, and thank you for all of your hard work! $\endgroup$ – blunders Mar 27 '12 at 17:37
0
$\begingroup$

I wrote a calculator for general cases of this problem. Let's say you have 6 unique characters (A,B,C,D,E,F) and each combination is 3 characters in length (e.g. "DBF", "EAC"...). If you have 12 samples, then the collision probability is 26.7%.

https://codepen.io/Walkipedia/pen/wvzeZeM

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.