Caso de Estudio: Autómata $(4,1/2)$

Para ver como funcionan todos los resultados anteriores tomemos un autómata reversible $(4,1/2)$ con $\phi=BB991133$ y ${\phi}^{-1}=28F528F5$. En ambos casos las dos reglas tienen el mismo valor de $r=1/2$ y, por lo tanto, el mismo tamaño de vecindad, $2r+1=2$.

Figura 3.14: Autómata celular lineal reversible $(4,1/2)$ regla $BB991133$

Se ve que cada estado tiene la misma probabilidad de generarse que el resto tanto en $\phi$ como en ${\phi}^{-1}$; tomemos varias cadenas aleatorias de elementos y veamos cuales son sus ancestros para $\phi$.

Figura 3.15: Ancestros de diversas cadenas

En todos los casos se observa que el número de ancestros es igual a ${k}^{2r}={4}^{2*(1/2)}=4$. Ahora analizemos las distintas partes de los ancestros para dichas cadenas.

Figura 3.16: Indices de Welch para los ancestros del autómata $(4,1/2)$

Se puede observar que en todos los casos se cumple que $L=2$, $M=1$ y $R=2$; con $LR=4=k^{2r}$. Se cumple que las diferencias de los ancestros se presenten a los extremos, dejando una parte central única. Ahora observemos el diagrama de de Bruijn asociado a la regla de evolución.

Figura 3.17: Diagrama de de Bruijn del autómata reversible $(4,1/2)$ , regla $BB991133$

Cada liga aparece el mismo número de veces que las demás, si tomamos las ligas que forman la secuencia $00$, observamos lo siguiente:

Figura 3.18: Rutas posibles de la secuencia $00$

Esta ruta tiene $L=2$ posibles nodos iniciales $((0),(1))$, comparten un único nodo central $(1)$ indicando que $M=1$ y terminan en $R=2$ nodos distintos $((1),(3))$.

Tomemos ahora el diagrama de parejas de dicho autómata:

Figura 3.19: Diagrama de Parejas del autómata reversible $(4,1/2)$ , regla $BB991133$

Si editamos este diagrama de modo que solo presentemos los ciclos que existen en él obtenemos la siguiente construcción.

Figura 3.20: Diagrama de Parejas editado mostrando solamente sus ciclos

Los únicos ciclos que existen aparecen en la diagonal principal que es el diagrama de de Bruijn mismo, y aparte de esto no se presentan de ninguna otra forma, lo que indica que no es posible construir una secuencia de longitud indefinida de $2$ o más modos distintos.

Los diagramas de subconjuntos de la regla original y la regla reflejada son los siguientes:

Figura 3.21: Diagramas de subconjuntos del autómata reversible $(4,1/2)$ , regla $BB991133$

Para la regla original el máximo nivel que se puede alcanzar empezando desde las clases unitarias es el nivel $2$, lo que indica que $R=2$, y de ahí, estas mismas rutas no salen de este nivel. Lo mismo ocurre con las clases unitarias del diagrama de la regla reflejada, en donde el máximo nivel al que se arriba es el $2$ también, mostrando que $L=2$ y tampoco estas rutas abandonan este nivel. Editemos los diagramas y tomemos los conjuntos que están auto-ligados en estos niveles.

Figura 3.22: Diagramas de Welch del autómata $(4,1/2)$ regla $BB991133$

De esta forma obtenemos los diagramas de Welch del autómata $(4,1/2)$ regla $BB991133$. Veamos ahora en el diagrama derecho las rutas de la secuencia $0$ y en el diagrama izquierdo las rutas de la secuencia $0$.

Figura 3.23: Rutas de la secuencia $0$ en los diagramas de Welch

Ambas rutas convergen a un único nodo, estos nodos finales tiene un solo elemento en común que es $1$; es decir, que la secuencia $00$ regresa hacia atrás en la evolución con el estado $1$ como se vio anteriormente. Del diagrama de de Bruijn obtengamos la matriz de conectivdad de $0$ $(\mathrm{M}_0)$

$$\mathrm{M}_0 = \left (\matrix{ 0 & 1 & 0 & 1 \cr 0 & 1 & 0 & 1 \cr 0 & 0 & 0 & 0 \cr 0 & 0 & 0 & 0 \cr }\right )$$

En esta matriz existen ${k}^{2r}=4^{(2*(1/2))}=4$ elementos distintos de $0$. Ahora bien, si elevamos $\mathrm{M}_0$ al cuadrado, obtenemos la matriz de conectividad de la secuencia $00$ denotada como $\mathrm{M}_{00}$.

