エレガントに解いてみる～連続して先手番を引いてもクレームを入れないであげておくれよの巻～

将棋ソフトPonanzaのメイン開発者である山本一成さんのnote。

問コインを100回投げて、表か裏が10回連続で出る確率は？

道に落ちている食べ物は拾って食べてしまい，ネットに落ちている数学の問題は解いてしまうのが人間の性というやつです。今日はこの問題をエレガントに解いちゃいましょう。数式の関係でスマホでは読みにくいのでPCで読んでください。

山本さんの記事ではモンテカルロ法を用いて，そこそこ正しい値8.773％を出しています。何の工夫もせずに取りあえずだいたいの値が分かる方法というのは偉大です。山本さんは知人の数学者さんに"エレガント"に解いてもらったらしく，正解は8.6659％だそうです。しかしそのエレガントな解法が何かは書いていません。

今日はこの厳密解を数学を使って導出し，手計算でそこそこ正しい値を計算しましょう。そして最後にこの結果が関係ありそうな現実の問題について考えてみます。

漸化式を出そう

$n$ 回コインを投げて，表か裏が10回連続で出る確率を $p[n]$ とします。

$n=1,\dots,9$ のとき，表か裏が10回連続で出るなんてあり得ないので\begin{align}
p[1]=p[2]=\cdots=p[9]=0
\end{align} $n=10$ のとき，表が連続10回と裏が連続10回の2通りあるので\begin{align}
p[10]=2\times \cfrac{1}{2^{10}}=\cfrac{1}{2^{9}}.
\end{align} $n\geq 11$ のとき，表か裏が10回連続で出るのは， $n-1$ 回目までに表か裏が10回連続で出るか， $n-10$ 回目までは表か裏が10回連続で出ずに，そこから $n-10$ 回目の出目と異なる出目が10回連続で出るかの2通りで，それらは同時には起こらないので\begin{align}
p[n]=p[n-1]+\cfrac{1}{2^{10}}(1-p[n-10]).
\end{align}というわけで，次の漸化式が得られました。

\begin{align}
&p[1]=p[2]=\cdots=p[9]=0,~~ p[10]=\cfrac{1}{2^{9}}.&\\
&p[n]=p[n-1]+\cfrac{1}{2^{10}}(1-p[n-10])\hspace{5mm} (n\geq 11). &
\end{align}

まずはエレファントに解いてみる

f:id:egory_cat:20180218003049p:plain

コンピュータを使って $p[100$ ] を計算してみましょう。

長さ10の循環リストを用意してぐるぐる回りながら計算するのが効率良さそうですが，この程度なら長さ100のリストを用意して計算してもいいでしょう。

計算しました。答えは\begin{align}
\frac{54926694791702732340559056895}{633825300114114700748351602688}\fallingdotseq 0.086659 =8.6659\%
\end{align}です。漸化式をゴリゴリと力業で計算したのでエレファントな解答です。

四色定理 - Wikipedia

複雑に思える問題に対して簡潔にまとまった比較的短い証明（解答）を、エレガントな証明（解答）と言うことがある。四色定理のある種「力業な証明」は、これと対極にあるものとして揶揄を込めて「エレファント（象）」な証明とも言われた。

エレガントな解法

本題はここから。この問題をエレガントに解いてみましょう。

ですが上で出した答えを見て分かるように，どんなにうまく解いても厳密解を出そうとすると地獄のような計算になることは必至です。そこで出来る限り厳密に解いて，最終的には近似値を出すことにましょう。

計算に使う道具は母関数です。数列 $a[0], a[1], a[2], a[3],\ldots$ に対し，べき級数\begin{align}f(x)=\sum_{n=0}^\infty a[n] x^{n}\end{align}を数列の母関数と呼びます。このべき級数は一般には収束するかどうかも問わないのですが，たまたま有理関数になることもあります。

そして，母関数が有理関数になったら，数列 $a[n]$ はいい性質を持っている（きれいな数列である） と捉えるのが母関数の基本的な考え方です。

例えば\begin{align}
\cfrac{1}{1-x}=1+x+x^{2}+x^{3}+\cdots
\end{align}という展開はよく知られています。これは $1,1,1,1,\dots$ という数列の母関数が \begin{align} \cfrac{1}{1-x}\end{align} という有理関数である事を示しています。

