"初期Seed厳選"における最適戦略の考察

(数学的な表記として正しくないものも含まれています. ご承知おきください.)

序文

乱数調整の手法は大きく二つに分かれる.

1. 初期Seed生成の脆弱性を突いて初期Seedそのものを操作することで目的のSeedを得る方法.
2. 乱数生成器の脆弱性を突いて初期Seedを特定^[1]し, その後の乱数消費の操作によって目的Seedを得る方法.

2番目の手法を用いる際, 最初に引いていた初期Seedに依って目的Seedを得るまでに超長時間の操作を要求されることがある. 目的Seedの出現頻度が余りに少ない場合に起こりがちな問題で, 乱数消費の操作時間が短く済む初期Seedを引けるまでソフトリセットを繰り返す"初期Seed厳選"をすることで対処することが多い.

このとき, どのような戦略(基準)にそって初期Seedを採択すれば, 目的Seedを得るまでにかかる時間を最小化出来るかを考察する.

事前条件

乱数生成器の周期が十分に大きく, 各出力が独立であると見做してよいことを仮定する. すなわち, 目的Seedの出現確率が消費数によらず常に

$p$として良いものとする.

初期Seed厳選のモデリング

初期Seedから目的Seedまでに必要な消費数を

$a$[adv]として, 閾値

$U$[adv]に対して

$a<U$を満たすならばその初期Seedを採択するという戦略を考える.

一回の試行にかかる時間(初期Seedを得るまでにかかる1回あたりの時間)を

$C$[s], 乱数消費速度を

$A$[adv/s]とする.

このとき, 試行回数

$N$[回]で条件を満たす初期Seedを得られたのであれば, 最終的に目的Seedを得るまでにかかった時間

$T$[s]は

$$\begin{array}{r}T=NC+\frac{a}{A}\cdots (1)\end{array}$$
と表される.

厳選時間の期待値計算

目的Seedを得るまでに掛かった時間の期待値

$E(T)$を考える.

式

$(1)$より,

$C,A$が定数と見なせることに注意すると, 期待値の線形性を用いることで

$$\begin{array}{rl}E(T)& =E(NC+\frac{a}{A})\\ & =E(N)\cdot C+E(a)\cdot \frac{1}{A}\cdots (2)\end{array}$$
と変形できる.

試行回数の期待値

初期Seed厳選は, 一回の試行において初期Seedが採択される確率

$p_{accept}$を成功確率とするベルヌーイ試行といえる.

$p_{accept}$は,

$U$回消費を行うまでに目的Seedが出現する確率だから,

$$\begin{array}{r}{p}_{accept}=1-(1-p{)}^U\end{array}$$
として表せる.

ベルヌーイ試行を成功するまで繰り返したとき, その試行回数は幾何分布に従うことが知られており^[2], 幾何分布の期待値は元となるベルヌーイ試行の成功確率の逆数となる.
すなわち

$$\begin{array}{r}E(N)=\frac{1}{p_{accept}}=\frac{1}{1-(1-p{)}^U}\end{array}$$
が導かれる.

消費数の期待値

また, 初期Seedから目的Seedまでの消費数

$a$の期待値は

$U$のみに依存して決まる. 初期Seedの事前条件により,

$a$は

$0$から

$U-1$までの離散一様分布に従うと見做してよい^[3]ため,

$$\begin{array}{r}E(a)=\frac{U}{2}\end{array}$$
と導かれる.

総括

以上より,

$$\begin{array}{r}E(T)=C\cdot \frac{1}{1-(1-p{)}^U}+\frac{U}{2A}\end{array}$$
が得られる.

$(p,C,A)$を固定して考えることで,

$E(T)$は

$U$についての関数

$f(U)$と見做せる. 従って所与の問題はこの関数の最適化問題に帰着される.

実験

パラメータを用意して期待値を計算する. 今回はそれぞれ

• $C=300$
• $A=1.2$
• $p=\frac{1}{1000000}$

とした^[4].

プロット

$f(U)$の計算式を Wolfram Alphaに投入する と次のようになる.

最小値

Wolfram Alphaは最小値の計算も出来る. 実際に解かせてみると以下の通り.

実験より,

$E(T)$の最小値を与える閾値

$U$が求められた.

(以上, 常体終わり)

所感

最小値(

$U=26832$)付近を拡大してみてみるとこんな感じの見た目をしてます.

あまり小さすぎる閾値を設定すると所要時間は跳ね上がる一方で, 大きい閾値を設定すると線形増加するので, 上手く設定してあげると幸せになれそうです.

ともあれ, きちんとパラメータを与えれば良さそうな閾値

$U$を決められることが分かって満足です.

追記

$E(T)$の最小値を与えるような

$\bar{U}>0$をパラメータ

$(C,A,p)$から計算できないかとアレコレ考えていたのですが, どうやら

$$\begin{array}{r}\bar{U}\approx \sqrt{\frac{2CA}{p}}\end{array}$$

が良い近似を与えることが分かりました. 大学数学か何かで出てきそうな近似ですね.

残念ながら証明は出来ていないのですが, 腕に覚えがある方は挑戦してみてください.

ただのマクローリン近似でした.

$|p|$が充分に小さい時,

$$\begin{array}{rl}E(T)=f(U)& \approx C\cdot \frac{1}{1-(1-pU)}+\frac{U}{2A}\\ & =\frac{C}{pU}+\frac{U}{2A}\end{array}$$
となるので, 代わりにこの関数の最小値を求めることで所与の値が導出されます.

---

1. 厳密には現在Seedを特定する場合もあるが, 説明の都合上初期Seedとして統一している. ↩︎

2. https://bellcurve.jp/statistics/course/6988.html ↩︎

3. "5以上の目が出たら振りなおす, とした場合のさいころの出目が

   $\{1,2,3,4\}$上の一様分布に従う" と類推解釈が可能. ↩︎

4. BDSPにおいてg7TIDの1点狙いをする場合のモデル. ↩︎