2015/04/26

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

分野: 場合の数  レベル: 最難関大学

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

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

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

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

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

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

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

様々なランダムウォーク

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

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

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

特定の位置xにいる確率

入試で頻繁に登場する重要な問題です。

例題

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

解答

$n$ 回のうち $k$ 回プラスに移動し,$n-k$ 回マイナスに移動したとすると,$n$ ステップ後の位置は $k-(n-k)=2k-n$
これが $x$ と等しくなるとき $k=\dfrac{n+x}{2}$

・ $n+x$ が奇数のとき
上記のような $k$ は存在しないので求める確率は $0$

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

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

次はやや難問です。

例題

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

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

ランダムウォーク

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

・最初にマイナスに移動した場合
対称性より同様に $c_{n-1}$ 通り。

よって,求める確率は $\dfrac{2c_{n-1}}{2^{2n}}=\dfrac{{}_{2n-2}\mathrm{C}_{n-1}}{n2^{2n-1}}$

酔っぱらっていてもここまで完全にランダムな動きをする人はいない気がします。
分野: 場合の数  レベル: 最難関大学