有限型のサブシフト

数学では、有限型のサブシフトは動的システムをモデル化するために使用され、特に記号力学とエルゴード理論の研究対象となっています。また、有限状態マシンによって実行されるすべての可能なシーケンスの集合も記述します。最も広く研究されているシフト空間は、有限型のサブシフトです。

有限型の（片側）シフトは、 のように文字 で構成できる、一方の端のみが無限であるすべてのシーケンスの集合です。有限型の（両側）シフトも同様ですが、両端が無限であるシーケンスで構成されます。 ${\displaystyle A,B,C}$${\displaystyle AAA\cdots ,ABAB\cdots ,\dots }$

サブシフトは、グラフ のような、これらの文字上の有向グラフによって定義できます。これは、連続する文字間の遷移がグラフで許可されているものだけであるシーケンスで構成されます。この例では、サブシフトは 3 つの片側シーケンスのみで構成されます: 。同様に、このグラフによって記述される両側サブシフトは、3 つの両側シーケンスのみで構成されます。 ${\displaystyle A\to B\to C\to A}$${\displaystyle ABCABC\cdots ,BCABCA\cdots ,CABCAB\cdots }$

同じ文字上の他の有向グラフは、他のサブシフトを生成します。たとえば、グラフに別の矢印を追加すると、3 つのシーケンスではなく、数え切れないほど無限の数のシーケンスを含むサブシフトが生成されます。 ${\displaystyle A\to C}$

マルコフ遷移行列と状態への不変分布が与えられれば、サブシフトの集合に確率測度を課すことができます。たとえば、不変分布 を持つ状態 上の左側に示されているマルコフ連鎖を考えてみましょう。 との区別を「忘れる」と、 上のサブシフトのこの空間を上のサブシフトの別の空間に投影し、この投影によって確率測度も 上のサブシフトの確率測度に投影されます。 ${\displaystyle A,B_{1},B_{2}}$${\displaystyle \pi =(2/7,4/7,1/7)}$${\displaystyle B_{1},B_{2}}$${\displaystyle A,B_{1},B_{2}}$${\displaystyle A,B}$${\displaystyle A,B}$

興味深いのは、 のサブシフト上の確率測度は、上のマルコフ連鎖によって生成されるのではなく、多重次数によっても生成されるわけではないということです。直感的に、これは の長いシーケンスを観察すると、 がますます確実になるためであり、これはシステムの観測可能な部分が無限過去の何かによって影響を受ける可能性があることを意味します。^{[1] [2]}${\displaystyle A,B}$${\displaystyle A,B}$${\displaystyle B^{n}}$${\displaystyle Pr(A|B^{n})\to {\frac {2}{3}}}$

逆に、6つのシンボル上のサブシフトの空間が存在し、それが2つのシンボル上のサブシフトに射影され、より小さいサブシフト上の任意のマルコフ測度が任意の次数のマルコフではない原像測度を持つようになる（例2.6 ^[2]）。

V をn個の記号（アルファベット）の有限集合とする。XをVの元とシフト演算子Tのすべての双無限列の集合⁠ ⁠ とする。Vに${\displaystyle V^{\mathbb {Z} }}$離散位相を与え、Xに積位相を与える。記号フローまたはサブシフトはXの閉じたT不変サブセットY ^[3]であり、関連する言語L _{Y は}Yの有限部分列の集合である。^[4]

ここで、A を{0, 1}の要素を持つn × n 隣接行列とします。これらの要素を使用して、有向グラフG = ( V , E )を構築します。ここで、 Vは頂点の集合、E は、 A _{x , y} = 1の場合に限り、E内の有向辺x → yを含む辺の集合です。Y をすべての無限許容辺シーケンスの集合とします。ここで、許容とは、シーケンスがグラフのウォークであることを意味し、シーケンスは片側無限または両側無限のいずれかになります。T をそのようなシーケンスの左シフト演算子とします。これは、動的システムの時間発展演算子の役割を果たします。有限タイプのサブシフトは、このようにして取得されたペア( Y、T )として定義されます。シーケンスが一方向にのみ無限に拡張される場合、それは有限タイプの片側サブシフトと呼ばれ、双方向の場合は有限タイプの両側サブシフトと呼ばれます。

形式的には、辺の列を次のように定義できる。

${\displaystyle \Sigma _{A}^{+}=\left\{(x_{0},x_{1},\ldots ):x_{j}\in V,A_{x_{j}x_{j+1}}=1,j\in \mathbb {N} \right\}.}$

これは、行列Aの( p , q )番目の要素が 1 の場合にのみ、シンボルpの後にシンボルqが続くことができるすべてのシンボル シーケンスの空間です。すべての双無限シーケンスの空間は同様に定義されます。