さらにこの展開の両辺を $x$ で微分すると，\begin{align}
\cfrac{1}{(1-x)^{2}}=1+2x+3x^{2}+4x^{3}+\cdots
\end{align}となります。これは $1,2,3,4,\dots$ という数列の母関数が \begin{align}\cfrac{1}{(1-x)^{2}}\end{align}である事を示しています。

$1,1,1,1,\dots$ や $1,2,3,4,\dots$ という数列は凄くシンプルな数列ですが，そのことが母関数が有理関数になっているという形で表れているのです。

母関数を扱うときは，次の公式が重要です。

公式： $g(x)$ が定数項の無いべき級数(例えば $g(0)=0$ を満たす多項式)なら\begin{align}
\cfrac{1}{1-g(x)}=1+g(x)+g(x)^2+g(x)^3+\dots
\end{align}

大抵の場合はこの公式と，上でやったような微分のテクニックだけで知っていれば十分です。

$p[n]$ の母関数

さて，数列 $p[n]$ の母関数を求めてみましょう。漸化式を再掲します。

\begin{align}
&p[1]=p[2]=\cdots=p[9]=0,~~ p[10]=\cfrac{1}{2^{9}}.&\\
&p[n]=p[n-1]+\cfrac{1}{2^{10}}(1-p[n-10])\hspace{5mm} (n\geq 11). &
\end{align}

数列 $p[n]$ の母関数を $f(x)$ で表しましょう。\begin{align}
f(x)=\sum_{n=1}^\infty p[n] x^{n}
=\cfrac{1}{2^{9}} x^{10}+
\left(
\cfrac{1}{2^{9}}+\cfrac{1}{2^{10}}
\right)
x^{11}+\cdots.
\end{align} $p[n]$ の漸化式を母関数の言葉で書き換えると次のようになります。\begin{align}f(x)-\cfrac{1}{2^{9}}x^{10}=xf(x)+\cfrac{1}{2^{10}}
\left(\cfrac{x^{11}}{1-x}-x^{10}f(x)\right)
\end{align}なぜこうなるか説明しましょう。右辺と左辺の $x^{n}$ の係数を全て比較して，一致していれば正しい等式である事が分かります。\begin{align}
f(x)=\cfrac{1}{2^{9}} x^{10}+
\left(
\cfrac{1}{2^{9}}+\cfrac{1}{2^{10}}
\right)
x^{11}+\cdots
\end{align}だったので，右辺も左辺も10次以下の項は現れないことが分かります。

$n\geq 11$ のときの $x^{n}$ の係数を比較しましょう。左辺の $x^{n}$ の係数は $p[n]$ です。右辺の $x^{n}$ の係数はどうでしょうか。

$xf(x)$ の $x^{n}$ の係数は $p[n-1]$ で， $\cfrac{x^{11}}{1-x}$ を展開したやつの $x^{n}$ の係数は $1$ で， $x^{10}f(x)$ の $x^{n}$ の係数は $p[n-10]$ です。よって，右辺の $x^{n}$ の係数は\begin{align}
p[n-1]+\cfrac{1}{2^{10}}(1-p[n-10])
\end{align}となります。これは漸化式より $p[n]$ ，つまり左辺の $x^{n}$ の係数に一致します。以上より右辺と左辺の $x^{n}$ の係数は全て一致し，正しい等式である事が分かりました。

この式を $f(x)$ について解いてやれば次のようになります。
\begin{align}
f(x) =&\cfrac{(x/2)^{10}(2-x)}{(1-x+(x/2)^{10})(1-x)}&\\\
=& \cfrac{(1-x+(x/2)^{10})(2-x)-(1-x)(2-x)}{(1-x+(x/2)^{10})(1-x)}&\\\
=& \cfrac{2-x}{1-x}+\cfrac{2-x}{1-x+(x/2)^{10}}&\\\
=&1+\cfrac{1}{1-x}-\cfrac{2-x}{1-\left(x-(x/2)^{10}\right)}&
\end{align}

この有理関数を展開して， $x^{100}$ の係数 $p[100]$ を計算しましょう。それが求めたかった確率です。

