無理数遷移確率ランダムウォークの脱乱択化

全文

(1)Vol.2012-AL-142 No.2 2012/11/2. 情報処理学会研究報告 IPSJ SIG Technical Report. 無理数遷移確率ランダムウォークの脱乱択化白髪丈晴1. 山内由紀子1. 来嶋秀治1. 山下雅史1. 概要：ランダムウォークの脱乱択化とは, 決定的な過程によってランダムウォークを模倣する試みであり, ロータールーターモデルと呼ばれるモデルが提案されている. グラフ上の頂点をトークンがランダムに隣接点へ移動するランダムウォークに対して, ロータールーターモデルでは, グラフの各頂点上にあらかじめ隣接点の順番を決め, その順番に従ってトークンを移動させる. 従来のロータールーターモデルは有理数の遷移確率しか模倣することが出来なかったが, 本稿では無理数の遷移確率をもつランダムウォークも模倣出来る新しいロータールーターモデルを提案する. さらに, ランダムウォークにおけるトークンの期待配置と提案モデルにおけるトークンの配置の誤差の上下界の解析を与える.. Deterministic Random Walks for Irrational Transition Probabilities TAKEHARU S HIRAGA1. Y UKIKO YAMAUCHI1. S HUJI K IJIMA1. M ASAFUMI YAMASHITA1. Abstract: The rotor-router model, a.k.a. the deterministic random walk, is a deterministic process possibly emulating a random walk. In a random walk, tokens move to adjacent vertices at random. In the classical rotor-router model, every vertex launches tokens into adjacent vertices according do a prescribed order defined for each vertex, thus the rotorrouter model cannot handle irrational transition probabilities. In this paper, we devise a new model, which can handle irrational transition probabilities. Then, we analyze the difference between the number of tokens in our rotor-router model and the expected number of tokens in a random walk.. 配置とロータールーターに対して, 単一頂点誤差が O(mn). 1. はじめに. で押さえられることを示した. 梶野, 来嶋, 牧野は一般の既. ランダムウォークの脱乱択化とは, 決定的過程によって, ランダムウォークを模倣する試みである.. 約な有限グラフに対して解析を与えている. [2] 従来モデルでは単一頂点誤差が総トークン数に関わらな. Cooper と Spencer[1] は, James Propp によって 2000 年ご. い値で上から押さえることが出来ることを示したが, 多重. ろ提案された複数トークン型のロータールーターモデルに. 辺の本数 m に依存しており, 多重辺を用いて遷移比率を定. ついて研究し, 各頂点におけるロータールーターモデルと. めるため無理数の遷移確率は模倣できないという性質が. ランダムウォークのトークン数の誤差の期待値（単一頂点. あった.. d. 誤差）の解析を行った. 彼らは d 次元の整数格子点 Z に. 本稿では, 従来のモデルに対し二進小数を用いた無理数. 対して, 偶奇性条件を満たす任意の初期トークン配置, 任意. の遷移確率を模倣できる新たなモデルを提案する. このモ. のロータールーター, 任意の頂点, 任意の時間について, 単. デルに対して, 頂点数 n のグラフ上で, 遷移確率行列 P が. 一頂点誤差は次元 d のみに依存し, 総トークン数には依存. 既約で非周期的な場合, 総トークン数 M に対し単一頂点誤. しない定数 cd で押さえられることを示した.. 差が O(n3 log M ) で押さえられることを示す. すなわち単. 来嶋, 古賀, 牧野 [3] は, 頂点数 n, 枝数 m の強連結な有向. 一頂点誤差が総トークン数に依存するが, 単純辺の本数で. 多重グラフについて, 対応するマルコフ連鎖の遷移確率行. 押さえることが出来る. また, ある時刻, トークン数, P にお. 列が非負の固有値のみを持つ場合に, 任意の初期トークン. いて, 単一頂点誤差が Ω(log M ) であることを示す.. 1. 九州大学 Kyushu University. c 2012 Information Processing Society of Japan ⃝. 1.

(2) Vol.2012-AL-142 No.2 2012/11/2. 情報処理学会研究報告 IPSJ SIG Technical Report.

(3)

(4)

(5) (T ) (T )

(6) 本稿では提案モデルの単一頂点誤差

(7) χw − µw

