Subdesplazamiento de tipo finito

En matemáticas , los subdesplazamientos de tipo finito son espacios de desplazamiento definidos por un conjunto finito de palabras prohibidas. Se utilizan para modelar sistemas dinámicos y, en particular, son objeto de estudio en dinámica simbólica y teoría ergódica . También describen el conjunto de todas las secuencias posibles ejecutadas por una máquina de estados finitos . Los espacios de desplazamiento más estudiados son los subdesplazamientos de tipo finito.

Un ejemplo de un desplazamiento (unilateral) de tipo finito es el conjunto de todas las secuencias, infinitas en un solo extremo, que pueden estar formadas por las letras${\displaystyle A,B}$, como${\displaystyle AAA\cdots ,ABAB\cdots ,\dots }$Esto se conoce como turno completo y se denota por${\displaystyle \{A,B\}^{\mathbb {N} }}$.

Al prohibir la palabra${\displaystyle BB}$, se define un desplazamiento de tipo finito${\displaystyle \Sigma =\{(x_{0},x_{1},x_{2},\ldots )\mid x_{i}x_{i+1}\neq BB\}}$llamado el cambio dorado , llamado así porque el número de palabras legales de longitud${\displaystyle n}$son los números de Fibonacci . Los desplazamientos bilaterales de tipo finito son similares, pero consisten en secuencias que son infinitas en ambos extremos.

Un subdesplazamiento se puede definir mediante un grafo dirigido sobre las letras, como el grafo${\displaystyle A\to B\to C\to A}$Consiste en secuencias cuyas transiciones entre letras consecutivas son solo aquellas permitidas por el grafo. Para este ejemplo, el subdesplazamiento consta de solo tres secuencias unilaterales:${\displaystyle ABCABC\cdots ,BCABCA\cdots ,CABCAB\cdots }$. De manera similar, el subdesplazamiento bilateral descrito por este gráfico consta de solo tres secuencias bilaterales.

Otros gráficos dirigidos sobre las mismas letras producen otros subdesplazamientos. Por ejemplo, añadir otra flecha${\displaystyle A\to C}$Al aplicar el grafo, se obtiene un subdesplazamiento que, en lugar de contener tres secuencias, contiene un número infinito no numerable de secuencias. Salvo una recodificación local de letras, todo subdesplazamiento de tipo finito puede describirse mediante un grafo dirigido de este tipo.

Dejar${\displaystyle {\mathcal {A}}}$ser un conjunto finito de${\displaystyle n}$símbolos (alfabeto). Dejemos${\displaystyle X}$denota el conjunto${\displaystyle {\mathcal {A}}^{\mathbb {Z} }}$de todas las secuencias bi-infinitas de elementos de${\displaystyle {\mathcal {A}}}$junto con el operador de turno${\displaystyle T}$Nosotros dotamos${\displaystyle {\mathcal {A}}}$con la topología discreta y${\displaystyle X}$con la topología del producto . Un flujo simbólico o subdesplazamiento es un flujo cerrado.${\displaystyle T}$subconjunto invariante${\displaystyle Y}$de${\displaystyle X}$^{[ 1 ]} y el lenguaje asociado${\displaystyle {\mathcal {L}}_{Y}}$es el conjunto de subpalabras finitas de elementos de${\displaystyle Y}$. ^{[ 2 ]}

Dejar${\displaystyle F}$ser un conjunto finito de palabras en el alfabeto${\displaystyle {\mathcal {A}}}$, que se denominan palabras prohibidas . El subdesplazamiento asociado de tipo finito se define como el espacio

$${\displaystyle \Sigma _{F}=\{(x_{0},x_{1},x_{2},\ldots )\mid \forall i,k\geq 0,x_{i}x_{i+1}\cdots x_{i+k}\notin F\}}$$

de secuencias que evitan el conjunto de palabras prohibidas${\displaystyle F}$.

