勝ち残りじゃんけんの回数

普通大人数でじゃんけんをするときはなかなか勝ちが決まらないため、何グループかに分割して行う。
では、分割しないで、勝ち残りで優勝を決めるまで行うとどれほどかかるのだろうか？

問題設定

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

これは中学時代から暇なときに考えていた問題で、ようやく、それらしきものが出たのでここにまとめておく（母関数の表式を見れば分かるように微妙なものになっている）。

漸化式

$n$ 人でじゃんけんをして $k$ 人が勝ち残る確率を $P(n\to k)$ と書く。手の出し方は $n$ 人いるので $3^n$ 通り。そこから $k$ 人選び、どの手で勝ったかを決めることにより

$\displaystyle P\left(n\rightarrow k\right) =\frac {3}{{3}^{n}}\left({\begin{matrix}{n}\\ {k}\end{matrix}}\right)$

、
が成り立つ。二項係数は縦長括弧で表す。
あいこになる、つまり人数の変わらない確率は、誰かしらが勝つ場合の余事象であるので

$\displaystyle \begin{align}P\left({n\rightarrow n}\right) &=1-{\sum _{k=1}^{n-1}{P\left({n\to k}\right) }} \\ &=1-{\sum _{k=1}^{n-1}{\frac {3}{{3}^{n}}\left({\begin{matrix}{n}\\ {k}\end{matrix}}\right) }} \\ &=1-\frac {{2}^{n}-2}{{3}^{n-1}}\end{align}$

となる。最後の等号は二項定理による。
これより、じゃんけんの回数の期待値は、一回じゃんけんをする度、１増えるので

$\displaystyle \begin{align}{E}_{n}&={\sum _{k=1}^{n}{P\left({n\rightarrow k}\right) \left({{E}_{k}+1}\right) }} \\ &=\left({1-\frac {{2}^{n}-2}{{3}^{n-1}}}\right) \left({{E}_{n}+1}\right)+{\sum _{k=1}^{n-1}{\frac {1}{{3}^{n-1}}\left({\begin{matrix}{n}\\ {k}\end{matrix}}\right) \left({{E}_{k}+1}\right) }}\end{align}$

これを $E_n$ について解けば

$\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$

具体的に求めてみると

$\displaystyle {E}_{1}=0, \quad{E}_{2}=\frac {3}{2}, \quad {E}_{3}=\frac {9}{4}$

となる。ここまでは、大学入試のむしろ易しい程度の問題だろう。

