CとAの数物 Note

数学と物理のはざまに棲息。

n人でじゃんけんするときの回数(改良編)

数列

以前こんな問題について書いた。
c-and-a.hatenablog.com

問題設定

n人でじゃんけんを行い、あいこであればもう一度、勝ちが出れば、勝った人たちでまたじゃんけんを行う。これを最後に一人出るまで繰り返す。優勝者がでるまでに行ったじゃんけんの回数の期待値をE_nとする。E_nを求めよ。なお、E_1=0としておく。

簡単に言えば、みんなでじゃんけんをやったとき、優勝者を決めるのには何回必要かを考えた。これはなかなかに骨の折れる問題でとても解くのが難しく、前回の解答はとても満足のできる形にならなかった。

今回、もっとすっきりした解が求まったのでそれを紹介しよう。

前回と共通するところまでは飛ばそう。

回数の期待値の漸化式は

\displaystyle {E}_{n}=\frac {1}{{2}^{n}-2}\left\lbrace {{3}^{n-1}+{\sum _{k=1}^{n-1}{\left({\begin{matrix}{n}\\ {k}\end{matrix}}\right) {E}_{k}}}}\right \rbrace,\quad E_1=0
とかけるのだった。これの導出は上のリンクから飛んでみて欲しい。

まず、母関数を考えるのは同じで

\displaystyle F( x) =\sum ^{\infty }_{n=0}\frac{E_{n}}{n!} x^{n}
とかく。便宜的にE_0=0とした。

前回と同じようなトリックを使うと

\displaystyle E_{n} =\frac{1}{2^{n} -2}\left\{3^{n-1} -2E_{n} +E_{n} +E_{n} +\sum ^{n-1}_{k=1}\begin{pmatrix} n\\ k \end{pmatrix} E_{k}\right\}
より
\displaystyle E_{n} =\frac{1}{2^{n}}\left\{3^{n-1} +E_{n} +\sum ^{n}_{k=0}\begin{pmatrix} n\\ k \end{pmatrix} E_{k}\right\},\quad n\geq 2
が成り立つ。ここでは-2E_nを左辺に移項し、E_nのうち一つはシグマに吸収させている。

これを母関数に代入し整理していく
\begin{align*}
F( x) & =\sum ^{\infty }_{n=0}\frac{E_{n}}{n!} x^{n} =\sum ^{\infty }_{n=2}\frac{E_{n}}{n!} x^{n}\\
& =\sum ^{\infty }_{n=2}\frac{1}{n!}\frac{1}{2^{n}}\left\{3^{n-1} +E_{n} +\sum ^{n}_{k=0}\begin{pmatrix}
n\\
k
\end{pmatrix} E_{k}\right\} x^{n}\\
& =\frac{1}{3}\sum ^{\infty }_{n=2}\frac{1}{n!}\left(\frac{3}{2} x\right)^{n} +\sum ^{\infty }_{n=2}\frac{E_{n}}{n!}\left(\frac{x}{2}\right)^{n} +\sum ^{\infty }_{n=2}\frac{1}{n!}\left(\frac{x}{2}\right)^{n}\sum ^{n}_{k=0}\begin{pmatrix}
n\\
k
\end{pmatrix} E_{k}\\
& =\frac{1}{3}\left( e^{3x/2} -1-\frac{3x}{2}\right) +F( x/2) +\sum ^{\infty }_{n=0}\frac{1}{n!}\left(\frac{x}{2}\right)^{n}\sum ^{n}_{k=0}\begin{pmatrix}
n\\
k
\end{pmatrix} E_{k}
\end{align*}
式変形ではE_0=E_1=0を使って、和の開始をずらしたりしているので注意してほしい。

