確率漸化式の素朴な問題（Mathlog新機能実験）

この記事の目標

次の問題を解きます。出典は覚えていないのですが，以前友人に出題されたことのある問題です。しかも状況がかなり分かりやすいので，有名問題かもしれません。

以下，この問題に$2$通りの答案を与えていきます。

分からないなら文字で置けばいいじゃない？

僕は，わからないものは文字で置きまくれば幸せになれるという思考の持ち主です。そのため，大量に文字を置きつつ答案を作っていきます。

以下，合同式は法を3としたものを考えているものとします。

⑴の解答

$1-p_n$は，$n$回投げて出た目がすべて3の倍数でない確率に等しいから，$$ 1-p_n=\left(\bunsuu46\right)^n,\qquad\style{font-family:inherit}{\text{つまり，}}\qquad \bm{p_n=1-\left(\bunsuu23\right)^n} $$

⑵の解答

$Y_n\equiv 1$となる確率を$a_n$，$Y_n\equiv2$となる確率を$b_n$とする。このとき$n\geqq2$に対して，

• $Y_{n-1}\equiv 0$のとき，$n$回目は3または6が出ればよい。
• $Y_{n-1}\equiv 1$のとき，$n$回目は2または5が出ればよい。
• $Y_{n-1}\equiv 2$のとき，$n$回目は1または4が出ればよい。

つまり，確率遷移図は次のようになる。（ただし矢印は$\bunsuu13$を表す。）
$$ \xymatrix { *++[o][F-]{q_n\vphantom{b}} \ar[dr] \ar[r]\ar[ddr] & *++[o][F-]{\!\!\rlap{q_{n+1}}\hphantom{a_n}\vphantom{b}\,\,} \\*++[o][F-]{a_n\vphantom{b}} \ar[r]\ar[dr]\ar[ur] & *++[o][F-]{\!\!\rlap{a_{n+1}\vphantom{b}}\hphantom{q_n}\,\,} \\*++[o][F-]{b_n} \ar[r]\ar[ur]\ar[uur] & *++[o][F-]{\!\!\rlap{b_{n+1}}\hphantom{q_n}\,\,} \\ }$$

よって，$q_n=\bunsuu13q_{n-1}+\bunsuu13a_{n-1}+\bunsuu13b_{n-1}=\bunsuu13(q_{n-1}+a_{n-1}+b_{n-1})=\bunsuu13$である。（$n\geqq2$）

また，$n=1$のときは$q_1=\bunsuu13$であるから，すべての自然数$n$について$\bm{q_n=\bunsuu13}$

（同様に，$a_n=b_n=\bunsuu13$もすべての自然数$n$について成り立つ。）

⑶の解答

次のように記号を定める：

• $X_n\equiv0$かつ$Y_n\equiv0$となる確率を$r_n$（$r_1=\bunsuu13$）
• $X_n\equiv0$かつ$Y_n\equiv1$となる確率を$c_n$（$c_1=0$）
• $X_n\equiv0$かつ$Y_n\equiv2$となる確率を$d_n$（$d_1=0$）
• $X_n\not\equiv0$かつ$Y_n\equiv0$となる確率を$e_n$（$e_1=0$）
• $X_n\not\equiv0$かつ$Y_n\equiv1$となる確率を$f_n$（$f_1=\bunsuu13$）
• $X_n\not\equiv0$かつ$Y_n\equiv2$となる確率を$g_n$（$g_1=\bunsuu13$）

このとき，$r_n,c_n,d_n,e_n,f_n,g_n$における確率遷移図は右図のようになる。（ただし，矢印はすべて$\bunsuu13$を表している。）

