日本語トップ
親ページに戻る

確率的ランキング過程 (Stochastic ranking process) の数学

下手な日本語より数式のほうがわかりやすいかたに， 親ページの動画で紹介した数学モデル(stochastic ranking process， 確率的ランキング過程)の数学的紹介をします．

提案するモデルの数学研究上の特徴．

1. Stochastic ranking processの数学的定義

Nを自然数とし，N個の粒子を i=1,2,…,N とラベルする． このN個の粒子たちが1列に並んでいて， 時間経過とともに下記にしたがってそれらの順位（たとえば左から右に並んでいる と考えて，左端から数えたときの位置）が変わるものとする． すなわち，確率空間を (Ω,F,P)， 時刻 t∈[0,∞) をパラメータとして， N個の粒子の順列 SNに値をとる確率過程，
X(N)(t) =(X(N)1 , …, X(N)N ): Ω→SN
を考え，粒子iの時刻tにおける順位を Xi(t)=X(N)i(t) とおく．

モデルの定数は次の2種類である．

  1. 初期時刻 t=0 における各粒子の位置 xi=Xi(0)）； (x1 ,…, xN )∈SN
    （ xi=i, i=1,…,N, とおいて差し支えないが， このモデルでの粒子の自然な順序は初期位置とは異なる．）
  2. 各粒子に与えられた非負定数（粒子iのジャンプ率） wi ≧ 0, i=1,…,N

時間発展の規則を記述するために， 補助的な確率変数列τを定義する． 各i=1,…,Nに対して
非負非減少確率変数列 τi,j , j=0,1,2,… （粒子iのj回目のジャンプ時刻）； 　τi,0=0≦τi,1≦… を用意する． （以下の記述の簡単のため τi,0=0 とおいた．） {τi,j , j=0,1,2,…}, i=1,2,…, は独立であり， 各iに対して， τi,j+1-τi,j , j=0,1,2,…, は独立同分布であって， その分布は平均の逆数（ジャンプ頻度）が wi である指数分布
P[τi,0 ≧ t ] = exp(-wi t), t≧0, に従うとする． このとき，確率1で， i≠i' または j≠j' を満たす全てのi,j,i',j'に対して τi,j ≠ τi',j' となることが知られているので，確率論の普通の手続き通り， 必要ならば確率空間Ωを制限して以下，τi,j たちは どの2つもどんなサンプルω∈Ωに対しても等しい値をとらない確率変数たちとする．

注意：命題や定理で Nについての極限を考える際，X, x, w, τ は全て N 毎に定める ので， X(N)i(t) のように添字(N)を付けるべきであるが， Nについての極限をとるまでは見やすくするために，Nを固定して添字(N)は省略する．

確率過程 X の時間発展（stochastic ranking process） を以下で定義する．

  1. 各粒子i と j=1,2,…, に対して， Xi(τi,j) = 1． すなわち， 各j＞0 について τi,j は粒子iが1位にジャンプする時刻である．
  2. 各粒子i と各時刻t に対して， Xm(t)＞ Xi(t) （順位が下位＝右側）なる m について τm,j =t となる j があれば，
    Xi(t)=Xi(t-0)+1． ここで，tの関数fに対して左極限を f(t-0)= lims↑t f(s) と書いた． すなわち， 注目している粒子より下位の粒子が 1位にジャンプすると，ランキングが（ジャンプした粒子に順次押されて）1増える．
  3. 上記 b または c 以外の時刻tではXi(t) たちは定数である． すなわち，ジャンプ以外では粒子間の相対的な順位の大小は変わらず， 注目する粒子の順位の変化は 自身のジャンプと下位の粒子のジャンプに押されることだけによる．
明らかに，粒子系として（非対称）マルコフ過程である．

2. Stochastic ranking process の無限粒子極限 (N→∞)

以下，次の表記を用いる

2-1. N→∞ その1（すぐわかること）：軌道に関する大数の法則

1つの粒子iに注目して，自分自身がジャンプしない時間帯 （τi ,j＜t＜τi ,j+1）の動きを考える． 粒子は列の中を（他の粒子の1位へのジャンプに順次押されて）単調に，しかし， ランダムに順位を下げる（＝右へ移動する＝数字が増加する）． この軌道を空間的に粒子数Nで規格化したときの関数形は， Nが大きいときジャンプ率の分布のラプラス変換に近づく． したがって，特に，決定論的（非ランダム）になる．

証明は（今までこういう問題を考えたことがなければ驚くほど）簡単で， 独立確率変数列の大数の法則しか用いない初等的なものである． 正確には以下のとおり．

命題1．

