[math][東京工業大学][確率]2017年東京工業大学数学問題4

Table of Contents

問題

$n$は正の整数とし、文字$a, b, c$を重複を許して$n$個並べてできる文字列すべての集合を$A_n$とする。$A_n$の要素に対し次の条件（＊）を考える。
（＊）文字$c$が$2$つ以上連続して現れない。
以下$A_n$から要素を一つ選ぶとき、どの要素も同じ確率で選ばれるとする。
$(1)$ $A_n$から要素を一つ選ぶとき、それが条件（＊）を満たす確率$P(n)$を求めよ。
$(2)$ $n\geq 12$とする。$A_n$から要素を一つ選んだところ、これは条件（＊）を満たし、その$7$番目の文字は$c$であった。このとき、この要素の$10$番目の文字が$c$である確率を$Q(n)$とする。極限値$\displaystyle \lim_{n\to\infty}{Q(n)}$を求めよ。

方針

$(1)$ 漸化式を立てる。$A_n$の最後の文字に着目すると良い。

$(2)$ 条件付き確率を考える。

解答

$(1)$ $A_n$の要素の個数は$3^n$である。条件（＊）を満たす$A_n$の要素に対して、末尾の文字が何になるかで場合分けする。条件（＊）を満たす$A_n$の個数を$p_n$とし、$p_n$のうち末尾が$a, b, c$であるものの個数をそれぞれ$a_n, b_n, c_n$とする。すなわち、$$p_n = a_n+b_n+c_n \tag{a}\label{a}$$である。$p_1 = 3, p_2 = 8$である（$n = 2$のときは$“cc”$が条件を満たさない）。$p_n$の末尾に文字を追加し、$p_{n+1}$を作るとき、$a_n, b_n$には$a, b, c$のどれを追加しても条件を満たす。$c_n$は、$a, b$を追加したときだけ条件を満たす。したがって、$$p_{n+1} = 3(a_n+b_n) + 2c_n \tag{b}\label{b}$$である。

また、次の漸化式が成り立つ。$$\begin{cases}a_{n+1} & = & a_n + b_n + c_n\\ b_{n+1} & = & a_n + b_n + c_n\\ c_{n+1} & = & a_n+b_n\end{cases} \tag{c}\label{c}$$

さらに、対称性から$$a_n = b_n \tag{d}\label{d}$$である。

\eqref{d}を\eqref{c}に代入して、$$\begin{cases}a_{n+1} & = & 2a_n+c_n\\ c_{n+1} & = & 2a_n\end{cases} \tag{e}\label{e}$$である。したがって、$$\begin{eqnarray}a_{n+2} & = & 2a_{n+1}+c_{n+1}\\ & = & 2a_{n+1}+2a_{n}\end{eqnarray}$$である。\eqref{a}, \eqref{c}から、$p_n = a_{n}+b_n+c_n = a_{n+1}$であるから、$p_{n+2} = 2p_{n+1}+2p_{n}$である。この漸化式を解く。特性方程式$t^2=2t+2$を解くと、$t = 1\pm \sqrt{3}$となる。したがって、$p_n = A(1-\sqrt{3})^{n-1} + B(1+\sqrt{3})^{n-1}$の形で表すことができる。$p_1 = 3, p_2 = 8$であるから、$$\begin{cases}A+B & =& 3\\ A(1-\sqrt{3})+B(1+\sqrt{3}) & = & 8\end{cases}$$である。これから、$\displaystyle A=\frac{1}{2}\left(3-\frac{5\sqrt{3}}{3}\right), B = \frac{1}{2}\left(3+\frac{5\sqrt{3}}{3}\right)$となる。もう少し整理すると、$\displaystyle (1-\sqrt{3})^3 = -2\sqrt{3}\left(3-\frac{3\sqrt{3}}{5}\right), (1+\sqrt{3})^3 = 2\sqrt{3}\left(3+\frac{3\sqrt{3}}{5}\right)$であるから、$\displaystyle A = -\frac{1}{4\sqrt{3}}(1-\sqrt{3})^3, B = \frac{1}{4\sqrt{3}}(1+\sqrt{3})^3$となり、$\displaystyle p_n = \frac{1}{4\sqrt{3}}(-(1-\sqrt{3})^{n+2}+(1+\sqrt{3})^{n+2})$がわかる。以上から、$\displaystyle P(n) = \frac{p_n}{3^n} = \underline{\frac{1}{4\sqrt{3}\cdot 3^n}(-(1-\sqrt{3})^{n+2}+(1+\sqrt{3})^{n+2})}$である。

$(2)$ $A_n$から要素を一つ選び、それが条件（＊）を満たし、かつその$7$番目の文字が$c$である確率を$q_n$とする。まず、$6$番目の文字は$a$か$b$でなくてはならず、また$8$番目の数字も$a$か$b$でなくてはならない。この確率は、$\displaystyle q_n = \frac{p_5\cdot 2\cdot 1\cdot 2\cdot p_{n-8}}{3^n}$である。また、$A_n$から要素を一つ選び、それが条件（＊）を満たし、かつその$7$番目と$10$番目の数字が$c$である確率を$r_n$とする。このときも$6,8, 9, 11$番目の数字は$a$か$b$でなければならない。この確率は、$\displaystyle r_n = \frac{p_5\cdot 2\cdot 1 \cdot 2\cdot 2\cdot 1\cdot 2\cdot p_{n-11}}{3^n}$である。求める確率$Q(n)$は、条件付き確率$Pr(r_n|q_n)$である。簡単のため$\displaystyle \alpha = 1-\sqrt{3}, \beta = 1+\sqrt{3}, \gamma = \frac{\alpha}{\beta}$と置いておくと、$|\gamma| < 1$であり、$$\begin{eqnarray}Q(n) & = & Pr(r_n|q_n)\\ & = & \frac{r_n}{q_n} \\ & = & \frac{4p_{n-11}}{p_{n-8}}\\ & = & 4\cdot \frac{-{\alpha}^{n-9}+{\beta}^{n-9}}{-{\alpha}^{n-6}+{\beta}^{n-6}}\\ & = & 4\frac{-{\gamma}^{n-9}+1}{{\beta}^3(-{\gamma}^{n-9}{\alpha}^3+1)}\\ & \to & \frac{4}{{\beta}^3}\\ & = & \frac{4}{(1+\sqrt{3})^3} \\ & = & \frac{2}{5+3\sqrt{3}}\\ & = & \underline{3\sqrt{3}-5}\end{eqnarray}$$となる。