$$ \xymatrix { *++[o][F-]{r_n\vphantom{b}} \ar[dr] \ar[r]\ar[ddr] & *++[o][F-]{\!\!\rlap{r_{n+1}}\hphantom{a_n}\vphantom{b}\,\,} \\*++[o][F-]{c_n\vphantom{b}} \ar[r]\ar[dr]\ar[ur] & *++[o][F-]{\!\!\rlap{c_{n+1}\vphantom{b}}\hphantom{q_n}\,\,} \\*++[o][F-]{d_n} \ar[r]\ar[ur]\ar[uur] & *++[o][F-]{\!\!\rlap{d_{n+1}}\hphantom{q_n}\,\,} \\ *++[o][F-]{e_n\vphantom{b}} \ar[dr] \ar@[blue][uuur]\ar[ddr] & *++[o][F-]{\!\!\rlap{e_{n+1}}\hphantom{a_n}\vphantom{b}\,\,} \\*++[o][F-]{f_n\vphantom{b}} \ar@[blue][uuur]\ar[dr]\ar[ur] & *++[o][F-]{\!\!\rlap{f_{n+1}\vphantom{b}}\hphantom{q_n}\,\,} \\*++[o][F-]{g_n\vphantom{b}} \ar@[blue][uuur]\ar[ur]\ar[uur] & *++[o][F-]{\!\!\rlap{g_{n+1}}\vphantom{b}\hphantom{q_n}\,\,} \\ }$$
数式で表すと，以下の通り。$$ \begin{cases} r_{n+1}=\bunsuu13r_n+\bunsuu13c_n+\bunsuu13d_n+\bunsuu13e_n& \cdots\cdots\style{font-family:inherit}{\text{①}}\\ c_{n+1}=\bunsuu13r_n+\bunsuu13c_n+\bunsuu13d_n+\bunsuu13f_n& \cdots\cdots\style{font-family:inherit}{\text{②}}\\ d_{n+1}=\bunsuu13r_n+\bunsuu13c_n+\bunsuu13d_n+\bunsuu13g_n& \cdots\cdots\style{font-family:inherit}{\text{③}}\\ e_{n+1}=\bunsuu13f_n+\bunsuu13g_n& \cdots\cdots\style{font-family:inherit}{\text{④}}\\ f_{n+1}=\bunsuu13e_n+\bunsuu13g_n& \cdots\cdots\style{font-family:inherit}{\text{⑤}}\\ g_{n+1}=\bunsuu13e_n+\bunsuu13f_n& \cdots\cdots\style{font-family:inherit}{\text{⑥}}\\ \end{cases} $$

また，

• $r_n+e_n=(Y_n\equiv0\style{font-family:inherit}{\text{となる確率}})=q_n=\bunsuu13\quad \cdots\cdots$⑦
• $c_n+f_n=(Y_n\equiv1\style{font-family:inherit}{\text{となる確率}})=a_n=\bunsuu13\quad \cdots\cdots$⑧
• $d_n+g_n=(Y_n\equiv2\style{font-family:inherit}{\text{となる確率}})=b_n=\bunsuu13\quad \cdots\cdots$⑨

