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.

A GUID (globally unique identifier) is a 32 character hexadecimal string:

http://en.wikipedia.org/wiki/Globally_Unique_Identifier

If you randomly generate 2, the chance of them being the same is incredibly small.

But what if you generate 1,000,000, what are the chances there is 1 or more duplicates in those 1,000,000?

What about 10,000,000, or 100,000,000 or even 1 billion? Each new GUID has a chance to match all those previously inserted into the set.

Graphs!

Thanks to Rawlings answer we have the following graphs:

enter image description here

enter image description here

enter image description here

share|improve this question
add comment

1 Answer

Take a look at the Wikipedia article on the Birthday Problem.

In summary, if you have $n$ possible values (here, $2^{128}$) and you take $k$ values at random, there is probability

$$ \frac{k!{n \choose k}}{n^k} $$

of NOT having a collision.

(These are very large numbers to deal with, but that article has a section on approximations that might be useful.)

Here is an example of a graph of the probability of a GUID collision occurring against number of GUIDs generated, plotted using Wolfram Alpha and the second approximation suggested by Didier Plau below.

share|improve this answer
1  
Your notation for binomial coefficients is potentially confusing. –  Did Apr 18 '11 at 10:27
1  
{n\choose k} $ $ –  Did Apr 18 '11 at 10:29
1  
Try ${n \choose k}$ for ${n \choose k}$. –  t.b. Apr 18 '11 at 10:30
2  
In the range you are interested in, $k^2/n$ is very small hence good approximations are $1-k^2/(2n)$ or $\exp(-k^2/(2n))$. –  Did Apr 18 '11 at 10:32
1  
NB although a GUID is 128-bits long, not all of those are necessarily random. Microsoft's v4 GUIDs, for example, have 4 bits fixed. If I'm correctly interpreting Wikipedia, v1 GUIDs generated on the same computer would have only 76 bits of entropy. –  Peter Taylor Apr 18 '11 at 12:26
show 8 more comments

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.