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
where and for some , the finite sequences being considered up to translation of the indices. The self-map (called the shift) turns into a dynamical system.
Note that the following inclusion is usually strict: .
Given , some of the most natural questions are:
- Is empty?
- What is the entropy of ? This quantifies how big is. It is the positive number where is the set of all the finite sequences of length $n$ which occurs as a subsequence of any and is the cardinality of that set.
- How many irreducible components does have? An irreducible component is the closure of an orbit, i.e., , 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 is , one defines a -matrix with 0,1-entries. The largest positive eigenvalue is the exponential of the entropy (or zero if and only if ) and its multiplicity is the number of irreducible components. But of course is very large if is large.
K. McGoff considers the following random model with parameter and a subshift of finite type . Given a very large integer, is defined by declaring that each sequence of length belongs to independently and with probability . He then considers the limit of the probabilities when . Let us quote his main results in a somewhat weakened form and specialized to for simplicity.
There is a dichotomy between small (empty shift with positive limit probability, zero entropy with full limit probability, non-trivial distribution of the number of components) and large (non-empty, entropy close to and a single, aperiodic irreducible component with full limit probability).
The above results for small are shown for all . For large , the non-emptyness holds for , the convergence of the entropy for and the irreducibility and aperiodicity for close enough to 1.
Leave a comment