シュタイナー三項系のサンプリングとマルコフ連鎖の高速混合
4
0
0
全文
(2) Vol.2018-AL-166 No.7 2018/1/29. 情報処理学会研究報告 IPSJ SIG Technical Report. を変更することで行う．状態 M について，i 番目のブロッ. Algorithm 1: Decide next state M CST S 1. クに含まれる a を b に書き換えた状態を返す関数を. if w.p. 1/2 then. 2. i ← M からブロックをランダムに選択;. 3. a ← mi から要素をランダムに選択;. 4. b ← V から要素をランダムに選択;. 5. M ′ ← update(M, i, a, b) if M ′ ∈ Ξ′n then. update(M, i, a, b) = (m1 , m2 , ..., (mi \ a ∪ b), ..., mm ) (3) とし，1 ステップの状態遷移は Algorithm1 に記載する．. return M ′ ;. 6. 3.3 定常分布 7. return M ;. 本節では，以下の定理を証明する． 定理 3.. 2.2 ラベル付き STS. πM = 1/|Θn ∗ (I)| で定義される確率分布 π は. M CST S の定常分布である．. ラベル付き STS とは，ブロック間に順序があるとした STS の事である．すなわちラベル付き STS T = (t1 , t2 , ..., tm ) ∈ ( V )m は {t1 , ..., tm } ∈ Ξn を満たす． 3. 定 義 1. ラ ベ ル 付 き STS 全 体 の 集 合 を Ξn ∗ = {T = ( ) (t1 , t2 , ..., tm )|ti ∈ V3 , ζ(T ) ∈ Ξn } と す る ．た だ し ， ∪ ζ(T ) = i∈{1,...,m} {ti } とする． 任意のラベル付き STS I = (i1 , ..., im ) ∈ Ξn ∗ について，. Ξn ∗ (I) = {T ∈ Ξn ∗ |∀j ∈ {1, ..., m}|ij ∩ tj | ≥ 2}. (2). 補題 4. M CST S が状態 M から M ′ (̸= M ) に遷移する確 率 pM M ′ が 0 でないとき，pM M ′ = 証明.. Algorithm1 の手順ごとに M から M ′ に遷移する確. 率を求める．. • 手順 1 M にとどまらない確率 1/2 • 手順 2 M ′ に遷移するブロックが選択される確率 ′. • 手順 3 M に遷移する要素が選択される確率 • 手順 4 M ′ に遷移する要素が選択される確率 したがって以上の積から，pM M ′ =. と定義する． 補題 2. 写像 ζ : Ξn ∗ → Ξn は Ξn ∗ (I) から Ξn への全射で ある． 証明.. 定理 1 より，2 つの STS からなる 2 部グラフには. 必ず完全マッチングが存在する．これは，各ブロックに一 つ存在する，マッチングに使用されていない頂点を変更す ることで，任意の STS に遷移できることを示している．し たがって，あるラベル付き STS I について，各ブロック の頂点を高々一つ変更すれば任意の STS となるので，ζ は. Ξn ∗ (I) から Ξn への全射である． ただし，ζ は Ξn ∗ (I) から Ξn への単射ではない．Ξn か らの一様サンプリングを行うためには，Ξn ∗ (I) からの一様 ∗. 1 6nm. 1 m. 1 3 1 n. 1 6nm ．. 補題 5. 任意の M, M ′ について，詳細均衡条件 pM M ′ =. pM ′ M を満たす． 証明.. M と M ′ の関係に従って，場合分けを行う．M と. ′. M で 2 か所以上値が異なる場合，一度の update 関数の適用 によって遷移することはできないので，pM M ′ = pM ′ M = 0 である．また，M と M ′ で 1 か所のみ値が異なる場合，. M ′ = update(M, i, a, b) とすると M = update(M ′ , i, b, a) な の で ，4 よ り pM M ′ = pM ′ M =. 1 6nm ．以 上 よ り ，. p M M ′ = pM ′ M ． 補題 6. M CST S は既約である． 証明.. 任意の状態 T ′ から初期状態 I に遷移可能である. サンプリングを行った後，Ξn から Ξn (I) への単射である. ことを示す．任意の k ∈ {1, ..., m} について |ik ∩ t′k | ≥ 2. 関数を用いて，その妥当性を判定する必要がある．そのよ. より，各ブロック t′k に ik と異なる頂点 ik \ t′k が高々. うな関数の一例を付録 A に示す．. 一つ存在する．したがって，∀k ∈ {1, ..., m} について，. Mk = update(Mk−1 , k, t′k \ ik , ik \ t′k ) とすると，T ′ から I. 3. M CST S (I). への経路 {T ′ = M0 , M1 , ..., Mm = I} を得られる．各遷移. 本章では，マルコフ連鎖 M CST S (I) を定め，その極限分. において，Mk の j 番目のブロック mkj = ij となるので， この遷移によって Θn ∗ (I) に属さない状態に遷移すること. 布を議論する．. はない．したがって，任意の状態 T ′ から I に遷移するこ ∗. 3.1 状態空間 Θn (I) ∗. ′. M CST S (I) の状態空間は Θn (I) = {T ⊆ m, ∀k ∈. {1, ..., m}|ik ∩t′k |. (V ) 3. とが可能である． ′. ||T | =. ≥ 2} とする．明らかに Ξn ∗ (I) ⊂. Θn ∗ (I) である．. 補題 7. M CST S はエルゴード的である． 証明.. Algorithm1 の手順 1 より，自己遷移確率 pM M ≥. 1 2. であるため，M CST S は非周期的である．補題 6 より，. 3.2 状態遷移 M CST S の状態遷移は，現在の状態について 1 つの頂点 ⓒ 2018 Information Processing Society of Japan. M CST S は既約である．したがって，M CST S はエルゴー ド的である．. 2.
(3) Vol.2018-AL-166 No.7 2018/1/29. 情報処理学会研究報告 IPSJ SIG Technical Report. たがって，補題が成り立つ．. Algorithm 2: γXY. {x1 , x2 , ..., xm }, Y. 1. j ← 0; . 2. M0 ← X; . {y1 , y2 , ..., ym } ∈ Θn (I) に つ い て ，γXY は X か ら. 3. for k ∈ {1, ..., n} do. Y への経路である．. 補 題. Mj+1 ← update(Mj , ik \ yk , ik \ mk ); j + +;. 5. Mj+1 ← update(Mj , xk \ yk , yk \ mk ); j + +;. 7. =. 証明.. |mk ∩ yk | = 1 より，|ik ∩ yk \ mk | = 1. したがって，. ik \ mk ∈ yk ．また，ik \ yk ∈ / yk なので，|mk ∩ yk | = 1 で. if |mk ∩ yk | = 2 then. 6. =. ∗. if |mk ∩ yk | = 1 then. 4. 12. 任 意 の X. ある時，4 行目の遷移によって |mk ∩ yk | = 2 となる．さら に，yk \ xk ∈ yk ，xk \ yk ∈ / yk より，|mk ∩ yk | = 2 である 時，6 行目の遷移によって |mk ∩ yk | = 3 となる．したがっ. エルゴード的で詳細均衡条件を満たすことから ([3] 参 照)，補題 5, 補題 7 より定理 3 が示される．. 補題 11 と補題 12 から，γXY は X から Y への正準経路 となっている．. 3.4 Θn ∗ (I) と Ξn の関係 M CST S (I) の状態空間の大きさ |Θn ∗ (I)| は，|Ξn | の関 係について言及しておく． ( )n2 /6 |Ξn | 1 定理 8. |Θn ∗ (I)| > 5 式 (1) より，|Ξn | ≥ ∗. (. ∈. γXY } と し て ，写 像 ηM M ′. :. cp(M, M ) → Ξn を， ) n62. n 3. e2 3 2. ．また，Θn ∗ (I) の定. よいのは高々一つの頂点である事，その値は高々 n 通りで あることから，|Θn ∗ (I)| < 3m nm < (3n)n )n2 /6 ( |Ξn | 1 5 |Θn ∗ (I)| >. 2. /6. ．以上より，. 3 2 e2. 4. M CST S (I) の混合時間 本章では，M CST S (I) の混合時間について以下の定理を 示す．. ηM M ′ (X, Y ) =. ∪. (xk ∩yk )∪((xk ⊕yk )\mk ) (4). k∈{1,...,m}. と定義する． 補題 13. ηM M ′ は単射である． 証明.. mk , m′k , ηM M ′ (X, Y )k から，xk , yk を復元できるこ. とを示す．簡単のため，ηk = ηM M ′ (X, Y )k とする．ηM M ′ の定義より，xk ∩ yk = ηk ∩ mk ，xk ⊕ yk = ηk ⊕ mk ．し たがって，ηk ⊕ mk の各頂点が xk , yk のどちらに属するか を判別できればよい．. 定理 9. M CST S (I) の混合時間 τ (δ) = O(n6 (n2 log n +. log δ. 中 に M M ′ を 含 む よ う な X, Y の 集 合 を cp(M, M ′ ) = ′. 義より，T ∈ Θn (I) の各ブロックについて，I と異なって. −1. γXY の 集 合 Γ の 混 雑 度 ρ(Γ) を 計 算 す る ．正 準 経 路 {(X, Y )|(M, M ′ ). 3 2 e2. 証明.. て，|mk ∩ yk | がどのような値でも，mk = yk となる．. まず，Algorithm2 が操作するブロックの順番は決まって いるので，M, M ′ 間で操作されていないブロックに関して. )). まず，混合時間の見積もりのために必要な補題を示す．. は，操作済みであるかの判定が可能である．M, M ′ 間で操. 補 題 10. X = (x1 , x2 , ..., xm ), Y = (y1 , y2 , ..., ym ) ∈. 作されているブロックについては，場合分けして考える．. Θn ∗ (I) について，∀k ∈ {1, ..., n}, |xk ∩ yk | ≥ 1 証明.. Θn ∗ (I) の 定 義 よ り ，∀k ∈ {1, ..., n}|ik ∩ xk | ≥. 2．∀k ∈ {1, ..., n}|xk ∩ yk | = 0 と 仮 定 す る と ，∀k ∈ {1, ..., n}|ik ∩ yk | ≤ 1 となり，Θn ∗ (I) の定義と矛盾す る．したがって，補題が成り立つ． ∗. |mk ∩ ηk | = 2 である場合は，M, M ′ 間で操作されて いる頂点以外，そのブロックで操作されるものはない．. |mk ∩ ηk | = 1 である場合は，2 つの頂点を操作する必要が ある．このブロックは，Algorithm 2 における 4 行目と 6 行目両方で遷移を行うことになるが，4 行目では除外・追 加する頂点共に ik に属するのに対し (図 1)，6 行目の操作. ∗. では属していない (図 2)．この性質を用いて，ηk ⊕ mk に. M0 , M1 , ..., Mk = Y を Algorithm 2 のように構成する．. 属しているが，M, M ′ 間で操作対象となっていない頂点が. 補題 11. γXY に従ったとき，遷移する全ての状態は Θn ∗ (I). 操作済みであるかどうかの判定が可能である．. X ∈ Θn (I) から Y ∈ Θn (I) への正準経路 γXY : X =. に属する． 証明.. まず，4 行目の遷移については，除外する頂点，追. 加する頂点共に ik に属するので，mk ∩ ii に属する頂点が 減少することはない．また 5 行目の条件より，xk と yk は 異なる頂点を一つ有し，6 行目の遷移によって mk = yk と なることがわかる．|ik ∩ yk | ≥ 2 より，|ik ∩ mk | ≥ 2．し ⓒ 2018 Information Processing Society of Japan. 以上の議論より全ての頂点が操作済みであるか否かを判 定できるので，mk に属し操作済みでない頂点と，ηk に属 し操作済みである頂点は xk に，その他の頂点は yk に属 することがわかる．したがって，mk , m′k , ηM M ′ (X, Y )k か ら，xk , yk を復元できる． 補題 14. ρ(Γ) = O(n3 ). 3.
(4) Vol.2018-AL-166 No.7 2018/1/29. 情報処理学会研究報告 IPSJ SIG Technical Report. Algorithm 3: get canonical stateI (T ) 1. mat ← f ind matching(ζ(I), T ). 2. for k ∈ 1, 2, ..., m do t∗k ← f ind counterpart(mat, ik );. 3. 図 1: x, y の復元 1 4. return {t∗1 , t∗2 , ..., t∗m };. 付. 録. 付録 A Ξn から Ξn ∗ (I) への単射. 図 2: x, y の復元 2. Ξn から Ξn ∗ (I) への単射である関数の一例を Algorithm 証明.. 1 ρ(Γ) = max (M,M ′ )∈E(Ωmn ) πM pM M ′ =. 1. max. (M,M ′ )∈E(Ωmn ). 1 1 |Θn | 6nm. ∑. 1 1 |Θn | 6nm. 2 部グラフにおける，完全マッチングを決定的に一つ探索. する関数であり，f ind counterpart はあるマッチングにお 1 けるある頂点の片割れを探索する関数である． πη (X,Y ) |Θn | M M ′ ′ 補題 16. T ∗ = get canonical stateI (T ) とすると，T = (X,Y )∈cp(M,M ). ∑. (5) 1. max. (M,M ′ )∈E(Ωmn ). πX πY. (X,Y )∈cp(M,M ′ ). 補題 13 より，. =. 3 に示す．ここで，find matching は 2 つの STS からなる. 1 |Θn |. ζ(T ∗ ) 証明.. ∪. (右辺) = ζ(T ∗ ) =. n2 (n − 1) = 2 3. =. = O(n ). ∪. t∗k. i∈{1,...,m}. f ind counterpart(mat, ik ). i∈{1,...,m}. = Jerrum と Sinclair は，混雑度と混合時間の関係につい. ∪. tk = T = (左辺). i∈{1,...,m}. て，以下を示している ([3] 参照)． 定理 15. Ω を状態空間とするマルコフ連鎖の混合時間. τ (δ) = O(ρ(Γ)2 (log |Ω| + log δ −1 ))． 以上より，M CST S (i) の混合時間の上界が示せる．. 定理 17. get canonical stateI (T ) は Ξn から Ξn ∗ (I) への 単射である． 証明.. 定理 9 の証明.. τ (δ) = O(ρ(Γ)2 log |Ω| + log δ −1 ) 2. = O(n6 (. n log n + log δ −1 )) 6. 任 意 の T1 , T2. ∈. Ξn (T1. ̸=. T2 ) に つ い て ，. get canonical stateI (T1 ) = get canonical stateI (T2 ) = T ∗ と仮定する．この時，補題 16 より，T1 = T2 = ζ(T ∗ )． これは仮定と矛盾するので，get canonical stateI は単射 である．. = O(n6 (n2 log n + log δ −1 )) 参考文献. 5. おわりに 本研究では，STS の一様サンプリングを行うためのマル. [1] [2]. コフ連鎖を示し，大きな頂点数に対しても既約性を保証し， 高速混合であることを示した．今後の課題は，STS の数に. [3]. 対して指数関数的に大きい状態空間の縮小と，混合時間の 短縮である．. 謝辞. [4]. [5]. 本研究は JST さきがけ JPMJPR16E4 の支援を受けて いる．. ⓒ 2018 Information Processing Society of Japan. [6]. P. J. Cameron, A Markov chain for Steiner triple systems, Working document, 2002. ¨ P. Kaski, V. M¨akinen, P. R. J. Ostergard, The cycle switching graph of the Steiner triple systems of order 19 is connected, Graphs and Combinatorics, 27:539, 2011. D．A．Levin, Y．Peres, E．L．Wilmer, Markov Chains and Mixing Times, American Mathematical Soc, 2009． N. Linial and Z. Luria, Upper bounds on the number of Steiner triple systems and 1-factorizations, Random Struct. Alg. 43:399–406, 2013. V. D. Tonchev, and R. S. Weishaar, Steiner triple systems of order 15 and their codes. J. Stat. Plan. Inference 58, 207–216, 1997. M. R. Wilson, Nonisomorphic Steiner triple systems, Math. Z. 135, 303–313, 1974.. 4.
(5)
図
関連したドキュメント
The basic bound on the chromatic number of a graph of maximum degree ∆ is ∆ + 1 obtained by coloring the vertices greedily; Brooks theorem states that equality holds only for
By the algorithm in [1] for drawing framed link descriptions of branched covers of Seifert surfaces, a half circle should be drawn in each 1–handle, and then these eight half
The main purpose of this paper is to show, under the hypothesis of uniqueness of the maximizing probability, a Large Deviation Principle for a family of absolutely continuous
In Section 13, we discuss flagged Schur polynomials, vexillary and dominant permutations, and give a simple formula for the polynomials D w , for 312-avoiding permutations.. In
• In section 6, we used the average-free construction in Lemma 5.5 on the average- free Steiner triple systems of order 9n and on another set of 5-sparse Steiner triple sytems
Keywords and phrases: super-Brownian motion, interacting branching particle system, collision local time, competing species, measure-valued diffusion.. AMS Subject
modular proof of soundness using U-simulations.. & RIMS, Kyoto U.). Equivalence
It turns out that the symbol which is defined in a probabilistic way coincides with the analytic (in the sense of pseudo-differential operators) symbol for the class of Feller
