次: 最後に 上: n人巴戦について 前: 連立方程式（漸化式）による解き方

ところで，試合の終わる回数は？

Tを優勝が決定する回数を表す確率変数とします．

まずは

$$\begin{align*}E(T) &=\sum_{k=1}^{\infty} kP(T=k) \\ &=\sum_{k=1}^{\infty} P(T\ge k) \end{align*}$$

と変形します．

1行目から2行目の変形は

$$\begin{align*}\sum_{k=1}^{\infty} P(T\ge k) &= \sum_{k=1}^\infty \sum_{j=k}^\in... ...{j=1}^\infty \sum_{k=1}^j P(T=j) \\ &= \sum_{j=1}^\infty j P(T=j) \end{align*}$$

です．³

以下， $k\ge 1$に対して $P(T\ge k)$を考えます．

最短で優勝が決まるのは n-1回目ですから

$$\boxed{ P(T\ge 1)=P(T\ge 2)=\cdots =P(T\ge n-1)=1 }$$ (9)

が成り立ちます．

また，

$$\boxed{ \lim_{N\to\infty} P(T\ge N)=0 }$$ (10)

も注意しておきましょう．

さて，$k \ge n$のとき，1回目に勝利したものが いつ負けるかを考えます．

$k \ge n$だから必ずn-1回目までに負けるので

$$\begin{align*}P(T\ge k)&= P(T\ge k \text{かつ\quad $1$ 回目に勝利のものが$2$ 回脈.. ...(T\ge k-2)+\cdots \\ &\cdots\cdots +(\frac12)^{n-2}P(T\ge k-(n-2)) \end{align*}$$

つまり

$$\boxed{ \begin{split} P(T\ge k)=\frac12 P(T\ge k-1)+& (\frac... ...\cdots \\ &\cdots +(\frac12)^{n-2}P(T\ge k-(n-2)) \end{split}}$$ (11)

が成り立つ．⁴

(15)の$k=n\sim N$までの和をとります． (13)に注意して，

$$\begin{align*}\sum _{k=n}^N P(T\ge k)&= \frac12 \sum _{k=n}^NP(T\ge k-1)+ (\frac... ...-\left( \text{$P(k\ge N),\ldots ,P(k\ge N-(n-1))$ の線型和} \right) \end{align*}$$

$N\to\infty$としたとき，(14)より 最終項は0に収束する．

したがって，

$$\sum _{k=n}^N P(T\ge k)=2^{n-1}-n$$

よって，

$$\begin{align*}E(T) &=\sum _{k=1}^\infty P(T\ge k)\\ &=\sum _{k=1}^{n-1} P(T\ge k)+\sum _{k=n}^\infty P(T\ge k)\\ &=(n-1)+(2^{n-1}-n) \\ &=2^{n-1}-1 \end{align*}$$

次: 最後に 上: n人巴戦について 前: 連立方程式（漸化式）による解き方