${\displaystyle \Sigma _{A}=\left\{(\ldots ,x_{-1},x_{0},x_{1},\ldots ):x_{j}\in V,A_{x_{j}x_{j+1}}=1,j\in \mathbb {Z} \right\}.}$

シフト演算子 Tは、すべての記号を左にシフトすることによって、片側シフトまたは両側シフト内のシーケンスを別のシーケンスにマッピングします。つまり、

${\displaystyle \displaystyle (T(x))_{j}=x_{j+1}.}$

明らかに、このマップは両側シフトの場合にのみ逆変換可能です。

有限タイプのサブシフトは、 Gが強く連結されている場合、つまり任意の 1 つの頂点から他の任意の頂点へのエッジのシーケンスが存在する場合、推移的と呼ばれます。密な軌道を持つ動的システムに対応するのは、まさに有限タイプの推移的なサブシフトです。

重要な特殊なケースとして、完全なnシフトがあります。これは、すべての頂点を他のすべての頂点に接続する辺を持つグラフです。つまり、隣接行列のすべてのエントリは 1 です。完全なnシフトは、測度のないベルヌーイ方式に対応します。

慣例により、シフトという用語は完全なnシフトを指すものと理解されます。したがって、サブシフトとは、シフト不変 (つまり、シフト演算子の作用に対して不変なサブスペース)、空でない、および以下に定義される積位相に対して閉じた、完全なシフトの任意のサブスペースです。一部のサブシフトは、上記のように遷移行列によって特徴付けられます。このようなサブシフトは、有限型のサブシフトと呼ばれます。多くの場合、有限型のサブシフトは、単に有限型のシフトと呼ばれます。有限型のサブシフトは、位相マルコフシフトと呼ばれることもあります。

多くのカオス力学系は有限型のサブシフトと同型である。例としては、横方向ホモクリニック接続を持つ系、正の計量エントロピーを持つ閉多様体の微分同相写像、プルーエ・テュー・モース系、チャコン系（これは弱混合だが強混合ではないことが示された最初の系である）、シュトゥルム系、テプリッツ系などがある。^[5]

ソフィックシステムは、遷移グラフの異なるエッジが同じシンボルにマッピングされる可能性がある有限タイプのサブシフトのイメージです。たとえば、隠れマルコフ連鎖からの出力のみを見ると、出力はソフィックシステムのように見えます。^{[1]これは、}オートマトンを通るパスのラベルの集合と見なすことができます。つまり、有限タイプのサブシフトは、決定論的なオートマトンに対応します。^{[6]このようなシステムは、}通常の言語に対応します。

文脈自由システムも同様に定義され、句構造文法によって生成されます。

更新システムは、有限の単語の固定された有限のコレクションのすべての無限連結の集合として定義されます。

有限型のサブシフトは、特定の最近傍配置を除いた、自由（非相互作用）1次元ポッツモデル（イジングモデルのn文字一般化^{）と同一です。相互作用イジングモデルは、配置空間の連続関数（}以下で定義される積位相に関して連続）とともにサブシフトとして定義されます。パーティション関数とハミルトニアンは、この関数で明示的に表現できます。^{[説明が必要]}

サブシフトは特定の方法で量子化することができ、量子有限オートマトンのアイデアにつながります。

サブシフトは自然な位相を持ち、これは⁠ ⁠上の積位相から導かれる。ここで ${\displaystyle V^{\mathbb {Z} },}$

${\displaystyle V^{\mathbb {Z} }=\prod _{n\in \mathbb {Z} }V=\{x=(\ldots ,x_{-1},x_{0},x_{1},\ldots ):x_{k}\in V\;\forall k\in \mathbb {Z} \}}$

そしてV には離散位相が与えられている。サブシフトの位相を誘導する ⁠ ⁠ の位相の基底は、円筒集合の族で${\displaystyle V^{\mathbb {Z} },}$ある。

${\displaystyle C_{t}[a_{0},\ldots ,a_{s}]=\{x\in V^{\mathbb {Z} }:x_{t}=a_{0},\ldots ,x_{t+s}=a_{s}\}}$

円筒集合は⁠ ⁠ ⁠の閉開集合です。 ⁠ ⁠のすべての開集合は、円筒集合の可算な和集合です。 部分シフトのすべての開集合は、 ⁠ ⁠の開集合と部分シフトとの交差です。 この位相に関して、シフトT は同相写像です。つまり、この位相に関して、連続逆と 連続です。${\displaystyle V^{\mathbb {Z} }.}$${\displaystyle V^{\mathbb {Z} }}$${\displaystyle V^{\mathbb {Z} }}$