(追記：本記事に書いてある方法よりすっきり求まる方法を新たにまとめてのでこっちをどうぞ）
c-and-a.hatenablog.com

母関数への準備

さて、難しい数列ではお馴染みの母関数を用いていくのだが、このままでは些か扱いづらい。母関数で扱う以上、初項が $0$ である必要はないし、添え字が $1$ から始まると見栄えが悪い。そこで

$\displaystyle {a}_{n}={E}_{n+2}$

とおいてやる。すると

$\displaystyle {a}_{0}=\frac {3}{2}, \quad{a}_{1}=\frac {9}{4}$

となる。

さて、これらを求めた式に入れ込もう。

$\displaystyle {a}_{n-2}=\frac {1}{{2}^{n}-2}\left\lbrace {{3}^{n-1}+{\sum _{k=1}^{n-1}{\left({\begin{matrix}{n}\\ {k}\end{matrix}}\right) {a}_{k-2}}}}\right \rbrace$

添え字を $n,k$ にシフトさせれば

$\displaystyle \begin{align}{a}_{n}&=\frac {1}{{2}^{n+2}-2}\left\lbrace {{3}^{n+1}+{\sum _{k=-1}^{n-1}{\left({\begin{matrix}{n+2}\\ {k+2}\end{matrix}}\right) {a}_{k}}}}\right \rbrace \\ &=\frac {1}{{2}^{n+2}-2}\left\lbrace {{3}^{n+1}+{\sum _{k=0}^{n-1}{\left({\begin{matrix}{n+2}\\ {k+2}\end{matrix}}\right) {a}_{k}}}}\right \rbrace,\quad\left({\because {a}_{-1}={E}_{1}=0}\right) \end{align}$

となり、二項係数の性質

$\displaystyle \left({\begin{matrix}{n+2}\\ {k+2}\end{matrix}}\right) =\frac {\left({n+2}\right) \left({n+1}\right) }{\left({k+2}\right) \left({k+1}\right) }\left({\begin{matrix}{n}\\ {k}\end{matrix}}\right)$

より、また改めて数列を

$\displaystyle {b}_{n}=\frac {{a}_{n}}{\left({n+2}\right) \left({n+1}\right) }, \quad{b}_{0}=\frac {3}{2}\cdot \frac {1}{2\cdot 1}=\frac {3}{4}, \quad {b}_{1}=\frac {9}{4}\cdot \frac {1}{3\cdot 2}=\frac {3}{8}$

と定義すれば

$\displaystyle {b}_{n}=\frac {1}{{2}^{n+2}-2}\left\lbrace {\frac {{3}^{n+1}}{\left({n+2}\right) \left({n+1}\right) }+{\sum _{k=0}^{n-1}{\left({\begin{matrix}{n}\\ {k}\end{matrix}}\right) {b}_{k}}}}\right \rbrace$

とまあそこそこ簡潔になる。ここまでは、ずいぶんと昔に出せていたことだが、母関数を作っても上手く処理できなかった。シグマが $0$ から $n-1$ なのもそうだし、分母の $-2$ がとても厄介だった。そのどちらも解決する式変形を見つけることが突破口となった。

Breakthrough

分子を少し操作する。

$\displaystyle {b}_{n}=\frac {1}{{2}^{n+2}-2}\left\lbrace {\frac {{3}^{n+1}}{\left({n+2}\right) \left({n+1}\right) }-2{b}_{n}+{b}_{n}+{b}_{n}+{\sum _{k=0}^{n-1}{\left({\begin{matrix}{n}\\ {k}\end{matrix}}\right) {b}_{k}}}}\right \rbrace$

$-2b_n$ は左辺に移項し、更に $b_n$ を一つシグマに吸収させる。

$\displaystyle \left({1+\frac {2}{{2}^{n+2}-2}}\right) {b}_{n}=\frac {1}{{2}^{n+2}-2}\left\lbrace {\frac {{3}^{n+1}}{\left({n+2}\right) \left({n+1}\right) }+{b}_{n}+{\sum _{k=0}^{n}{\left({\begin{matrix}{n}\\ {k}\end{matrix}}\right) {b}_{k}}}}\right \rbrace$

あとはちょこっと操作すれば

$\displaystyle {b}_{n}=\frac {1}{{2}^{n+2}}\left\lbrace {\frac {{3}^{n+1}}{\left({n+2}\right) \left({n+1}\right) }+{b}_{n}+{\sum _{k=0}^{n}{\left({\begin{matrix}{n}\\ {k}\end{matrix}}\right) {b}_{k}}}}\right \rbrace$

となり、とても見栄えがよくなった。式の両辺に $b_n$ があるのは如何なのかとおもうかもしれないので、試しに $n=0$ を代入してみよう。

$\displaystyle \begin{align}{b}_{0}&=\frac {1}{{2}^{0+2}}\left\lbrace {\frac {{3}^{0+1}}{\left({0+2}\right) \left({0+1}\right) }+{b}_{0}+{\sum _{k=0}^{0}{\left({\begin{matrix}{0}\\ {k}\end{matrix}}\right) {b}_{k}}}}\right \rbrace \\ &=\frac {1}{4}\left\lbrace {\frac {3}{2}+{b}_{0}+{b}_{0}}\right \rbrace \end{align}$

となり

$\displaystyle {b}_{0}=\frac {3}{4}$

を再現できている。さて、母関数を作ろう。

母関数

通常の母関数では

$\displaystyle F\left({x}\right) ={\sum _{n\geq 0}{{b}_{n}{x}^{n}}}$

とするのだが、コンビネーションを含む漸化式の場合

$\displaystyle F\left({x}\right) ={\sum _{n\geq 0}{\frac {1}{n!}{b}_{n}{x}^{n}}}$

とおいたほうが見通しがいいことがよくある。

先に断っておくが、ここからの式変形において、収束条件、無限和の順序交換など、一切の条件を確認せず行ったので、恐らく、より正しい母関数が存在する。今回は第一稿ということで許してほしい。

さて、母関数に漸化式を代入すると

$\displaystyle \begin{align}F\left({x}\right) &={\sum _{n\geq 0}{\frac {1}{n!}\frac {1}{{2}^{n+2}}\frac {{3}^{n+1}}{\left({n+2}\right) \left({n+1}\right) }{x}^{n}}}+{\sum _{n\geq 0}{\frac {1}{n!}\frac {1}{{2}^{n+2}}{b}_{n}{x}^{n}}} \\ &+{\sum _{n\geq 0}{\frac {1}{n!}\frac {1}{{2}^{n+2}}{\sum _{k=0}^{n}{\left({\begin{matrix}{n}\\ {k}\end{matrix}}\right) {b}_{k}}}{x}^{n}}}\end{align}$

となる。1項目から順に見ていこう。

第１項

少しまとめれば

$\displaystyle \frac {3}{4}{\sum _{n\geq 0}{\frac {1}{\left({n+2}\right) !}{\left({\frac {3}{2}x}\right) }^{n}}}=\frac {3}{4}H\left({\frac {3}{2}x}\right)$

$H(x)$ は

$\displaystyle H\left({x}\right) ={\sum _{n\geq 0}{\frac {1}{\left({n+2}\right) !}{x}^{n}}}$

である。これは簡単であろう。

$\displaystyle {x}^{2}H\left({x}\right) ={\sum _{n\geq 2}{\frac {1}{n!}{x}^{n}}}=-1-x+{\sum _{n\geq 0}{\frac {1}{n!}{x}^{n}}}=-1-x+{e}^{x}$

よって

$\displaystyle H\left({x}\right) =\frac {{e}^{x}}{{x}^{2}}-\frac {1}{{x}^{2}}-\frac {1}{x}$

これより１項目は

$\displaystyle \frac {3}{4}H\left({\frac {3}{2}x}\right) =\frac {1}{3{x}^{2}}{e}^{{{3x}/{2}}}-\frac {1}{3{x}^{2}}-\frac {1}{2x}$

第２項

これは簡単で、２項目は

$\displaystyle \frac {1}{4}{\sum _{n\geq 0}{\frac {1}{n!}{b}_{n}{\left({\frac {x}{2}}\right) }^{n}}}=\frac {1}{4}F\left({\frac {x}{2}}\right)$

第３項

まず

$\displaystyle {\sum _{n\geq 0}{\frac {1}{n!}\frac {1}{{2}^{n+2}}{\sum _{k=0}^{n}{\left({\begin{matrix}{n}\\ {k}\end{matrix}}\right) {b}_{k}}}{x}^{n}}}=\frac {1}{4}{\sum _{n\geq 0}{{\sum _{k=0}^{n}{\frac {1}{\left({n-k}\right) !k!}{b}_{k}}}{\left({\frac {x}{2}}\right) }^{n-k}{\left({\frac {x}{2}}\right) }^{k}}}$

と書き換える。

$\displaystyle {\sum _{n\geq 0}{{\alpha }_{n}}}{\sum _{k\geq 0}{{\beta }_{k}}}={\sum _{n\geq 0}{{\sum _{k=0}^{n}{{\alpha }_{n-k}{\beta }_{k}}}}}$

という関係式（各成分をみれば等号が成り立つことが分かる）を使えば

$\displaystyle \frac {1}{4}{\sum _{n\geq 0}{\frac {1}{n!}{\left({\frac {x}{2}}\right) }^{n}}}{\sum _{k\geq 0}{\frac {1}{k!}{b}_{k}{\left({\frac {x}{2}}\right) }^{k}}}=\frac {1}{4}{e}^{{{x}/{2}}}F\left({\frac {x}{2}}\right)$

と書ける。この式変形に母関数を階乗を含む形に定義したことが活きてくる。

よってまとめれば

$\displaystyle F\left({x}\right) =\frac {1}{3{x}^{2}}{e}^{{{3x}/{2}}}-\frac {1}{3{x}^{2}}-\frac {1}{2x}+\frac {1}{4}\left({1+{e}^{{{x}/{2}}}}\right) F\left({{{x}/{2}}}\right)$

$2x$ に書き換えて

$\displaystyle F\left({2x}\right) =\frac {1}{12{x}^{2}}{e}^{3x}-\frac {1}{12{x}^{2}}-\frac {1}{4x}+\frac {1}{4}\left({1+{e}^{x}}\right) F\left({x}\right)$