ブートストラップパーコレーション

統計力学において、ブートストラップパーコレーションは、格子または他の空間からランダムな初期構成のアクティブセルを選択し、次にアクティブな近傍が少ないセルをアクティブセットから順次削除してシステムが安定するまで行うパーコレーションプロセスです。この削除が発生する順序は、最終的な安定状態に影響を与えません。^[1]^[2]

アクティブセルが生き残るために必要なアクティブ近傍のしきい値が十分に高い場合（格子によって異なります）、唯一の安定状態は、アクティブセルがない状態、またはアクティブセルのすべてのクラスターが無限に大きい状態です。たとえば、フォンノイマン近傍を持つ正方格子では、クラスターセルごとに少なくとも2つのアクティブ近傍を持つ有限のクラスターがありますが、3つまたは4つのアクティブ近傍が必要な場合は、安定したクラスターは無限でなければなりません。 ^[1]アクティブであり続けるために3つのアクティブ近傍が必要であるため、無限クラスターは3つまたは4つの可能な基本方向に無限に広がる必要があり、そこに含まれる有限の穴は必然的に長方形になります。この場合、臨界確率は1であり、つまり、初期状態で各セルがアクティブである確率が1未満の場合、ほぼ確実に無限クラスターは存在しません。^[3]初期状態が $n$ $\times$ $n$ の正方形を除くすべての場所でアクティブで、その正方形内の各行と各列の1つのセルが非アクティブである場合、これらの単一セルの空隙は、非アクティブセルが分離可能な順列のパターンを持つ場合に限り、正方形全体を覆う空隙を形成するように結合します。^[4]より高い次元では、任意のしきい値に対して、同様の臨界確率があり、それ以下ではすべてのセルがほぼ確実に非アクティブになり、それを超えるといくつかのクラスターがほぼ確実に生き残ります。^[5]

ブートストラップパーコレーションは、コンウェイのライフゲームに似たセルオートマトンとして解釈することができ、生きているセルは生きている近傍のセルが少なすぎると死にます。しかし、コンウェイのライフゲームとは異なり、死んだセルは二度と生き返ることはありません。^[6]^[7]また、非アクティブなセルは感染しているとみなされ、感染した近傍のセルが多すぎるアクティブなセルは自分自身も感染するという伝染病モデルとして見ることもできます。 ^[5]初期クラスターの一部のセルが生き残ることを可能にする最小の閾値は、その隣接グラフの退化と呼ばれ、閾値kで生き残るクラスターの残骸はこのグラフのkコアと呼ばれます。^[8]

ブートストラップパーコレーションの応用例の1つは、分散コンピューティングのフォールトトレランスの研究です。大規模なプロセッサグリッド内の一部のプロセッサが故障（非アクティブ化）した場合、残りのネットワークの高い接続性を維持するために、アクティブな隣接プロセッサが少なすぎる他のプロセッサも非アクティブ化する必要がある可能性があります。ブートストラップパーコレーションの分析は、システムが許容できる障害確率を決定するために使用できます。^[9]

参考文献