(8) に対. 2. モデル. して, 以下の定理を示す.. いま, 有限の状態空間 V をもち, 遷移確率行列 P で定義されるランダムウォークを考える. 以下, P は既約で非周期的と仮定する. 有向グラフ G = (V, E) の枝集合を. E = {(u, v) | P (u, v) ̸= 0} と定め, N (v) ⊆ V を v から出る枝の終端点の集合とし, δ(v) = |N (v)|, n = |V | とする. (t). (t). 定理 2.1. 既約で非周期な P に対し,.

(9)

(10)

(11) (w)

(12)

(13)

(14) 2 max

(15) a

(16) (n − 1)n2 (lg M + 1) j j

(17) (T ) )

(18) <

(19) χw − µ(T

(20) w 1 − λ∗ 3 = O(n log M ). (t). ここで, µ(t) = (µv1 , µv2 , ..., µvn ) を時刻 t でのトークンの期待配置を表すベクトルとする. すなわち µ(0) = (0). (0). (0). (µv1 , µv2 , ..., µvn ) はグラフ G 上の M 個のトークンの初期配置であり, µ(t+1) = µ(t) P , 再帰的に, µ(t) = µ(0) P t である. 本研究の目標は µ(t) を決定的な過程で模倣することである. 提案モデルを以下に定義する. 非負の整数 i を i = ∑N i j i j=0 βj 2 で表すとする. ただし βj ∈ {0, 1} は i の二進数 i i 表記 βN βN −1 ...β1i β0i の各位の値であり, N は N = ⌊lg i⌋ で. ある. 非負の整数 i ∈ {0, 1, 2, ...} が i =. ∑N j=0. βji 2j で表される. とき, 関数 ψ を. ψ(i) =. N ∑. が任意の w ∈ V と T ≥ 0 で成り立つ. ただし, λ∗ = (w). max{|λi | | λi は P の固有値かつ |λi | ̸= 1}, aj は P の正 ∑n−1 (w) 規化された右固有ベクトル bj に対し j=0 aj bj = ew を満たす値である .

(21)

(22)

(23) (T ) (T )

(24) 定理 2.2.

(25) χw − µw

(26) = Ω(log M ) となる遷移確率行列. P , 時刻 T > 0, w ∈ V , 総トークン数 M が存在する.. 3. 頂点まわりの推移確率の近似についてこの章では提案モデルが対応するランダムウォークを模倣する根拠の一つとして, 頂点まわりの推移確率の近似に関する以下の定理を示す.. βji 2−(j+1). (1). j=0. と定義する. ψ(i) ∈ [0, 1) であることに注意されたい. グラフ上の各頂点 v ∈ V の各隣接点 u ∈ N (v) に対し, 対応する区間 ζ(v, u) を定義する. 頂点 v の δ(v) 個の隣接点を N (v) = {u1 , u2 , ..., uδ(v) k に対応する区 [∑} に対し, 各 u∑ ) k−1 k 間 ζ(v, uk ) は ζ(v, uk ) = P (v, u ), P (v, u ) j j j=0 j=0 である. ただし, P (v, u0 ) = 0 とする. ここで, ϕv (i) を,. ψ(i) ∈ ζ(v, uk ) のとき ϕv (i) = uk と定義する. つまり ϕv (i) は v に i 番目に到達したトークンの発射先の頂点を表す.. 定理 3.1. 任意の頂点 v, u ∈ V , 任意の P , 任意の自然数 z に対し,.

(27)

(28) ( )

(29) Iv,u (0, z)

(30) 2 lg z + 2 log z

(31)

(32) < − P (v, u) = O

(33)

(34) z z z が成り立つ. 定理 3.1(では) , 遷移比率の誤差が, 発射したトークン数 z. に対し O. log z z. で収束することを示している.. 定理 3.1 を示すため, いくつかの補題を示す. これらの補題は, 4, 5 章の解析にも用いられる.. 自然数 x, y に対し,. 補題 3.1. 任意の自然数 i, k に対して,. F (x, y) = {ψ(i) | i = x, x + 1, ..., y − 1} Ψv,u (x, y) = {c | c ∈ F (x, y), c ∈ ζ(v, u)} Iv,u (x, y) = |Ψv,u (x, y)| と定義する. Iv,u (x, y) は頂点 v を訪れた x から y − 1 番目のトークンのうち, 頂点 u へ移動したトークンの個数を表. ( ) ψ(i) = ψ i (mod 2k ) + ψ. (⌊. i 2k. ⌋) ·. 1 2k. が成り立つ.. す. 時刻 t における提案モデルのトークン配置を表すベク (t). (t). (t). トルを, χ(t) = (χv1 , χv2 , ..., χvn ) で表す. 具体的なトークンの遷移について述べる. 時刻 t = 0 (0). において, 頂点 v ∈ V 上にある χv (0). ついて, 1, ..., χv. (0) ϕv (0), ..., ϕv (χv. 個のトークンに. 番目のトークンは, それぞれ隣接頂点. − 1) へ移動する. 再帰的に, 時刻 t におい (t) {1, ..., χv }). て, v ∈ V 上の j(j ∈ 番目のトークンは, 隣接 ∑t−1 (s) 頂点 ϕv ( s=0 χv + j − 1) へ移動し, 時間 (t, t + 1) の間に (t). 自然数 i, k が i < 2k のときは, ψ(i (mod 2k )) = (⌊ ⌋) ψ(i), ψ 2ik = ψ(0) = 0 より成り立つ. 以下, i ≥ 2k のと. 証明.. きを考える.. ⌋ ⌊ ∑N j ∑N j=0 aj 2 j いま i = = a 2 とすると , j=0 j 2k ∑N ∑ ∑ N k−1 j−k j , および j=0 aj 2j (mod 2k ) = j=k aj 2 j=0 aj 2. χv 個のトークン全てを隣接点へ移動させ, 時刻 t + 1 を迎. が成り立つ. l = j − k, bl = al+k (l = 0, 1, ..., N − k) とす. える.. ると,. c 2012 Information Processing Society of Japan ⃝. 2.

(35) Vol.2012-AL-142 No.2 2012/11/2. 情報処理学会研究報告 IPSJ SIG Technical Report. (⌊ ⌋) ( ) i 1 ψ i mod 2k + ψ · k 2k 2     k−1 N ∑ ∑ 1 j j−k = ψ aj 2  + ψ  aj 2  · k 2 j=0 j=k (N −k ) k−1 ∑ ∑ 1 −(j+1) l = aj 2 +ψ bl 2 · k 2 j=0. 立つ. 補題 3.3. 任意の自然数 x, k に対して,

(36) )

