Подсдвиг конечного типа

В математике и , подсдвиги конечного типа используются для моделирования динамических систем в частности, являются объектами изучения символической динамики и эргодической теории . Они также описывают набор всех возможных последовательностей, выполняемых конечным автоматом . Наиболее широко изученными пространствами сдвигов являются подсдвиги конечного типа.

Мотивирующие примеры

(Односторонний) сдвиг конечного типа — это множество всех последовательностей, бесконечных только на одном конце, которые могут быть составлены из букв $A,B,C$ , нравиться $AAA\cdots ,ABAB\cdots ,\dots$ . (Двусторонний) сдвиг конечного типа аналогичен, но состоит из последовательностей, бесконечных на обоих концах.

Подсдвиг можно определить с помощью ориентированного графа этих букв, например графа $A\to B\to C\to A$ . Он состоит из последовательностей, переходы которых между последовательными буквами разрешены только графом. В этом примере подсдвиг состоит всего из трех односторонних последовательностей: $ABCABC\cdots ,BCABCA\cdots ,CABCAB\cdots$ . Аналогично, двусторонний сдвиг, описываемый этим графом, состоит всего из трех двусторонних последовательностей.

Другие ориентированные графы на тех же буквах дают другие подсдвиги. Например, добавив еще одну стрелку $A\to C$ к графу производит подсдвиг, который вместо трех последовательностей содержит несчетное бесконечное число последовательностей.

Марковские и немарковские меры.

Учитывая матрицу марковского перехода и инвариантное распределение состояний, мы можем наложить вероятностную меру на набор подсдвигов. Например, рассмотрим цепь Маркова, приведенную слева для состояний $A,B_{1},B_{2}$ , с инвариантным распределением $\pi =(2/7,4/7,1/7)$ . Если мы «забудем» различие между $B_{1},B_{2}$ , проецируем это пространство подсдвигов на $A,B_{1},B_{2}$ в другое пространство подсдвигов на $A,B$ , и эта проекция также проецирует вероятностную меру до вероятностной меры на подсдвигах на $A,B$ .

Любопытно то, что вероятностная мера подсдвигов на $A,B$ не создается цепью Маркова на $A,B$ , даже не несколько заказов. Интуитивно это происходит потому, что если наблюдать длинную последовательность $B^{n}$ , то можно было бы все больше убеждаться в том, что $Pr(A|B^{n})\to {\frac {2}{3}}$ Это означает, что на наблюдаемую часть системы может бесконечно влиять что-то в прошлом. ^[1]^[2]

И наоборот, существует пространство подсдвигов на 6 символов, проецируемых на подсдвиги на 2 символа, такое, что любая марковская мера на меньшем подсдвиге имеет меру прообраза, не являющуюся марковской ни одного порядка (пример 2.6). ^[2]).

Определение

Пусть $V$ — конечное множество из $n$ символов (алфавита). Пусть $X$ обозначает множество ⁠ $V^{\mathbb {Z} }$ ⁠ всех бибесконечных последовательностей элементов $V$ вместе с оператором сдвига $T$ . Мы наделяем $V$ дискретной топологией , а $X$ — топологией произведения . Символический поток или подсдвиг — это замкнутое $T$ -инвариантное подмножество $Y$ множества $X.$ ^[3] и ассоциированный язык $L Y$ представляет собой множество конечных подпоследовательностей $Y$ . ^[4]

Теперь пусть $A$ — $n \times n$ матрица смежности размера с элементами в ${0, 1}.$ Используя эти элементы, мы строим ориентированный граф $G = (V, E)$ , где $V$ — множество вершин, а $E —$ множество ребер, содержащих направленное ребро $x \to y$ в $E$ , тогда и только тогда, когда $A x, y = 1$ . Пусть $Y$ — множество всех бесконечных допустимых последовательностей ребер, где под допустимыми подразумевается, что последовательность является обходом графа , и последовательность может быть как односторонней, так и двусторонней бесконечной. Пусть $T —$ оператор сдвига влево на таких последовательностях; он играет роль оператора временной эволюции динамической системы. Подсдвиг конечного типа тогда определяется как пара $(Y, T),$ полученная таким образом. Если последовательность продолжается до бесконечности только в одном направлении, она называется односторонним сдвигом конечного типа, а если она двусторонняя , то она называется двусторонним сдвигом конечного типа.

Формально можно определить последовательности ребер как

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

Это пространство всех последовательностей символов, таких, что за символом $p$ может следовать символ $q$ только в том случае, если $(p, q)$ -й элемент матрицы $A$ равен 1. Пространство всех бибесконечных последовательностей определяется аналогично :

\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 (T(x))_{j}=x_{j+1}.

Ясно, что это отображение обратимо только в случае двустороннего сдвига.

