大阪大学 1995年 理系 第5問 解説

方針・初手

確率の漸化式を立てる問題である。図形 $T_{n+1}$ が2つの $T_n$ から構成されていることに着目し、$T_{n+1}$ の頂点 $O$ から左右の $T_n$ の頂点への通信路の故障または正常で場合分けをして、$p_{n+1}$ と $p_n$ の関係式を導く。その後は誘導に従って不等式を評価し、はさみうちの原理を用いて極限を求める。

解法1

(1)

図形 $T_{n+1}$ の一番上の点 $O$ から、下に接続される2つの図形 $T_n$ の一番上の点をそれぞれ $O_1, O_2$ とする。 $O$ から一番下の集合 $A_{n+1}$ のどの点へも通信できないのは、次の2つの事象が同時に起こる場合である。

• $O$ から $O_1$ を経由して、その下の $A_n$ のどの点へも通信できない。
• $O$ から $O_2$ を経由して、その下の $A_n$ のどの点へも通信できない。

$O$ と $O_1$ の間の通信路が故障している確率は $p$ である。 $O$ と $O_1$ の間の通信路が正常（確率 $1-p$）であっても、$O_1$ からその下の $A_n$ のどの点へも通信できない確率は $p_n$ である。 したがって、$O$ から $O_1$ を経由して一番下の点へ通信できない確率は、

$$ p + (1 - p)p_n $$

となる。$O_2$ 側についても同様であり、これらは互いに独立である。 よって、求める関係式は

$$ p_{n+1} = \{ p + (1 - p)p_n \}^2 $$

である。

(2)

（1） で求めた漸化式より、

$$ 1 - p_{n+1} = 1 - \{ p + (1 - p)p_n \}^2 $$

ここで、中括弧の中を変形すると、

$$ p + (1 - p)p_n = 1 - (1 - p) + (1 - p)p_n = 1 - (1 - p)(1 - p_n) $$

となる。これを代入すると、

$$ \begin{aligned} 1 - p_{n+1} &= 1 - \{ 1 - (1 - p)(1 - p_n) \}^2 \\ &= 1 - \left\{ 1 - 2(1 - p)(1 - p_n) + (1 - p)^2(1 - p_n)^2 \right\} \\ &= 2(1 - p)(1 - p_n) - (1 - p)^2(1 - p_n)^2 \end{aligned} $$

確率の性質から $0 \leqq p \leqq 1$、$0 \leqq p_n \leqq 1$ であるため、$(1 - p)^2(1 - p_n)^2 \geqq 0$ である。 したがって、

$$ 1 - p_{n+1} \leqq 2(1 - p)(1 - p_n) $$

が成り立つ。

(3)

$p_n$ は確率であるから、すべての自然数 $n$ について $1 - p_n \geqq 0$ である。 （2） の結果より、

$$ 0 \leqq 1 - p_{n+1} \leqq 2(1 - p)(1 - p_n) $$

が成り立つ。これを繰り返し用いると、

$$ 0 \leqq 1 - p_n \leqq \{ 2(1 - p) \}^{n-1} (1 - p_1) $$

となる。 条件より $p > \frac{1}{2}$ であるから、

$$ 0 \leqq 1 - p < \frac{1}{2} $$

両辺を2倍して、

$$ 0 \leqq 2(1 - p) < 1 $$

である。したがって、$n \to \infty$ のとき $\{ 2(1 - p) \}^{n-1} \to 0$ となる。 はさみうちの原理より、

$$ \lim_{n \to \infty} (1 - p_n) = 0 $$

よって、求める極限は

$$ \lim_{n \to \infty} p_n = 1 $$

である。

解説

樹形図（完全二分木）のようなネットワークにおける確率の漸化式を立てる典型問題である。自己相似性に着目し、部分木（ここでは $T_n$）の状態を利用して漸化式を構築するアプローチが重要である。極限の計算においては、漸化式が非線形（2次式）であるため一般項を求めることができないが、誘導に従って不等式評価を行うことで極限を求める手法も頻出である。

答え

(1)

$p_{n+1} = \{ p + (1 - p)p_n \}^2$

(2)

解法1に示した通り

(3)

$1$