Si la secuencia se extiende hasta el infinito en una sola dirección, como se indicó anteriormente, se denomina subdesplazamiento unilateral de tipo finito, y si es bilateral , se denomina subdesplazamiento bilateral de tipo finito.

El operador de turno${\displaystyle T}$mapea una secuencia en el desplazamiento unilateral o bilateral a otra desplazando todos los símbolos hacia la izquierda, es decir

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

Evidentemente, este mapa solo es invertible en el caso del desplazamiento bilateral.

Una subclase particularmente útil la constituyen los desplazamientos de aristas . Sea A una matriz de adyacencia n × n con entradas en {0, 1}. Utilizando estos elementos, construimos un grafo dirigido G = ( V , E ) con V el conjunto de vértices y E el conjunto de aristas que contienen la arista dirigida x → y en E si y solo si A _{x , y} = 1. Sea Y el conjunto de todas las secuencias infinitas admisibles de aristas, donde por admisible se entiende que la secuencia es un recorrido del grafo, y la secuencia puede ser infinita unilateral o bilateral. Sea T el operador de desplazamiento a la izquierda sobre dichas secuencias; desempeña el papel del operador de evolución temporal del sistema dinámico. Un desplazamiento de arista se define entonces como un par ( Y , T ) obtenido de esta manera.

Formalmente, se pueden definir las secuencias de aristas como

${\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\}.}$

Este es el espacio de todas las secuencias de símbolos tales que el símbolo p puede ir seguido del símbolo q solo si la entrada ( p , q ) -ésima de la matriz A es 1. El espacio de todas las secuencias bi-infinitas se define de forma análoga:

${\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\}.}$

Los desplazamientos de borde son un subconjunto de los subdesplazamientos de tipo finito cuyo conjunto de palabras prohibidas comprende únicamente palabras de dos letras. Por otro lado, se puede demostrar que todo subdesplazamiento de tipo finito es topológicamente conjugado a un desplazamiento de borde mediante una recodificación local . ^{[ 3 ]}

Un desplazamiento de aristas se denomina transitivo si G es fuertemente conexo : existe una secuencia de aristas desde cualquier vértice a cualquier otro. Los subdesplazamientos de tipo finito con órbitas densas son precisamente aquellos conjugados a un desplazamiento de aristas transitivo.

Un caso especial importante es el desplazamiento n completo : tiene un grafo con una arista que conecta cada vértice con cada otro vértice; es decir, todas las entradas de la matriz de adyacencia son 1. El desplazamiento n completo corresponde al esquema de Bernoulli sin la medida .

Por convención, el término desplazamiento se entiende como el desplazamiento n completo . Un subdesplazamiento es entonces cualquier subespacio del desplazamiento completo que sea invariante bajo la acción del operador de desplazamiento, no vacío y cerrado para la topología de producto definida más adelante. Algunos subdesplazamientos pueden caracterizarse mediante una matriz de transición, como se indicó anteriormente; dichos subdesplazamientos se denominan subdesplazamientos de tipo finito. A menudo, los subdesplazamientos de tipo finito se denominan simplemente desplazamientos de tipo finito . Los subdesplazamientos de tipo finito también se denominan a veces desplazamientos de Markov topológicos .

Muchos sistemas dinámicos caóticos son isomorfos a subdesplazamientos de tipo finito; ejemplos de ello son los sistemas con conexiones homoclinas transversales , los difeomorfismos de variedades cerradas con entropía métrica positiva y los mapas de Markov lineales a trozos del intervalo.

Un subdesplazamiento tiene una topología natural, derivada de la topología del producto en ⁠${\displaystyle V^{\mathbb {Z} },}$dónde​

${\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} \}}$

y a V se le da la topología discreta . Una base para la topología de ⁠${\displaystyle V^{\mathbb {Z} },}$que induce la topología del subdesplazamiento, es la familia de conjuntos de cilindros

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

