PyMCで学ぶベイズ統計モデリング｜イカサマコインの判別にチャレンジ
Aru
Aru's テクログ（Aruaru0）
漸化式（２） a(n+1)=pa(n)+q
Aru
漸化式の２つめの記事です。ここでは、以下の形をした漸化式の解法を説明します。
対象とする漸化式のパターン
$$
a_{n+1} = p a_{n} + q
$$
解き方
以下の形の漸化式の解を求めます。
$$
a_{n+1} = p a_{n} + q
$$
結構見かける形で、基本は次のような形に変形します。
$$
(a_{n+1} – \alpha) = p(a_n – \alpha)
$$
ここで、$b_n = a_n – {\alpha} $ とおけば $b_{n+1} = pb_n$ となって等比数列になります。
では、上記の形に変形するにはどうすれば良いでしょうか。
この形にするには、以下のように考えます。
まず、$(a_{n+1} – \alpha) = p(a_n – \alpha)$を以下のように変形します。
$$
\begin{eqnarray}
(a_{n+1} – \alpha) = p(a_n – \alpha)\\
a_{n+1}= pa_n – p\alpha + \alpha
\end{eqnarray}
$$
ここで、元の式$a_{n+1}=pa_n+q$と比較すると、次の関係が成り立つことがわかります。
$$ -p\alpha + \alpha = q $$
つまり、この式を満たす$\alpha$を計算すればよいことになります。
この式を変形すると、 $ \alpha = p\alpha + q $ となり、昔習った特性方程式となります。
高校時代に、私が習った先生は、「とりあえず、$a_{n+1}$と$a_n$を$x$に置き換えなさい」と、こんなもんだと覚えなさいということで、なんか引っかかっていましたが、ちゃんと導出したらスッキリしました。そんなに導出も難しくないんだからちゃんと教えてくれても良さそうですが。
実際に、問題を解いてみる
実際に問題を解いてみます。
問題
$a_1 = 3$、$a_{n+1} = 3a_n – 4$を$ｎ$で表せ。
特性方程式は、以下の通り
$$ \begin{eqnarray} \alpha &=& 3\alpha – 4\\ 2\alpha &=& 4\\ \alpha &=& 2 \end{eqnarray} $$
式を変形して、
$$
a_{n+1} – 2 = 3(a_n – 2)
$$
試験などでは、一応、上の式と問題の式が一致していることを確認した方が良いかと思います。
$$
b_n = a_n – 2
$$
とすると、
$$
b_{n+1} = 3b_n
$$
$$
b_1 = a_1 – 2 = 3 – 2 = 1
$$
したがって、
$$
b_n = 3^{n-1}
$$
ここで、$b_n = a_n – 2$を代入して、
$$
a_n – 2 = 3^{n-1}
$$
$$
a_n = 3^{n-1} + 2
$$
以上で解がもとまりました。
このパターンは、漸化式の中でも簡単な方です。計算ミスだけが怖いので、計算ミスだけは注意しましょう。
ABOUT ME
専門分野は並列処理・画像処理・機械学習・ディープラーニング。プログラミング言語はC, C++, Go, Pythonを中心として色々利用。現在は、Kaggle, 競プロなどをしながら悠々自適に活動中