_power-manhattan-challenge.md

パワーマンハッタン大学チャレンジの排出確率とアルゴリズム

注意: 生成される文字列についてのネタバレを含みます。

注意: 2022/07/14 現在のアルゴリズムです。

結論

排出確率は約 0.2% です。

生成アルゴリズム

「パワーマンハッタン」の部分

i 番目の文字を決定するときに、 i 番目の文字に近い文字を選びやすくなるようになっている。 数学的に言うと i を中心とする分散 1,5 の正規乱数により i 番目の文字を決定している。 i 番目の文字の生起確率の確率密度分布を示したものが図1である。

図1: 文字ごとの生起確率

例えば1文字目の生起確率は青色の曲線に示されており、「パ」の出現確率が一番高いことがわかる。 なお、範囲外の乱数が生成された場合は再抽選されるため、該当の文字の出現確率は端の方が高くなる。

この分布を離散化する際に、絶対値の切り捨てを行っている。 すなわち $x$ の絶対値の切り捨ては $x \geq 0$ のときは通常の切り捨て $\lfloor x \rfloor$ であるが、 $x < 0$ のときは $-\lfloor -x \rfloor$ となる。

「ー」の文字について離散化を行った後の確率分布を図2に示す。

図2: 「ー」の文字を離散化した確率分布

もとの正規乱数の確率密度関数が緑で示されているのに対し、各文字の正規確率の離散分布が青色で示されている。 なお、もとの正規乱数の確率密度関数は再抽選を考慮した後の値である。

さらに「ン」が選択され、その前の2文字が「ーマ」または「ッタ」の場合一定確率で「ソ」に置き換わるようになっている。

大学etc. の部分

いくつかあるパターンの中から、「大学」が最も高い確率で選択されるようになっている。 数学的には自由度1のカイ二乗分布のスケールを $1/1.5$ 倍した分布に従う乱数によって選択される。

排出率に関する考察

1文字目を例として考える。 「パ」の選択の際に生成した乱数を確率変数 $X \sim N(0, 1.5)$ と表すと、 $X$ が再生成されない範囲にあるためには $sgn(X) \lfloor |X| \rfloor + 0 \in [0, 8]$ すなわち $X \in (-1, 9)$ であればよい。 正規分布の累積密度関数を $\Phi(x; \mu, \sigma)$ と表すと、 $Pr(X \in (-1, 9)) = \Phi(9, 0, 1.5) - \Phi(-1, 0, 1.5) \simeq 0.75$ である。 また、 $sgn(X) \lfloor |X| \rfloor = 0$ すなわち $X \in (-1, 1)$ である確率は $Pr(X \in (-1, 1)) = \Phi(1, 0, 1.5) - \Phi(-1, 0, 1.5) \simeq 0.50$ である。 したがって1文字目に「パ」が選ばれる確率は $Pr(X \in (-1, 1)) / Pr(X \in (-1, 9)) \simeq 0.67$ である。

同様に考えると、 $i$ 文字目に「パワーマンハッタン大学」の $i$ 文字目が選ばれる確率 $p_i$ は $p_i = Pr(X \in (-1, 1)) / Pr(X \in ( - i - 1, 9 - i))$ である。 ただし、 $i=0$ を最初の文字とする。

計算結果の $p_i$ は次の表のようにまとめられる。

$i$	$p_i$
0	0.662
1	0.545
2	0.507
3	0.497
4	0.495
5	0.497
6	0.507
7	0.545
8	0.662

次に、各文字が「ソ」へ変化しない確率は $Pr(Y < 1), Y \sim \chi^2(1) / 1.5$ である。 したがって $Pr(Y < 1) \simeq 0.78$ である。

以上より、「パワーマンハッタン」が生起する確率は

$$ \left( \prod_i p_i \right) Pr(Y < 1) ^ 2 \simeq 0.0041 \times 0.78^2 \simeq 0.0024 $$

すなわち 0.24% 程度である。

「大学」の生起確率は「ソ」に変化しない確率と同じである。 したがって、「パワーマンハッタン大学」の生起確率は $0.0041 \times 0.78^3 \simeq 0.0019$ となり、約 0.2% である。

実際の排出率のテスト

1000000 回生成して文字ごとの出現確率を調べた。

結果は ./test-log.txt に記されている。注意すべき点として、「ン」は「パワーマンハッタン大学」の中に複数含まれているため、生起確率はその合計値が記されている。

これを見ると、計算した生起確率と結果が一致していることがわかる。

continuous-cdf.png

probability-2nd-char.png

test-log.txt

testing for 1000000 times...
== 1th char ==
パ: 662084 (0.662084)
ワ: 215416 (0.215416)
ー: 92064 (0.092064)
マ: 25177 (0.025177)
ン: 4676 (0.004676)
ハ: 544 (0.000544)
ッ: 36 (0.000036)
タ: 3 (0.000003)
== 2th char ==
ワ: 543698 (0.543698)
ー: 178196 (0.178196)
パ: 177951 (0.177951)
マ: 75052 (0.075052)
ン: 20885 (0.020885)
ハ: 3787 (0.003787)
ッ: 397 (0.000397)
タ: 34 (0.000034)
== 3th char ==
ー: 505691 (0.505691)
ワ: 165339 (0.165339)
マ: 165282 (0.165282)
ン: 70235 (0.070235)
パ: 70019 (0.070019)
ハ: 19450 (0.01945)
ッ: 3554 (0.003554)
タ: 430 (0.00043)
== 4th char ==
マ: 496417 (0.496417)
ン: 162781 (0.162781)
ー: 161998 (0.161998)
ワ: 68786 (0.068786)
ハ: 68548 (0.068548)
パ: 19236 (0.019236)
ッ: 18796 (0.018796)
タ: 3438 (0.003438)
== 5th char ==
ン: 500416 (0.500416)
ハ: 161032 (0.161032)
マ: 160688 (0.160688)
ッ: 68389 (0.068389)
ー: 68284 (0.068284)
ワ: 18973 (0.018973)
タ: 18740 (0.01874)
パ: 3478 (0.003478)
== 6th char ==
ハ: 497961 (0.497961)
ン: 180242 (0.180242)
ッ: 161804 (0.161804)
タ: 68711 (0.068711)
マ: 68491 (0.068491)
ー: 18993 (0.018993)
ワ: 3392 (0.003392)
パ: 406 (0.000406)
== 7th char ==
ッ: 506115 (0.506115)
タ: 165178 (0.165178)
ハ: 164964 (0.164964)
ン: 140382 (0.140382)
マ: 19329 (0.019329)
ー: 3609 (0.003609)
ワ: 399 (0.000399)
パ: 24 (0.000024)
== 8th char ==
タ: 545087 (0.545087)
ン: 197946 (0.197946)
ッ: 177496 (0.177496)
ハ: 75205 (0.075205)
マ: 3786 (0.003786)
ー: 440 (0.00044)
ワ: 40 (0.00004)
パ: 0 (0)
== 9th char ==
ン: 667194 (0.667194)
タ: 215203 (0.215203)
ッ: 91855 (0.091855)
ハ: 25162 (0.025162)
マ: 539 (0.000539)
ー: 43 (0.000043)
ワ: 4 (0.000004)
パ: 0 (0)
== suffix ==
大学: 779358 (0.779358)
大丈夫: 31782 (0.031782)
大仏: 31771 (0.031771)
犬学: 31507 (0.031507)
大聖堂: 31485 (0.031485)
大名: 31377 (0.031377)
大根: 31371 (0.031371)
大将軍: 31349 (0.031349)
== パワーマンハッタン ==
hit count: 1965 (0.001965)