Feeds:
Posts

K. McGoff: Random Subshifts of Finite Type

It is often interesting to study the properties of objects picked at random in some class. This may shed some light on whether some observed system has is typical in some probabilistic model or may even turn out to be an efficient way of  obtaining an interesting behavior. This idea was put to spectacular use by Erdös in combinatorics (see Random graphs, Bollobas?), and closer to us, by Gromov (and later Yann Ollivier) for finitely presented groups.

In a very recent preprint, K. McGoff has considered random subshift of finite type (see An introduction to symbolic dynamics by Marcus and Lind). A subshift of finite type is a compact set of the form

$X:=\{x\in\{1,\dots,N\}^{\mathbb N}: \forall p\in\mathbb Z\; x_px_{p+1}\dots x_{p+L-1}\in\mathcal A\}$

where $N\in\mathbb N^*$ and $\mathcal A\subset\{1,\dots,N\}^L$ for some $L$, the finite sequences being considered up to translation of the indices. The self-map $\sigma: (x_p)_{p\in\mathbb Z}\mapsto (x_{p+1})_{p\in\mathbb Z}$ (called the shift) turns $X$ into a dynamical system.

Note that the following inclusion is usually strict: $\mathcal B(X,L):=\{x_p\dots x_{p+L-1}:x\in X,\; p\in\mathbb Z\} \subset \mathcal F$.

Given $\mathcal F$, some of the most natural questions are:

1. Is $X$ empty?
2. What is the entropy of $X$? This quantifies how big $X$ is. It is the positive number $h(X):=\lim_{n\to\infty}\frac1n\log \#X(n)$ where $X(n)$ is the set of all the finite sequences of length $n$ which occurs as a subsequence of any $x\in X$ and $\#X(n)$ is the cardinality of that set.
3. How many irreducible components does $X$ have? An irreducible component  is the closure of an orbit, i.e., $\{\sigma^n(x):n\in\mathbb Z\}$, which is not included in a larger one.

Let us stress that these questions are well-known to have an algorithmic answer. If the maximal length of sequences appearing in $\mathcal F$ is $L$, one defines a $N^{L-1}\times N^{L-1}$-matrix with 0,1-entries. The largest positive eigenvalue is the exponential of the entropy (or zero if and only if $X=\emptyset$) and its multiplicity is the number of irreducible components. But of course $N^{L-1}$ is very large if $L$ is large.

K. McGoff considers the following random model with parameter $0\leq \alpha\leq 1$ and a subshift of finite type $X$. Given $L$ a very large integer, $\mathcal F\subset\mathcal B(X,L)$ is defined by declaring that each sequence of length belongs to $\mathcal F$ independently and with probability $1-\alpha$. He then considers the limit of the probabilities when $L\to\infty$. Let us quote his main results in a somewhat weakened form and specialized to $X=\{1,\dots,N\}^{\mathbb Z}$ for simplicity.

There is a dichotomy between small $\alpha$ (empty shift with positive limit probability,  zero entropy with full limit probability, non-trivial distribution of the number of components) and large $\alpha$ (non-empty, entropy close to $\log(\alpha\lambda)$ and a single, aperiodic irreducible component with full limit probability).

The above results for small $\alpha$ are shown for all $\alpha<1/N$. For large $\alpha$, the non-emptyness holds for $\alpha\geq 1/N$, the convergence of the entropy for $\alpha>1/N$ and the irreducibility and aperiodicity for $\alpha$ close enough to 1.