誕生日のパラドックスから考察する、個人ブログURLに必要なランダムビット数

tl;dr

  • ブログのURLにランダム値を使うとして、必要なビット数は何桁だろうか
  • ハッシュ衝突の問題は「誕生日のパラドックス」と同じ状況設定
  • 数学的な裏付けの元で、ランダムビットを28桁確保すれば十分

Intro

「個人ブログのパーマリンクに関する最適戦略について」において、

  • {{base-url}} / blog / {{year}} / {{random}}

というURLをこのブログに使うことに決めました。しかし、 {{random}} はどれだけのビット数を使い、どのようなフォーマットを使うべきでしょうか。

幸い、 {{year}} を入れているので、「永遠」を考える必要はありません。 せいぜい「1年」でどれだけの記事を書くのかを見積れば良いことになります。

毎日、1記事を書いたとして \(365\) 記事、多めに見積もって \(400\) 記事とします。 さらに毎日、 \(5\) 記事書くことを上限と仮定すると \(5 \times 400 = 2000\) 記事となり、せいぜい \(2000\) 記事がある場合に必要なランダムビット数を求めたいと思います。

誕生日のパラドックス

「誕生日のパラドックス - Wikipedia」より、

誕生日のパラドックス（たんじょうびのパラドックス、英: birthday paradox）とは「何人集まれば、その中に誕生日が同一の2人（以上）がいる確率が、50%を超えるか?」という問題から生じるパラドックスである。鳩の巣原理より、366人（閏日も考えるなら367人）集まれば確率は100%となるが、しかしその5分の1に満たない70人しか集まらなくても確率は99.9%を超え、50%を超えるのに必要なのはわずか23人である。

誕生日のパラドックスは論理的な矛盾に基づいているという意味でのパラドックスではなく、結果が一般的な直感と反しているという意味でのパラドックスである。

Wikipediaでも計算してありますが、ここでも計算しておきます。

きちんと問題として整理すると以下のようになります。

Aさんを含め、n人がいる。一年を365日とし、誕生日は全ての日で等確率とする。

  1. Aさんと同じ誕生日の人が存在する確率 \(P_1\)
  2. 同じ誕生日の人が存在する確率 \(P_2\)
  3. \(P_1\) と \(P_2\) が \(50\) %を超えるのにそれぞれ必要な人数 \(n_\text{min1}\), \(n_\text{min2}\)

  1. Aさんと同じ誕生日の人が存在する確率 \(P_1\)

    余事象で求める。

    Aさん以外の人は \(\frac{364}{365}\) の確率でAさんの誕生日と衝突しない。 Aさん以外の人は \(n-1\) 人存在するので、

    \[ P_1 = 1 - \qty(\frac{364}{365})^{n-1} \]

  2. 同じ誕生日の人が存在する確率 \(P_2\)

    余事象で求める。

    n人の誕生日が異なる確率は \[ \frac{364}{365}\cdot\frac{363}{365}\cdot\frac{362}{365}\cdots\frac{365-(n-1)}{365} = \frac{{}_{364}\mathrm{P}_{n-1}}{365^{n-1}} = \frac{{}_{365}\mathrm{P}_n}{365^n}\]

    よって \[ P_2 = 1 - \frac{{}_{365}\mathrm{P}_n}{365^n} \]

  3. \(P_1\) と \(P_2\) が \(50\) %を超えるのにそれぞれ必要な人数 \(n_\text{min1}\), \(n_\text{min2}\)

    \(n_\text{min1}\) については計算できる。

    \begin{aligned} P_1 = 1 - \qty(\frac{364}{365})^{n-1} &> 0.5 \\\
    0.5 &> \qty(\frac{364}{365})^{n-1} \\\
    \log_2(0.5) &> (n-1)\log_2\qty(\frac{364}{365}) \\\
    -1 &> (n-1)(-0.003958) \\\
    253.65 &< n \end{aligned}

    よって \(n_\text{min1}=254\) となる。

    \(n_\text{min2}\) については面倒なので、Pythonを用いて図示する。

    import matplotlib.pyplot as plt
import numpy as np

memo = np.full(400, -1.0)
def NPn (n):
    """
    余事象の確率
    n人の誕生日が異なる確率
    """
    if n == 0 or n == 1:
        memo[0] = 1
        return memo[0]
    elif n >= 366:
        return 1;
    elif memo[n] != -1:
        return memo[n]
    else:
        p = NPn(n-1) * ((365-(n-1))/365.0)
        memo[n] = p
        return memo[n]

def Pn (n):
    """
    n人のうち、2人以上誕生日が同じ確率
    """
    return 1 - NPn(n)

n = 70
with plt.style.context(('science-transparent')):
    y = [Pn(i) for i in range(n)]
    plt.plot(y)

    plt.xlabel('n')
    plt.ylabel('P_n')

    plt.axhline(0.5, color='C1')
    n_min2 = np.searchsorted(y, 0.5)
    plt.annotate('({}, {:.2f})'.format(n_min2, y[n_min2]),
                 (n_min2, y[n_min2]), (n_min2-15, 0.8),
                 arrowprops = dict(arrowstyle='-|>', mutation_scale=20))

    plt.show()

    グラフから、 \(n_\text{min2} = 23\) 。

