ランダムウォークの基礎(一次元,高校範囲)

確率 12\dfrac{1}{2}+1+1 ポイント,12\dfrac{1}{2}1-1 ポイントとなるゲームを繰り返すような確率モデルを一次元ランダムウォークと言う。 ランダムウォークのイメージ

ランダムウォークは大学入試にも頻繁に登場する&現実のいろいろな現象の記述に使える重要なモデルです。

一次元ランダムウォークの具体例

以下のような現象,状況の記述にランダムウォークが登場します。

  • コイントス
    コイントスを行い,勝ったら1円もらえ,負けたら1円失うようなゲームを繰り返し行う。

  • 酔歩
    酔っぱらいが東西に伸びる一次元の直線を歩く。ただし,単位時間あたり1だけ東に進むか西に進む(それぞれ確率0.5)ことを繰り返す。
    注:ランダムウォークは酔歩,乱歩とも呼ばれます。

  • 株価の変動
    1日ごとの株価の変動。これは変動幅が一定ではないので後ほど紹介する「正規分布バージョン」を使う方が適切でしょう。

様々なランダムウォーク

  • 非対称バージョン
    +1+1 となる確率が pp1-1 となる確率が 1p1-p であるような非対称な状況もランダムウォークと言います。

  • 正規分布バージョン
    より一般に,もらえるポイントが正規分布に従う場合なども考えることがあります(例えば1回目の試行で0.3ポイント2回めの試行で-0.2ポイント得たりする)。

  • 高次元バージョン
    高次元のランダムウォークモデルも重要です。(例えば平面上で上下左右にそれぞれ 14\dfrac{1}{4} で動くモデル)

特定の位置xにいる確率

入試で頻出の重要な問題です。

例題

一次元ランダムウォークにおいて,nn ステップ後に xx ポイントもっている確率を求めよ。

解答

nn 回のうち kk 回プラスに移動し,nkn-k 回マイナスに移動したとすると,nn ステップ後の位置は k(nk)=2knk-(n-k)=2k-n

これが xx と等しくなるとき k=n+x2k=\dfrac{n+x}{2}

  • n+xn+x が奇数のとき
    上記のような kk は存在しないので求める確率は 00

  • n+xn+x が偶数のとき
    nn 回の試行で n+x2\dfrac{n+x}{2} 回プラスに移動する確率は,反復試行の確率の考え方より 12nnCn+x2\dfrac{1}{2^n}\cdot{}_n\mathrm{C}_{\frac{n+x}{2}}

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

次はやや難問です。

例題

一次元ランダムウォークにおいて,時刻 2n2n で初めて原点に戻ってくる確率を求めよ。

解答

条件を満たす経路の数を数える。

ランダムウォーク

  • 最初にプラスに移動した場合
    (2n1)(2n-1) ステップ目まで原点を通らない」かつ「(2n1)(2n-1) ステップ後にプラス1の位置にいる」ような移動方法の数はカタラン数 cn1=1n2n2Cn1c_{n-1}=\dfrac{1}{n}{}_{2n-2}\mathrm{C}_{n-1} である。→カタラン数の意味と漸化式

  • 最初にマイナスに移動した場合
    対称性より同様に cn1c_{n-1} 通り。
    よって,求める確率は 2cn122n=2n2Cn1n22n1\dfrac{2c_{n-1}}{2^{2n}}=\dfrac{{}_{2n-2}\mathrm{C}_{n-1}}{n2^{2n-1}}

高校数学の問題集 ~最短で得点力を上げるために~ のT163では,関連する問題と計算ミスを減らすコツを紹介しています。

酔っぱらっていてもここまで完全にランダムな動きをする人はいない気がします。