時刻 t までに1回以上ジャンプした粒子とジャンプ未経験の粒子 （前者は上位＝列の左側，後者は下位＝列の右側にいる）の境界位置を yC(N)(t) とおく． N→∞ のとき，ジャンプ率の分布
λ(N)(dw) := N-1 Σ1≦k≦N δ(w-w(N)k)dw
が極限分布λ(dw)（確率測度ならば何でもOK） に弱収束するならば，
yC(t) = 1- ∫[0,∞) e-w t λ(dw)
とおくとき，全ての t≧0 で
limN→∞ yC(N)(t)= yC(t) 　（確率収束）． 　　 ◆

証明．

境界となる位置は， 時刻 t までに1回以上ジャンプした粒子 j の個数に等しく， それは， τ(N)k,1＜t なる k の数に等しい． よって，
yC(N)(t) = N-1 Σ1≦k≦N χ(τ(N)k,1＜t)

右辺の和の各項は有界（0か1の値しかとらないから）で， 和はτの定義によって独立確率変数の和だから，大数の弱法則から， 期待値との差
yC(N)(t)- N-1 Σ1≦k≦N E[ χ(τ(N)k,1＜t) ] は N→∞ のとき 0 に確率収束する．

ところで，確率の定義とτの定義から
E[ χ(τ(N)k,1＜t) ] = P[ τ(N)k,1＜t ] = 1 - exp(-w(N)k t) だから，仮定から
N-1 Σ1≦k≦N E[ χ(τ(N)k,1＜t) ]
= 1 - N-1 Σ1≦k≦N exp(-w(N)k t)
= 1 - ∫[0,∞) exp(-w t) λ(N)(dw)
→ yC(t),　　N→∞．　　■

注．

t=0で1位にいた粒子をi （すなわち， x(N)i=X(N)i(0)=1）として， iがジャンプするまでのその軌道を粒子数Nで割った（空間を規格化した）もの を考えると，
yC(N)(t) = N-1 (X(N)i(t)-1), 　　0≦t＜τ(N)i,1
がわかる． すなわち， yC(N)(t) は初期時刻に 1位にいた粒子が ジャンプするまでの（粒子数Nで規格化された）軌道を表す．

2-2. N→∞ その2（すぐにはわからないこと）： 空間分布に関する従属確率変数列の大数の法則

最初に定理のための仮定を並べ，定理の主張を書くために必要な記号と， それらの定義可能性(well-defined)の根拠となる命題を用意する．

命題1で粒子の軌道を空間的に粒子数Nで規格化したように， 以下規格化した順位（確率過程）
Y(N)i(t) =N-1 (X(N)i(t)-1), 　　i=1,2,…,N,　t≧0,
を考える． そして時刻 t におけるN個の粒子たちのジャンプ率 w と規格化した順位 y の 結合経験分布（すなわち，[0,∞)×[0,1)上の確率測度）を
μ(N)t(dw,dy) =N-1 Σ1≦i≦N δ(w-w(N)i)δ(y-Y(N)i(t)) dw dy
とおく．

仮定1．

  1. 0 ＜ ∫ w λ(dw) ＜ ∞
  2. 初期分布 μ(N)0(dw,dy) は N→∞ のとき次の意味で ある分布 μ0(dw,dy) に収束する：　
    任意の有界連続関数 g: [0,∞)→R に対して
    limN→∞ supy∈ [0,1) | ∫[0,∞)×[0,y] g(w) μ(N)0(dw,dy) -∫[0,∞)×[0,y] g(w) μ0(dw,dz) |=0

命題2．

μ0(dw,dy) は y∈[0,1) 上のルベーグ測度に関して絶対連続で， その密度を μy,0(dw) と おくとき， μy,0 は w∈[0,∞)上の確率測度 （y に関する条件付き確率）である．　　 ◆

証明．

g(w)=1として弱収束すること（仮定1.II）を用い， μ(N)0の具体形を代入し， 0≦ Y(N)i(t) ＜ y なる i は [Ny]個 であることに注意すると，
μ0([0,∞)×[0,y))=[0,y) が全ての y で成り立つ． よって任意の可測な A⊂[0,∞) に対して μ0(A×[0,y))はルベーグ測度に関して絶対連続． またその密度 μy,0(A) について μy,0([0,∞))=1 なので，条件付き確率の一般論と合わせて μy,0 は w∈[0,∞)上の確率測度である．　　■

