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.
Read Full Post »