3項目は
\begin{align*}
\sum ^{\infty }_{n=0}\frac{1}{n!}\left(\frac{x}{2}\right)^{n}\sum ^{n}_{k=0}\begin{pmatrix}
n\\
k
\end{pmatrix} E_{k} & =\sum ^{\infty }_{n=0}\sum ^{n}_{k=0}\frac{1}{( n-k) !}\left(\frac{x}{2}\right)^{n-k} \cdot \frac{E_{k}}{k!}\left(\frac{x}{2}\right)^{k}\\
& =\sum ^{\infty }_{n=0}\sum ^{\infty }_{k=0}\frac{1}{n!}\left(\frac{x}{2}\right)^{n} \cdot \frac{E_{k}}{k!}\left(\frac{x}{2}\right)^{k}\\
& =e^{x/2} F\left(\frac{x}{2}\right)
\end{align*}
と簡約できるので、最終的に

\displaystyle F( x) =\frac{1}{3}\left( e^{3x/2} -1-\frac{3x}{2}\right) +F( x/2) +e^{x/2} F( x/2)
、とかけるので、x/2をxに置き換えて
\displaystyle F( 2x) =\frac{1}{3}\left( e^{3x} -1\right)-x +\left( e^{x} +1\right) F( x)
という関数方程式を満たすことが分かる。F(x)=(1-e^x)f(x)とおいて、代入すれば
\displaystyle \left( 1-e^{2x}\right) f( 2x) =\frac{1}{3}\left( e^{3x} -1\right) -x+\left( 1-e^{2x}\right) f( x)
となるので、未知関数の係数をそろえることが出来、整理すれば
\displaystyle f( 2x) =-\frac{1}{3} e^{x} -\frac{1}{3}\frac{1}{e^{x} +1} +\frac{x}{e^{2x} -1} +f( x)
となる。

先に解答の方針を示そう。f(x)と上の式の右辺の３項がそれぞれ

\displaystyle f( x) =\sum ^{\infty }_{n=0}\frac{a_{n}}{n!} x^{n}
\displaystyle \frac{1}{3} e^{x} +\frac{1}{3}\frac{1}{e^{x} +1} -\frac{x}{e^{2x} -1} =\sum ^{\infty }_{n=0}\frac{b_{n}}{n!} x^{n}
と展開できるとしよう。このとき
\displaystyle f( 2x) =\sum ^{\infty }_{n=0}\frac{2^{n} a_{n}}{n!} x^{n}
となるので、x^nの係数を比べて
\displaystyle 2^{n} a_{n} =-b_{n} +a_{n}
となるので
a_0=0,\quad a_{n} =-\frac{b_{n}}{2^{n} -1},\quad n\geq 1

を得る。n=0については後で計算するが、b_0=0なので、a_0=0としてよい。そして
\begin{align*}
F( x) & =\left( 1-e^{x}\right) f( x)\\
& =-\sum ^{\infty }_{n=1}\frac{1}{n!} x^{n}\sum ^{\infty }_{m=1}\frac{a_{m}}{m!} x^{m}\\
& =-\sum ^{\infty }_{n=1}\sum ^{\infty }_{m=1}\frac{1}{( n+m) !}\begin{pmatrix}
n+m\\
m
\end{pmatrix} a_{m} x^{n+m}\\
& =-\sum ^{\infty }_{n=2}\frac{x^{n}}{n!}\sum ^{n-1}_{m=1}\begin{pmatrix}
n\\
m
\end{pmatrix} a_{m}
\end{align*}
であるのでE_0=E_1=0と
\displaystyle E_{n} =-\sum ^{n-1}_{m=1}\begin{pmatrix} n\\ m \end{pmatrix} a_{m} =\sum ^{n-1}_{m=1}\begin{pmatrix} n\\ m \end{pmatrix}\frac{b_{m}}{2^{m} -1},\quad n\geq 2
とかけるわけだ。

あとはb_nを求めていくのだが、まずは項ごとに考えていく。まずは