である。さらに，数列$\suuretu{f_n-g_n}$について，⑤と⑥より，$$ f_1-g_1=0,\quad f_{n+1}-g_{n+1}=-\bunsuu13\left(f_n-g_n\right) $$
であるため，すべての自然数$n$について$f_n-g_n=0$であり，$f_n=g_n$である。特に⑧⑨より，$c_n=d_n$である。よって，①②は，④～⑨及び$c_n=d_n$を代入することで，①については，$$ \begin{align} &r_{n+1}=\bunsuu13r_n+\bunsuu13c_n+\bunsuu13c_n+\bunsuu13\left(\bunsuu13-r_n\right)\\ \therefore\quad &r_{n+1}=\bunsuu23c_n+\bunsuu19. \end{align} $$
②については，$$ \begin{align} &c_{n+1}=\bunsuu13r_n+\bunsuu13c_n+\bunsuu13c_n+\bunsuu13\left(\bunsuu13-c_n\right)\\ \therefore\quad &c_{n+1}=\bunsuu13r_n+\bunsuu13c_n+\bunsuu19. \end{align} $$
と変形できる。この二式を用いて数列$\suuretu{r_n}$の一般項を求めよう。$r_{n+1}=\bunsuu23c_n+\bunsuu19$より$r_{n+2}=\bunsuu23c_{n+1}+\bunsuu19$だから，$$ \bunsuu32\left(r_{n+2}-\bunsuu19\right)=\bunsuu13r_n+\bunsuu13\cdot\bunsuu32\left(r_{n+1}-\bunsuu19\right)+\bunsuu19$$
整理すると，$$ r_{n+2}-\bunsuu13r_{n+1}-\bunsuu29r_n=\bunsuu4{27}\quad \cdots\cdots\spadesuit $$
ここで，$r_n-\bunsuu13=s_n$とおくと，$s_1=0,s_2=-\bunsuu29$であり，$\spadesuit$は$$ s_{n+2}-\bunsuu13s_{n+1}-\bunsuu29s_n=0 $$
である。方程式$x^2-\bunsuu13x-\bunsuu29=0$の異なる2解を$\alpha,\beta\ (\alpha<\beta)$として，$$ s_{n+2}-\alpha s_{n+1}=\beta(s_{n+1}-\alpha s_n) $$
と変形できる。よって数列$\suuretu{s_{n+1}-\alpha s_n}$は，初項$-\bunsuu29$，公比$\beta$の等比数列なので，$$
s_{n+1}-\alpha s_n=-\bunsuu29\beta^{n-1}\quad\cdots\cdots\style{font-family:inherit}{\text{⑩}}
$$
同様に，$$
s_{n+2}-\beta s_{n+1}=\alpha(s_{n+1}-\beta s_n)
$$
と変形できるから，数列$\suuretu{s_{n+1}-\beta s_n}$は，初項$-\bunsuu29$，公比$\alpha$の等比数列より，$$
s_{n+1}-\beta s_n=-\bunsuu29\alpha^{n-1}\quad\cdots\cdots\style{font-family:inherit}{\text{⑪}}
$$
⑩⑪より，$$
s_n=-\bunsuu2{9(\beta-\alpha)}(\beta^{n-1}-\alpha^{n-1})=-\bunsuu{2}{9}\left{\left(\bunsuu23\right)^{n-1}-\left(-\bunsuu{1}{3}\right)^{n-1}\right}
$$$$
\therefore\quad \bm{r_n=\bunsuu13-\bunsuu29\left{\left(\bunsuu23\right)^{n-1}-\left(-\bunsuu13\right)^{n-1}\right}}
$$

⑶の別解を模索する

さすがに先ほどの解答の⑶は，模範的な解答ではないと思います。（自然な発想ではあるんですけどね。。。）

ということで，⑶の解答を，最短距離を目指した別解を提示します。

⑶の短い解答

⑴⑵で用いた$p_n,q_n$を用いると，$r_n$について，$$ r_{n+1}=\bunsuu13r_n+\bunsuu13(p_n-r_n)+\bunsuu13(y_n-r_n) $$
という関係式が成り立つ。すなわち，$$ r_{n+1}=-\bunsuu13r_n-\bunsuu13\left(\bunsuu{2}{3}\right)^n+\bunsuu49\qquad\cdots\cdots(\#) $$
この$(\#)$を変形すると，$$ r_{n+1}+\bunsuu13\left(\bunsuu23\right)^{n+1}-\bunsuu13=-\bunsuu13\left\{r_{n}+\bunsuu13\left(\bunsuu23\right)^{n}-\bunsuu13\right\} $$
となるため，数列$\left\{r_{n}+\bunsuu13\left(\bunsuu23\right)^{n}-\bunsuu13\right\}$は公比$-\bunsuu13$で初項は（頑張って計算すれば）$\bunsuu29$の等比数列である。すなわち，$$ \qquad r_{n}+\bunsuu13\left(\bunsuu23\right)^{n}-\bunsuu13=\bunsuu29\left(-\bunsuu13\right)^{n-1} $$
$$ \therefore\quad \bm{r_n=\bunsuu13-\bunsuu13\cdot\left(\bunsuu23\right)^n-\bunsuu23\cdot\left(-\bunsuu13\right)^n} $$

まとめ

というわけで今回は，問題こそ「和と積が$3$の倍数になる確率は？」と聞かれているだけでしたが，いざ手を動かしてみると難しい問題でした。これ，$\bmod 5$とか$\bmod 7$とかになったら，とんでも大変なことになるんじゃないかな。。。

この問題に対する別解を思いついた方は，コメントを頂けると嬉しいです！

また，新機能としてXypicが実装されましたね。いくつか図を書いてみましたが，いかがでしょうか。コメントいただけると嬉しいです。（ちなみに僕はTikZ派ですので，慣れない記法でしたね。。）