注．

  1. 仮定1.I の左側の不等式は，ジャンプする粒子がちゃんとある， という当然の仮定（ジャンプが全くなく，したがって静止している系では， 研究すべき事はなにもない）． 仮定1.I の右側の不等式は，下記の定理の主張において， y=0 での収束に必要だが， y＞0 での収束を扱う上では不要である． 直感的には，この仮定が破れるとは，ジャンプ率の大きい粒子が多すぎること を意味し，その結果 y=0 (1位) へのジャンプが激しすぎてy=0に条件付けた分布が ill-defined になる， という状況を指すが，y＞0 では下記定理の主張を見るとわかるように 指数減衰のweightがかかるので，仮定1.I が無くても問題ない． （確率過程を考えているだけならば y=0 での分布がill-definedでも支障はないが， 偏微分方程式との関係を論じるときは，境界条件に当たるので y=0 の状況も 気をつけたほうが良いだろう．）
  2. 仮定1.II は初期分布の弱収束，程度の仮定でよいはずだが， モデルをもう少し一般化することのほうが優先事項と考えるので， 現時点では初期分布に関する仮定を最大にゆるめる試みは急いでいない．

命題3．

命題1の yC:　[0,∞) → [0,1) は yC(0)=0 を満たし，連続狭義増加関数である．　　 ◆

証明．

命題1 に与えた yC の具体形から明らか．　　■

命題3から，定数 y∞∈(0,1] と， 連続狭義増加関数 t0: [0,y∞) → [0,∞) が存在して， yC(t0(y))=y,　　0≦ y＜y∞ ,
すなわち，
y=1 - ∫[0,∞) exp(-w t0(y)) λ(dw)
と書ける． （t0(y) は粒子が 1位 (y=0) から出発して（ジャンプしないで） y まで順位を下げるのに要する時間を表すことは定義からわかる．）

yC を一般化して，
yB(y,t) = 1 - ∫[0,∞) exp(-w t) μ0(dw×[y,1)), 　　t≧0,　0≦ y＜ 1
とおく． yC(t)=yB(0,t) である． （yB(y,t) は位置 y から出発して（ジャンプしないで） t 時間たったときの位置（順位）を表すことは yC と 見比べればわかるだろう．）

命題4．

yB(・,t): [0,1) → [yC(t),1) は 全単射連続狭義増加関数である． 　　◆

証明．

yB(y,t) の具体形から， 全射で y に関して非減少連続であることはすぐわかる． さらに命題2（特にμy,0([0,∞))=1）を合わせると， 狭義増加であることもわかる．　　■

命題4から，逆関数 y^(・,t): [yC(t),1) → [0,1) が存在する：
1-y = ∫[0,∞) exp(-w t) μ0(dw×[y^(y,t),1)), 　　t≧0, yC(t)≦ y＜ 1.
（y^(y,t) は時刻 t に y (＞ yC(t)) にいる粒子が 時刻 0 に（途中でジャンプしないとき）いた位置を表すことは yB の意味からわかるだろう．）

定理を述べるための仮定と記号が用意できたので，定理を述べる．

定理1 [主定理]．

（スケールされた） stochastica ranking process {Y(N)i} について仮定1が成り立つとき， 時刻 t におけるN個の粒子たちのジャンプ率 w と規格化した順位 y の 結合経験分布
μ(N)t(dw,dy)
は N → ∞ のとき，[0,∞)×[0,1) 上の分布 μt(dw,dy) に 確率収束する．ここで，分布の集合上の位相は弱収束位相を考える．すなわち， 任意の有界連続関数
f: [0,∞)×[0,1) → R
に対して
(★)　　limN→∞ N-1 Σ1≦i≦N f(w(N)i,Y(N)i(y) ) = ∫[0,∞)×[0,1) f(w,y) μt(dw,dy) 　　（確率収束）．

極限分布 μt は

0＜y＜yC(t) のとき，
μt([w,w+dw)×[y,1))= λ(dw) exp(-w t0(y))

yC(t)＜y＜1 のとき，
μt([w,w+dw)×[y,1))= μ0([w,w+dw)×[y^(y,t),1)) exp(-w t)

で与えられる． （ここで t0 と y^ はそれぞれ命題3と命題4に 基づいてそれぞれの命題のすぐ下に定義されている．） 　　◆

注．

3. 主定理[定理1]の証明の方針