Los conjuntos de cilindros son conjuntos abiertos en ⁠${\displaystyle V^{\mathbb {Z} }.}$Cada conjunto abierto en${\displaystyle V^{\mathbb {Z} }}$⁠ es una unión numerable de conjuntos de cilindros. Cada conjunto abierto en el subdesplazamiento es la intersección de un conjunto abierto de ⁠${\displaystyle V^{\mathbb {Z} }}$con el subdesplazamiento. Con respecto a esta topología, el desplazamiento T es un homeomorfismo ; es decir, con respecto a esta topología, es continuo con inverso continuo.

El espacio${\displaystyle V^{\mathbb {Z} }}$es homeomorfo a un conjunto de Cantor .

En un espacio de desplazamiento se pueden definir diversas métricas. Una métrica se define considerando que dos puntos están "cercanos" si comparten muchos símbolos iniciales; esta es la métrica p -ádica . De hecho, tanto los espacios de desplazamiento unilaterales como bilaterales son espacios métricos compactos .

Un subdesplazamiento de tipo finito puede dotarse de cualquiera de varias medidas diferentes , lo que da lugar a un sistema dinámico que conserva la medida . Un objeto de estudio común es la medida de Markov , que es una extensión de una cadena de Markov a la topología del desplazamiento.

Una cadena de Markov es un par ( P , π) que consta de la matriz de transición , una matriz n × n P = ( p _ij ) para la cual todos los p _ij ≥ 0 y

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

para todo i . El vector de probabilidad estacionario π = ( π _i ) tiene todos los π _i ≥ 0 ,${\textstyle \sum \pi _{i}=1}$y tiene

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

Se dice que una cadena de Markov, tal como se definió anteriormente, es compatible con el desplazamiento de tipo finito si p _ij = 0 siempre que A _ij = 0. La medida de Markov de un conjunto de cilindros puede definirse entonces por

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

La entropía de Kolmogorov-Sinai en relación con la medida de Markov es

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

Medidas de Markov y no markovianas

Como se indicó anteriormente, dada una matriz de transición de Markov y una distribución invariante en los estados, podemos imponer una medida de probabilidad en el subdesplazamiento. Por ejemplo, consideremos la cadena de Markov dada a la izquierda en los estados.${\displaystyle A,B_{1},B_{2}}$, con distribución invariante${\displaystyle \pi =(2/7,4/7,1/7)}$. Si "olvidamos" la distinción entre${\displaystyle B_{1},B_{2}}$, proyectamos este subdesplazamiento en${\displaystyle A,B_{1},B_{2}}$en un subturno en${\displaystyle A,B}$y esta proyección también proyecta la medida de probabilidad hacia abajo a una medida de probabilidad en el subdesplazamiento en${\displaystyle A,B}$.

Lo curioso es que la medida de probabilidad en el subdesplazamiento en${\displaystyle A,B}$no es creado por una cadena de Markov en${\displaystyle A,B}$, ni siquiera múltiples órdenes. Intuitivamente, esto se debe a que si uno observa una larga secuencia de${\displaystyle B^{n}}$, entonces uno se volvería cada vez más seguro de que el${\displaystyle Pr(A|B^{n})\to {\frac {2}{3}}}$, lo que significa que la parte observable del sistema puede verse afectada por algo que ocurrió infinitamente en el pasado. ^{[ 4 ] [ 5 ]}

Por el contrario, existe un subdesplazamiento en 6 símbolos, proyectado a un subdesplazamiento en 2 símbolos, tal que cualquier medida de Markov en el subdesplazamiento más pequeño tiene una medida de preimagen que no es de Markov de ningún orden (Ejemplo 2.6 ^{[ 5 ]} ).

La función zeta de Artin-Mazur se define como la serie de potencias formal.

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

donde Fix( T ⁿ ) es el conjunto de puntos fijos del desplazamiento n -ésimo. ^{[ 6 ]} Tiene una fórmula de producto

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

