UUID (version 4) における衝突確率を計算する

UUID というのは、全世界・全時間において一意性を持った識別子とされています。RFC 4122 の言葉を借りると、

A UUID is 128 bits long, and can guarantee uniqueness across space and time

http://www.ietf.org/rfc/rfc4122.txt

とされています。

ですが、128 bit という有限長なんだから $2^{128}$ 回試行すれば少なくとも 1 回は生成した UUID が衝突するということになります。UUID は万能じゃねーんだ。冷静になれ。 UUID ってのは一意性が「保証」されているわけじゃなく、「実用上は一意と見做せる」ということになります。ですから、衝突する確率というのは 0 にはなりません。じゃぁ、果たしてどのくらいの確率で衝突が発生するのか、計算してみましょう。

計算のまえに結論を言う。 $n$ 回 UUID を生成したときに衝突が発生する確率は $1-\exp\left(-\frac{{n}^2}{2^{123}}\right)$ くらい。試行回数に対する衝突確率の伸びをグラフ化するとこんなかんじ。 $x$ 軸はログスケールな。

前提

確率的に計算できそうなの UUID の Version 4 しかなさそうです。Version 4 では、128 bit のうち、122 bit にランダムな数値をセットして UUID とします (残りの 6 bit は固定値です)。

定式化

ここでは、「version 4 の方法で $n$ 回 UUID を生成したとき、それらが 1 つでも衝突してしまう確率 $P$ 」を求めます。 "1 つでも"というところからピンと来ると思いますが、これは "衝突が一切発生しない" という事象に対する背反事象になります。このため、まずは衝突が一切発生しない確率をもとめ、それを 1 から引くという考え方をするのが王道です。

計算

順を追って考えましょう。

$n$ 回の試行のうちの、最初の 1 回目を考えます。このとき、衝突する UUID は存在しないので、衝突しない確率は 1 (100 %) です。
$n$ 回の試行のうちの、2 回目を考えます。このとき、1 回目に生成した UUID と衝突する可能性があります。UUID として発生し得るパターンは $2^{122}$ パターンあるので、衝突する確率は $\frac{1}{2^{122}}$ になり、衝突しない確率は $1-\frac{1}{2^{122}}$ になります。
$n$ 回の試行のうちの、3 回目を考えます。このとき、1 回目に生成した UUID、あるいは 2 回目に生成した UUID と衝突する可能性があります。したがって、衝突する確率は $\frac{2}{2^{122}}$ になり、衝突しない確率は $1-\frac{2}{2^{122}}$ になります。
...
$n$ 回の試行のうちの、n 回目を考えます。このとき、1 回目から $n-1$ 回目に生成した UUID と衝突する可能性があります。したがって、衝突する確率は $\frac{n-1}{2^{122}}$ になり、衝突しない確率は $1-\frac{n-1}{2^{122}}$ になります。

以上から、n 回の試行において衝突が一切発生しない確率は、

$1 \cdot \left(1-\frac{1}{{2}^{122}}\right) \cdot \left(1-\frac{2}{{2}^{122}}\right) \cdots \left(1-\frac{n-1}{{2}^{122}}\right)=\prod_{i=1}^{n-1}\left(1-\frac{i}{{2}^{122}}\right)$

ということになります。従って、衝突が発生する確率 $P$ は、 $P=1-\prod_{i=1}^{n-1}\left(1-\frac{i}{2^{122}}\right)$ です。

近似しましょう

で、こんな式を見せられても、実値を計算するのがマジでダルいですから、近似しましょう。 $1-\frac{i}{2^{122}}$ というのを何とかして綺麗にしてやりたい。ここで、指数関数のテイラー展開を思い出すと、 $x \ll 1$ のとき、 ${e}^{x} \approx 1 + x$ です。試行回数 $n$ が $\frac{i}{2^{122}} \ll n$ となる範囲を考えることにすると、この指数関数のテイラー展開を利用して、 $1-\frac{i}{{2}^{122}} \approx \exp\left(-\frac{i}{{2}^{122}}\right)$ と近似できます。

これを $P$ の式に代入し、おなじみの公式 $\sum_{i=1}^{n-1}i=\frac{n(n-1)}{2}$ を使うと、 $P\approx 1-\exp\left(-\frac{1}{2^{122}}\frac{n(n-1)}{2}\right)$ が導けます。

${n}^2 \gg n$ とすれば、 $P\approx 1-\exp\left(-\frac{{n}^2}{{2}^{123}}\right)$ になります。かなりきれいになりました。

じゃぁ衝突確率が $p$ になるときの試行回数 $n$ はどのくらいなの

衝突が発生する確率 $P$ が $p$ になるための試行回数 $n$ を求めてみましょう。

$1-\exp\left(-\frac{{n}^2}{2^{123}}\right) \approx p$ を $n$ に対して解けば良いです。これ、わりとかんたんで、 $n\approx \sqrt{2^{123} \ln{\frac{1}{1-p}}}$ になります。これをグラフにしてみると以下のようなかんじになります。