Подсдвиг конечного типа называется транзитивным, если $G$ : сильно связна существует последовательность ребер из любой одной вершины в любую другую вершину. Именно транзитивные подсдвиги конечного типа соответствуют динамическим системам с плотными орбитами.

Важным частным случаем является полный $n$ -сдвиг : он имеет граф с ребром, соединяющим каждую вершину с любой другой вершиной; то есть все элементы матрицы смежности равны 1. Полный $n$ -сдвиг соответствует схеме Бернулли без меры .

Терминология

По соглашению, термин «сдвиг» понимается как относящийся к полному $n$ -сдвигу. Подсдвигом . тогда называется любое подпространство полного сдвига, инвариантное к сдвигу (то есть подпространство, инвариантное относительно действия оператора сдвига), непустое и замкнутое для топологии произведения, определенной ниже Некоторые подсмены можно охарактеризовать матрицей перехода, как указано выше; такие подсдвиги тогда называются подсдвигами конечного типа. Часто подсдвиги конечного типа называют просто сдвигами конечного типа . Подсдвиги конечного типа иногда называют топологическими марковскими сдвигами .

Примеры

Многие хаотические динамические системы изоморфны подсдвигам конечного типа; примеры включают системы с трансверсальными гомоклиническими связностями , диффеоморфизмы с замкнутых многообразий положительной метрической энтропией , систему Пруэ–Туэ–Морса , систему Чакона (это первая система, которая, как показано, является слабо перемешивающей , но не сильно перемешивающей ), системы Штурма и Теплица системы . ^[5]

Обобщения

Софическая система — это образ подсдвига конечного типа, в котором разные ребра графа переходов могут отображаться в один и тот же символ. Например, если наблюдать только за выходными данными скрытой цепи Маркова, то выходные данные кажутся софической системой. ^[1] Его можно рассматривать как набор разметок путей через автомат : тогда подсдвиг конечного типа соответствует автомату, который является детерминированным . ^[6] Такие системы соответствуют регулярным языкам .

Бесконтекстные системы определяются аналогично и генерируются грамматиками фразовой структуры .

Система восстановления определяется как совокупность всех бесконечных конкатенаций некоторого фиксированного конечного набора конечных слов.

Подсдвиги конечного типа идентичны свободным (невзаимодействующим) одномерным моделям Поттса ( $n$ -буквенным обобщениям моделей Изинга ), за исключением некоторых конфигураций ближайших соседей. Взаимодействующие модели Изинга определяются как подсдвиги вместе с непрерывной функцией конфигурационного пространства. ^{[ когда определено как? ]} (непрерывный относительно топологии продукта, определенной ниже); статистическая сумма и гамильтониан явно выражаются через эту функцию. ^{[ нужны разъяснения ]}

Подсдвиги могут быть квантованы определенным образом, что приводит к идее квантовых конечных автоматов .

Топология

Подсмена имеет естественную топологию, полученную из топологии продукта на ⁠ $V^{\mathbb {Z} },$ ⁠ где

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$ задана дискретная топология . Основа топологии ⁠ $V^{\mathbb {Z} },$ ⁠, индуцирующая топологию подсдвига, представляет собой семейство цилиндрических множеств

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

Наборы цилиндров представляют собой замкнуто-замкнутые множества в ⁠. $V^{\mathbb {Z} }.$ ⁠ Каждый открытый набор в ⁠ $V^{\mathbb {Z} }$ ⁠ — счетное объединение множеств цилиндров. Каждое открытое множество в подсмене является пересечением открытого множества ⁠ $V^{\mathbb {Z} }$ ⁠ с подсменой. По отношению к этой топологии сдвиг $Т$ является гомеоморфизмом ; то есть относительно этой топологии она непрерывна с непрерывным обратным.

Пространство ⁠ $V^{\mathbb {Z} }$ ⁠ гомеоморфно канторову множеству .

Метрика

В пространстве сдвигов можно определить множество различных метрик. Можно определить метрику в пространстве сдвига, считая две точки «близкими», если у них много общих начальных символов; это $p$ -адическая метрика . Фактически, как одно-, так и двусторонние пространства сдвига являются компактными метрическими пространствами .

Мера

Подсдвиг конечного типа может быть снабжен любой из нескольких различных мер , что приводит к сохраняющей меру динамической системе . Общим объектом исследования является мера Маркова , которая представляет собой расширение цепи Маркова до топологии сдвига.

Цепь Маркова — это пара $(P, π),$ состоящая из матрицы перехода , $n \times n$ матрицы размера $P = (p ij),$ для которой все $p ij \geq 0$ и

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

для всех $я$ . Стационарный вектор вероятности $π = (π i)$ имеет все $π i \geq 0$ , ${\textstyle \sum \pi _{i}=1}$ и имеет

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