ここでは，主定理の証明の論点（「問題は何か」）と 方針（「どう扱ったからうまくいったか」）を説明するにとどめる． 証明の詳細に興味を持っていただけるかたは 原著論文(K.Hattori, T.Hattori, Existence of an infinite particle limit of stochastic ranking process ) を参照していただきたい．

  1. 従属確率変数列の和の極限なので，単純な教科書知識の適用ではない． 各粒子の列の中での動き（自分自身がジャンプしない期間の動き）が， 自分より下位にいる粒子のジャンプの影響による （上位にいる粒子の影響は受けない）ことと， 自分の位置自体が確率変数であること，から従属性が生じる．
  2. しかし，結論（極限分布）があらわに書けているので， 証明すべき式 (★) の左辺と右辺の差が N→∞ で 0 に近づくことを 直接強引に証明すればすむ． すなわち，もっともだいじなことは，極限分布のあらわな表式の発見である． （実際，答えを発見するまでは主定理の証明はもっと難しいだろうと予想していた．） この発見には蒸発を流れの原因とする多成分流体系という直感的描像が 決定的に重要である．これについては項を改めて説明する．
  3. (w,y)の2次元分布の収束であって， y に関しては極限が密度を持つことが わかっている（主定理の主張の一部になっている）ので， (★) の試行関数 f として，
    f(w,z)= g(w) χ(z∈[y,1))
    の形に限れば十分である．これで，問題は時刻 t に区間 [y,1) にいる粒子たちが 初期時刻からどのような軌道をたどってきたかを調べることに帰着する．
  4. 粒子の軌道が確率変数でなく決定論的ならば， 目的の量は独立確率変数の和で書けるので， 大数の法則が適用できる． 命題1から N が大きいとき，粒子の軌道は決定論的な関数に近い． そこで，極限軌道に置き換えた量は独立確率変数列の大数の法則を適用し， 有限Nの軌道（確率変数）と極限軌道の差の効果は強引に評価して N→∞で消えることを確認する．後者については，列の中で軌道が交差する ことがない，つまり，1位へのジャンプ以外では居並ぶ粒子間の相対的な順位 の上下は変わらない，という事実を a priori boundとして用いる．

4. 主定理の極限分布の具体形の直感的意味

前項のように，主定理の証明には極限の具体形を事前に正しく予想できた ことが決定的に重要であった． 予想は幸運によるものではなく，次のような深い歴史のある考察に基づく．

通常目にする水の流れ（川）や空気の流れ（風）などの流体の時間発展は， ナビエ・ストークスの方程式と呼ばれる偏微分方程式系の解として 得られると考えられている． 流体を含め，通常目にする全ての物質の運動は 極めて多数のランダムな運動（熱運動）を する極めて小さな分子たちの運動に基づく．分子数が極めて大きいので， 多粒子極限によって記述できると考えるとき，流体の運動は， 巨視的な（分子レベルの運動と比べるときわめて少数の未知関数 だけで記述可能なregularityの高い）決定論的現象として， 偏微分方程式によって正確に記述できる，と直感的には考えられている． （この直感は数学的には流体力学極限の問題として， ナビエ・ストークスの方程式に関しては未解決である．）

この古典的な描像（数学としては未解決の問題）の類推によって stochastic ranking processの無限粒子極限を眺めると， 無限粒子極限は以下の描像に従う流体として記述できるだろうことが予想できる：

  1. 1次元（多成分）流体，特に粒子（分子）は流れの中では追い越しなく 順に右（下流＝分子レベルではランクの下位）に流れるだけ （多成分というのは蒸発率 w の異なる分子の集まりを考えているから）
  2. ダイナミックス（時間にともなう変化の原因）は， 各流体成分が固有に持つ蒸発率だけで決まる蒸発（流れからの消失＝離脱）と， 蒸発した分を左（上流＝上位）から補う流れだけ （processの時間発展の定義のとおり）
  3. 左端は蒸発した各成分を補う流入（ジャンプは列のどこからでも1位にジャンプする， とprocessを定義したから）
  4. 右端は流出が無い固定端境界条件（1位へのジャンプ以外では列から離脱しない， と定義したから）

注．

この項では主定理の証明の発見の経緯を説明しているので，予想，と書いたが， 主定理が証明できたということはこの予想が 極限の具体形について正しかったことを意味する．

以上の性質はそのまま偏微分方程式の初期値問題として定式化できて， その初期値問題の解として主定理の分布の具体形を得る． きちんとしたことは項を改めて説明することにして， ここでは，概要を言葉で説明する．

