概要
ズンドコキヨシにおいて、平均何回ズンまたはドコを出力したら「キ・ヨ・シ！」に到るかについて、初等的な算出法が見当たらなかったので今更ながら記事にしました。
高校数学までの範囲くらいで理解できる内容になっています。
どういうプログラムだったか最早忘れたという方はズンドコキヨシまとめをご参照ください。
Javaの講義、試験が「自作関数を作り記述しなさい」って問題だったから
— てくも (@kumiromilk) March 9, 2016
「ズン」「ドコ」のいずれかをランダムで出力し続けて「ズン」「ズン」「ズン」「ズン」「ドコ」の配列が出たら「キ・ヨ・シ！」って出力した後終了って関数作ったら満点で単位貰ってた
目的
求めたいのは「ズン・ズン・ズン・ズン・ドコ」のパターンが現れるまでに何回ズンドコする（ズンorドコをプリントする）か、その期待値です。つまり、
p_k: \text{k回ズンドコしたとき、k回目に初めて「ズンズンズンズンドコ」パターンが現れる確率}
と定義したときの
E = \Sigma_{k=1}^\infty kp_k
が求める値になります。
計算
$p_k$は「k回以上ズンドコする確率」から「k+1回以上ズンドコする確率」を引いたものであり、
「k回以上ズンドコする確率」とはすなわち「k-1回目までにパターンが現れない確率」に等しいです。
よって$q_k$を、
q_k: \text{k回ズンドコしたとき「ズンズンズンズンドコ」パターンが現れない確率}
と定義すると、
p_k = q_{k-1} - q_k \tag {1}
が成り立ちます。
また、$k > 5$のとき、$p_k$は「k-5回ズンドコしてもパターンが現れず、k-4回目以降からパターンが現れる確率」でもあるため、
p_k = q_{k-5} \cdot \frac{1}{2^5} \tag{2}
が成り立ちます。
これら(1)(2)の等式を用いると、期待値$E$は、
\begin{eqnarray}
E &=& \Sigma_{k=1}^\infty kp_k \\
&=& \Sigma_{k=1}^\infty k(q_{k-1} - q_k) \tag{(1)より} \\
&=& \Sigma_{k=0}^\infty q_k \tag {うまく相殺されてこうなる} \\
&=& \Sigma_{k=5}^\infty q_{k-5} \\
&=& 2^5 \cdot \Sigma_{k=5}^\infty p_k \tag{(2)より} \\
&=& 2^5 (1 - \Sigma_{k=1}^4 p_k) \tag{*} \\
&=& 2^5 (1 - 0)
\end{eqnarray}
と計算できます。
(*)の導出には「$p_k$の総和は1であること」つまり「無限にズンドコしていけばいつか必ずパターンが現れる（現れない確率が0に収束する）」ことを利用しています。
よって、「キ・ヨ・シ！」までの平均ズンドコ数は$2^5 = 32$回ということがわかりました。
実際に試してみる
以上の結果が正しいか、Pythonでも検証してみましょう。
import random
import pandas as pd
ZUNDOKO_PATTERN = ['ズン', 'ズン', 'ズン', 'ズン', 'ドコ']
# ズンドコキヨシを実行し、ズンドコ回数を返却する関数
def do_zundoko():
zundoko_list = []
while zundoko_list[-5:] != ZUNDOKO_PATTERN:
zundoko_list.append(random.choice(['ズン', 'ドコ']))
return len(zundoko_list)
# 100万回実行してリストに格納
zundoko_len_list = []
for i in range(1, 1000001):
zundoko_len_list.append(do_zundoko())
# 実行結果の統計量やヒストグラムを表示
df = pd.DataFrame(zundoko_len_list, columns=["zundoko length"])
print(df.describe())
df.hist(bins=50)
実行結果
確かに平均はきちんと32付近になりました。
ヒストグラムは以下のようになっています。
（横軸がズンドコ回数、縦軸が頻度）
かなり左に偏った分布になっていることがわかります。多くの場合は平均よりもかなり早くキ・ヨ・シに至るようです。
以上です。