自己回避歩行

数学において、自己回避歩行( SAW ) とは、同じ点を複数回訪れない格子(格子パス)上の一連の動きのことです。これは、グラフ理論的概念であるパスの特殊なケースです。自己回避多角形( SAP ) は、格子上の閉じた自己回避歩行です。物理学者は、真実であると信じられ、数値シミュレーションによって強力に裏付けられている多くの推測を提示していますが、数学的観点から自己回避歩行について厳密にわかっていることはほとんどありません。

計算物理学では、自己回避ウォークとは、R ²またはR ³内の特定の数のノードを持つチェーンのようなパスであり、通常は固定ステップ長で、それ自体または別のウォークと交差しないという特性があります。SAW のシステムは、いわゆる排除体積条件を満たします。高次元では、SAW は通常のランダムウォークとほぼ同じように動作すると考えられています。

SAWとSAPは、タンパク質などの糸状およびループ状分子の位相的および結び目理論的挙動のモデリングにおいて中心的な役割を果たします。実際、SAWは、溶媒やポリマー などの鎖状実体の実際の挙動をモデル化するために、化学者ポール・フローリー[ ^{1] [疑わしい–議論する]}によって最初に導入された可能性があります。これらの実体は、物理的な体積によって同じ空間点を複数占有することが禁止されています。

SAW はフラクタルです。たとえば、d = 2ではフラクタル次元は4/3 ですが、d = 3では5/3 に近く、d ≥ 4ではフラクタル次元は2です。この次元は、それを超えると排除体積が無視できる上限臨界次元と呼ばれます。排除体積条件を満たさない SAW は、SAW の拡大によって生じる明示的な表面形状をモデル化するために最近研究されました。 ^{[2] [説明が必要]}

SAW の特性は解析的に計算できないため、数値シミュレーションが使用されます。ピボット アルゴリズムは、nステップの自己回避ウォークの均一測度のマルコフ連鎖モンテカルロシミュレーションでよく使用される方法です。ピボット アルゴリズムは、自己回避ウォークを実行し、このウォーク上の点をランダムに選択し、n ステップ後のウォークに対称変換 (回転と反射) を適用して新しいウォークを作成することで機能します。

任意の格子における自己回避歩行の数を計算することは、一般的な計算問題である。現在のところ、厳密な近似法はあるものの、公式は知られていない。^{[3] [4]}

自己回避ウォークおよび統計物理モデル全般に関連する現象の 1 つに、普遍性の概念、つまり、マクロな観測量が格子の選択などのミクロな詳細から独立していることが挙げられます。普遍法則の推測に現れる重要な量の 1 つは、次のように定義される接続定数です。 c _{n が}nステップの自己回避ウォークの数を表すものとします。すべての( n + m )ステップの自己回避ウォークは、 nステップの自己回避ウォークとmステップの自己回避ウォークに分解できるため、 c _{n + m} ≤ c _n c _mとなります。したがって、シーケンス{log c _n }は劣加法であり、フェケテの補題を適用して、次の制限が存在することを示すことができます。

${\displaystyle \mu =\lim _{n\to \infty }c_{n}^{\frac {1}{n}}.}$

μは接続定数と呼ばれ、c _{n は}ウォークに選択された特定の格子に依存するため、 μも同様です。 μの正確な値は六方格子の場合のみ知られており、次の式に等しくなります。^[5]

${\displaystyle {\sqrt {2+{\sqrt {2}}}}.}}$

他の格子では、μは数値的に近似されているだけで、代数的数でさえないと考えられている。^[6]

${\displaystyle c_{n}\approx \mu ^{n}n^{\frac {11}{32}}}$

n → ∞として、μ は格子に依存しますが、べき乗補正は依存しません。言い換えると、この法則は普遍的であると信じられています。 ${\displaystyle n^{\frac {11}{32}}}$

自己回避ウォークはネットワーク理論の文脈でも研究されてきた。^[7]この文脈では、SAW を動的プロセスとして扱うのが通例であり、各タイムステップでウォーカーがネットワークの隣接ノード間をランダムにホップする。ウォークは、ウォーカーが行き止まりの状態に到達し、新たに訪問していないノードに進むことができなくなると終了する。最近、エルデシュ・レーニイネットワークでは、このように動的に成長する SAW のパス長の分布を解析的に計算でき、ゴンペルツ分布に従うことがわかった。^[8]任意のネットワークについて、ウォークのパス長の分布、未訪問ネットワークの次数分布、ノードへの初回到達時間分布は、一連の結合再帰方程式を解くことで得られる。^[9]

フルプレーンにおけるnステップの自己回避ウォークの均一測度について考えてみましょう。n → ∞の均一測度の限界が、無限のフルプレーンウォークの測度を誘導するかどうかは、現在のところ不明です。しかし、ハリー・ケステンは、半平面における自己回避ウォークに対してそのような測度が存在することを示しました。自己回避ウォークに関する重要な疑問の 1 つは、スケーリング限界の存在と共形不変性です。スケーリング限界とは、ウォークの長さが無限大になり、格子のメッシュがゼロになるときの限界です。自己回避ウォークのスケーリング限界は、パラメータκ = ⁠を持つシュラム・レーヴナー進化によって記述されると推測されています。8/3⁠ .

• 臨界現象 – 臨界点に関連する物理学
• ハミルトン経路 – グラフ内の各頂点を1回だけ訪れる経路
• ナイトツアー – チェス盤上に置かれた数学の問題
• ランダムウォーク – 多数のランダムなステップからパスを形成するプロセス
• スネーク – ビデオゲームのジャンル
• 普遍性 – 動的詳細に依存しないシステムの特性フォールバックとしてウィキデータの説明を表示するページ
• 空間充填曲線– すべて自己回避曲線です。
• 4 色定理- すべての 2D SAW には、4 色定理に従わなければならない部屋があります。

• OEISシーケンス A007764 (n × n グリッドの反対側の角を結ぶ交差しない (または自己回避する) ルーク パスの数) - N × Nグリッドの反対側の角を結ぶ自己回避パスの数 ( Nは0から 12)。N = 21 までの拡張リストも含まれます。
• Weisstein、Eric W.「自己回避歩行」。MathWorld。
• 2D 自己回避歩行の Java アプレット
• n 次元の正方格子上で SAW と拡張 FiberWalk をシミュレートするための汎用 Python 実装。
• ダイヤモンド立方体上で SAW を生成するための Norris ソフトウェア。