定義から， 区間 [0,1) に総量1の流体があり，蒸発率が [w,w+dw) である成分の総量は λ(dw)=λ([w,dw)) で与えられている．定理の主張にある
μt([w,w+dw)×[y,1))
は，時刻 t において，蒸発率が [w,w+dw) である成分で点 y より下流にいる ものの量を表す．

  1. 下流（順位下位）側：　 yC(t)＜y＜1 では，命題1から， 時刻 t まで一度も蒸発したことがない流体成分分子がたまっている． 蒸発率の定義から，蒸発率 w の成分に対して t時間一度も蒸発しない割合は exp (-w t) である． 命題4から，時刻 t に y にいる流体分子は時刻 0 には y^(y,t) にいた． 定義から流れの中で追い越しが起きないから， 時刻 t に[y,1)にいる流体分子は時刻 0 に [y^(y,t),1) にいた流体分子のうち t時間蒸発しなかったものである．したがって，
    μt([w,w+dw)×[y,1))= μ0([w,w+dw)×[y^(y,t),1)) exp(-w t)
  2. 上流側：　 0＜y＜yC(t) は時刻 t までに一度以上蒸発した 流体成分分子が流れている．
    まず，次のことに注意する． 蒸発した流体分子は（成分比を保存したまま）左端から流入する． 蒸発量は各分子の成分に対応する蒸発率 w だけで決まり， 空間位置に無関係だから，λで与えられている成分比にしたがって 袋に入っている種々の色の玉から決まった割合で玉を取り出して また袋に戻す，という操作と同じことで， 取り出される玉の割合は時刻によらず定常的である． すなわち，上流側の流体成分の分布は定常的である． 総量は一定だから， 0＜y≦yC(t)ならば
    点 yより下流側の各流体成分の総量 μt([w,w+dw)×[y,1))も定常的，すなわち t によらない．
    命題3から 0＜y≦yC(t)と t≧ t0(y) は同値． 定常性から
    μt([w,w+dw)×[y,1)) = μt0(y)([w,w+dw)×[y,1))
    右辺は流体成分 [w,w+dw) の総量 λ(dw) のうち 時刻 t0(y) までジャンプしなかったものの量だから， 下流側の考察と同様に，
    λ(dw) exp(-w t0(y))
    に等しい．

こうして，主定理のあらわな式が，巨視的な考察から予想できる．

5. ジャンプ率の極限分布が離散的な場合

ここまで，ジャンプ率はλに従って（仮定1を満たす）任意の分布で成り立つ． 特に，ジャンプ率が連続的な値をとることを許す． 以下，巨視的な考察を偏微分方程式として定式化するときにわかりやすいように， ジャンプ率が有限種類または可算種類の場合を考える． すなわち，非負定数列 0≦f1＜f2＜… と 正定数列（成分比）ρj≧0, j=1,2,…, があって
Σj ρj =1 および
λ(dw) = Σj ρj δ(w-fj) dw 　すなわち，　 ρj = λ({fj})
となっている場合を考える． （仮定1.I は 0 ＜ Σj ρj fj ＜ ∞ となる．） このとき，
μt([w,w+dw)×[y,1))= Σj Uj(y,t) δ(w-fj) dw
すなわち，点 y より下流にいる蒸発率 fj の流体成分の量を
Uj(y,t) = μt({fj}×[y,1))
とおくと，主定理（定理5）の公式は

0＜y＜yC(t) のとき，
Uj(y,t) = μt({fj}×[y,1)) = λ({fj}) exp(-fj t0(y)) = ρj exp(-fj t0(y))

yC(t)＜y＜1 のとき，
Uj(y,t) = μ0({fj}×[y^(y,t),1)) exp(-fj t) = Uj(y^(y,t),0) exp(-fj t)

となる． yC，t0，y^ はそれぞれ 命題1，命題3，命題4 の辺りの定義から，
yC(t) = 1- Σj ρj exp(-fj t)
y=1 - Σj ρj exp(-fj t0(y)) 　　（0＜y＜yC(t) のとき）
1-y = Σj Uj(y^(y,t),0) exp(-fj t) 　　（yC(t)＜y＜1 のとき）
となる．

この関数 Uj たちは，§4. （極限分布の直感的意味）で説明した 偏微分方程式の初期値問題の唯一の大局解として得られる． このことに興味のあるかたは， 蒸発項を持つ1次元invscid Burgers型非線形偏微分方程式系 の時間大局解の存在定理のページにお進みいただきたい．

注．

Webランキングへの応用の際は， Amazon.co.jp に登録されている書籍のように，有限粒子系を扱うから， 書籍 j に fj を対応させることで，いつも N粒子（有限粒子）系で， しかも重みを等しくとって ρj=N-1 の場合だけを扱えば 良いように見えるかもしれない． しかし， 命題1や定理5の結果はあくまで N→∞ 極限で成り立つ． たとえば命題1の証明では，大数の法則を用いて， 確率変数をその期待値で置き換えていることがあらわにわかる． だから結果を応用する場合には， たとえ対象が有限系でも， 無限粒子極限の数学的内容を避けて通ることはできない．

親ページに戻る inserted by FC2 system