ズンドコキヨシが停止するまでの平均ズンドコ回数について

#概要
ズンドコキヨシにおいて、平均何回ズンまたはドコを出力したら「キ・ヨ・シ！」に到るかについて、初等的な算出法が見当たらなかったので今更ながら記事にしました。

高校数学までの範囲くらいで理解できる内容になっています。

どういうプログラムだったか最早忘れたという方は<a href="https://qiita.com/shunsugai@github/items/971a15461de29563bf90" target="_blank">ズンドコキヨシまとめ</a>をご参照ください。

<blockquote class="twitter-tweet"><p lang="ja" dir="ltr">Javaの講義、試験が「自作関数を作り記述しなさい」って問題だったから<br>「ズン」「ドコ」のいずれかをランダムで出力し続けて「ズン」「ズン」「ズン」「ズン」「ドコ」の配列が出たら「キ・ヨ・シ！」って出力した後終了って関数作ったら満点で単位貰ってた</p>&mdash; てくも (@kumiromilk) <a href="https://twitter.com/kumiromilk/status/707437861881180160?ref_src=twsrc%5Etfw">March 9, 2016</a></blockquote> <script async src="https://platform.twitter.com/widgets.js" charset="utf-8"></script>

# 目的
求めたいのは「ズン・ズン・ズン・ズン・ドコ」のパターンが現れるまでに何回ズンドコする（ズンorドコをプリントする）か、その期待値です。つまり、

```math
p_k: \text{k回ズンドコしたとき、k回目に初めて「ズンズンズンズンドコ」パターンが現れる確率}
```

と定義したときの

```math
E = \Sigma_{k=1}^\infty kp_k     
```

が求める値になります。

# 計算

$p_k$は「k回以上ズンドコする確率」から「k+1回以上ズンドコする確率」を引いたものであり、
「k回以上ズンドコする確率」とはすなわち「k-1回目までにパターンが現れない確率」に等しいです。
よって$q_k$を、

```math
q_k: \text{k回ズンドコしたとき「ズンズンズンズンドコ」パターンが現れない確率}
```

と定義すると、

```math
p_k = q_{k-1} - q_k \tag {1}
```

が成り立ちます。

<br>

また、$k > 5$のとき、$p_k$は「k-5回ズンドコしてもパターンが現れず、k-4回目以降からパターンが現れる確率」でもあるため、

```math
  p_k = q_{k-5} \cdot \frac{1}{2^5} \tag{2}
```

が成り立ちます。

これら(1)(2)の等式を用いると、期待値$E$は、

```math
\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でも検証してみましょう。

```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)
```

###実行結果

<img width="237" alt="スクリーンショット 2020-05-10 22.57.44.jpeg" src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/123809/aaa863f3-2c60-fe69-a4cb-87ce70ac1c3f.jpeg">

確かに平均はきちんと32付近になりました。

ヒストグラムは以下のようになっています。
（横軸がズンドコ回数、縦軸が頻度）

<img width="538" alt="スクリーンショット 2020-05-10 22.57.54.png" src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/123809/eef25db8-f2c3-5a80-1a05-06036d8413b1.png">

かなり左に偏った分布になっていることがわかります。多くの場合は平均よりもかなり早くキ・ヨ・シに至るようです。

以上です。

#####参考文献

- [コインを振る回数の期待値](https://jp.quora.com/%E9%80%A3%E7%B6%9A%E3%81%97%E3%81%A6n%E5%9B%9E%E8%A3%8F%E3%81%8C%E5%87%BA%E3%82%8B%E3%81%BE%E3%81%A7%E3%82%B3%E3%82%A4%E3%83%B3%E3%82%92%E6%8C%AF%E3%82%8A%E7%B6%9A%E3%81%91%E3%82%8B%E3%81%A8%E3%81%84%E3%81%86)
- <a href="https://qiita.com/mpyw/items/321c5485236615ca4664#comment-adb7fba3e87b85b4c18e" target="_blank">確率過程の理論によるズンドコ回数の算出法</a>