投げたときに表と裏の出る確率がそれぞれ のコインがある。, , の 文字を のように 個ずつすべて並べて得られる文字列に対して，コインを投げて次の操作を行う。
表が出たら文字列の左から 文字目と 文字目を入れかえる。
裏が出たら文字列の左から 文字目と 文字目を入れかえる。
例えば，文字列が であるときに， 回続けてコインを投げて表，裏の順に出たとすると，文字列は から を経て となる。
最初の文字列は であるとする。コインを 回続けて投げたあとの文字列が である確率を とし， である確率を とする。
(1) を正の整数とするとき， を求めよ。
(2) を正の整数とするとき， を求めよ。
文字の並べ方は 通りです。操作は「左の つを入れかえる」と「右の つを入れかえる」の つだけで、どちらも確率 です。
どちらの操作も、 つの文字を入れかえるだけです。入れかえを 回すると並びの偶奇が変わりますから、 から偶数回で行けるのは , , の つ、奇数回で行けるのは , , の つです。
ですから が奇数のとき です。 も偶数側なので です。(1) が偶数回だけを聞いているのは、奇数回では両方とも で差が取れないからです。
通りを , , , , , の順に輪に並べると、表の移り先と裏の移り先がちょうど両隣になります。つまりこの操作は、 点の輪を右か左へ つずつ、確率 で進んでいくだけのものです。
に着くのは、直前が で表が出たときか、 で裏が出たときです。 に着くのは、直前が で表のときか、 で裏のときです。
式にすると 、 です。ここで はその文字列にいる確率です。
引くと の項が消えて となります。同じように と を調べると、今度は の項が消えて です。
つの差が、 回ごとに半分になって互いへ移ります。 回で 倍です。 ですから、 です。
偶数回のあとは , , の つしかありません。そこで 回をひとまとめにして、この つの間の移り方だけを見ます。
からは 回目で か へ行きます。 からは か 、 からは か です。
つなぐと、 回で に戻る確率が 、 と へはそれぞれ です。輪で見れば、 回で戻るか、右へ つか、左へ つか、というだけのことです。どの点から出発しても同じ形になります。
とおきます。他の つの確率の和は ですから、 という 本の漸化式になります。
の解は です。そこから と書けます。
（まだ投げていないので ）ですから、、つまり です。
のとき ですから、 が偶数なら です。 が奇数なら です。
も同じ漸化式をみたし、 から です。差を取ると で、(1) と合います。回数を増やすと つの確率はどれも に近づきます。