投げたときに表と裏の出る確率がそれぞれ \dfrac{1}{2} のコインがある。\mathrm{A}, \mathrm{B}, \mathrm{C} の 3 文字を \mathrm{BAC} のように 1 個ずつすべて並べて得られる文字列に対して，コインを投げて次の操作を行う。
表が出たら文字列の左から 1 文字目と 2 文字目を入れかえる。
裏が出たら文字列の左から 2 文字目と 3 文字目を入れかえる。
例えば，文字列が \mathrm{BAC} であるときに，2 回続けてコインを投げて表，裏の順に出たとすると，文字列は \mathrm{BAC} から \mathrm{ABC} を経て \mathrm{ACB} となる。
最初の文字列は \mathrm{ABC} であるとする。コインを n 回続けて投げたあとの文字列が \mathrm{ABC} である確率を p_n とし，\mathrm{BCA} である確率を q_n とする。
(1) k を正の整数とするとき，p_{2k}-q_{2k} を求めよ。
(2) n を正の整数とするとき，p_n を求めよ。
3 文字の並べ方は 6 通りです。操作は「左の 2 つを入れかえる」と「右の 2 つを入れかえる」の 2 つだけで、どちらも確率 \dfrac{1}{2} です。
どちらの操作も、2 つの文字を入れかえるだけです。入れかえを 1 回すると並びの偶奇が変わりますから、\mathrm{ABC} から偶数回で行けるのは \mathrm{ABC}, \mathrm{BCA}, \mathrm{CAB} の 3 つ、奇数回で行けるのは \mathrm{ACB}, \mathrm{BAC}, \mathrm{CBA} の 3 つです。
ですから n が奇数のとき p_n = 0 です。\mathrm{BCA} も偶数側なので q_n = 0 です。(1) が偶数回だけを聞いているのは、奇数回では両方とも 0 で差が取れないからです。
6 通りを \mathrm{ABC}, \mathrm{BAC}, \mathrm{BCA}, \mathrm{CBA}, \mathrm{CAB}, \mathrm{ACB} の順に輪に並べると、表の移り先と裏の移り先がちょうど両隣になります。つまりこの操作は、6 点の輪を右か左へ 1 つずつ、確率 \dfrac{1}{2} で進んでいくだけのものです。
\mathrm{ABC} に着くのは、直前が \mathrm{BAC} で表が出たときか、\mathrm{ACB} で裏が出たときです。\mathrm{BCA} に着くのは、直前が \mathrm{CBA} で表のときか、\mathrm{BAC} で裏のときです。
式にすると p_{n+1} = \dfrac{1}{2}\{P_n(\mathrm{BAC})+P_n(\mathrm{ACB})\}、q_{n+1} = \dfrac{1}{2}\{P_n(\mathrm{CBA})+P_n(\mathrm{BAC})\} です。ここで P_n はその文字列にいる確率です。
引くと \mathrm{BAC} の項が消えて p_{n+1}-q_{n+1} = \dfrac{1}{2}\{P_n(\mathrm{ACB})-P_n(\mathrm{CBA})\} となります。同じように \mathrm{ACB} と \mathrm{CBA} を調べると、今度は \mathrm{CAB} の項が消えて P_{n+1}(\mathrm{ACB})-P_{n+1}(\mathrm{CBA}) = \dfrac{1}{2}(p_n-q_n) です。
2 つの差が、1 回ごとに半分になって互いへ移ります。2 回で \dfrac{1}{4} 倍です。p_0-q_0 = 1-0 = 1 ですから、p_{2k}-q_{2k} = \left(\dfrac{1}{4}\right)^k です。
偶数回のあとは \mathrm{ABC}, \mathrm{BCA}, \mathrm{CAB} の 3 つしかありません。そこで 2 回をひとまとめにして、この 3 つの間の移り方だけを見ます。
\mathrm{ABC} からは 1 回目で \mathrm{BAC} か \mathrm{ACB} へ行きます。\mathrm{BAC} からは \mathrm{ABC} か \mathrm{BCA}、\mathrm{ACB} からは \mathrm{CAB} か \mathrm{ABC} です。
つなぐと、2 回で \mathrm{ABC} に戻る確率が \dfrac{1}{4}+\dfrac{1}{4} = \dfrac{1}{2}、\mathrm{BCA} と \mathrm{CAB} へはそれぞれ \dfrac{1}{4} です。輪で見れば、2 回で戻るか、右へ 2 つか、左へ 2 つか、というだけのことです。どの点から出発しても同じ形になります。
a_k = p_{2k} とおきます。他の 2 つの確率の和は 1-a_k ですから、a_{k+1} = \dfrac{1}{2}a_k + \dfrac{1}{4}(1-a_k) = \dfrac{1}{4}a_k + \dfrac{1}{4} という 1 本の漸化式になります。
a = \dfrac{1}{4}a+\dfrac{1}{4} の解は a = \dfrac{1}{3} です。そこから a_{k+1}-\dfrac{1}{3} = \dfrac{1}{4}\left(a_k-\dfrac{1}{3}\right) と書けます。
a_0 = 1（まだ投げていないので \mathrm{ABC}）ですから、a_k-\dfrac{1}{3} = \dfrac{2}{3}\left(\dfrac{1}{4}\right)^k、つまり a_k = \dfrac{1}{3}+\dfrac{2}{3}\left(\dfrac{1}{4}\right)^k です。
n = 2k のとき 4^k = 2^{2k} = 2^n ですから、n が偶数なら p_n = \dfrac{1}{3}+\dfrac{2}{3 \cdot 2^n} です。n が奇数なら p_n = 0 です。
q_{2k} も同じ漸化式をみたし、q_0 = 0 から q_{2k} = \dfrac{1}{3}-\dfrac{1}{3}\left(\dfrac{1}{4}\right)^k です。差を取ると \left(\dfrac{1}{4}\right)^k で、(1) と合います。回数を増やすと 3 つの確率はどれも \dfrac{1}{3} に近づきます。