空間⁠ ⁠は${\displaystyle V^{\mathbb {Z} }}$カントール集合に同相である。

シフト空間には、さまざまなメトリックを定義できます。2 つの点が多くの初期シンボルを共有している場合に、それらの点を「近い」と見なすことで、シフト空間にメトリックを定義できます。これがp進メトリックです。実際、片側シフト空間と両側シフト空間はどちらもコンパクトな メトリック空間です。

有限型のサブシフトには、いくつかの異なる測度のいずれかが付与される可能性があり、これにより測度保存力学系がもたらされます。一般的な研究対象は、シフトのトポロジーへの マルコフ連鎖の拡張であるマルコフ測度です。

マルコフ連鎖は、遷移行列、すべてのp _ij ≥ 0となるn × n行列P = ( p _ij ) 、および

${\displaystyle \sum _{j=1}^{n}p_{ij}=1}$

定常確率ベクトルπ = ( π _i )はすべてのπ _i ≥ 0であり 、 ${\textstyle \sum \pi _{i}=1}$

${\displaystyle \sum _{i=1}^{n}\pi _{i}p_{ij}=\pi _{j}.}$

上で定義したマルコフ連鎖は、A _ij = 0のときは常にp _ij = 0であるとき、有限型のシフトと互換​​性があると言われる。円筒集合のマルコフ測度は次のように定義される。

${\displaystyle \mu (C_{t}[a_{0},\ldots ,a_{s}])=\pi _{a_{0}}p_{a_{0},a_{1}}\cdots p_{a_{s-1},a_{s}}}$

マルコフ測度と関係のある コルモゴロフ・シナイエントロピーは

${\displaystyle s_{\mu }=-\sum _{i=1}^{n}\pi _{i}\sum _{j=1}^{n}p_{ij}\log p_{ij}}$

アルティン・マズールゼータ関数は、形式的な冪級数として定義される。

${\displaystyle \zeta (z)=\exp \left(\sum _{n=1}^{\infty }{\Bigl |}{\textrm {Fix}}(T^{n}){\Bigr |}{\frac {z^{n}}{n}}\right),}$

ここでFix( T ⁿ )はn倍シフトの固定点の集合である。^[7] これは積の式で表される 。

${\displaystyle \zeta (z)=\prod _{\gamma }\left(1-z^{|\gamma |}\right)^{-1}\ }$

ここでγは閉軌道上を走る。^[7] 有限型のサブシフトの場合、ゼータ関数はzの有理関数である：^[8]

${\displaystyle \zeta (z)=(\det(I-zA))^{-1}\ .}$

• 転送オペレータ
• デ・ブリュイングラフ
• 量子有限オートマトン
• 公理A

• ブリン、マイケル、スタック、ギャレット (2002)。『動的システム入門』（第 2 版）。ケンブリッジ大学出版局。ISBN 0-521-80841-3。
• David Damanik,厳密なエルゴード的サブシフトと関連演算子(2005)
• ピテアス・フォッグ、N. (2002)。Berthé, ヴァレリー;フェレンチ、セバスチャン。モーデュイ、クリスチャン。シーゲル、A. (編)。力学、算術、組み合わせ論における置換。数学の講義ノート。 Vol. 1794年。ベルリン：シュプリンガー・フェルラーク。ISBN 3-540-44141-7.ZBL1014.11015  .​
• Natasha Jonoska、「有限型のサブシフト」、Sofic Systems and Graphs、(2000)。
• Michael S. Keane, Ergodic theory and subshifts of finite type、(1991)、Tim Bedford、Michael Keane、Caroline Series 編、Oxford University Press、Oxford (1991) の第 2 章として掲載。ISBN 0-19-853390 -X (短い解説付きの紹介と演習、および広範な参考文献を提供します。) 
• リンド、ダグラス、マ​​ーカス、ブライアン (1995)。シンボリックダイナミクスとコーディング入門。ケンブリッジ大学出版局。ISBN 0-521-55124-2.ZBL1106.37301  。​
• テシュル、ジェラルド(2012)。『常微分方程式と動的システム』プロビデンス：アメリカ数学会。ISBN 978-0-8218-8328-0。
• 謝慧敏 (1996)。文法の複雑さと 1 次元動的システム。カオスの方向。第 6 巻。ワールド サイエンティフィック。ISBN 9810223986。

• ウィリアムズ、スーザン G. 編 (2004)。シンボリック ダイナミクスとその応用: アメリカ数学会、短期コース、2002 年 1 月 4 日 - 5 日、カリフォルニア州サンディエゴ。応用数学シンポジウムの議事録: AMS 短期コースの講義ノート。第 60 巻。アメリカ数学会。ISBN 0-8218-3157-7.ZBL1052.37003  。​