Цепь Маркова, как она определена выше, называется совместимой со сдвигом конечного типа, если $p ij = 0$ всякий раз, когда $A ij = 0$ . Тогда марковская мера цилиндрического множества может быть определена формулой

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

Энтропия Колмогорова – Синая по отношению к мере Маркова равна

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

Дзета-функция

Дзета-функция Артина –Мазура определяется как формальный степенной ряд

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

где $Fix(Т н)$ — множество неподвижных точек n $-кратного$ сдвига. ^[7] Имеет формулу продукта

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

где $γ$ пробегает замкнутые орбиты. ^[7] Для подсдвигов конечного типа дзета-функция является рациональной функцией от $z$ : ^[8]

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

См. также

Примечания

^ Jump up to: ^а ^б Софические меры: характеристики скрытых цепей Маркова с помощью линейной алгебры, формальных языков и символической динамики - Карл Петерсен, Mathematics 210, весна 2006 г., Университет Северной Каролины в Чапел-Хилл
^ Jump up to: ^а ^б Бойл, Майк; Петерсен, Карл (13 января 2010 г.), Скрытые марковские процессы в контексте символической динамики , arXiv : 0907.1858
^ Се (1996) стр.21
^ Се (1996) стр.22
^ Мэтью Никол и Карл Петерсен, (2009) « Эргодическая теория: основные примеры и конструкции », Энциклопедия сложности и системных наук , Springer https://doi.org/10.1007/978-0-387-30440-3_177
^ Пифей Фогг (2002) стр.205
^ Jump up to: ^а ^б Брин и Стак (2002) стр.60
^ Брин и Штук (2002) стр.61

Ссылки

Брин, Майкл; Застрял, Гаррет (2002). Введение в динамические системы (2-е изд.). Издательство Кембриджского университета . ISBN 0-521-80841-3 .
Дэвид Даманик, Строго эргодические подсдвиги и ассоциированные операторы , (2005)
Пифей Фогг, Н. (2002). Берте, Валери ; Ференци, Себастьен; Модуит, Кристиан; Сигел, А. (ред.). Замены в динамике, арифметике и комбинаторике . Конспект лекций по математике. Том. 1794. Берлин: Springer-Verlag . ISBN 3-540-44141-7 . Збл 1014.11015 .
Наташа Йоноска , Подсдвиги конечного типа, Софические системы и графы , (2000).
Майкл С. Кин, Эргодическая теория и сдвиги конечного типа , (1991), появляется в главе 2 в книге «Эргодическая теория, символическая динамика и гиперболические пространства» , Тим Бедфорд, Майкл Кин и Кэролайн Ряд, ред. Издательство Оксфордского университета, Оксфорд (1991). ISBN 0-19-853390-X (содержит краткое пояснительное введение с упражнениями и обширными ссылками.)
Линд, Дуглас; Маркус, Брайан (1995). Введение в символическую динамику и кодирование . Издательство Кембриджского университета . ISBN 0-521-55124-2 . Збл 1106.37301 .
Тешль, Джеральд (2012). Обыкновенные дифференциальные уравнения и динамические системы . Провиденс : Американское математическое общество . ISBN 978-0-8218-8328-0 .
Се, Хуэйминь (1996). Грамматическая сложность и одномерные динамические системы . Направления в хаосе. Том. 6. Мировая научная. ISBN 9810223986 .

Дальнейшее чтение

Уильямс, Сьюзен Г., изд. (2004). Символическая динамика и ее приложения: Американское математическое общество, краткий курс, 4–5 января 2002 г., Сан-Диего, Калифорния . Материалы симпозиумов по прикладной математике: конспекты лекций краткого курса АМС. Том. 60. Американское математическое общество . ISBN 0-8218-3157-7 . Збл 1052.37003 .

[:0-1] Jump up to: ^а ^б Софические меры: характеристики скрытых цепей Маркова с помощью линейной алгебры, формальных языков и символической динамики - Карл Петерсен, Mathematics 210, весна 2006 г., Университет Северной Каролины в Чапел-Хилл

[:1-2] Jump up to: ^а ^б Бойл, Майк; Петерсен, Карл (13 января 2010 г.), Скрытые марковские процессы в контексте символической динамики , arXiv : 0907.1858

[X21-3] Се (1996) стр.21

[X22-4] Се (1996) стр.22

[nicol-5] Мэтью Никол и Карл Петерсен, (2009) « Эргодическая теория: основные примеры и конструкции », Энциклопедия сложности и системных наук , Springer https://doi.org/10.1007/978-0-387-30440-3_177

[PF205-6] Пифей Фогг (2002) стр.205

[BS60-7] Jump up to: ^а ^б Брин и Стак (2002) стр.60

[BS61-8] Брин и Штук (2002) стр.61

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]