^ ab Chalupa, J.; Leath, PL; Reich, GR (1979)、「ベーテ格子上のブートストラップパーコレーション」、Journal of Physics C: Solid State Physics、12 (1): L31–L35、Bibcode :1979JPhC...12L..31C、doi :10.1088/0022-3719/12/1/008。
^ アドラー、ジョアン（1991）、「ブートストラップパーコレーション」、Physica A：統計力学とその応用、171（3）：453–470、Bibcode：1991PhyA..171..453A、doi：10.1016/0378-4371（91）90295-n。
^ van Enter, Aernout CD (1987)、「Straley のブートストラップパーコレーションの証明」、Journal of Statistical Physics、48 (3–4): 943–945、Bibcode :1987JSP....48..943V、doi :10.1007/BF01019705、MR 0914911、S2CID 119825786。
^ シャピロ、ルイス; スティーブンス、アーサー B. (1991)、「ブートストラップパーコレーション、シュレーダー数、およびNキング問題」、SIAM 離散数学ジャーナル、4 (2): 275–280、doi :10.1137/0404025、MR 1093199。
^ ab Balogh, József; Bollobás, Béla ; Duminil-Copin, Hugo; Morris, Robert (2012)、「すべての次元におけるブートストラップパーコレーションの鋭い閾値」、Transactions of the American Mathematical Society、364 (5): 2667–2701、arXiv : 1010.3326、doi :10.1090/S0002-9947-2011-05552-2、MR 2888224、S2CID 2708046。
^ Aizenman, M.; Lebowitz, JL (1988)、「ブートストラップパーコレーションにおけるメタ安定性の影響」、Journal of Physics A: Mathematical and General、21 (19): 3801–3813、Bibcode :1988JPhA...21.3801A、doi :10.1088/0305-4470/21/19/017。
^ Schonmann, Roberto H. (1992)、「ブートストラップパーコレーションに関連するいくつかのセルラーオートマトンの動作について」、Annals of Probability、20 (1): 174–193、doi : 10.1214/aop/1176989923、JSTOR 2244552、MR 1143417。
^ Gottschau, Marinus (2016)、退化グラフ上のブートストラップパーコレーション、arXiv : 1605.07002、Bibcode :2016arXiv160507002G。
^ カークパトリック、スコット; ウィルケ、ウィンフリード W.; ガーナー、ロバート B.; ヒュールス、ハラルド (2002)、「高密度ストレージアレイのパーコレーション」、Physica A: 統計力学とその応用、314 (1–4): 220–229、Bibcode :2002PhyA..314..220K、doi :10.1016/S0378-4371(02)01153-6、MR 1961703。

[clr-1] Chalupa, J.; Leath, PL; Reich, GR (1979)、「ベーテ格子上のブートストラップパーコレーション」、Journal of Physics C: Solid State Physics、12 (1): L31–L35、Bibcode :1979JPhC...12L..31C、doi :10.1088/0022-3719/12/1/008。

[2] アドラー、ジョアン（1991）、「ブートストラップパーコレーション」、Physica A：統計力学とその応用、171（3）：453–470、Bibcode：1991PhyA..171..453A、doi：10.1016/0378-4371（91）90295-n。

[3] van Enter, Aernout CD (1987)、「Straley のブートストラップパーコレーションの証明」、Journal of Statistical Physics、48 (3–4): 943–945、Bibcode :1987JSP....48..943V、doi :10.1007/BF01019705、MR 0914911、S2CID 119825786。

[4] シャピロ、ルイス; スティーブンス、アーサー B. (1991)、「ブートストラップパーコレーション、シュレーダー数、およびNキング問題」、SIAM 離散数学ジャーナル、4 (2): 275–280、doi :10.1137/0404025、MR 1093199。

[bbdm-5] Balogh, József; Bollobás, Béla ; Duminil-Copin, Hugo; Morris, Robert (2012)、「すべての次元におけるブートストラップパーコレーションの鋭い閾値」、Transactions of the American Mathematical Society、364 (5): 2667–2701、arXiv : 1010.3326、doi :10.1090/S0002-9947-2011-05552-2、MR 2888224、S2CID 2708046。

[6] Aizenman, M.; Lebowitz, JL (1988)、「ブートストラップパーコレーションにおけるメタ安定性の影響」、Journal of Physics A: Mathematical and General、21 (19): 3801–3813、Bibcode :1988JPhA...21.3801A、doi :10.1088/0305-4470/21/19/017。

[7] Schonmann, Roberto H. (1992)、「ブートストラップパーコレーションに関連するいくつかのセルラーオートマトンの動作について」、Annals of Probability、20 (1): 174–193、doi : 10.1214/aop/1176989923、JSTOR 2244552、MR 1143417。

[8] Gottschau, Marinus (2016)、退化グラフ上のブートストラップパーコレーション、arXiv : 1605.07002、Bibcode :2016arXiv160507002G。

[9] カークパトリック、スコット; ウィルケ、ウィンフリード W.; ガーナー、ロバート B.; ヒュールス、ハラルド (2002)、「高密度ストレージアレイのパーコレーション」、Physica A: 統計力学とその応用、314 (1–4): 220–229、Bibcode :2002PhyA..314..220K、doi :10.1016/S0378-4371(02)01153-6、MR 1961703。