ポアソン到着とタイムスタンプ

はじめに

ここでは以下の問題を考えます．

ファイル名を秒からミリ秒にするの、ランダムな分布を仮定するとしても誕生日だから1000倍の余裕ができるというわけではなくもっと小さいんじゃないかなと直感的には予想するけどどれぐらいなんだろう。

久我山菜々+ (@nonamea774) May 17, 2023

衝突確率とタイムスタンプの間隔，リクエストの到着率の関係は [1] で既に議論されているので，ここではもう少し具体的な数値を挙げて計算します．

衝突確率

ポアソン分布に従って，一定期間（たとえば1日）の間にリクエストが平均 $\lambda$ 件到着する状況を考える． 期間を $N$ 等分したタイムスタンプを用いてリクエストを処理するとする． このとき，リクエストのタイムスタンプが衝突する確率 $p$ を求めたい． そのために，余事象として衝突しない確率を考える． 最初のタイムスタンプ1区間のうちに1件到着し，以降1件も到着しない確率は $$\frac{\lambda }{N}{e}^{-\lambda /N}\times e^{-\lambda /N}\times \cdots \times e^{-\lambda /N}=\frac{\lambda }{N}{e}^{-\lambda }$$ である． タイムスタンプを1つ選ぶ方法は $N$ 通りあるので， 一定期間のうちに1件到着し，なおかつタイムスタンプが衝突しない確率 $q_1$ は $$q_1=N\times \frac{\lambda }{N}{e}^{-\lambda }$$ となる． 次に，一定期間のうちに2件到着する場合を考える． たとえば，最初のタイムスタンプ2区間のうちに1件ずつ到着し，以降1件も到着しない確率は $$\frac{\lambda }{N}{e}^{-\lambda /N}\times \frac{\lambda }{N}{e}^{-\lambda /N}\times e^{-\lambda /N}\times \cdots \times e^{-\lambda /N}={\left(\frac{\lambda }{N}\right)}^2{e}^{-\lambda }$$ である． タイムスタンプを2つ選ぶ方法は $N(N-1)/2$ 通りあるので， 一定期間のうちに2件到着し，なおかつタイムスタンプが衝突しない確率 $q_2$ は $$q_2=\frac{N(N-1)}{2}\times {\left(\frac{\lambda }{N}\right)}^2{e}^{-\lambda }$$ となる． 同様にして，一定期間のうちに $k$ 件到着し，なおかつタイムスタンプが衝突しない確率 $q_k$ は，二項係数を用いて次のように書ける． $$q_k=\left(\genfrac{}{}{0ex}{}{N}{k}\right){\left(\frac{\lambda }{N}\right)}^k{e}^{-\lambda }$$

よって，二項定理より衝突する確率 $p$ は以下のようになる． $$p=1-\sum _{k=0}^N{q}_k=1-\sum _{k=0}^N\left(\genfrac{}{}{0ex}{}{N}{k}\right){\left(\frac{\lambda }{N}\right)}^k{e}^{-\lambda }=1-e^{-\lambda }{(1+\frac{\lambda }{N})}^N$$

また，到着率 $\lambda$ について整理すると， ランベルトのW関数を用いて次のように書ける． $$\lambda =-N(W_{-1}(-\frac{\sqrt[N]{1-p}}{e})+1)$$

近似式

$\alpha =\lambda /N$ とおく． $e^{-x}$ のテイラー展開を使うと次式を得る． $$p=1-e^{-\lambda }{(1+\frac{\lambda }{N})}^N=1-{\left(\frac{1+\alpha }{e^{\alpha }}\right)}^N\approx 1-{(1-\frac{{\alpha }^2}{2})}^N$$ これと ${(1-x)}^N\approx 1-Nx$ より衝突確率 $p$ は次のように近似できる． $$p\approx \frac{N{\alpha }^2}{2}=\frac{{\lambda }^2}{2N}$$

また，リクエストの到着率 $\lambda$ は次のように近似できる． $$\lambda \approx \sqrt{2Np}$$

数値例

1日あたりの衝突確率を1%まで許容しながらリクエストを秒単位のタイムスタンプで処理する場合， どのくらい多くののリクエストを処理できるか考えます． 1日は86400秒なので $N=86400,p=0.01$ となる到着率 $\lambda$ を求めればよいです． $$\lambda \approx \sqrt{2\times 864}=24\sqrt{3}\approx 42$$ 実際には41.68件/日なのでそこそこ正確です． 1日あたり1%まで許容しても40件程度しか処理できないのは意外でした． ミリ秒単位で処理する場合は $$\lambda \approx \sqrt{2\times 864000}\approx 1315$$ となり，およそ32倍のリクエストを処理できるようになります． 1000倍にならない点が誕生日のパラドックスに似ているかもしれません． 他のケースについて計算した結果を以下に示します．

更新履歴

• 2023-06-14: 公開

Permanent ID of this document: 834c86967799b6e69d4c5ea9fbb76c8b

参考文献