前回は"初期Seed厳選"における最適戦略を考察するために, 目的Seedを得るまでにかかる時間の期待値を計算した.
ただし, あくまで期待値は期待値であって, 実際に目的Seedを得るまでの時間はバラつきが生じる. あまりにもバラつきが大きい戦略を取ってしまうと, いわゆる確率の"下振れ"を引いてしまったときに何時までたっても厳選が終わらない, といったことも考えられる.
今回は, このバラつきを考慮に入れて, 確率の下振れを引いた場合でもなるべく少ない時間で厳選を終わらせる方法を考察する.
乱数生成器の周期が十分に大きく, 各出力が独立であると見做してよいことを仮定する. すなわち, 目的Seedの出現確率が消費数によらず常にとして良いものとする.
初期Seedから目的Seedまでに必要な消費数を[adv]として, 閾値[adv]に対してを満たすならばその初期Seedを採択するという戦略を考える.
一回の試行にかかる時間(初期Seedを得るまでにかかる1回あたりの時間)を[s], 乱数消費速度を[adv/s]とする.
このとき, 試行回数[回]で条件を満たす初期Seedを得られたのであれば, 最終的に目的Seedを得るまでにかかった時間[s]は
と表される.
標本のバラつきを評価する指標には, "分散"と"標準偏差"の二種類が存在する. 分散は平均値からの偏差の2乗によって計算され, その平方根を取ることで標準偏差が得られる.
平均を, 標準偏差をとする正規分布において, 約の
標本がの中に含まれることが知られている.
また, 正規分布に従わない一般の分布の場合でも, 少なくともの標本はの範囲内に入ることが知られている[1].
すなわち, 目的のSeedを得るまでにかかる時間は概ね[s]で抑えられると言い換えられるので, これを最小化することを考える.
を計算するために, まずは分散を考える.
が定数と見なせることと試行回数と必要な消費数が独立に決まることに注意すると,
と変形される.
前回の考察にて, 初期Seed厳選が成功確率のベルヌーイ試行と見做せること, ベルヌーイ試行が成功するまでの繰り返した際の試行回数は幾何分布に従うことが分かっている.
幾何分布の分散は, ベルヌーイ試行の成功確率を用いて
として表される. を用いて書き直すことで
が導出される.
前回の考察と同様に, がからまでの離散一様分布に従うと見做すことで,
が導出される.
導出結果を纏めると,
となる.
また, を仮定してマクローリン近似を行うことで,
と近似できる.従って, 目的Seedを得るまでにかかる時間の標準偏差
が計算できた.
導出された標準偏差と前回の期待値の近似の結果を用いて, 今回最小化を試みる目的関数を次のように定義する.
パラメータを用意してを計算する. 今回はそれぞれ
とした[2].
の計算式を Wolfram Alphaに投入する と次のようになる.
前回と同様に, Wolfram Alphaに最小値を計算させる.
実験より, 目的関数の最小値を与える閾値が求められた.
(以上, 常体終わり)
前回の期待値の結果()と比較してみましょう.
今回の最小値が, であったことを踏まえると, ざっくり[s]の短縮になったようです.
それなりに効果がありそうだと期待していたのですが, 思ってたほどではありませんでした.
とはいえ, 例えばの値をみる と今回の最小値の二倍近く, 1日以上かかる可能性がある事が分かります.
この結果は, 最適戦略の重要性を示す一つの成果といえそうです.
前回と同様に, の最小値を与えるようなを考えたいのですが…
流石にこの式を解析的に解くのは難しそう…
一応, Excelの近似曲線機能と睨めっこしながらあれこれ試行錯誤したところ,
が良さそうな近似を与えることが分かりました.
実際, 今回のパラメータ(, , )を代入すると,
となり, 真値に対する誤差が に収まっています.
https://bigdata-analysis.hatenablog.com/entry/68_95_99-rule ↩︎
BDSPにおいてg7TID
の1点狙いをする場合のモデル. 前回とは異なり, 自動化環境にて再測定した値を使用している. ↩︎