donde γ recorre las órbitas cerradas. ^{[ 6 ]} Para subdesplazamientos de tipo finito, la función zeta es una función racional de z : ^{[ 7 ]}

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

Un desplazamiento sófico es una imagen de un subdesplazamiento de tipo finito donde diferentes aristas del grafo de transición pueden mapearse al mismo símbolo. Por ejemplo, si solo se observa la salida de una cadena oculta de Markov, entonces la salida parece ser un sistema sófico. ^{[ 4 ]} Puede considerarse como el conjunto de etiquetas de caminos a través de un autómata : un subdesplazamiento de tipo finito corresponde entonces a un autómata que es determinista . ^{[ 8 ]} Dichos sistemas corresponden a lenguajes regulares .

Los sistemas libres de contexto se definen de forma análoga y se generan mediante gramáticas de estructura de frases .

Un sistema de renovación se define como el conjunto de todas las concatenaciones infinitas de una colección finita y fija de palabras finitas.

Los subdesplazamientos de tipo finito son idénticos a los modelos de Potts unidimensionales libres (no interactuantes) ( generalizaciones de n letras de los modelos de Ising ), con la exclusión de ciertas configuraciones de vecinos más cercanos. Los modelos de Ising interactuantes se definen como subdesplazamientos junto con una función continua del espacio de configuración (continua con respecto a la topología del producto, definida más adelante); la función de partición y el hamiltoniano se pueden expresar explícitamente en términos de esta función.

Los subdesplazamientos pueden cuantificarse de cierta manera, lo que lleva a la idea de los autómatas finitos cuánticos .

• Espacio de cambio
• Operador de transferencia
• Gráfico de De Bruijn
• Autómatas finitos cuánticos
• Axioma A
• Fibraciones de grafos

• Brin, Michael; Stuck, Garrett (2002). Introducción a los sistemas dinámicos (2.ª  ed.). Cambridge University Press . ISBN 0-521-80841-3.
• David Damanik, Subdesplazamientos estrictamente ergódicos y operadores asociados , (2005)
• Pytheas Fogg, N. (2002). Berthé, Valérie ; Ferenczi, Sébastien; Mauduit, cristiano; Siegel, A. (eds.). Sustituciones en dinámica, aritmética y combinatoria . Apuntes de conferencias de matemáticas. vol.  1794. Berlín: Springer-Verlag . ISBN 3-540-44141-7. Zbl 1014.11015 . 
• Natasha Jonoska , Subdesplazamientos de tipo finito, sistemas sóficos y grafos , (2000).
• Michael S. Keane, Teoría ergódica y subdesplazamientos de tipo finito , (1991), que aparece como capítulo 2 en Teoría ergódica, dinámica simbólica y espacios hiperbólicos , Tim Bedford, Michael Keane y Caroline Series, Eds. Oxford University Press, Oxford (1991). ISBN 0-19-853390-X(Ofrece una breve introducción explicativa, con ejercicios y amplias referencias.)
• Lind, Douglas; Marcus, Brian (1995). Introducción a la dinámica simbólica y la codificación . Cambridge University Press . ISBN 0-521-55124-2. Zbl 1106.37301 . 
• Teschl, Gerald (2012). Ecuaciones diferenciales ordinarias y sistemas dinámicos . Providence : American Mathematical Society . ISBN 978-0-8218-8328-0.
• Xie, Huimin (1996). Complejidad gramatical y sistemas dinámicos unidimensionales . Direcciones en el caos. Vol.  6. World Scientific. ISBN 9810223986.

• Williams, Susan G., ed. (2004). Dinámica simbólica y sus aplicaciones: Curso intensivo de la Sociedad Matemática Americana, 4-5 de enero de 2002, San Diego, California . Actas de simposios de matemáticas aplicadas: Apuntes de clase del curso intensivo de la AMS. Vol.  60. Sociedad Matemática Americana . ISBN 0-8218-3157-7. Zbl 1052.37003 .