Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

On a site that I operate I use several layers of protection for our subscription content. Among the other protections, each content item is placed into a folder with a randomly generated 19-character name. That name can include numbers, lowercase letters, and uppercase letters.

While it will not really lower the benefit provided by this layer of protection for a second file to end up in a folder, I am curious about the chances of that happening. That leads me to two related questions:

  1. Assuming that we have 2500 files/folders, what is the chance that the next folder we generate will be a repeat?
  2. How many folders must exist for the chance of repetition to rise above 1%?
share|improve this question
add comment

2 Answers

up vote 3 down vote accepted

Let's say you generate $K$-character folder names from an alphabet consisting of $A$ different symbols, and you currently have $N$ distinctly named folders.

The chance of a particular folder name being generated is $1 / A^K$. The chance that your next folder name matches one that already exists therefore $N/A^K$.

For this to be above a particular value $p$, you need $N > pA^K$.

For you, you have $K=19$, $A=62$ and $N=2500$, so the chance of a repeat is $2500/62^{19}$, whcih is around 1 part in $5\times 10^{30}$, i.e. vanishingly small.

For there to be a greater than 1% chance of a collision, you need $N > 0.01 \times 62^{19} = 10^{32}$ folders.

Note that since each folder name takes up around 20 bytes (19 characters plus a null character), you would need in excess of $10^{24}$ GB of disk space just to store the names of this many folders, never mind their contents.

share|improve this answer
add comment

There are a total of $62^{19} \approx 1.136 \times 10^{34}$ possible 19-character case-sensitive alphanumeric strings.

  1. Thus, assuming you have 2500 distinct folders already, the chance of the next folder generated being a repeat is $\frac{2500}{1.136 \times 10^{34}} \approx 2.200 \times 10^{-31} $.

  2. (a) If you are asking what the probability of any two folder names colliding, then this is a classic birthday problem. The probability that given $n$ folders, there is at least one repeat, is given by $$ p(n) = 1 - \frac{n! \cdot {62^{19} \choose n}}{62^{19n}} ,$$ but this is expensive to compute, so we approximate by $$ p(n) \approx 1 - e^{-n(n-1)/(2 \times 62^{19})}.$$ Solving for $p(n)=0.01$ gives $n \approx 1.5 \times 10^{16}$ folders required.

    (b) If, on the other hand, you are asking how many folders are needed for the probability of the next folder colliding to be at least 0.01, then Chris Taylor's answer covers that superbly.

share|improve this answer
    
In the second part you're computing the chance that there is a collision in $n$ random folders. I think the OP was asking how large should $n$ be such that if he had $n$ distinct folders, the next one generated had greater than a 1% chance of being a repeat. –  Zach Langley Feb 15 '12 at 18:26
    
@ZachLangley: Good point. I may have misinterpreted the question, although I do think the way the OP worded it was a bit ambiguous. I'll rewrite my answer to mention that. –  Yun William Yu Feb 15 '12 at 18:30
    
I was asking the question that Chris answered, but 2.a) provides good information too. –  Jeffrey Blake Feb 15 '12 at 18:36
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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