# Probability of duplicate GUID

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:

-

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.

-
Your notation for binomial coefficients is potentially confusing. – Did Apr 18 '11 at 10:27
{n\choose k}  – Did Apr 18 '11 at 10:29
Try ${n \choose k}$ for ${n \choose k}$. – t.b. Apr 18 '11 at 10:30
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
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