確率漸化式の計算泥沼を泳ぎ切れ – 2017年東工大 数学 第4問
2017年東工大 数学 第4問 は、定番と言える、確率と漸化式の組み合わせです。問題文は以下の通りです。
n は正の整数とし、文字 a, b,c を重複を許して n 個並べてできる文字列の集合を A_n とする。 A_n の要素に対し次の条件(*)を考える。
(*) 文字 c が2つ以上連続して現れない。
以下 A_n から要素を一つ選ぶとき、どの要素も同じ確率で選ばれるとする。
(1) A_n から要素を一つ選ぶとき、それが条件(*)を満たす確率 P(n) を求めよ。
(2) n \geqq 12 とする。 A_n から要素を一つ選んだところ、これは条件(*)を満たし、その7番目の文字は c であった。このとき、この要素の10番目の文字が c である確率を Q(n) とする。極限値 \lim_{n \to \infty} Q(n) を求めよ。
題意は一般項の導出を求めているので、漸化式を立てられれば、何とかなると期待できます。早速取り掛かります。
なお、以下の内容は、東工大が公表したものではありません。
小問１の解法
漸化式の立式
以下、条件(*)を満たす文字列だけを考慮します。
文字を左から右に1文字ずつ追加して文字列を生成するものとします。一番右の n 番目の文字が a,b のとき、その1文字前の n-1 番目の文字は何でもＯＫですが、 n 番目の文字が c のときは、 n-1 番目の文字は a か b のいずれかである必要があります。
一番右の文字がひとつ前の文字に依存して決まるということは、一番右の文字が何かによって、次の文字が決まってくるということなので、それぞれごとに確率を求めることにします。すなわち、
R(n) = A_n から選んだ文字列が条件(*)を満たし、かつ n 番目の文字が a か b である確率
S(n) = A_n から選んだ文字列が条件(*)を満たし、かつ n 番目の文字が c である確率
と定義します。このとき、以下の式が成り立ちます。
\begin{aligned}
& P(n) = R(n) +S(n) & \cdots(1)\\
& R(n+1) = \frac{2}{3}P(n) \\
& = \frac{2}{3} \{R(n) +S(n) \} & \cdots(2)\\
& S(n+1) = \frac{1}{3} R(n) & \cdots (3) \\
& \text{ } ( n \geqq 1)
\end{aligned}式(2)および式(3)から、
\begin{aligned}
R(n+1) - \frac{2}{3} R(n) -\frac{2}{9} R(n-1) = 0 \\
(n \geqq 2)
\end{aligned}が成り立ちます。
漸化式を解く
ここで2次方程式
x^2-\frac{2}{3} x -\frac{2}{9} = 0の2つの解を \alpha, \beta(\alpha<\beta) と置きます。
\begin{aligned}
& \alpha = \frac{1 + \sqrt{3} }{3} \\
& \beta = \frac{1 - \sqrt{3} }{3} \\
\end{aligned}です。
漸化式(3)は一般的な3項漸化式の手法によって、以下のように一般項を求めることが出来ます。
\begin{aligned}
& R(n) = \frac{1}{\beta -\alpha} \{ (\beta^{n-1} -\alpha^{n-1}) R(2) \\
& \text{ }- \alpha\beta (\beta^{n-2} -\alpha^{n-2}) R(1) \} \\
& \text{ } ( n \geqq 3)
\end{aligned}ここで
\begin{aligned}
& \beta -\alpha = \frac{2 \sqrt{3} } {3} \\
& \alpha \beta = -\frac{2}{9} \\
& R(1) = \frac{2}{3} \\
& R(2) = \frac{2}{3}
\end{aligned}なので、これらを代入して
\begin{aligned}
& R(n) = \frac{\sqrt3}{2} \{ \frac{2}{3} (\beta^{n-1} -\alpha^{n-1}) \\
& \text{ }+ \frac{4}{27} (\beta^{n-2} -\alpha^{n-2}) \} \\
& = \text{ } \frac{ \sqrt3}{2} \{ (\frac{2}{3} \beta + \frac{4}{27}) \beta^{n-2} \\
& \text{ }- (\frac{2}{3} \alpha+ \frac{4}{27} ) \alpha^{n-2} \} \\
& \text{ } ( n \geqq 3)
\end{aligned}となりますが、実は
\begin{aligned}
& \frac{2}{3} \beta + \frac{4}{27} = \frac{6 + 6 \sqrt{3} +4}{27} \\
& = \frac{10 + 6 \sqrt{3} }{27} \\
& = \frac{(1 + \sqrt{3} )^3}{27} = \beta^3
\end{aligned}\begin{aligned}
& \frac{2}{3} \alpha + \frac{4}{27} = \frac{6 - 6 \sqrt{3} +4}{27} \\
& = \frac{10 - 6 \sqrt{3} }{27} \\
& = \frac{(1 - \sqrt{3} )^3}{27} = \alpha^3
\end{aligned}なので、
\begin{aligned}
& R(n) = \frac{\sqrt3}{2} (\beta^{n+1} -\alpha^{n+1}) \\
& \text{ } ( n \geqq 1)
\end{aligned}となります。
一般項 P(n) を求める
したがって、式(1)および式(3)より、
\begin{aligned}
& P(n) = R(n) + \frac{1}{3}R(n-1) \\
& \text{ } = \frac{\sqrt3}{2} (\beta^{n+1} -\alpha^{n+1}) \\
& \text{ } + \frac{\sqrt3}{6} (\beta^{n} -\alpha^{n}) \\
& \text{ } = \frac{\sqrt3}{2} \{ (\beta + \frac{1}{3}) \beta^{n} - (\alpha + \frac{1}{3})\alpha^{n}) \\
& \text{ } ( n \geqq 1)
\end{aligned}ですが、ここで
\begin{aligned}
& \beta + \frac{1}{3} = \frac{1 + \sqrt{3} +1}{3} \\
& = \frac{2 + \sqrt{3} }{3} \\
& = \frac{3}{2} \cdot \frac{4 + 2 \sqrt{3} }{9} \\
& = \frac{3}{2} \cdot \frac{(1 + \sqrt{3})^2 }{9} = \frac{3}{2} \beta^2
\end{aligned}\begin{aligned}
& \alpha + \frac{1}{3} = \frac{1 - \sqrt{3} +1}{3} \\
& = \frac{2 - \sqrt{3} }{3} \\
& = \frac{3}{2} \cdot \frac{4 - 2 \sqrt{3} }{9} \\
& = \frac{3}{2} \cdot \frac{(1 - \sqrt{3})^2 }{9} = \frac{3}{2} \alpha^2
\end{aligned}なので、
\begin{aligned}
&P(n) = \frac{3\sqrt3}{4} (\beta^{n+2} - \alpha^{n+2}) \\
&= \frac{3\sqrt3}{4} \left \{ \left ( \frac{1+\sqrt{3}}{3} \right)^{n+2} - \left ( \frac{1- \sqrt{3}}{3} \right )^{n+2} \right \} \\
& \text{ } ( n \geqq 1)
\end{aligned}となります。
小問２の解法
小問1とは別の確率 Q(n) の極限を求められていますが、この Q(n) は、条件付確率なので注意しましょう。
一般に、事象 A が起きた時に事象 B が起きる条件付確率 P(B|A) は、
P(B|A) = \frac{P(A \cap B)}{P(A)}で算出できます。
文字列長を n とします。事象 A, B を、
事象 A = 文字列 a \in A_n が条件(*)を満たし、かつ7番目の文字が c である
事象 B = 文字列 a \in A_n が条件(*)を満たし、かつ10番目の文字が c である
と定義します。このとき、求める Q(n) は P(B|A) なので、 P(A) と P(A \cap B) の具体的な値を求めます。
P(A) の導出
事象 A を満たす文字列は、
| 文字順 | 文字列の内容 |
|---|---|
| 1～6 | 条件(*)を満たす6文字の文字列で、かつ6文字目が a, b のいずれか |
| 7 | c |
| 8 | a, b のいずれか |
| 9以降 | 条件(*)を満たす n- 8 文字の文字列 |
の構造をとるので、 P(A) は
P(A) = R(6) \cdot \frac{1}{3} \cdot \frac{2}{3} \cdot P(n-8)となります。
P(A \cap B) の導出
事象 B を満たす文字列は、
| 文字順 | 文字列の内容 |
|---|---|
| 1～6 | 条件(*)を満たす6文字の文字列で、かつ6文字目が a, b のいずれか |
| 7 | c |
| 8,9 | a, b のいずれか |
| 10 | c |
| 11 | a, b のいずれか |
| 12以降 | 条件(*)を満たす n- 11 文字の文字列 |
の構造をとるので、 P(A \cap B) は
\begin{aligned}
& P(A \cap B ) \\
& = R(6) \cdot \frac{1}{3} \cdot \left( \frac{2}{3} \right)^2 \cdot \frac{1}{3} \cdot \frac{2}{3} \cdot P(n-11)
\end{aligned}となります。
Q(n) の導出と極限
以上の計算により、
\begin{aligned}
& Q(n ) \\
& = \frac {R(6) \cdot \frac{1}{3} \cdot \left( \frac{2}{3} \right)^2 \cdot \frac{1}{3} \cdot \frac{2}{3} \cdot P(n-11)}{R(6) \cdot \frac{1}{3} \cdot \frac{2}{3} \cdot P(n-8)} \\
& = \frac { \frac{2}{3} \cdot \frac{1}{3} \cdot \frac{2}{3} \cdot P(n-11)} { P(n-8)} \\
& = \frac{ 4 (\beta^{n-9} - \alpha^{n-9})}{ 27 (\beta^{n-6} - \alpha^{n-6}) } \\
& = \frac { 4 ( 1- ( \frac{\alpha}{\beta} )^{n-9})} { 27 (\beta^{3} - \alpha^{3} ( \frac{\alpha}{\beta} )^{n-9} ) } \\
\end{aligned}です。ところが、 | \frac{\alpha}{\beta}| < 1 なので、
\lim_{n \to \infty} \left ( \frac{\alpha}{\beta} \right )^{n-9} = 0が成り立ちます。したがって、
\begin{aligned}
& \lim_{n \to \infty} Q(n ) \\
& = \frac { 4 } { 27 \beta^{3} } \\
& = \frac { 4 } { 27 ( \frac{1 + \sqrt{3} }{3})^{3} } \\
& = \frac { 4 } { 10 + 6\sqrt{3} } \\
& = 3 \sqrt{3} - 5
\end{aligned}となります。
解法のポイント
本稿は漸化式を立てて一般項を求めるタイプの問題ですが、その漸化式を立てるのに、ちょっと工夫が必要です。一気に導くことが難しいようなら、一歩引いて、本稿のように複数の漸化式を立ててみるというのも、一つの考え方です。代数の問題を解く時に、不明な変数をとりあえず x, y,z と置いて連立方程式を立ててみる、というのと同じ発想です。
一般解導出のための計算は泥沼と言うほどではないかもしれませんが、ちょっといやらしいので、ミスをしないよう気をつけましょう。途中に出てくる
\begin{aligned}
& \frac{2}{3} \beta + \frac{4}{27} = \frac{6 + 6 \sqrt{3} +4}{27} \\
& = \frac{10 + 6 \sqrt{3} }{27} \\
& = \frac{(1 + \sqrt{3} )^3}{27} = \beta^3
\end{aligned}みたいな計算は、気が付かなくても減点の対象にならないと思いますが、これのおかげで一般項がよりすっきりと表現できます。入試問題なのでこのようにきれいに片づけられるよう、配慮されている可能性は高いので、計算の結果が妙に汚い場合は、このような整理が出来ないか、一応検討してみてください。逆にどうやってもすっきりした表現にならない場合は、計算ミスを疑ってみましょう。