\displaystyle \frac{1}{3} e^{x} =\sum ^{\infty }_{n=0}\frac{1}{3\cdot n!} x^{n}=\frac{1}{3} +\sum ^{\infty }_{n=1}\frac{1}{3\cdot n!} x^{n}
がすぐに分かる。次に、ベルヌーイ数B_nの生成母関数
\displaystyle \frac{x}{e^{x} -1} =\sum ^{\infty }_{n=0}\frac{B_{n}}{n!} x^{n}
を用いると
\displaystyle -\frac{x}{e^{2x} -1} =-\frac{1}{2}\frac{2x}{e^{2x} -1} =-\frac{1}{2}\sum ^{\infty }_{n=0}\frac{B_{n}}{n!}( 2x)^{n} =\sum ^{\infty }_{n=0}\frac{-2^{n-1} B_{n}}{n!} x^{n}
ベルヌーイ数はB_0=1と定義されるのでn=0だけ、分けて書くと
\displaystyle -\frac{x}{e^{2x} -1} =-\frac{1}{2} +\sum ^{\infty }_{n=1}\frac{-2^{n-1} B_{n}}{n!} x^{n}
となる。最後に
\displaystyle \frac{1}{e^{x} +1} -\frac{1}{2} =-\frac{1}{2}\frac{e^{x} -1}{e^{x} +1} =-\frac{1}{2}\tanh\frac{x}{2}
であったので
\displaystyle \frac{1}{3}\frac{1}{e^{x} +1} =\frac{1}{6} -\frac{1}{6}\tanh\frac{x}{2}
である。\tanh xのTaylor展開はベルヌーイ数を用いて
\displaystyle \tanh x=\sum ^{\infty }_{n=1}\frac{2^{n+1}\left( 2^{n+1} -1\right)}{( n+1) !} B_{n+1} x^{n}
とかけるので
\displaystyle \frac{1}{3}\frac{1}{e^{x} +1} =\frac{1}{6} -\sum ^{\infty }_{n=1}\frac{1}{n!}\frac{2^{n+1} -1}{3( n+1)} B_{n+1} x^{n}
となる。よって
\displaystyle \sum ^{\infty }_{n=0}\frac{b_{n}}{n!} x^{n} =\sum ^{\infty }_{n=1}\frac{x^{n}}{n!}\left(\frac{1}{3} -\frac{2^{n+1} -1}{3( n+1)} B_{n+1} -2^{n-1} B_{n}\right)
となり、確かにb_0=0であり、n\geq 1では
\displaystyle b_{n} =\frac{1}{3} -\frac{2^{n+1} -1}{3( n+1)} B_{n+1} -2^{n-1} B_{n}
と分かる。よって求めたかった期待値は
\displaystyle E_{n} =\sum ^{n-1}_{m=1}\frac{1}{2^{m} -1}\begin{pmatrix} n\\ m \end{pmatrix}\left(\frac{1}{3} -\frac{2^{m+1} -1}{3( m+1)} B_{m+1} -2^{m-1} B_{m}\right)
である。

小さい値について計算すると

\displaystyle E_{2} =\frac{3}{2} ,\ E_{3} =\frac{9}{4} ,\ E_{4} =\frac{45}{14}
と正しい値を出力してくれる。Mathematicaを使うと、n=100なんかも計算できて、ちゃんと有理数の値も分かるのだが、分子と分母が巨大すぎて書ききれないので、近似値をかくと
\displaystyle E_{100} \simeq 1.355203941481465182\times 10^{17}
である。つまり、100人で勝ち残りじゃんけんをすると、平均して135,520,394,148,146,518回もじゃんけんを行う必要があることが分かる。これでは、1秒に1回じゃんけんが出来たとしても、43億年程度かかってしまう計算になる。これは地球の年齢45億年に匹敵する。また、あと3人増えただけで、つまり、103人では、かかる時間は145億年になり、宇宙の年齢を超してしまう。勝ち残りじゃんけんが如何に非効率かがとても分かる結果になった。