ランダムウォークでは、0点からスタートして+1点または-1点を繰り返す試行がよく扱われます。今回は、15回目に+5点に到達して終了する場合のパターン数を考えます。
ランダムウォークの条件整理
今回の条件は次の通りです。
- 開始点：0点
- 各ステップ：+1点 または -1点
- 終了条件：+5点に到達した時点
- 15ステップで到達
この条件は「反射境界問題」と呼ばれるもので、途中で+5点を超えないように制約がつきます。
カタラン数との関連
カタラン数 C_n は、長さ 2n の道で、原点を下回らずに到達するパターン数として使えます。今回は +5点がゴールなので、反射境界を設けた場合、15ステップでゴールに達するパターンは修正カタラン数を使って計算可能です。
計算の進め方
まず、ステップ数を n = 15、ゴールを k = 5 として考えます。ゴールに到達するパターン数は次の式で表されます：
Number of paths = C(15, 10) – C(15, 11)
ここで C(n, r) は組み合わせの二項係数です。
理由は、正しいパターンは最終的に+5に到達するもので、途中で+5を超えない条件を引き算で考えるためです。
数値計算例
C(15,10) = 3003
C(15,11) = 1365
従って、パターン数 = 3003 – 1365 = 1638
まとめ
0点から始めて+1または-1のランダムウォークで、15回目に+5点に到達して終了するパターンは 1638通り です。途中で+5を超えない制約があるため、修正カタラン数の考え方が便利です。
コメント