(37) [

(38)

(39)

(40) F (x, x + 2k ) ∩ i , i + 1

(41) = 1

(42)

(43) k k 2 2 が任意の i ∈ {0, 1, ..., 2k − 1} について成り立つ. 証明.. l=0. =. k−1 ∑. aj 2−(j+1) +. j=0. =. k−1 ∑. =. aj 2−(j+1) +. N ∑. N ∑. aj 2−(j+1) +. N ∑. すものとする.. 1 2k. aj 2−(j−k+1) ·. j=k. j=0. =. bl 2−(l+1) ·. l=0. j=0 k−1 ∑. N −k ∑. 集合 F の定義と, 補題 3.1 より,. F (x, x + 2k ) { (⌊ ⌋) ) ψ 2xk ( k = ψ x mod 2 + 2k. 1 2k. aj 2−(j+1). (. , ..., ψ (x + l) mod 2. j=k. j=0. より題意を得る. 補題 3.2. 任意の自然数 k と α(0 ≤ α < 2k ) に対して. 1 + ψ(α) 2k+1. が成り立つ. 証明.. 補題 3.1 より,. (. k. k. ψ(2 + α) = ψ (2 + α) mod 2. k. ). (⌊ +ψ. 2k + α 2k. ⌋). 1 · k 2. ψ(1) = ψ(α) + k 2 1 = k+1 + ψ(α) 2. ). +. ψ. (⌊ x+l ⌋) 2k. (2) と表される. 簡便のため  (⌊ ⌋) i+x+l    ψ (⌊ 2k ⌋) k a(i) = ψ i+x+l−2 k 2   . (i = 0, 1, ..., 2k − l − 1) (i = 2k − l, 2k − l + 1 , ..., 2k − 1). とおく. この時, 任意の自然数 i に対し 0 ≤ ψ(i) < 1 なの. となり, 題意を得る.. で, 0 ≤ a(i) < 1 を満たすことに注意されたい. この a(i) を用いると, { } a(i) k (2) = ψ(i) + k | i = 0, 1, ..., 2 − 1 2. この時, F の定義より以下の観察が成り立つ. 観察 3.1. 任意の自然数 k について { } i k k F (0, 2 ) = | i = 0, 1, ..., 2 − 1 2k. と表すことが出来る. ここで b(j) = ( ) a(i) ψ(i) = 2jk , 0 ≤ i, j < 2k − 1 と置くと, 観察 3.1. が成り立つ. 証明.. k. 2k (⌊ ⌋)  x+2k −1  ψ k ( ) 2 , ..., ψ (x + 2k − 1) mod 2k + k  2 { (⌊ ⌋) (⌊ ⌋) ( ) ψ 2xk ψ x+1 k 2k = ψ 2k − l + , ψ(2 − l + 1) + 2k 2k ⌋) ⌋) (⌊ (⌊ ψ x+l−1 ψ x+l 2k 2k , ..., ψ(2k − 1) + , ψ(0) + 2k 2k (⌊ ⌋)  (⌊ x+l+1 ⌋) x+2k −1  ψ k ( ) ψ 2 k 2k , ψ(1) + , ..., ψ 2 − l − 1 +  2k 2k. aj 2−(j+1) = ψ(i). ψ(2k + α) =. 自然数 l を (x + l) mod 2k = 0(0 ≤ l < 2k ) を満た. 自然数 k に関する帰納法で示す. まず k = 0 のとき,. 次に k = l のとき, F (0, 2 ) = l. l+1. ると仮定する. 集合 F (2 , 2. l { 20l , 21l , ..., 2 2−1 l } l. であ. ) = {ψ(i) | i = 2 , 2l +. 1, ..., 2l+1 − 1} を考えると, 補題 3.2 より, F (2l , 2l+1 ) = 1 { 2l+1 + ψ(i) | i = 0, 1, ..., 2l − 1} となる. 集合 F (0, 2l+1 ) は. F (0, 2l ) と F (2l , 2l+1 ) の和集合である. よって, F (0, 2l+1 ) = 0 1 { 2l+1 , 2l+1 , ..., 2 2l+1−1 } が成り立ち, 任意の自然数 k に対し l+1. 観察 3.1 が成り立つことが示された. 集合 F の定義と補題 3.1, 観察 3.1 より以下の補題が成り. c 2012 Information Processing Society of Japan ⃝. {. F (x, x + 2k ) =. F (0, 1) = {ψ(0)} = {0} で条件を満たす. l. と併せて,. b(i) i + k | i = 0, 1, ..., 2k − 1 k 2 2. } (3). となり, 題意を得る. 補題 3.4. 任意の自然数 x, k, 任意の頂点 u, v ∈ V に対して,. 2k P (v, u) − 2 < Iv,u (x, x + 2k ) < 2k P (v, u) + 2 が成り立つ. 証明.. 頂点 v が u に定める区間 ζ(v, u) を [p, q) とおく. 補. 題 3.3 の証明の (3) 式より,. 3.

(44) Vol.2012-AL-142 No.2 2012/11/2. 情報処理学会研究報告 IPSJ SIG Technical Report. s b(s) s + 1 b(s + 1) + k <p≤ + 2k 2 2k 2k b(t) t + 1 b(t + 1) t + k <q≤ k + 2k 2 2 2k. (4) (5). となるような s, t が{存在する. このとき, ψ の定義 }よ b(i) i + | i = s + 1, s + 2, ..., t で 2k 2k. り Ψv,u (x, x + 2k ) = ある.. (4), (5) 式を変形すると, 2k p−b(s+1)−1 ≤ s < 2k p−b(s), 2k q − b(t + 1) − 1 ≤ t < 2k q − b(t) となり,. 4. 単一頂点誤差の上界の解析この節では, 定理 2.1 を証明する. いま, λi ∈ C(i =. 0, 1, .., n − 1) を遷移確率行列 P の固有値, bi ∈ Cn (i = 0, 1, ..., n − 1) を λi に対応する正規化された右固有ベクトルとする. 遷移確率行列 P を既約で非周期的とすると, 一般性を失うことなく ( √ ) , |λ0 | = 1, 1 > |λ1 | ≥ |λ2 | ≥ ... ≥ |λn−1 |, |bi | = ⟨b | b⟩ = 1 (i = 1, . . . , n) とできる. 頂点 u ∈ V に対し, eu ∈ {0, 1}V を u 番目の単位ベクトルとする. eu ∑n (u) (u) は aj ∈ C(j = 1, . . . , n) を使って eu = j=1 aj bj と書. 2k (q − p) − b(t + 1) − 1 + b(s) + 1. くことが出来る. すなわち,. < t − s < 2k (q − p) − b(t) + b(s + 1) + 1. . が成り立つ. Iv,u (x, x + 2k ) = t − s, P (v, u) = q − p, 任意の i に対し 0 ≤ b(i) < 1 なので,. . .  B= b0.  bn−1  . ···. b1. a. and. (u). 2k P (v, u) − 2 < Iv,u (x, x + 2k ) < 2k P (v, u) + 2 が成り立つ.. |Iv,u (x, x + y)| < yP (v, u) + 2 lg y + 2. このとき, z ⊤ z P z (v, w) = e⊤ v P ew = ev P. ∑N j=0. = e⊤ v. aj 2j と置く. Iv,u (x, x + a + b) =. N ∑. (w). aj P z bj. = e⊤ v. n ∑. (w). aj (λj )z bj =. ( ) = Iv,u x, x + a0 20   N −1 k k+1 ∑ ∑ ∑ + Iv,u x + aj 2j , x + aj 2j . < a0 20 P (v, u) + 2 +. N ∑. 補題 4.1. 任意の w ∈ V , T ≥ 0 に対し, ) (T ) χ(T w − µw. ). k=1 N ∑ ) ak 2k P (v, u) + 2 = 2N + P (v, u) ak 2k. k=0. =. k=0. < yP (v, u) + 2(lg y + 1) = yP (v, u) + 2 lg y + 2 を得る. 同様に yP (v, u) − 2 lg y − 2 < Iv,u (x, x + y) も示すことが出来る. 補題 3.5 において x = 0, y = z とすると, 定理 3.1 が示さ. c 2012 Information Processing Society of Japan ⃝. ∑. Xv(t) −1. ∑. (. ) P T −t−1 (ϕv (i), w) − P T −t (v, w). t=0 v∈V i=X (t−1) v. =. ∑T. (s). s=0. χv である.. 補題 4.1 を使い, 以下の補題を示す. 補題 4.2. 任意の w ∈ V , T ≥ 0 に対し, ) (T ) χ(T w − µw =. (. T −1 ∑. ∑ ∑. t=0 v∈V u∈N (v). ) T −t−1 Iv,u (Xv(t−1) , Xv(t) ) − χ(t) (u, w) v P (v, u) P. が成り立つ. 証明.. れる.. T −1 ∑. が成り立つ. ただし, Xv. ak 2k P (v, u) + 2. (T ). の補題を示すことが出来る.. (T ). j=0. (. (w). 既存研究 [1], [2], [3] と同様に, χw , µw について, 以下. j=0. j=0. aj (λj )z e⊤ v bj. j=1. (T ). ( ) = Iv,u (x, x + a0 20 ) + Iv,u x + a0 20 , x + a0 20 + a1 21   N −1 N ∑ ∑ +... + Iv,u x + aj 2j , x + aj 2j  j=0. n ∑. と書くことが出来る.. aj 2j ). j=0. (. n ∑. j=1. Iv,u (x, x + y) = Iv,u (x, x +. =. (w). aj bj. j=1. 意する. この時,. N ∑. n ∑ j=1. Iv,u (x, x + a) + Iv.u (x + a, x + a + b) が成り立つことに注. k=0.  (u)   a1    = .   ..    (u) an−1. a(u) = B −1 eu が成り立つ.. が成り立つ. ここで, y =. . としたとき, eu = Ba(u) である. B は正則行列であり,. 補題 3.5. 任意の自然数 x, y と任意の u, v ∈ V に対して,. 証明.. (u). a0. (t−1). 定義より, Iv,u (Xv. (t). , Xv ) は時刻 t のとき頂点 v. が u へ発射したトークンの総数を表していることに注意する. このとき,. 4.

(45) Vol.2012-AL-142 No.2 2012/11/2. 情報処理学会研究報告 IPSJ SIG Technical Report. を得る. よって補題 4.3 より題意を得る.. ) (T ) χ(T w − µw. =. T −1 ∑. Xv(t) −1. ∑. ∑. (. P T −t−1 (ϕv (i), w) − P T −t (v.w). ). 定理 2.1 の証明を行う.. t=0 v∈V i=X (t−1) v. =. T −1 ∑. . ∑. ∑. . t=0 v∈V. Iv,u (Xv(t−1) , Xv(t) )P T −t−1 (u, w). u∈N (v). ) (T ) χ(T w − µw. ). T −t (v, w) −χ(t) v P. =. T −1 ∑. . ∑. ∑. . t=0 v∈V. −χ(t) v. =. T −1 ∑. =. T −1 ∑. =. ∑ ∑ (. Iv,u (Xv(t−1) , Xv(t) ) − χ(t) v P (v, u). ). t=0 v∈V u∈N (v). u∈N (v) T −1 ∑. Iv,u (Xv(t−1) , Xv(t) ). ) T −t−1 −χ(t) (u, w) v P (v, u) P. . P (v, u)P T −t−1 (u, w). ∑ ∑ (. t=0 v∈V u∈N (v). Iv,u (Xv(t−1) , Xv(t) )P T −t−1 (u, w). u∈N (v). ∑. 証明.. ∑ ∑ (. n−1 ∑. Iv,u (Xv(t−1) , Xv(t) ). aj (λj )T −t−1 e⊤ u bj (w). j=0. t=0 v∈V u∈N (v). ) T −t−1 −χ(t) (u, w) v P (v, u) P. =. T −1 ∑. ∑ ∑. t=0 v∈V u∈N (v). (. となり題意を得る. 定理 2.1 を証明する前に, 以下の 2 つの補題を証明する. 補題 4.3. 任意の u, v ∈ V , t ≥ 0 に対して, ) ∑ ( Iv,u (Xv(t−1) , Xv(t) ) − χ(t) v P (v, u) = 0. +. ) (w) ⊤ Iv,u (Xv(t−1) , Xv(t) ) − χ(t) v P (v, u) a0 eu b0. T −1 ∑. ∑ ∑ (. Iv,u (Xv(t−1) , Xv(t) ) − χ(t) v P (v, u). ). t=0 v∈V u∈N (v) n−1 ∑. u∈N (v). aj (λj )T −t−1 e⊤ u bj (w). j=1. が成り立つ. 証明.. 定義より,. ここで, 補題 4.4 より. ∑. (t−1). u∈N (v) Iv,u (Xv. (t). (t). , Xv ) = χv が成. り立つことから, ) ∑ ( Iv,u (Xv(t−1) , Xv(t) ) − χ(t) v P (v, u) u∈N (v). =. ∑. Iv,u (Xv(t−1) , Xv(t) ). u∈N (v). ∑. −. χ(t) v P (v, u). u∈N (v). (t) = χ(t) v − χv = 0. となり, 題意を得る. 補題 4.4. 任意の u, v ∈ V , t ≥ 0 に対して, ) ∑ ( (w) ⊤ Iv,u (Xv(t−1) , Xv(t) ) − χ(t) v P (v, u) a0 eu b0 = 0 u∈N (v). ベクトル b0 は固有値 λ0 = 1 に対する右固有ベク. トルであり, b0 の i 番目の成分を b0 (i) とすると任意の. i, j(i, j = 0, 1, ..., n − 1) について b0 (i) = b0 (j) = 1 が成り立つ.. ∑ (. ) (w) ⊤ Iv,u (Xv(t−1) , Xv(t) ) − χ(t) v P (v, u) a0 eu b0. u∈N (v). =. (w) a0. ) (w) ⊤ Iv,u (Xv(t−1) , Xv(t) ) − χ(t) v P (v, u) a0 eu b0 = 0. u∈N (v). であり, ) (T ) χ(T w − µw =. (. T −1 ∑. ∑ ∑ n−1 ∑. t=0 v∈V u∈N (v) j=1. ) (w) T −t−1 ⊤ Iv,u (Xv(t−1) , Xv(t) ) − χ(t) eu bj v P (v, u) aj (λj ). が成り立つ. よって, −1 ∑ ∑ n−1

(46)

(47) T∑ ∑

(48) (T ) )

