反復試行3

今日の1題

ランダムウォークの確率

今日はランダムウォークの確率について考えます。ランダムウォークの確率とは，数直線，座標平面，座標空間内に点がありこれがランダムに動くとき，この点がある点に到達する確率を求める問題です。それでは，1題やってみたいと思います。

大体つかめたでしょうか。大学入試でもよく出題されるので見たことがある方も多いと思います。今日は少し複雑なランダムウォークの確率について考えたいと思います。そのための準備として，まずカタラン数について考えます。

カタラン数

カタラン数というものは色々な場面に登場します。今日は最短経路の数の問題に現れるカタラン数について考えます。

ランダムウォークとカタラン数

それでは，カタラン数が出てくるランダムウォークの問題について考えます。

(3)のように条件が複雑になってきたら，表の回数，裏の回数をグラフにして最短経路の数の問題に持ちこむとよいと思います。これ位であれば，各交差点にくる場合の数を計算して地道に計算していけばよいと思います。小学生のときにやったやつです。それでは，今日の1題です。

いかがでしたでしょうか。この問題でもやはり地道に書いていった方がよいと思います。今日のような階段状の道の最短経路の数を一般的に求める問題は，やった経験がないとなかなか難しいと思います。これ以上難しいものは大学入試ではあまり出題されないかもしれませんが，一応1996年に北大(前期)に出題があります。この問題はかなり厳しいと思いますが，なかなか面白いと思います。それではその問題を紹介して今日は終わりたいと思います。ではまた。