先ほどの青枠の公式を用いると，

\begin{align}
f(x)=&1+\sum_{i=0}^\infty x^i-(2-x)\sum_{i=0}^\infty \left(x-\left(\frac{x}{2}\right)^{10} \right)^{i}& \\
=&1+\sum_{i=0}^\infty x^i-2\sum_{i=0}^\infty \left(x-\left(\frac{x}{2}\right)^{10} \right)^{i}+x\sum_{i=0}^\infty \left(x-\left(\frac{x}{2}\right)^{10} \right)^{i}&
\end{align}

です。 $x^{100}$ がいつ現れるか考えると，以下の様に $p[100]$ を計算できます。物好きな方は計算を追ってみてください。

\begin{align}
p[100]=&1 - 2\sum_{j=0}^{10}\binom{(100-10j)+j}{j}\left(-\cfrac{1}{2^{10}}\right)^j +\sum_{j=0}^{9}\binom{(99-10j)+j}{j}\left(-\cfrac{1}{2^{10}}\right)^j &\\
=&1-2\sum_{j=0}^{10}(-1)^{j}\binom{100-9j}{j}2^{-10j} + \sum_{j=0}^{9} (-1)^{j}\binom{99-9j}{j}2^{-10j} &\\
=&1-2+1-2\sum_{j=1}^{10}(-1)^{j}\binom{100-9j}{j}2^{-10j} +\sum_{j=1}^{9} (-1)^{j}\binom{99-9j}{j}2^{-10j} &\\
=&2\sum_{j=1}^{10}(-1)^{j-1}\binom{100-9j}{j}2^{-10j} -\sum_{j=1}^{9} (-1)^{j-1}\binom{99-9j}{j}2^{-10j}&\\
=&\cfrac{-2}{2^{100}}+\sum_{j=1}^{9}(-1)^{j-1} \left\{2\binom{100-9j}{j}2^{-10j} -\binom{99-9j}{j}2^{-10j}\right\}&\\
=&\cfrac{1}{2^{100}}\left\{-2+\sum_{j=1}^{9}(-1)^{j-1} \left(2\binom{100-9j}{j}-\binom{99-9j}{j}\right)2^{100-10j} \right\}&\\
=&\cfrac{1}{2^{100}} \left\{-2+\sum_{j=1}^{9} (-1)^{j-1}~\cfrac{100-8j}{j}~\binom{99-9j}{j-1}2^{100-10j}\right\}&
\end{align}

計算を追いたくない人は代わりに WolframAlpha に検算してもらった結果↓を見てください。ちゃんとエレファントに解いた答えと同じになっています。
WolframAlpha に検算してもらった結果

この中の和 $\sum_{j=1}^{9}$ に現れる項の絶対値を $A[j]$ とおきましょう。\begin{align}
A[j]=\cfrac{100-8j}{j}~\binom{99-9j}{j-1}2^{100-10j}.
\end{align}すると， $A[j]$ は正の数で， $j$ を大きくしていくと $2^{10}$ が $100$ よりある程度大きいせいで急激に小さくなっていきます（ $j$ が1つ大きくなると，指数部分 $2^{100-10j}$ は $2^{-10}$ 倍になりますが，残りの部分は大きめに見積もっても $90$ 倍くらいにしかならず，全体として $\cfrac{90}{2^{10}}$ 倍以下になります）。おおざっぱに測ってみると， $A[2]$ は $A[1]$ の $0.04$ 倍以下しかなく， $A[3]$ は $A[2]$ の $0.02$ 倍以下しかありません。