$$\mathrm{M}_{00} = \left (\matrix{ 0 & 1 & 0 & 1 \cr 0 & 1 & 0 & 1 \cr 0 & 0 & 0 & 0 \cr 0 & 0 & 0 & 0 \cr }\right )$$

Vemos que el número de elementos distintos de $0$ sigue siendo $4$ cumpliendo con la multiplicidad uniforme, además, los renglones distintos de $0$ son $(0,1)$ y las columnas distintas de $0$ son $(1,3)$ indicando cuales son los nodos iniciales y finales de esta ruta. En ambos casos la suma de renglones distintos de $0$ es igual a $L=2$ y la suma de columnas con la misma propiedad es $R=2$. Ahora vamos a resolver el problema de eigenvalores para la matriz de conectividad $\mathrm{M}_{0}$. Calculando los eigenvalores tenemos $\vert\mathrm{M}_{0}-\lambda I\vert=0$.

$$\begin{array}{ccccc} \left \vert\matrix{ -\lambda & 1 & 0 & ... ...-{\lambda}^{3}=0;& \lambda_1=0& y& \lambda_2=1. \\ \end{array}$$

Los eigenvalores que se obtienen son $\lambda_1=0$ de multiplicidad tres que es el caso trivial y $\lambda_2 = 1$ el cual indica que si elevamos esta matriz, equivalente a obtener la matriz de conectividad de una secuencia formada concatenando el mismo estado repetidamente, se seguirá conservando el mismo número de ancestros.

$$\mathrm{M}^n_0 = \left (\matrix{ 0 & 1 & 0 & 1 \cr 0 & 1 & 0... ... & 0 & 0 \cr 0 & 0 & 0 & 0 \cr }\right ) \mbox{; para $n>0$.}$$

En todos los casos el número de elementos distintos a $0$ es ${k}^{2r}=4$. Ahora obtengamos el eigenvector-renglón de $\mathrm{M}_0$ denotado por $\vert\mathrm{e}_0>$ y el eigenvector-columna de $\mathrm{M}_0$ transpuesta que denotaremos con $<\mathrm{e}_0\vert$.

$$\begin{array}{lcccc} \vert\mathrm{e}_0>&=& \left( \begin{ar... ...{array}{cccc} 0&1&0&1 \\ \end{array}\right )^T \\ \end{array}$$

Si multiplicamos ambos eigenvectores obtenemos la siguiente matriz:

$$\begin{array}{ccccccc} \vert\mathrm{e}_0><\mathrm{e}_0\vert=... ...\cr 0 & 0 & 0 & 0 \cr }\right )&=& \mathrm{M}_0 \\ \end{array}$$

Esta es la matriz de conectividad de la secuencia $00$ obtenida anteriormente, la cual hemos podido reconstruir por medio de los eigenvectores.

Trabajemos con estados distintos, tomemos la matriz de conectividad del estado $1$.

$$\mathrm{M}_1= \left (\matrix{ 0 & 0 & 0 & 0 \cr 1 & 0 & 1 & 0 \cr 1 & 0 & 1 & 0 \cr 0 & 0 & 0 & 0 \cr }\right )$$

Obtengamos los eigenvalores de la matriz de conectividad de la secuencia $00$ y del estado $1$.

$$\begin{array}{rrccc} \vert\mathrm{M}_{00}-\lambda I\vert=& \... ...bda^4-\lambda^3=0;& \lambda_1=0& \lambda_2=1 \\ \\ \end{array}$$

Los eigenvalores no triviales en ambos casos son iguales a $1$; calculemos el eigenvector-renglon de $\mathrm{M}_1$ y el eigenvector-columna de $\mathrm{M}_{00}$.

$$\begin{array}{lcccc} \vert\mathrm{e}_1>&=& \left( \begin{ar... ...{array}{cccc} 0&1&0&1 \\ \end{array}\right )^T \\ \end{array}$$

Multiplicando el eigenvector-renglon $\vert\mathrm{e}_1>$ con el eigenvector-columna $<\mathrm{e}_{00}\vert$ se obtiene la siguiente matriz.

$$\begin{array}{cccccc} \vert\mathrm{e}_1><\mathrm{e}_{00}\ver... ...r 0 & 1 & 0 & 1 \cr 0 & 0 & 0 & 0 \cr }\right ) \\ \end{array}$$

Si tomamos las matrices de conectividad de $0$ y de $1$ y las multiplicamos en el orden que indica la secuencia $100$ obtenemos:

$$\begin{array}{ccc} (\mathrm{M}_1)(\mathrm{M}_0)(\mathrm{M}_0... ... \cr 0 & 0 & 0 & 0 \cr }\right ) =&\mathrm{M}_{100} \end{array}$$

Que fue la matriz que obtuvimos por eigenvectores anteriormente.