上記のとおり \(n_\text{min1} = 254\), \(n_\text{min2} = 23\) となり \(P_\text{min2}\) は直感よりも少ないように思います。

直感との乖離の理由は「自分と同じ誕生日の人が存在する確率」と「同じ誕生日の組が存在する確率」を混同してしまうからです。

ランダム値の衝突

今回問題にしているようなランダム値の衝突については、 「あるひとつのランダム値が衝突する事象」ではなく、「どれでもいいのでランダム値が衝突する事象」を考える必要があるので、 まさに誕生日のパラドックスと同じ状況設定となります。

誕生日のパラドックスでは365個の集合でしたが、今回は変数 \(N\) とします。

前段の \(P_2\) を参考に、 \(N\) 個の集合から \(n\) 個ランダム値を取ってきたときに、同じ値が存在する確率 \(p\) は次の形となります。

\begin{aligned} p &= 1 - \frac{N-1}{N}\cdot\frac{N-2}{N}\cdot\frac{N-3}{N}\cdots\frac{N-(n-1)}{N} \\\
&= 1 - \qty(\qty(1-\frac{1}{N})\qty(1-\frac{2}{N})\qty(1-\frac{3}{N})\qty(1-\frac{n-1}{N})) \\\
&= 1 - \prod_{m=1}^{n-1}\qty(1-\frac{m}{N}) \end{aligned}

ここで、ネイピア数のテイラー展開は次の形です。 \(x\) が十分小さいときは1次までの近似が使えます。

\begin{aligned} e^{-ax} &= 1 - ax + a^2\frac{x^2}{2!} - a^3\frac{x^3}{3!} + a^4\frac{x^4}{4!} + \cdots \\\
&\approx 1 - ax \end{aligned}

\(N\) はランダム値の全体総数なので、 \(\frac{i}{N}\) は十分小さく、ネイピア数のテイラー展開から近似を使えます。

\begin{aligned} p = 1 - \prod_{m=1}^{n-1}\qty(1-\frac{1}{N}m) &\approx 1 - \prod_{m=1}^{n-1}\exp\qty(-\frac{1}{N}m) \\\
&= 1 - \exp\qty(\sum_{m=1}^{n-1}\qty(-\frac{m}{N})) \\\
&= 1 - \exp\qty(-\frac{1}{N}\sum_{m=1}^{n-1}m) \\\
&= 1 - \exp\qty(-\frac{n(n-1)}{2N}) \end{aligned}

さらに \(n\) について変形します。途中、 \(n\) が十分大きいことから、定数の減算を無視しました。

\begin{aligned} \exp\qty(-\frac{n(n-1)}{2N}) &= 1-p \\\
-\frac{n(n-1)}{2N} &= \ln(1-p) \\\
n(n-1) &= -2N\ln(1-p) \\\
n^2 &\approx 2N\ln\qty(\frac{1}{1-p}) \\\
n &= \sqrt{2N\ln\qty(\frac{1}{1-p})} \end{aligned}

数値計算

Nが与えられている場合

ランダム値の大きさ(\(N\))が与えられている場合、何個ランダム値を取り出したら(\(n\))衝突するでしょうか。 なお \(p=0.5\) とします。

\begin{aligned} n = \sqrt{2N\ln\qty(\frac{1}{1-0.5})} &= \sqrt{2N\ln2} \\\
&\approx 1.1774\sqrt{N} \\\
&\approx \sqrt{N} \end{aligned}

最後の近似はオーダーを見積もるためにとても雑な近似を行いました。

もしランダムビットが 64bit の場合、ランダム値の集合は \(2^{64}\) となり、 \(2^{32} = (42.9\text{億})\) 個(WolframAlpha)のランダム値を生成したら、確率 \(0.5\) で衝突することになります。

Nを求めたい場合

逆に今回私は試行回数、1年 \(2000\) 記事(\(n=2000\))からランダム値の大きさ(\(N\))を求めたいと思っています。 なお、ランダム値の大きさ \(N\) はビット数 \(b\) を用いて \(N=2^b\) と書けます。

衝突する確率 \(p\) は \(1\) %と仮定します。

\begin{aligned} n &= \sqrt{2N\ln\left(\frac{1}{1-0.01}\right)} \\\
2000 &= \sqrt{2N\ln\left(\frac{1}{0.99}\right)} \\\
2000^2 &= 2N \cdot 0.0100 \\\
N = 2^b &= 1000 \cdot 2000 \cdot 100 \\\
b &= 27.5 \end{aligned}

以上、ランダムビット数は28桁あれば十分ということになります。

16進数の表記を使えば1文字で4ビットの自由度があるので、結局、8文字あれば十分ということが分かりました。

まとめ

誕生日のパラドックスを導入としてランダム値の衝突問題(ハッシュ衝突問題)について考えました。

長々書いてきましたが、数学的な裏付けのもとで必要なランダムビット数が分かり、パーマリンクのフォーマットを決めることができました。

次の記事「ox-hugo用のorg-captureテンプレートについて」ではこのフォーマットを実現するためのox-hugoの運用について書きたいと思います。

参考