多項式時間決定的サンプラーの頂点誤差解析
7
0
0
全文
(2) Vol.2014-AL-149 No.4 2014/9/12. 情報処理学会研究報告 IPSJ SIG Technical Report. √ (t) µv | = Ω( kt) となる例を与えている. この例は時刻 t が. テップ遷移した時のトークンの期待配置を表す. 本稿では. 大きくなるにしたがって誤差が無限に大きくなる例が存在. P がエルゴード的かつ可逆ならば, 任意の v ∈ V , t に対し. することを示唆している.. |χv − µv | ≤ 3(πmax /πmin )t∗ ∆ が成り立つことを示す. こ (t). マルコフ連鎖を脱乱択化することを目指し, Kijima ら [12] は一般の (有限) 有向多重グラフ (V, A) 上で解析を行い, マルコフ連 鎖がエ ルゴード 的, 可逆かつ lazy な場合に (t) (t) |χv − µv | = O(|V (t) (t) らは |χv − µv | =. (t). こで πmax (πmin ) は π の最大値 (最小値), t∗ はマルコフ連鎖 の混交度 (mixing rate), ∆ は状態遷移図の最大次数を表す. この結果から, 0-1 ナップサック解, 線形順序拡大, マッチ. ||A|) が成り立つことを示した. また, 彼. ングなど, 急速混交するマルコフ連鎖が設計されているいく. Ω(|A|) となる例も与えている.. つかの組合せ構造 (#P 完全問題) の一様サンプリングに対す. 負荷分散の分野において, Rabani ら [14] はロータールー. る多項式時間 (多項式スペース) の決定的サンプリングアル. ターモデルと関連する決定的アルゴリズムに対し解析を. ゴリズムを設計できる. 任意の ε (0 < ε < 1) に対し, 総トー. 行っている. 彼らはマルコフ連鎖がエルゴード的かつ対称. クン数 M ≥ 6ε−1 t∗ ∆ とすると, 決定的サンプリングアルゴ. (t). (t). 行列の場合に |χv − µv | = O(∆ log(|V |)/(1 − λ∗ )) を示. リズムは ∥e χ(t) − π∥∞ < ε を満たす χ e(t) を出力する. ここで. している. ここで ∆ は状態遷移図の最大次数を, λ∗ は遷移. χ e(t) := χ(t) /M , π は問題の集合上の一様分布である. 具体. 確率行列の第二固有値を表している.. 的には, 決定的サンプリングアルゴリズムは n 次元 0-1 ナッ. また, 超立方体, トーラスなどのある特定のグラフ構. プサック解に対して O∗ (n11.1 ε−1 ) 時間で, n 要素の半順序. 造に対しては状態数の対数サイズの上界が与えられてい. 集合の線形順序拡大に対して O∗ (n8 ε−1 ) 時間で, 頂点数 n,. る [1, 12]. 例えば, Akbari ら [1] は n 次元超立方体に対し. 枝数 m のグラフ上のマッチングに対して O∗ (m4 n4 ε−1 ) で. (t). 解を出力する. ここで O∗ は poly(log(ε−1 ), log m, log n) の. (t). |χv − µv | = O(n1.5 ) を示している. これらの解析は特定のグラフ構造に深く依存しており,. 項を無視する上界を表す. なお, トークン数に関する整数性. 他の組合せ構造へ拡張する事が非常に難しくなっている.. ギャップのため ε−1 は任意の決定的サンプリングアルゴリ. Kijima ら [12] は 0-1 ナップサック多面体, 2 部グラフのマッ. ズムで改善できない項である. ランダムウォークの脱乱択. チングなどの組合せ構造 (#P 完全問題) に対し. (t) |χv. −. (t) µv |. を入力の多項式サイズで抑えることが出来るかどうかを今 後の課題として挙げた.. 化との関連は [15] を参照されたい.. 2. マルコフ連鎖モンテカルロ法. ランダムウォークの脱乱択化に関連する他の話題とし. 決定的サンプリングアルゴリズムの準備として, この章. ては到達時間の解析がある. Holroyd と Propp [9] は 1 つの. ではマルコフ連鎖モンテカルロ法 (MCMC 法) について簡. トークンをロータールーターモデルで遷移させたときの到. 単に説明する. def.. 達時間に関する解析を行っている. 彼らは任意の頂点 v, 時. V = {1, . . . , N } を有限の状態集合とし, ある与えられ. 刻 t に対して |ν (t) (v) − πv | = O(|V ||A|) であることを示し. た V 上の正のベクトル f = (f1 , . . . , fN ) ∈ RN ≥0 に比例し. た. ただし, ν (t) (v) は時刻 t までに頂点 v をトークンが訪問. たサンプリングを行いたいとする. 例えば, 0-1 ナップサッ. した回数を, π は対応するランダムウォークの定常分布を. ク解 (5.1 章参照) 上の一様サンプリングを行いたい場合,. 表す. Holroyd と Propp [9] はロータールーターモデルを一. V を 0-1 ナップサック解の集合とし, 任意の v ∈ V に対し. 般化した stack walk と呼ぶ無理数の遷移確率を扱えるモデ. fv = 1 とする. マルコフ連鎖モンテカルロ法 (MCMC 法). ルも提案しており, Angel ら [2] が具体的に stack walk を構. のアイデアは, 目標となる分布 f /∥f ∥1 が極限分布となる. 成するアルゴリズムを提案している.. マルコフ連鎖を設計し, 極限分布からサンプリングを行う ∑ というものである (∥f ∥1 = v∈V fv は正規化定数を表す). ×N を V 上のマルコフ連鎖の遷移確率行列とする. P ∈ RN ≥0. 1.3 本稿の成果 本稿では, ある有限集合 V = {1, . . . , N } からサンプリン. Pu,v は u から v への遷移確率を表す (u, v ∈ V ). P が既約. グを決定的に行うアルゴリズム提案する. このアルゴリズム. t であるとは Pu,v > 0 を満たすような t が任意の u, v ∈ V. は, マルコフ連鎖の遷移確率行列 P を模倣する deterministic. に対して存在することであり, P が非周期であるとは任意. random walk の研究 (ロータールーターモデル等) に基づく.. t の v ∈ V に対して GCD{t ∈ Z>0 | Pv,v > 0} = 1 を満たす. このアルゴリズムは, V 上の M 個のトークン配置の更新. ことである. 特に, P が既約かつ非周期であるときに P は. (t) (t) (χ1 , . . . , χN ). ∈ ZN ≥0 を (t) 時刻 t = 0, 1, 2, . . . でのトークン配置とする. (χv は頂点 ∑ (t) v ∈ V , 時刻 t のトークン数を表す. また v∈V χv = M (0) (0) (t) (0) t を決定的に繰り返す. 今, χ(t) =. が成り立つ. ) また µ. = χ. , µ. = µ. P とする.. µ(t) ∈ RN ≥0 は M 個のトークンが P に従って独立に t ス. c 2014 Information Processing Society of Japan ⃝. エルゴード的であるという. P がエルゴード的ならば唯一 の定常分布 π ∈ RN ≥0 (πP = π を満たす確率分布) が存在し, 極限分布が π になる (V 上の任意の確率分布 ξ ∈ RN ≥0 に対 し ξP ∞ = π が成り立つ) ことが知られている. ここで, あ ×N に対し, 任意の u, v ∈ V で る P ∈ RN ≥0. 2.
(3) Vol.2014-AL-149 No.4 2014/9/12. 情報処理学会研究報告 IPSJ SIG Technical Report. fu Pu,v = fv Pv,u を満たすような f ∈. (1) RN ≥0. が存在するとき P は可逆であると. いう. P が (1) 式 (詳細つり合い式) を満たすならば, f P = f が成り立つことが容易に示せる. 即ち f /∥f ∥1 が P の定常 分布となる. 今, ξ, ζ を V 上の確率分布とする. このとき ξ と ζ の総変 動距離 (total variation distance) Dtv を def.. Dtv (ξ, ζ) = max A⊆V. ∑. 1 (ξv − ζv ) = ∥ξ − ζ∥1 . 2. (2). Dtv (ξ, ζ) ≤ 1 であることに注意する. そして, マルコフ連鎖 の混交時間 (mixing time) を ε > 0 に対し. v∈V. (0). 上の M 個のトークンの初期配置とし, 各トークンが独立に. P に従って t ∈ Z≥0 ステップ遷移した時のトークンの期待 (t) 配置を µ(t) ∈ RN ≥0 とする. 即ち, ∥µ ∥1 = M であり, また. µ(t) = µ(0) P t である. ここで, 簡単のため µ e(t) = µ(t) /M と (2 章参照). 定的な手法で模倣することである. G = (V, E) を P の状態 遷移図とする. 即ち, E = {(u, v) ∈ V 2 | Pu,v > 0} である.. E は自己ループ辺 (v, v) を含みうることに注意されたい. N + (v)(N − (v)) を v ∈ V の隣接頂点集合 (N + (v) = {u ∈. (3). t と定義する. ここで Pv,· は P t の v 行ベクトルを表す. 即 t ち Pv,· は初期状態 v ∈ V から出発し, t 回遷移を繰り返し. た後のマルコフ連鎖の確率分布を表す. 混交時間の定義 (3) t t , π) ≤ ε は Dtv (Pv,· より, τ (ε) 回遷移した後の確率分布 Pv,·. を満たす. 即ち, 目標の分布の近似サンプリングを得ること が出来る.. ( t ) def. 簡単のため, t ≥ 0 に対し h(t) = maxw∈V Dtv Pw,· ,π. とおく. 分布 h は劣乗法性を持つことが知られている. 以 下の命題は 4.2 章の解析で用いる. 証明は [15] を参照され たい. 命題 2.1. 任意の ℓ (ℓ ≥ 1), k (0 ≤ k < τ (γ)), γ (0 < γ <. 1/2) に対し h (ℓ· τ (γ) + k) ≤. (0). 移確率行列とする. 今, µ(0) = (µ1 , . . . , µN ) ∈ ZN ≥0 を V. 決定的サンプリングアルゴリズムのアイデアは µ(t) を決. と定義する. ここで ∥ξ∥1 と ∥ζ∥1 は共に 1 であるため,. { } t τ (ε) = max min t ∈ Z≥0 | Dtv (Pv,· , π) ≤ ε. ×N P ∈ RN を V 上のエルゴード的なマルコフ連鎖の遷 ≥0. おくと, P はエルゴード的であるため µ e(∞) = π が成り立つ. v∈A. def.. 3.1 アルゴリズム. 1 (2γ)ℓ 2. V | Pv,u > 0}, N − (v) = {u ∈ V | Pu,v > 0}) とする. 簡単 のため, δ + (v) = |N + (v)|, δ − (v) = |N − (v)| とする. P が可 逆ならば, N + (v) = N − (v) が成り立つため両方を N (v) と 書くこととし, また δ(v) = |N (v)| とする. 今, χ(0) = µ(0) とし, χ(t) ∈ ZN ≥0 を決定的サンプリングア ルゴリズムの時刻 t ∈ Z≥0 でのトークン配置とする. トー クン配置 χ(t) は Pv,u を模倣するよう, 以下のように各時刻 で更新される. まず, 一般性を失うことなく各 v ∈ V の各. u ∈ N + (v) に対し順番 u1 , . . . , uδ+ (v) を定める. そして, 時 刻 t から t + 1 の間に頂点 v から u へ遷移するトークン数 (t). Zv,u を以下のように定義する. ⌋ ⌊ (t) χv Pv,ui + 1 (i ≤ i∗ ) (t) Zv,u = ⌋ ⌊ i χ(t) (otherwise) v Pv,ui. (4). ここで,. ■. が成り立つ. def.. P の混交度 (mixing rate) を t∗ = τ (1/4) と定義する.. 3. 決定的サンプリングアルゴリズム. i∗ = χv − (t). ⌋ ∑δ+ (v) ⌊ (t) P χ v v,u i i=1. とする (“余り” を表す). そして, 各 u ∈ V に対し χ(t+1) を (t+1) def.. χu. =. 3.1 章で決定的サンプリングアルゴリズムを説明し, 3.2. ∑ v∈V. (t). Zv,u. (5). 章で主定理の概要を紹介する. このアルゴリズムはローター. と定める.. ルーターモデル ( [6, 12] 参照) や stack walk [2, 9] のアイデ アに基づいている. これらのモデルとの大きな違いは無記. 複数トークン型のランダムウォークにおいて, 各 u ∈ V , ∑ (t+1) (t) t ≥ 0 で µu = v∈V µv Pv,u が成り立つことに注意す. 憶性である. ロータールーターモデルや stack walk は各時. ると, もし χ(t) が µ(t) をよく模倣しているならば Zv,u は “. 刻におけるトークン配置と各頂点におけるルーターの状態. トークンのフローの期待値”µv Pv,u をよく模倣しており,. を記憶しておく必要があるが, 我々のアルゴリズムはトー. 従って χ(t+1) は µ(t+1) をよく模倣するはずである.. クン配置のみを記憶する. この性質が既存のモデルに比べ アルゴリズムをより単純にしている.. 5 章において 0-1 ナップサック解, 線形順序拡大, マッチ ングなど, 具体的な問題に対する決定的サンプリングアル ゴリズムを紹介し, 計算複雑性に関し議論を行う. ローター ルーターモデル [6,12], stack walk [2,9] との関連はフルペー パー [15] を参照されたい.. c 2014 Information Processing Society of Japan ⃝. (t). (t). 実際, 簡単に以下の観察を得ることが出来る. この観察は. 4.2 章の解析で用いる. 観察 3.1. 上記のアルゴリズムにおいて任意の u, v ∈ V ,. t ≥ 0 に対し
(4)
(5)
(6)
(7) (t)
(8) Zv,u − χ(t) v Pv,u
(9) ≤ 1 が成り立つ.. 3.
(10) Vol.2014-AL-149 No.4 2014/9/12. 情報処理学会研究報告 IPSJ SIG Technical Report. 3.2 主定理. が成り立ち, 以下の式を得る.. 定義より, τ (ε) を P の混交時間とすると Dtv (e µ(τ (ε)) , π) ≤. ε が成り立つ. これは µ e が目標の分布 π をよく模倣すること. (7) =. def.. ズムの分布 χ e(T ) = χ(T ) /M が目標の分布 π をよく模倣す. =. ることを示したい. 今, ∥ξ∥1 = ∥ζ∥1 = 1 を満たす ξ ∈ RN ≥0 ,. ζ ∈ RN ≥0 に対し, 頂点距離 (point-wise distance) Dpw (ξ, ζ) を Dpw (ξ, ζ) = max |ξv − ζv | = ∥ξ − ζ∥∞ .. =. w. ( T −1 ∑ ∑. 定理 3.2. P ∈. ×N RN ≥0. をエルゴード的かつ可逆な遷移確率. 行列とし, π を P の定常分布とする. このとき任意の T ≥ 0 に対し. T −t−1 χ(t+1) Pu,w u. t=0. u∈V. T −1 ∑. ∑(. ここで (8) 中の. と定義する.. Dpw χ e. (T ). ,µ e. (T ). ). ( ) ) − χ(t) P T −t w. −. ∑. ) (t). (χ. ) T −t−1 − (χ(t) P )u Pu,w . χ(t+1) u (. ∑ u∈V. (t+1). χu. (8). ) T −t−1 − (χ(t) P )u Pu,w の項は. 通常 0 にならないが, ) ∑∑ ∑ ∑( − χ(t) − (χ(t) P )u = χ(t+1) χ(t+1) v Pv,u u u u∈V v∈V. u∈V. πmax 3t∗ ∆ ≤ · πmin M. =. ∑. χ(t+1) u. ∑. −. u∈V. χ(t) v. v∈V. ∑. Pv,u. u∈V. = M −M = 0. が成り立つ. ここで πmax = max{πv | v ∈ V }, πmin =. min{πv | v ∈ V } とする.. T −t−1 P )u Pu,w. u∈V. u∈V. (. ). t=0 u∈V. (6). v∈V. χ(t+1) P T −t−1. t=0. を意味する. 従って, 私たちは決定的サンプリングアルゴリ. def.. T −1 (( ∑. が任意の t ≥ 0 に対し成り立つことに注意する. 従って. 特に, 定常分布が一様分布の場合, 以下の系を得る. ×N 系 3.3. P ∈ RN をエルゴード的かつ可逆な遷移確率 ≥0. (8) =. 4. 頂点誤差の解析. ∑(. ) T −t−1 χ(t+1) − (χ(t) P )u Pu,w u. t=0 u∈V. 行列とし, P の定常分布 π は一様分布とする. このとき,. M ≥ 6ε−1 t∗ ∆, T ≥ τ (ε/2) ならば決定的サンプラーの分布 ( (T ) ) χ e(T ) は Dpw χ e , π ≤ ε を満たす.. T −1 ∑. −. T −1 ∑. ∑(. ) χ(t+1) − (χ(t) P )u πw u. t=0 u∈V. =. T −1 ∑. ∑(. χ(t+1) − (χ(t) P )u u. )( ) T −t−1 Pu,w − πw. (9). t=0 u∈V. 本章では定理 3.2 を証明する. 証明に用いるいくつかの 手法は既存研究 [6, 12, 14] に基づいている.. ∑ (t+1) (t) が成り立つ. ここで定義 (5) より χu = v∈V Zv,u = ∑ (t) − v∈N − (u) Zv,u であるため (最後の等号は任意の v ̸∈ N (u). 4.1 証明の大枠. に対し Zv,u = 0 が成り立つため) ,. (t). まず, 以下の補題を示す. ×N 補題 4.1. P ∈ RN を状態空間 V 上のエルゴード的な遷 ≥0. 移確率行列とし, π を P の定常分布とする. このとき, 任意. (9) =. の w ∈ V と任意の T ≥ 0 に対し (T ) ) χw − µ(T w. =. T −1 ∑. ∑. = ∑. (. (t) Zv,u. −. χ(t) v Pv,u. )(. T −t−1 Pu,w. − πw. ). t=0 u∈V v∈N − (u). が成り立つ.. w. (7). t=0. c 2014 Information Processing Society of Japan ⃝. ∑. . (t) Zv,u −. t=0 u∈V. v∈N − (u). T −1 ∑. ∑. ∑. (. . ∑. ( T −t−1 ) Pu,w χ(t) − πw v Pv,u. v∈N − (u). (t) Zv,u − χ(t) v Pv,u. )(. T −t−1 Pu,w − πw. ). t=0 u∈V v∈N − (u). が成り立ち, 題意が示された.. 以下の定理を示す. ×N をエルゴード的かつ可逆な遷移確率 定理 4.2. P ∈ RN ≥0. 行列とし, π を P の定常分布とする. このとき任意の w ∈ V ,. χ(T ) P 0 − χ(0) P T ( ) ( ) = χ(T ) P 0 − χ(T −1) P 1 + χ(T −1) P 1 − χ(T −2) P 2 + ( ) ( ) · · · + χ(2) P T −2 − χ(1) P T −1 + χ(1) P T −1 − χ(0) P T χ(t+1) P T −t−1 − χ(t) P T −t. . 本章では可逆なマルコフ連鎖に対し解析を進める. まず,. が成り立つ. そして. =. ∑. 4.2 可逆なマルコフ連鎖に対する解析. まず, 仮定の χ(0) = µ(0) より ( ) (T ) ) χw − µ(T = χ(T ) P 0 − χ(0) P T w. 証明.. T −1 ( ∑. T −1 ∑. ). T ≥ 0 と γ (0 < γ < 1/2) に対し
(11)
(12) 2(1 − γ) πw
(13) (T ) )
(14) τ (γ) ∆
(15) χw − µ(T w
(16) ≤ 1 − 2γ πmin. (10). が成り立つ. 定理 4.2 に γ = 1/4 を代入し, 総トークン数 M で両辺を 割ることで定理 3.2 が直ちに得られる.. 4.
(17) Vol.2014-AL-149 No.4 2014/9/12. 情報処理学会研究報告 IPSJ SIG Technical Report. 証明.. 補題 4.1 と観察 3.1 より,
(18)
(19)
(20) (T ) )
(21)
(22) χw − µ(T w
(23). ≤. T −1 ∑. 5. 高速混交する連鎖に対する応用 本章ではいくつかの組合せ構造 (#P 完全問題) の一様サ.
(24)
(25) ∑ ∑
(26)
(27)
(28)
(29)
(30) T −t−1 (t) − χ(t) − πw
(31)
(32) Zv,u v Pv,u
(33) Pu,w. t=0 u∈V v∈N (u). ≤. T −1 ∑. ∑ ∑
(34)
(35) T −t−1
(36) Pu,w − πw
(37). =. ∑.
(38) t
(39) δ(u)
(40) Pu,w − πw
(41). (11). t=0 u∈V. が成り立つ. さらに P は可逆であるため, 任意の w, u ∈ V t に対し Pu,w =. (11) =. T −1 ∑. πw t πu Pw,u. ∑. t=0 u∈V. ≤ ∆. 介する.. 5.1 0-1 ナップサック問題の解集合. t=0 u∈V v∈N (u) T −1 ∑. ンプリングに対する多項式時間決定的サンプラーの例を紹. が成り立つ. 従って. 0-1 ナップサック問題の解集合は入力 a ∈ Rn>0 と b ∈ R>0 ∑n に対し, ΩKna = {x ∈ {0, 1}n | i=1 ai xi ≤ b} で定義され る. 今, ΩKna 上の遷移確率行列 PKna ∈ R|ΩKna |×|ΩKna | を任 意の x, y ∈ ΩKna に対し 1/2n. PKna (x, y) =.
(42)
(43)
(44) πw ( t )
(45)
(46) δ(u)
(47) Pw,u − πu
(48)
(49) πu. 1 − |NKna (x)|/2n. 0. (if y ∈ NKna (x)) (if y = x) (otherwise). と定義する. ここで NKna (x) = {y ∈ ΩKna | ∥x − y∥1 = 1}. T −1
(50) πw ∑ ∑
(51)
(52) t Pw,u − πu
(53) πmin t=0. とする. PKna は対称行列であるため, PKna の定常分布. u∈V. は ΩKna 上の一様分布になることに注意する. Morris と. T −1 ( t ) πw ∑ = 2∆ Dtv Pw,· ,π πmin t=0. (12). Sinclair [13] は PKna に対し以下の定理を示した. 定理 5.1. [13] PKna の混交時間 τ (γ) は任意の α > 0, γ > 0. ∑. t − が成り立つ. 最後の等式は総変動距離の定義 u∈V |Pw,u ( t ) πu | = 2Dtv Pw,· , π から成り立つ. ここで命題 2.1 より, 以. に対し τ (γ) = O(n 2 +α log γ −1 ) を満たす. 9. PKna で定義されるマルコフ連鎖に対し, 決定的サンプ ラーは以下のように設計される.. 下の補題を得る.. アルゴリズム 1. 補題 4.3. 任意の v ∈ V , T > 0 と γ (0 < γ < 1/2) に対し, T −1 ∑ t=0. Step 0. 各トークン i = 1, . . . , M に対し W 0 [i] := 0 とおく. /* W t [i] は ΩKna 上で時刻 t にトークン i のいる場所. ( t ) 1−γ Dtv Pv,· ,π ≤ τ (γ) 1 − 2γ. を保持している. */ Step 1. For (t = 0 to T − 1){ (t). (a). リスト Sx := {i ∈ {1, . . . , M } | W t [i] = x} を,. が成り立つ.. (t). 証明.. (. Sx ̸= ∅ である各 x ∈ ΩKna に対し作成する.. ). (t). 意の t ≥ 0 に対し h(t) ≤ 1 が定義 (2) より成り立つことに. を (4) に従い隣接点に遷移させ, W t+1 [i] を更新する.. }. 注意する. 命題 2.1 より, T −1 ∑. (. ). t Dtv Pw,· ,π =. t=0. =. ℓ=0. ∑. h(k) +. 定理 5.2. 任意の ε (0 < ε < 1) に対し, 適切な定数 c1 , c2 と. h(t). α を用い M := c1 n 2 +α ε−1 , T := c2 n 2 +α log ε−1 とする. 11. t=0. ∞ τ (γ)−1 ∑ ∑ ℓ=1. τ (γ)−1. k=0. Step 2. 各 i = 1, . . . , M に対し W T [i] を出力する.. このとき, アルゴリズム 1 は ( ) Dpw χ e(T ) , π ≤ ε. k=0. ∑. k=0. ≤. h(t) ≤. ∞ ∑. h(ℓ· τ (γ) + k). τ (γ)−1. =. T −1 ∑ t=0. ∞ τ (γ)−1 ∑ ∑. 1+. h(ℓ· τ (γ) + k). k=0. 2. ℓ. (2γ) = τ (γ) +. ∞ ∑ ℓ=1. γ 1−γ = τ (γ) + τ (γ) = τ (γ) 1 − 2γ 1 − 2γ が成り立ち, 題意を得る.. 1 ℓ τ (γ) (2γ) 2. (13). で π は ΩKna の一様分布を表す. また, アルゴリズム 1 の計 算時間は. O(T M log(M ) n poly(log a, log b)) = O∗ (n11+2α ε−1 ) である. ここで O∗ は poly log の項を無視する上界を表す. 証明.. 従って (12) と補題 4.3 より定理 4.2 を得る.. c 2014 Information Processing Society of Japan ⃝. 9. を満たす ΩKna 上の M 個のトークン配置を出力する. ここ. k=0. ∞ τ (γ)−1 ∑ ∑ 1 ℓ=1. (t). (b). Sx ̸= ∅ である各 x ∈ ΩKna に対し Sx 中のトークン. t 簡単のため h(t) = Dtv Pw,· , π とおく. このとき任. アルゴリズム 1 の各ステップでの計算時間を確認. する. Step 0 では M 個のトークンを 0 ∈ ΩKna にセット. 5.
(54) Vol.2014-AL-149 No.4 2014/9/12. 情報処理学会研究報告 IPSJ SIG Technical Report. するため, O(M n) 時間を要する. Step 1(a) では ΩKna 上. り高速混交するマルコフ連鎖が設計されている. 本章では. の M 個のトークン配置 χ(t) を構成する. 具体的には少. グラフ中の全てのマッチングからのサンプリングを扱う.. なくとも 1 つはトークンが存在している v ∈ ΩKna に対. なお, 2 部グラフの完全マッチングの数え上げはパーマネ. しリストを構成するが, ここでトークン数は M であるた. ントと関係しており, これもまた#P 完全であることが知. め, W t [i] (i = 1, . . . , M ) を ΩKna の辞書順にヒープすれば. られ, Jerrum, Sinclair, Vigoda [11] がアニーリングを用いた. O(M log(M ) n) 時間で Step 1(a) を実行できる. Step 1(b) で. MCMC 法に基づく FPRAS を設計している. 我々のアルゴ. は 3.1 章で記述したアルゴリズムに従ってトークンの再配. リズムを 2 部グラフの完全マッチングに適用するにはいく. 置を行う. これには x の隣接点を判定しトークンを遷移さ. つかの入力グラフに対する仮定が必要となる ( [10, 11] 参. せるのに O(n poly(log a, log b)) 時間を要する. なお, アルゴ. 照).. リズム中で一度 x の隣接点を判定し終えたら, ロータールー ターのようにトークンを遷移させれば. (t) O(n χx ). で計算が. 可能である. アルゴリズムでは Step 1 を T 回繰り返し行う ため, 計算時間の合計は O(T M log(M ) n poly(log a, log b)) となり, (13) は系 3.3 より明らかである. 従って題意が示さ. H = (U, F ) を任意の無向グラフ, |U | = n, |F | = m とす る. H のマッチング M とは, M ⊆ F であり, M のどの相 異なる 2 辺も頂点を共有しないものをいう. ここで, def.. ΩMat = {M ⊆ E | M は H のマッチング } と 定 義 す る.. れた.. |ΩMat | の 計 算 は#P 完 全 で あ る こ と が. 示 さ れ て い る. よ う に 定 義 す る.. 5.2 半順序集合の線形順序拡大 S = {1, 2, . . . , n} とし, Q = (S, ⪯) を S 上の半順序関 係とする. Q の線形順序拡大とは, Q を満たす全順序関係. X = (S, ⊑) である. 即ち, 全ての i ⪯ j である i, j ∈ S は i ⊑ j を満たす. ΩLin を Q の全ての線形順序拡大の集合 とする. 今, ある線形順序拡大のペア X, X ′ ∈ ΩLin に対 し, xp = x′p+1 , xp+1 = x′p , かつ任意の i ̸= p, p + 1 に対し. xi = x′i ならば X ∼p X ′ (p ∈ {1, . . . , n}) と書くこととす る. 即ち, X ∼p X ′ ならば. X ′ = (x1 , x2 , . . . , xp−1 , xp+1 , xp , xp+2 , . . . , xn ) こ こ で 任 意 の X, X ′ ∈ ΩLin に 対 し PLin ∈. R|ΩLin |×|ΩLin | を F (p)/2 ∑ ′ PLin (X, X ) = 1 − I∈NLin (X) PLin (X, I) 0. (if X ′ ∼p X) (if X ′ = X) (otherwise). と定義する. ここで NLin (X) = {Y ∈ ΩLin | X ∼p Y (p ∈. {1, . . . , n − 1})} であり, また F (p) =. ΩMat 上 の マ ル コ フ 連 鎖 を 以 下 の ま ず, E(M) = {e = {u, v} |. e∈ / M かつ u, v は共に M の辺に接する } を定義する. こ のとき, 任意の e = {u, v} ∈ / E(M) に対し, M−e (if e ∈ M) M + e (if u, v がどちらも M の辺と M(e) = 接していない) ′ M + e − e (if u, v のどちらかが e′ ∈ M と接している). と定義し, N (M) = {M(e) | e ∈ / E(M)} とする. このとき,. X = (x1 , x2 , . . . , xp−1 , xp , xp+1 , xp+2 , . . . , xn ). で あ る.. (14). p(n−p) 1 3 6 (n −n). 任意の M, M′ ∈ ΩMat に対して, 1/2m ∑ ′ PM,M = 1 − X∈N (M) PM,X 0. (if M′ ∈ N (M)) (if M′ = M) (15) (その他). と定義する. Jerrum と Sinclar [10] によって, 以下の定理が 示されている. 定理 5.4. [10] (15) で定義される P は ΩMat 上で既約かつ 一様分布に収束する. そして, τ (γ) ≤ 4mn(n ln n + ln γ −1 ) が任意の γ > 0 に対して成り立つ.. とする. PLin. PMat に対し, 5.1 章の 0-1 ナップサック解と同様に決定. はエルゴード的かつ可逆であり, 定常分布は ΩLin 上の一様. 的サンプリングアルゴリズムを構築することが出来, 計算. 分布となる [3]. また, Bubley and Dyer [3] は以下の定理を. 時間は O∗ (m4 n4 ε−1 ) となる. 詳細は [15] は参照されたい.. 示した. 定理 5.3. [3] PLin の混交時間 τ (γ) は任意の γ > 0 に対し ( ) τ (γ) = O n3 log nγ −1 を満たす.. 6. まとめ 本稿では決定的サンプリングアルゴリズムの提案を行い,. PLin に対し, 5.1 章の 0-1 ナップサック解と同様に決定的. 頂点誤差の上界 Dpw (e χ(t) , µ e(t) ) を与えた. またこの上界を. サンプリングアルゴリズムを構築することが出来, 計算時. 用い, 0-1 ナップサック解、線形順序拡大, マッチングなど. ∗. 8 −1. 間は O (n ε. ) となる. 詳細は [15] は参照されたい.. いくつかの組合せ構造 (#P 完全問題) 上の一様サンプリン グに対する 多項式時間決定的サンプリングアルゴリズムを. 5.3 グラフ中のマッチング グラフ中のマッチングを数え上げる問題は#P 完全であ ることが知られている. また, Jerrum と Sinclair [10] によ. c 2014 Information Processing Society of Japan ⃝. 設計した. 上界の πmax /πmin の項の改善, また決定的サン プラーに基づく#P 完全問題に対する多項式時間近似数え 上げアルゴリズムの設計が今後の課題となる.. 6.
(55) 情報処理学会研究報告 IPSJ SIG Technical Report. Vol.2014-AL-149 No.4 2014/9/12. 参考文献 [1]. [2] [3] [4]. [5]. [6]. [7]. [8]. [9]. [10]. [11]. [12] [13]. [14]. [15]. H. Akbari and P. Berenbrink, Parallel rotor walks on finite graphs and applications in discrete load balancing, Proc. SPAA 2013, 186–195. O. Angel, A.E. Holroyd, J. Martin, and J. Propp, Discrete low discrepancy sequences, arXiv:0910.1077. R. Bubley and M. Dyer, Faster random generation of linear extensions, Discrete Mathematics, 201 (1999), 81–88. 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. B. Doerr and T. Friedrich, Deterministic random walks on the two-dimensional grid, Combinatorics, Probability and Computing, 18 (2009), 123–144. P. Gopalan, A. Klivans, R. Meka, D. Stefankovic, S. Vempala, and E. Vigoda, An FPTAS for #knapsack and related counting problems, Proc. FOCS 2011, 817–826. 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. M. Jerrum and A. Sinclair, Approximation algorithms for NP-hard problems, D.S. Hochbaum ed., The Markov chain Monte Carlo method: an approach to approximate counting and integration, PWS Publishing, 1996. M. Jerrum, A. Sinclair, and E. Vigoda, A polynomial-time approximation algorithm for the permanent of a matrix with nonnegative entries, Journal of the ACM, 51 (2004), 671– 697. S. Kijima, K. Koga, and K. Makino, Deterministic random walks on finite graphs, Proc. ANALCO 2012, 16–25. B. Morris and A. Sinclair, Random walks on truncated cubes and sampling 0-1 knapsack solutions, SIAM Journal on Computing, 34 (2004), 195–226. 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.. c 2014 Information Processing Society of Japan ⃝. 7.
(56)
関連したドキュメント
Therefore, we presuppose that the random walk contains a sufficiently large number of steps, so that there can be an equivalent to finite partial sums of both sums in (2.13)
DRAGOMIR, A converse result for Jensen’s discrete inequality via Grüss’ inequality and applications in information theory, Analele Univ.
The formation of unstaggered and staggered stationary localized states (SLSs) in IN-DNLS is studied here using a discrete variational method.. The func- tional form of
Nonlinear systems of the form 1.1 arise in many applications such as the discrete models of steady-state equations of reaction–diffusion equations see 1–6, the discrete analogue of
All three problems (1*, 2*.1 2*.2) are open; there are conjectures which would provide complete answers to these problems and some partial results supporting these conjectures
Matroid intersection theorem (Edmonds) Discrete separation (Frank). Fenchel-type
RIMS Summer School (COSS 2018), Kyoto, July 2018.. Discrete Convex
This can be seen even more clearly from the discrete transforms: the famous uncertainty principles of Balian-Low for the discrete Gabor transform [Bali81, Daub90] and Battle for
