一般の遷移確率に対する関数ルーターモデルの全訪問時間
7
0
0
全文
(2) Vol.2016-AL-158 No.3 2016/6/24. 情報処理学会研究報告 IPSJ SIG Technical Report. 1.3 本研究の成果. 1.2 決定的過程の全訪問時間に対する既存研究 決定的なグラフ探索という観点から, 単純ランダムウォー. これまでの全訪問時間の研究が単純ランダムウォーク. クのアナロジーであるロータールーターモデルに対し, 近. を模倣するロータールーターモデルに対する研究だった. 年多くの研究が為されている. このモデルでは, 各頂点 u は. のに対し, 本論文は一般の遷移確率に対応する決定的過程,. u 上のトークンを隣接頂点に 1 つずつ順番に振り分ける.. さらには複数トークンの場合の全訪問時間に対し研究を. 言い換えると, u は隣接頂点 v に 1/δ(u) の比率でトークン. 行う. そして, 定理 4.1 によって, 任意のエルゴード的かつ. を遷移させる. ここで, δ(u) は隣接頂点の個数である.. 可逆な遷移確率行列（無理数の値も含みうる）に対応する. ルの振る舞いに対し研究を行い, 高々 2mD ステップ後に,. 決定的過程の全訪問時間の上界を与えることに成功した. ( ) 具体的には, k ≥ 1 に対し上界 O t∗ + m′ t∗ /k を与えた.. トークンがオイラー閉路の巡回に陥ることを示した. ここ. ここで m′ = maxu∈V (δ(u)/πu ) である. これは, 知り得る. で D はグラフの直径を表す. Bampas ら [6] は任意のグラフ. 限り初の一般の遷移確率に対応する決定的過程の全訪問. に対しオイラー閉路の巡回に陥るまで Ω(mD) かかる例の. 時間の上界である. この上界はロータールーターモデルに. 構成例を示した. これらの結果は単一トークンのローター. 対し, k = 1 の場合, t∗ = O(D) のとき既存の O(mD)[31]. ルーターモデルの全訪問時間が一般に Θ(mD) であること. と一致する. また, t∗ が小さい, もしくは k が大きい場合,. を示している. ロータールーターモデルの全訪問時間解析. O(mD/ log k)[13] を改善している. そして, 正則グラフでな ( ) いグラフに対し, 既存の O t∗ + (∆/δ)(mt∗ /k) [24] を ∆/δ. Yanovski ら [31] は単一トークンのロータールーターモデ. の他のアプローチとして, ロータールーターモデルにおけ (T ). るトークンの訪問頻度 Xv. とランダムウォークの特徴量. を結びつける手法が開発されている. ここで. (T ) Xv. は頂点 v. がトークンに時刻 T までに訪問された回数を示す. Holroyd (T ). と Propp [20] は Xv. と対応するランダムウォークの定常 (T ). 分布 π に対し, |πv − Xv /T | ≤ Kπv /T を示した. ここで (T ) Xv /T. の項に対し改善している. (T ). 証明では, まず SRT ルーターモデルの訪問頻度 Xv. と. 対応する (一般の) ランダムウォークの特徴量を結びつけ る. このアプローチは [19], [20], [24] の拡張となっている. (T ). 具体的には, |πv − (Xv /kT )| < Kπv /T が任意のエルゴー. がT. ド的かつ可逆な遷移確率行列に対し成り立つことを示した.. が増加するに従って πv に収束することを表している. この. ここで πv は遷移確率行列の定常分布であり, K は T に依. 事実を用いて, Friedrich と Sauerwald [19] は多くのグラフ. 存しない定数である. この上界は [20] の結果の k > 1 トー. 構造に対しロータールーターモデルの全訪問時間の上界を. クン, 一般の遷移確率に対する拡張となっている.. K は T に依存しない定数である. この定理は. 与えている. 全訪問時間の高速化の為, k > 1 トークンのロータールー. 1.4 ランダムウォークの脱乱択化に対する関連研究 関連の深い話題として, 複数トークンの決定的過程のトー. ターモデルに対する研究が Dereniowski ら [13] によって ( ) 為されている. 彼らは任意のグラフ, k = O poly(n) もし. クン配置と対応するランダムウォークのトークン配置の単. くは 2O(D) に対し全訪問時間の上界 O(mD/ log k) を示し,. 一頂点誤差の研究が行われている. Rabani ら [27] は拡散モ. 下界として Ω(mD/k) を満たす例を与えている. Kosowski. デルと呼ばれる決定的過程と対応する確率過程の単一頂点. と Pajak [24] は上記の上界を改善し, 任意のグラフに対し ( ) O t∗ + (∆/δ)(mt∗ /k) を示した. ここで ∆/δ は最大/最小. 誤差の研究を行い, また解析のフレームワークを構築した. 特定のグラフ構造上での単一頂点誤差は広く研究されてい. 次数を表す.. る. 例えば, 整数格子点上 [11], [12], [14], 木上 [10], d 次元. 単純ランダムウォークに対応するロータールーターモデ ルを超えた, 一般の遷移確率に対応する決定的過程に対す. 超立方体上 [1], [18] などである. Berenbrink ら [7] は近年,. d 正則グラフ上で既存の上界を改善した.. る研究も近年為されている. これは各頂点 u が u 上のトー. 一 般 の 遷 移 確 率 を 扱 う た め, 有 向 多 重 グ ラ フ 上 で の. クンを隣接頂点 v に Pu,v の比率で決定的に遷移させるモ. 研究が [22], [23] で行われている. SRT ルーターモデル. デルである. ここで Pu,v は対応するランダムウォークの u. は [28], [29] で扱われている. 彼らは SRT ルーターモデル. から v への遷移確率を表す (詳細は 2.2 節を参照されたい).. と一般のマルコフ連鎖の差を単一頂点誤差, 総変動距離と. Holroyd と Propp [20] はスタックウォーク (白髪らはこれを. いった指標で研究している.. SRT ルーターモデルと呼んだ [28]) を設計し, このモデルに. 近年, Chalopin ら [9] は複数トークンのロータールーター. おけるトークンの訪問頻度と到達時間の関連を示した. 白. モデルの周期的挙動について研究を行い, 周期的な状態に. 髪ら [28] は関数ルーターモデルと呼ぶより一般的なモデル. 陥るまでの時間の上下界を与えている.. を定義し, SRT ルーターモデルと対応するランダムウォー クの単一頂点誤差に対し上界を与えている. しかし, 既存研 究において, 一般の遷移確率に対応する決定的過程の全訪. 2. 準備 2.1 ランダムウォーク/マルコフ連鎖. 問時間に対する研究は知られていない.. V = {1, 2, . . . , n} を有限状態 (頂点) 集合, P ∈ Rn×n ≥0 を. ⓒ 2016 Information Processing Society of Japan. 2.
(3) Vol.2016-AL-158 No.3 2016/6/24. 情報処理学会研究報告 IPSJ SIG Technical Report. V 上の遷移確率行列とする. 即ち, P は. ∑ v∈V. Pu,v = 1 を. 任意の u ∈ V に対し満たす. ここで Pu,v は P の (u, v) 成 分を表す. 任意のエルゴード的. π∈. Rn>0. *1. な P は唯一の定常分布. (即ち, πP = π) を持ち, かつ極限分布が π に一致. する (即ち, 任意の V 上の確率分布 ξ に対し limt→∞ ξP = π が成り立つ) ことが知られている. ここで, 定常分布への収 束を厳密に定義するため, 総変動距離と混交時間の定義を 導入する. 今, ξ, ζ を V 上の確率分布とする. このとき, ξ と. ζ の総変動距離 Dtv (ξ, ζ) は以下のように定義される.
(4)
(5)
(6) ∑
(7) 1∑ def.
(8)
(9) Dtv (ξ, ζ) = max
(10) (ξv − ζv )
(11) = |ξv − ζv |.(1) A⊆V
(12)
(13) 2 v∈A. def.. τ (ε) = max min t ∈ Z≥0 u∈V. σv (i) を
(14)
(15)
(16) {j ∈ [0, i) | σv (j) = u}
(17) + 1 Pv,u を最小化する u∗ ∈ Ti (v) と定義する. そのような u ∈ Ti (v) が複数あった場合, 予め決めておいた順序に従って選ぶ. こ のとき, σv (0), σv (1), . . . は以下の性質を満たすことが知ら れている. 命題 2.1. [5], [30] 任意の P , v, u ∈ V , 整数 z > 0 に対し,
(18)
(19)
(20)
(21)
(22)
(23)
(24)
(25) {j ∈ [0, z) | σv (j) = u}
(26) − z· Pv,u
(27) < 1. v∈V. が成り立つ.. そして P の混交時間 τ (ε) は ε > 0 に対し. {. [z, z ′ ) = {z, z + 1, . . . , z ′ − 1} である ([z, z) = ∅). このとき,. } t | Dtv (Pu,· , π) ≤ ε. (2). 今, χ(0) = µ(0) , そして χ(t) ∈ Zn ≥0 を時刻 t の SRT ルー ∑ (t) ターモデルにおける k トークンの配置とする ( v∈V χv =. k). このとき, SRT ルーターモデルは以下のように動作す. と定義され, 便宜上. (0). る. まず t = 0 のとき, 各頂点 v は χv. def.. t∗ = τ (1/4),. (3). と定義する. t∗ はよく P の特徴付けに使われる (cf.[25]). 本論文では, P はエルゴード的かつ可逆と仮定する. P が. (0) σv (0), σv (1), . . . , σv (χv. 個のトークンを. − 1) に従って近傍へ振り分ける. (0). 言い換えると, 各頂点 v は |{j ∈ [0, χv ) | σv (j) = u}| 個 ∑ (1) (0) のトークンを u へ遷移させ, χu = v∈V |{j ∈ [0, χv ) | (1). σv (j) = u}| となる. 次の時刻 (t = 1) では, 各頂点 v は χv. 可逆とは, 任意の u, v ∈ V に対し πu Pu,v = πv Pv,u が成り. (0) (0) (0) (1) 個のトークンを σv (χv ), σv (χv +1), . . . , σv (χv +χv −1). 立つことをいう. 例えば, β-ランダムウォーク [21] やメト. に従って近傍へ振り分ける. 今, 時刻 t で v から u へ遷移す. ロポリスウォーク [26] の遷移確率行列は可逆である.. るトークン数を Zv,u とすると,
(28) { }
(29)
(30)
(31) (t) (t) Zv,u =
(32) j ∈ [0, χ(t) v ) | σv (Xv + j) = u
(33) ,. 2.1.1 複数トークンのランダムウォークの記法 (0). (0). 今, µ(0) = (µ1 , . . . , µn ) ∈ Zn ≥0 を V 上の k ≥ 1 トーク ンの初期配置とする. 各時刻 t ∈ Z≥0 で, v ∈ V 上の各トー クンは独立に確率 Pv,u で u ∈ V へランダムに遷移する. こ (t). (t). となる. ここで X (T ) = て, χ. 待配置とする. 即ち, µ(t) = µ(0) P t が成り立つ. ここで, 混 交時間の定義より t ≥ τ (ε) ならば Dtv (µ(t) /k, π) ≤ ε が成 り立つことに注意する.. 2.2 SRT ルーターモデル 任意の実数の遷移確率を含むランダムウォークを模. t=0. χ(t+1) u. v∈V. と定義される. なお, 定義より任意の v ∈ V に対し ∑ ∑ (t) (t) Zv,u = Zv,u = χ(t) v u∈V. が成り立つ. ここで, SRT ルーターモデルに対し, 命題 2.1 命題 2.2. 任意の P と T ≥ 0 に対し
(34)
(35) T
(36) ∑
(37)
(38)
(39) (t) (t)
(40) (Zv,u − χv Pv,u )
(41) < 1
(42)
(43) t=0. では, k 個のトークンは与えられた P に対し各 v ∈ V 上に. が成り立つ.. 定義される SRT ルーター σv : Z≥0 → N (v) に従って遷移. Proof. Zv,u の定義より,. を繰り返す. 今, σv (i) は与えられた σv (0), . . . , σv (i − 1) に対し, 再帰 的に以下のように定義される. まず, Ti (v) = {u ∈ N (v) |. |{j ∈ [0, i) | σv (j) = u}| − (i + 1)Pv,u < 0} とする. ここで *1. t P が 既 約 (∀u, v ∈ V, ∃t > 0, Pu,v > 0) か つ 非 周 期 的 t (∀v ∈ V, GCD{t ∈ Z>0 | Pv,v > 0}) のとき, P はエルゴー ド的であるという.. ⓒ 2016 Information Processing Society of Japan. (6). u∈N (v). に基づき以下の命題が成り立つ.. (N (v) = {u ∈ V | Pv,u > 0}) とする. SRT ルーターモデル. (5). v∈N (u). 過程が [20] や [28] で提案されており, それぞれスタック はこのモデルの定義を行う. N (v) を v の隣接頂点の集合. = 0) とする, そし. は任意の u ∈ V に対し ∑ ∑ (t) (t) = Zv,u = Zv,u. 倣するため, 超一様分布列 (cf. [5], [30]) に基づく決定的 ウォーク, SRT ルーターモデルと呼ばれている. 本節で. (0). χ(t) (Xv. (t+1). (t). こで µ(t) = (µ1 , . . . , µn ) ∈ Rn ≥0 を時刻 t のトークンの期. ∑T −1. (4). (t). T ∑ t=0. (t) Zv,u =. T
(44) { }
(45) ∑
(46)
(47) (t)
(48) j ∈ [0, χ(t) v ) | σv (Xv + j) = u
(49) t=0. T
(50) { }
(51) ∑
(52)
(53) = ) | σ (j) = u
(54)
(55) j ∈ [Xv(t) , Xv(t) + χ(t) v v t=0.
(56) { }
(57)
(58)
(59) =
(60) j ∈ [0, Xv(T +1) ) | σv (j) = u
(61). 3.
(62) Vol.2016-AL-158 No.3 2016/6/24. 情報処理学会研究報告 IPSJ SIG Technical Report. が成り立ち, また て, z =. (T +1) Xv. ∑T. (t). t=0. (T +1). χv Pv,u = Xv. Pv,u である. 従っ. と置くことで命題 2.1 より命題 2.2 が得ら. れる.. (T ) Xw − Mw(T ). =. T −1 ∑. (7). ′. T −1 ∑. ′. (χ(t ) − µ(t ) ) =. t′ =0. 3. 訪問頻度の解析. ′. t′ =1 ′. =. ′. (χ(t ) − µ(t ) ). T −1 t∑ −1 ∑. ∑ ∑. ′. (t) t −t−1 (Zv,u − χ(t) − πw ) v Pv,u )(Pu,w. t′ =1 t=0 u∈V v∈N (u). (8). SRT ル ー タ ー モ デ ル の 全 訪 問 時 間 の 解 析 の 前 に, 本 (T ). (T ). 節 で は |Xw − Mw | の 上 界 の 解 析 を 行 う. こ こ で, ∑T −1 (0) M (T ) = t=0 µ(t) (Mv = 0) である. 今, δ(v) = |N (v)|,. ∆ = maxv∈V δ(v) と定義する. 定理 3.1. P はエルゴード的かつ可逆と仮定する. このとき, ( )
(63)
(64) δ(u) πmax ∗
(65) (T )
(66) =O t ∆
(67) Xw − Mw(T )
(68) ≤ 3πw t∗ max u∈V πu πmin. が成り立つ. (2 番目の等式は χ(0) = µ(0) より成り立つ.) 簡 ∑ (t) (t) (t) 単の為, ϕu = v∈N (u) (Zv,u − χv Pv,u ) とする. このとき,. (8) =. 系 3.2. P はエルゴード的かつ可逆と仮定する. このとき,. =. ′. =. K=. O( πtw. +. ∗. t ∆ πmin k ). は T に依存しない定数である.. SRT ルーターモデルに対し上界を与えている
(69) . ( )
(70) πw ∆ 1 ∗ −1 系 3.2 は, T ≥ 3 2 + πmin k t ε ならば
(71) πw −. が成り立つ. 従って, 注意深く式変形を行うことで以下が得. =. t=0 t′ =t+1. =. t=0.
(72). (T )
(73) Xw kT
(74). ≤. では, P はエルゴード的かつ可逆と仮定する.. −2 T ∑ −t−2 ∑ T∑. ∑. ′. ) t ϕ(t u (Pu,w − πw ). t′ =0. T −2 T ∑ −t−2 ∑. u∈V t=0. ∑. ′. ′. (t ) ) t (Zv,u − χ(t v Pv,u )(Pu,w − πw ). t′ =0 v∈N (u). が成り立ち, 題意を得る.. (T ) Xw − Mw(T ) T∑ −t−2. ′. ′. (t ) ) t (Zv,u − χ(t v Pv,u )(Pu,w − πw ). t=0 u∈V v∈N (u) t′ =0. が成り立つ.. Proof. 補題 3.3 を示すために, まず以下の補題を導入する. 補題 3.4. [28] (補題 4.1.) 任意の w ∈ V と T > 0 に対し, ) (T ) χ(T w − µw. =. (10). t′ =0. u∈V t=0. =. 補題 3.3. 任意の w ∈ V と T > 1 に対し,. ′. ) t ϕ(t u (Pu,w − πw ).. 式 (9) と式 (10) を組み合わせると,. 定理 3.1 を示すため, まず以下の補題を示す. 以下の議論. ∑ ∑. ′. −t−1) t ϕ(t (Pu,w − πw ) u. T −2 T ∑ −t−2 ∑. (9) =. T −1 ∑. ′. t ϕu(t −t−1) (Pu,w − πw ). T −2 T −1 ∑ ∑. ε が成り立つことも示している.. ∑ ∑. (9). t′ =1 t=0. に対し上界を与えているのに対し, 系 3.2 が k トークンの. =. ′. −t−1) t ϕ(t (Pu,w − πw ) u. られる.. [20] の定理 4 は単一トークンのロータールーターモデル. T −2 ∑. −1 t∑ −1 ∑ T∑. ′ T −1 t∑ −1 ∑. Kπw T. が 任 意 の w ∈ V と T > 0 に 対 し 成 り 立 つ. こ こ で ∗. ′. t −t−1 ϕ(t) − πw ) u (Pu,w. u∈V t′ =1 t=0. 定理 3.2 より, [20] の定理 4 に似た以下の系が導かれる.. δ(u) πu. ∑. t′ =1 t=0 u∈V. が任意の w ∈ V と T > 0 に対し成り立つ..
(75)
(76) (T )
(77) 3πw t∗ maxu∈V Xw
(78)
(79) 3t∗
(80) +
(81) πw −
(82) ≤
(83) kT
(84) 2T kT. ′ T −1 t∑ −1 ∑. 定理 3.1 の証明. T = 1 のとき自明であるため, 以下では. T > 1 を仮定する. 補題 3.3 と命題 2.2 より,
(85)
(86)
(87) (T )
(88)
(89) Xw − Mw(T )
(90)
(91)
(92)
(93) T∑
(94) −t−2
(95) −2 ∑ ∑ T ∑
(96) ′ ′ (t ) (t ) t
(97) =
(98) (Zv,u − χv Pv,u )(Pu,w − πw )
(99)
(100)
(101) t=0 u∈V v∈N (u) t′ =0
(102)
(103)
(104) T −2 ∑ ∑
(105) T ∑ −t−2
(106)
(107) ∑
(108) ′
(109)
(110)
(111) t (t′ ) )
(112) ≤ (Zv,u − χ(t
(113) v Pv,u )
(114) Pu,w − πw
(115) ′
(116) t=0 u∈V v∈N (u). (t) T −t−1 (Zv,u − χ(t) − πw ) v Pv,u )(Pu,w. <. t=0 u∈V v∈N (u). が成り立つ.. T −2 ∑. t =0. ∑ ∑
(117)
(118) t
(119) Pu,w − πw
(120). t=0 u∈V v∈N (u). ■. =. T −2 ∑. ∑.
(121) t
(122) δ(u)
(123) Pu,w − πw
(124). (11). t=0 u∈V. X (T ) , M (T ) の定義と補題 3.4 より, ⓒ 2016 Information Processing Society of Japan. が成り立つ. ここで P の可逆性より,. 4.
(125) Vol.2016-AL-158 No.3 2016/6/24. 情報処理学会研究報告 IPSJ SIG Technical Report. (11) =. T −2 ∑. ∑. t=0 u∈V.
(126)
(127)
(128) πw t
(129) δ(u)
(130)
(131) (Pw,u − πu )
(132)
(133) πu. 4. 全訪問時間の上界 訪問頻度の解析と, 可逆なマルコフ連鎖の技術を組み合. T −2
(134) δ(u) ∑ ∑
(135)
(136) t ≤ πw max Pw,u − πu
(137) u∈V πu t=0. (12). u∈V. とが出来る. 今, SRT ルーターモデルの全訪問時間を以下の. が成り立つ. 総変動距離の定義 (1) より, T −2 ∑. T −2 ∑
(138) ∑
(139) t t
(140) Pw,u , π) − πu
(141) = 2 Dtv (Pw,·. t=0 u∈V. (13). t=0. (0 < γ < 1/2) に対し, ( t ) 1−γ Dtv Pv,· ,π ≤ τ (γ) 1 − 2γ. 定理 4.1 は (無理数を含みうる) 一般の遷移確率を模倣す る決定的過程の全訪問時間に対する初の上界である. G 上. 従って,. の単純ランダムウォークの遷移確率行列を定理 4.1 に当て. 1 − (1/4) τ (1/4) = 3t∗ 1 − 2· (1/4). (14). 系 3.2 の証明. 定理 3.1 より,
(142)
(143)
(144)
(145)
(146) (T )
(147) (T )
(148)
(149) π − X
(150)
(151) kT w w Xw
(152)
(153)
(154) πw −
(155) =
(156) kT
(157) kT
(158)
(159)
(160)
(161)
(162)
(163) (T ) (T )
(164) (T )
(165)
(166) kT πw − Mw
(167) +
(168) Mw − Xw
(169) ≤
(170)
(171) kT
(172) (T )
(173)
(174) Mw − kT πw
(175) 3πw t∗ maxu∈V ≤ + kT kT. が G 上の任意のロータールーターモデルに対し成り立つ. ここで t∗ は G 上の単純ランダムウォークの混交時間で ある.. ( ) [24] で示された上界は O t∗ + (∆/δ)(mt∗ /k) であった. (定理 4.1, 命題 4.2, 定理 4.5). ここで ∆/δ グラフの最大/最 δ(u) πu. ∗. (T ) |Mw. − kT πw | ≤ 3kt /2 が成り ∑ 立てば証明は終了する. 定義より v∈V µ(0) = k であ ∑T −1 ∑ (0) るため, πw = kT πw が成り立ち, また t=0 u∈V µ ∑ ∑ (T ) (0) t T −1 (t) T −1 ∑ Mw = t=0 µw = t=0 u∈V µu Pu,w が成り立つこ. が成り 立つ. 従って,. とに注意すると,.
(176) T −1
(177) T −1 ∑
(178)
(179)
(180) ∑ ∑
(181) ∑
(182) (T )
(183)
(184)
(185) t µ(0) µ(0) πw
(186)
(187) Mw − kT πw
(188) =
(189) u Pu,w −
(190)
(191) t=0 u∈V t=0 u∈V
(192) T −1
(193)
(194) ∑ ∑
(195)
(196)
(197) t =
(198) µ(0) (P − π )
(199) w u u,w
(200)
(201) t=0 u∈V. ≤. ∑ u∈V. µ(0) u. T −1 ∑. t |Pu,w − πw |. (15). t=0. が成り立つ. また補題 3.5 と総変動距離の定義 (1) より,. t=0. t |Pu,w. − πw | ≤. T −1 ∑. t Dtv (Pu,· , π). t=0. (16) (T ). が成り立つ. 従って, 式 (15) と式 (16) より |Mw −kT πw | ≤. ⓒ 2016 Information Processing Society of Japan. 小次数を表す. 従って系 4.2 は正則でないグラフに対し上 界を改善している. [13] の上界 O(mD/ log k)(定理 3.3, 3.7) ( ) と比べると, t∗ = O D(k/ log k) ならば上界を改善出来て いる (t∗ が小さい, もしくは k が大きい). 定理 4.1 を示すため, まず以下の補題を示す. 補題 4.3. P はエルゴード的かつ可逆と仮定する. このとき, 任意の u, w ∈ V に対し, t ≥ 2t∗ ならば t Pu,w ≥. πw 4. が成り立つ.. Proof. 分離距離 (separation distance) [2] は ( t ) Pu,v s(t) = max 1 − . u,v∈V πv と 定 義 さ れ る.. (18). こ の 距 離 は 任 意 の t, t′ ≥ 1 に 対 し. s(t + t′ ) ≤ s(t)s(t′ ) を満たす (submultiplicativity, [2] の補題. 3 ≤ t∗ 2. 3kt∗ /2 が成り立つため, 題意を得る.. はめることで, 以下の系を得る. 系 4.2. 任意の G と k ≥ 1 個のトークンの初期配置に対し, ( { ∗ }) mt ∗ 24mt∗ = O max ,t Tcover ≤ 2t∗ + 1 + k k. が成り立ち, 題意を得る.. T −1 ∑. ∗ 12 maxu∈V δ(u) πu · t Tcover ≤ 2t∗ + 1 + k}) ( { ∗ t ∆ ∗ ,t = O max πmin k. が任意の k ≥ 1 個のトークンの初期配置に対し成り立つ.. が成り立つ.. (13) ≤ 2·. (17). 定理 4.1. P はエルゴード的かつ可逆と仮定する. このとき,. 補 題 3.5. [28] (補 題 4.2.) 任 意 の v ∈ V と T > 0, γ. t=0. ように定義する. { } Tcover = min T ∈ Z≥0 | Xv(T ) ≥ 1 (∀v ∈ V ) まず, 以下の主定理を示す.. が成り立つ. ここで, 以下の補題を導入する.. T −1 ∑. わせることで SRT ルーターモデルの全訪問時間を得るこ. 3.7). 更に, 可逆な P に対し以下の補題が成り立つ. 補題 4.4. [25] (補題 19.3.) P は可逆と仮定する. このとき,. ( ) ¯ 2 s(2t) ≤ 1 − 1 − d(t) 5.
(202) Vol.2016-AL-158 No.3 2016/6/24. 情報処理学会研究報告 IPSJ SIG Technical Report. が 任 意 の t ≥ 0 に 対 し 成 り 立 つ.. ¯ こ こ で d(t) =. t t maxu,v∈V Dtv (Pu,· , Pv,· ) である.. 5. まとめと今後の課題 本論文では k ≥ 1 トークンの SRT ルーターモデルの訪 (T ). P がエルゴード的ならば. 問頻度 Xv. ¯ ∗) ≤ 1 d(t 2. る全訪問時間の上界を与えた. この上界は既存のローター. (19). が成り立つことが知られている ([25] の (4.34) を参照され. と, 任意のエルゴード的かつ可逆な P に対す. ルーターモデルの全訪問時間の上界を多くの場合改善して いる. 今後の課題として, β-ランダムウォーク, メトロポリ スウォークなど “高速な” ランダムウォークを脱乱択化す. たい). これらの事実を組み合わせることで,. ることが挙げられる. t Pu,w ¯ ∗ ))2 1− ≤ s(t) ≤ s(2t∗ ) ≤ 1 − (1 − d(t πw ( )2 1 3 ≤ 1− 1− = 2 4. 謝辞 本研究は JSPS 科研費 15J03840 の助成を受けたも のである. 参考文献. が成り立ち, 題意を得る.. [1]. 定理 4.1 の証明. 補題 4.3 は任意のエルゴード的かつ可逆 t な P , 任意の u, w ∈ V と t ≥ 2t∗ に対して Pu,w の下界を (T ). 与える. 従って [24] のように Mw. の下界を得ることが出 [3]. 来る. 即ち,. Mw(T ) =. T −1 ∑. ∑. t µ(0) u Pu,w ≥. T −1 ∑. ∑. t=2t∗. u∈V. T −1 ∑. ∑. [4]. t µ(0) u Pu,w. t=2t∗ u∈V. t=0 u∈V. ≥. [2]. µ(0) u. πw kπw (T − 2t∗ ) = 4 4. (20). [5] [6]. が成り立つ. 従って定理 3.1 と式 (20) から, (T ) Xw ≥ Mw(T ) − 3πw t∗ max u∈V. ≥. [7]. δ(u) πu. δ(u) kπw (T − 2t∗ ) − 3πw t∗ max u∈V πu 4. (21). が成り立つ. 式 (21) より, 任意の w ∈ V と. T ′ > 2t∗ +. 12t∗ maxu∈V δ(u) πu k. .. [8]. [9]. [10]. を満たす T ′ ∈ Z≥0 に対し, (T Xw. ′. [11] ). >0. が成り立つことが分かる. この事実と全訪問時間の定義 (22). [12]. より Tcover ≤ T ′ となり, 題意を得る. [13]. 系 4.2 の証明. G 上の単純ランダムウォークに対応する. SRT ルーターモデルが G 上のロータールーターモデル. [14]. と対応することと, G 上の単純ランダムウォークに対し. πu =. δ(u) 2m. であるから maxu∈V. δ(u) πu. = 2m が成り立つこと. に注意すると,. Tcover ≤ 2t∗ + 1 +. 24mt∗ k. が定理 4.1 より導かれ, 題意を得る.. ⓒ 2016 Information Processing Society of Japan. [15]. [16]. H. Akbari and P. Berenbrink, Parallel rotor walks on finite graphs and applications in discrete load balancing, Proc. SPAA 2013, 186–195. D. Aldous and P. Diaconis, Strong uniform times and finite random walks, Advances in Applied Mathematics, 8 (1987), 69–97. R. Aleliunas, R. Karp, R. Lipton, L. Lovasz and C. Rackoff, Random walks, universal traversal sequences, and the complexity of maze problems, Proc. FOCS 1979, 218–223. N. Alon, C. Avin, M. Koucky, G. Kozma, Z. Lotker, M. R. Tuttle, Many random walks are faster than one, Combinatorics, Probability & Computing, 20 (2011), 481–502. O. Angel, A.E. Holroyd, J. Martin, and J. Propp, Discrete low discrepancy sequences, arXiv:0910.1077. E. Bampas, L. Gasieniec, N. Hanusse, D. Ilcinkas, R. Klasing, and A. Kosowski, Euler tour lock-in problem in the rotorrouter model, Proc. DISC 2009, 423–435 P. Berenbrink, R. Klasing, A. Kosowski, F. Mallmann-Trenn, and P. Uznanski, Improved analysis of deterministic loadbalancing schemes, Proc. PODC 2015, 301–310. A. Broder, A. Karlin, P. Raghavan, E. Upfal, Trading space for time in undirected s–t connectivity, SIAM Journal on Computing 23 (1994) 324–334. J. Chalopin, S. Das, P. Gawrychowski, A. Kosowski, A. Labourel and P. Uznanski, Lock-in problem for parallel rotor-router walks, arXiv:1407.3200. J. Cooper, B. Doerr, T. Friedrich, and J. Spencer, Deterministic random walks on regular trees, Random Structures & Algorithms, 37 (2010), 353–366. J. Cooper, B. Doerr, J. Spencer, and G. Tardos, Deterministic random walks on the integers, European Journal of Combinatorics, 28 (2007), 2072–2090. J. Cooper and J. Spencer, Simulating a random walk with constant error, Combinatorics, Probability and Computing, 15 (2006), 815–822. D. Dereniowski, A. Kosowski, D. Pajak, and P. Uznanski, Bounds on the cover time of parallel rotor walks, LIPICS, 25 (STACS 2014), 263–275. B. Doerr and T. Friedrich, Deterministic random walks on the two-dimensional grid, Combinatorics, Probability and Computing, 18 (2009), 123–144. R. Elsasser and T. Sauerwald, Tight bounds for the cover time of multiple random walks, Theoretical Computer Science, 412 (2011), 2623–2641. U. Feige, A tight upper bound for the cover time of random walks on graphs, Random Structures and Algorithms, 6 (1995), 51–54.. 6.
(203) 情報処理学会研究報告 IPSJ SIG Technical Report. [17]. [18]. [19]. [20]. [21]. [22]. [23]. [24]. [25] [26]. [27]. [28]. [29]. [30] [31]. Vol.2016-AL-158 No.3 2016/6/24. U. Feige, A tight lower bound for the cover time of random walks on graphs, Random Structures and Algorithms, 6 (1995), 433–438. T. Friedrich, M. Gairing, and T. Sauerwald, Quasirandom load balancing, SIAM Journal on Computing, 41 (2012), 747–771. T. Friedrich and T. Sauerwald, The cover time of deterministic random walks, The Electronic Journal of Combinatorics, 17 (2010), R167. Lecture Notes in Computer Science, 6196 (COCOON 2010), 130–139. A. E. Holroyd and J. Propp, Rotor walks and Markov chains, M. Lladser, R.S. Maier, M. Mishna, A. Rechnitzer, (eds.), Algorithmic Probability and Combinatorics, The American Mathematical Society, 2010, 105–126. S. Ikeda, I. Kubo, and M. Yamashita, The hitting and cover times of random walks on finite graphs using local degree information, Theoretical Computer Science, 410 (2009), 94– 100. H. Kajino, S. Kijima, and K. Makino, Discrepancy analysis of deterministic random walks on finite irreducible digraphs, discussion paper. S. Kijima, K. Koga, and K. Makino, Deterministic random walks on finite graphs, Random Structures & Algorithms, 46 (2015), 739–761. A. Kosowski and D. Pajak, Does adding more agents make a difference? A case study of cover time for the rotor-router, Proc. ICALP 2014, 544–555. D. A. Levine, Y. Peres, and E. L. Wilmer, Markov Chain and Mixing Times, The American Mathematical Society, 2008. Y. Nonaka, H. Ono, K. Sadakane, M. Yamashita, The hitting and cover times of Metropolis walks, Theoretical Computer Science, 411 (2010), 1889–1894. Y. Rabani, A. Sinclair, and R. Wanka, Local divergence of Markov chains and analysis of iterative load balancing schemes, Proc. FOCS 1998, 694–705. T. Shiraga, Y. Yamauchi, S. Kijima, and M. Yamashita, Deterministic random walks for rapidly mixing chains, arXiv:1311.3749. T. Shiraga, Y. Yamauchi, S. Kijima, and M. Yamashita, Total variation discrepancy of deterministic random walks for ergodic Markov chains, Proc. ANALCO 2016, 138–148. R. Tijdeman, The chairman assignment problem, Discrete Mathematics. 32 (1980), 323–330. V. Yanovski, I.A. Wagner, and A.M. Bruckstein, A distributed ant algorithm for efficiently patrolling a network, Algorithmica, 37 (2003), 165–186.. ⓒ 2016 Information Processing Society of Japan. 7.
(204)
関連したドキュメント
Although the holonomy gives infinitely many tight contact structures up to isotopy (fixing the boundary), this turns out to be a special feature of the nonrotative case. This
First, we verify some conditions in Theorem 7.15 to prove the sublinearity of the corrector. In fact, in this case both sides Gaussian heat kernel bounds which are similar to the
A second way involves considering the number of non-trivial tree components, and using the observation that any non-trivial tree has at least two rigid 3-colourings: this approach
5. Scaling random walks on graph trees 6. Fusing and the critical random graph 7.. GROMOV-HAUSDORFF AND RELATED TOPOLOGIES.. compact), then so is the collection of non-empty
5. Scaling random walks on graph trees. Fusing and the critical random graph 7. Local times and cover times.. GROMOV-HAUSDORFF AND RELATED TOPOLOGIES.. compact), then so is
Scheffler, Limit theorems for continuous time random walks with infinite mean waiting times, to appear in J..
We consider on-diagonal heat kernel estimates and the laws of the iterated logarithm for a switch- walk-switch random walk on a lamplighter graph under the condition that the
Honda discovered that, if we take a convex decomposition of an overtwisted contact structure on M and look at all possible non-trivial isotopies (bypasses) of the cutting surfaces S i