(49) ≤

(50) χw − µ(T

(51) w t=0 v∈V u∈N (v) j=1. が成り立つ. 証明.. ∑ (. ) ∑ ( Iv,u (Xv(t−1) , Xv(t) ) − χ(t) v P (v, u). u∈N (v). c 2012 Information Processing Society of Japan ⃝.

(52)

(53) ( )

(54) (w) T −t−1 ⊤

(55) eu bj

(56)

(57) Iv,u (Xv(t−1) , Xv(t) ) − χ(t) v P (v, u) aj (λj )

(58)

(59) T −1 ∑ ∑ n−1 ∑

(60) (w)

(61) ∑ T −t−1 ≤ max

(62) aj

(63) |λ1 | j. t=0. v∈V u∈N (v) j=1.

(64) ( )

(65)

(66)

(67)

(68)

(69) ⊤

(70)

(71) P (v, u)

(72) Iv,u (Xv(t−1) , Xv(t) ) − χ(t)

(73) eu bj v

(74) ( )

(75)

(76)

(77) (t−1) (t) (t) 補題 3.5 から,

(78) Iv,u (Xv , Xv ) − χv P (v, u)

(79) 2 lg χtv. <. + 2 < 2 lg M + 2 が成り立ので,. 5.

(80) Vol.2012-AL-142 No.2 2012/11/2. 情報処理学会研究報告 IPSJ SIG Technical Report.

(81)

(82)

(83) (w)

(84)

(85)

(86) max

(87) a

(88) ∑ ∑ n−1 ∑ j j

(89) (T ) )

(90) < 2(lg M + 1)

(91) χw − µ(T

(92) w 1 − |λ1 | v∈V u∈N (v) j=1

(93)

(94)

(95) (w)

(96) 2 maxj

(97) aj

(98) (n − 1)n2 (lg M + 1) ≤ 1 − |λ1 |. ∑ℓ−k+1 −(4i+1) 2 16k−1 − 1 1 1 · k−1 + i=1 k−1 − 3 16 16 3 ∑ℓ−k+1 −(4i+1) 2 1 1 i=1 = − · k−1 16k−1 3 16 ∑ℓ−k+1 −(4i+1) ∑∞ −2i 2 i=1 i=1 2 = − <0 k−1 16 16k−1. 以上により, 定理 2.1 が示された. より

(99) ( ) [ )

(100) ℓ ℓ

(101) ∑ ∑ 1

(102)

(103) 16k − 1

(104) i i k−1 16 , 16 + 16 ∩ 0, + 1.

(105) F

(106) =

(107) 3

(108) 3. 5. 単一頂点誤差の下界の解析ここでは, 定理 2.2 を示す. 証明.. i=k. V = {v1 , v2 , v3 }, P (vi , vj ) =. 1 3 (i, j. = 1, 2, 3) とな. るグラフ上のランダムウォークを考える. トークンの初期配置を µ(0) = (M, 0, 0) とすると, 時刻 t = 1 での期待配置 ( ) M M は µ(1) = M 3 , 3 , 3 となる. v1 に対する区間 ζ(v1 , v1 ) を. [0, 13 ) とする.. ℓ ∑ℓ −1) ℓ を 1 以上の自然数とする. M = i=1 16i = 16(16 15 ( ) (1) (1) のとき, χv1 − µv1 = 23 ℓ = 16 lg 15 16 M + 1 であることを. 示す. まず,. ( χ(1) v1. = Iv1 ,v1. 0,. ℓ ∑. ) i. 16. i=1 ℓ. = Iv1 ,v1 (0, 16 ) +. ℓ ∑. (. Iv1 ,v1. k=2 ℓ. となる.. Iv1 ,v1 (0, 16 ). ℓ ∑ i=k. =. i. 16 ,. ℓ ∑. ) i. 16 + 16. i=k.

(109)

(110)

(111) Ψv1 ,v1 (0, 16ℓ )

(112) であり,. Ψv1 ,v1 (0, 16 ) = {c | c ∈ F (0, 16ℓ ), c ∈ ζ(v1 , v1 )} だから, F (0, 16ℓ ) について考えると, 観察 3.1 より, { } i ℓ F (0, 16ℓ ) = | i = 0, 1, ..., 16 − 1 16ℓ ℓ ℓ 16ℓ −1 < 163 < }16 3+2 3 { ℓ i で, Ψv1 ,v1 (0, 16ℓ ) = | 0 ≤ i ≤ 16 3−1 , よ 16ℓ ℓ ℓ Iv1 ,v1 (0, 16ℓ ) = 16 3−1 + 1 = 16 3+2 である.. ここで,. i=k. c 2012 Information Processing Society of Japan ⃝. る.. 6. 従来モデルの模倣先行研究の来嶋, 古賀, 牧野 [3] や梶野, 来嶋, 牧野 [2] では, 有理数の遷移確率をもつランダムウォークに対し, 多重ない上界を与えていた. 本章では, 提案モデルを少し変形することで従来モデルが模倣出来ることを示す.. なのって. ( ∑k )   16i +j   ψ ⌊ i=ℓ ⌋ 16k−1 k−1 = ψ(j) + | j = 0, 1, ..., 16 − 1   16k−1 { } ∑ℓ−k+1 i ψ( i=1 16 ) = ψ(j) + | j = 0, 1, ..., 16k−1 − 1 16k−1 { } ∑ℓ−k+1 −(4i+1) 2 k−1 i=1 = ψ(j) + | j = 0, 1, ..., 16 −1 16k−1 } { ∑ℓ−k+1 −(4i+1) 2 j k−1 i=1 + | j = 0, 1, ..., 16 −1 = 16k−1 16k−1 ここで,. ∑ℓ ℓ 16i 16ℓ + 2 ∑ 16k−1 + 2 + − i=1 3 3 3 k=2 ∑ℓ ℓ ∑ 16i 16k + 2 = − i=1 3 3 k=1 ( ) 2 2 1 15 = ℓ = · lg M +1 3 3 4 16 ( ) 1 15 = lg M + 1 = Ω(log M ) 6 16 ∑∞ 1 が成り立つ. ただし, 13 = i=1 22i であることに注意す =. 辺を用いて O(nm) の上界, すなわちトークンの個数に依ら. 補題 3.3 の証明の (2) 式より, ( ℓ ) ℓ ∑ ∑ F 16i , 16i + 16k−1 i=k. (1) χ(1) v1 − µ v1. k−1. ℓ. である.. i=k. が成り立つ. 以上の議論から,. 以下の補題で, ϕv (i) の周期性について述べる. 補題 6.1. 任意の v, u ∈ V に関して, 自然数 l, k, m を用いて区間 ζ(v, u) = [ 2lk ,. m ) 2k. と表すことが出来る場合, 任意の. i について ϕv (i) = u ならば ϕv (i + 2k ) = u が成り立つ. ( ) (⌊ ⌋) 証明. 補題 3.1 より, ψ(i) = ψ (⌊ i mod ⌋) 2k + ψ 2ik · 21k , ( ) k ψ(i + 2k ) = ψ i mod 2k + ψ i+2 · 21k であり, 観察 2k ( ) 3.1 よりある自然数 l を用いて ψ i mod 2k = 2lk と書くことが出来る. よって,. l 2k. ≤ ψ(i) <. l+1 l , 2k 2k. ≤ ψ(i+2k ) <. l+1 2k. k. が成り立つ. よって ϕv (i) = u ならば ϕv (i + 2 ) = u が成り立つ. 補題 6.1 より, 任意の v, u ∈ V に関して, 自然数 l, k, m を用いて区間 ζ(v, u) = [ 2lk ,. m ) 2k. と表すことが出来る場合, 2k. 本の多重辺を使い従来モデルを用いて表すことが出来る. また, 従来モデルの頂点 v から出る多重辺 ei (i =. 0, 1, ..., δ(v) − 1 をそれぞれ区間 [ 2ik , i+1 ) (δ(v) ≤ 2k ) に 2k 対応させ, 区間 [. δ(v) , 1) 2k. を無視することによって, 任意の従. 来モデルを模倣することが出来る.. 6.

(113) 情報処理学会研究報告 IPSJ SIG Technical Report. Vol.2012-AL-142 No.2 2012/11/2. 7. おわりに本稿では, 無理数の遷移確率を持つランダムウォークに対する新しいロータールーターモデルを提案した. 提案モデルの単一頂点誤差がグラフの頂点数 n と, 総トークン数 M に対し O(n3 log M ) で押さえられることを示した. また, ある時刻, 頂点, トークン数, P において, 単一頂点誤差が Ω(log M ) であることを示した. 今後の課題としては, 組み合わせ構造に起因するグラフに対し, 単一頂点誤差の頂点数の対数サイズの上界の導出や, 一般の場合の単一頂点誤差の上界と下界の一致などがある. 参考文献 [1]. [2]. [3]. J. N. Cooper and J. Spencer, Simulating a random walk with constant error, Combinatorics, Probability and Computing, 15(2006), 815–822. H. Kajino, S. Kijima, and K. Makino, Discrepancy analysis of deterministic random walks on finite irreducible graphs, discussion paper. S. Kijima, K. Koga and K. Makino, Deterministic random walks on finite graphs, Proceedings of ANALCO 2012, 16– 25.. c 2012 Information Processing Society of Japan ⃝. 7.

(114)