つまり $\sum_{j=1}^{9} (-1)^{i-1}A[i]$ で一番大事な部分は $A[1$ ] で， $\cfrac{1}{2^{100}} A[1]$ だけ計算してもそこそこ $p[100]$ に近い値になっているはずです。実際に計算してみましょう。\begin{align}
\cfrac{1}{2^{100}} A[1]=\cfrac{92\times 2^{90}}{2^{100}}
=\cfrac{92}{2^{10}}=\cfrac{92}{1024}\fallingdotseq 0.0898=8.98\%
\end{align}さらに $\cfrac{1}{2^{100}} (A[1]-A[2])$ ， $\cfrac{1}{2^{100}} (A[1]-A[2]+A[3])$ と項を増やしていくと，減衰振動のような動きをしながら真の値 $p[100]$ に近付いていきます。
手計算ではあまり項を増やすと大変なので， $\cfrac{1}{2^{100}} (A[1]-A[2])$ くらいで計算をやめておきましょう。けっこう面倒ですが，この程度なら手計算で出すことはできます (どうせバレないから電卓を使いました)。\begin{align}
\cfrac{1}{2^{100}} (A[1]-A[2])=\cfrac{92}{2^{10}}-\cfrac{42\times 81}{2^{20}}=\cfrac{92\cdot 2^{10}-42\cdot 81}{(1024)^{2}}\fallingdotseq 0.0866=8.66\%
\end{align}というわけで，真の値 $8.6659\%$ に近い，だいたいの値を出すことが出来ました。

もっとセンスのいい概算の方法はあるか？

近似値 $\cfrac{1}{2^{100}} A[1]$ の計算式はだいたい\begin{align}
\cfrac{100-10}{2^{10}}
\end{align}くらいです。問題に出てくる， $100$ ， $10$ ，そして確率 $\cfrac{1}{2}$ だけを使った単純な式です。 $p[100]$ が $\cfrac{100-10}{2^{10}}$ くらいになるという事の「納得できる説明」はあるでしょうか？

$i$ 回目から表か裏が10回連続で出る確率は $\cfrac{1}{2^{9}}$ で， $i$ は 1 から 90 まで可能性があるので，総和は $\cfrac{100-10}{2^{9}}$ になります。しかしこれらの事象は独立ではないので， $p[100]$ を出すには重複分を引かなければいけません。その引かれる確率がだいたい半分の $\cfrac{100-10}{2^{10}}$ くらいになるはずですなのですが，その理由をうまく説明する方法はあるでしょうか？

ボードゲームにおける先手・後手

値が出たのはいいとして，この値を知って何かいいことがあるでしょうか？

元の記事の筆者である山本一成さんと言えば将棋，将棋で1/2で決まるものと言えば，先手と後手を決める振り駒があります。５枚の歩を振って，表の「歩」が多かったら目上の人が先手，裏の「と金」が多かったら目上の人が後手番になります。

将棋のプロ棋士である森内九段は振り駒の公平性に疑問を持って100回ほど振り駒を振る実験をしてみたそうです。これも一種のモンテカルロ法でしょうか。
森内伝説～本人証言と考察～ - ニコニコ動画

ちなみにこの話はファンの間で誇張され，自宅で数千回振り駒を試したという話になってしまっています。

将棋は先手の勝率が52～53%と，少しだけ先手が有利とされているゲームです。
shogi1.com

公平のはずの振り駒で10回連続で不利な後手番を引いたらさぞ不満に感じる事でしょうし，10連続有利な先手番を引いたら幸運に感じるでしょう。

今回計算した結果によれば，100局将棋を指せば，10連続で先手か後手が続くという事は約 8.7% の確率で起こります。高くはない数字ですが，全くあり得ない数字でもありません。

実は将棋よりも先手後手の優劣がはっきりしているゲームがあります。どうぶつしょうぎです。どうぶつしょうぎは後手必勝である事が知られています。
「どうぶつしょうぎ」の完全解析

「絶対に負けない後手」が相手をしてくれるサイトもあります。
どうぶつしょうぎ名人

Ponanzaが活躍する将棋対局アプリ将棋ウォーズを運営するHEROZは，そのどうぶつしょうぎ版であるどうぶつしょうぎウォーズも提供しています。後手必勝と分かっていたら面白くないかというと全然そんな事はなく，後手絶対有利の中，先手がいかに後手を間違えさせるかという戦略の研究がなされています。対局後に何が正解だったかちゃんと分かるというのもいいですね。

どうぶつしょうぎウォーズの大会イベントなどで上位争いをしているときに連続して先手番を引かされたらさぞイラつくでしょうが，そんなときは今回の結果を思い出して「まあ，ありえない事ではないな」と冷静になりましょう。運営にクレームを入れたりしちゃダメよ。