Random subshifts of finite type

Abstract: Let

X

be an irreducible shift of finite type (SFT) of positive entropy, and let

B_{n} (X)

be its set of words of length

n

. Define a random subset

o m e g a

of

B_{n} (X)

by independently choosing each word from

B_{n} (X)

with some probability

a l p h a

. Let

X_{o m e g a}

be the (random) SFT built from the set

o m e g a

. For each

0 l e q a l p h a l e q 1

and

n

tending to infinity, we compute the limit of the likelihood that

X_{o m e g a}

is empty, as well as the limiting distribution of entropy for

X_{o m e g a}

. For

a l p h a

near 1 and

n

tending to infinity, we show that the likelihood that

X_{o m e g a}

contains a unique irreducible component of positive entropy converges exponentially to 1. These results are obtained by studying certain sequences of random directed graphs. This version of "random SFT" differs significantly from a previous notion by the same name, which has appeared in the context of random dynamical systems and bundled dynamical systems.

Review text

Let \(\mathcal A\) be a finite set, \(\mathcal F\) be a set of words on \(\mathcal A\) and \(X(\mathcal F)\) be the set of sequences \(x\) in \(\Sigma=\mathcal A^Z\) such that no word in \(\mathcal F\) appears in \(x\). Then \(X(\mathcal F)\) is a subshift, i.e. closed \(\sigma\)-invariant subset of \(\Sigma\), where \(\sigma\) is the left shift. If \(X\) is a subshift and \(X=X(\mathcal F)\), where \(\mathcal F\) is a finite set of words, then \(X\) is a subshift of a finite type (SFT). An SFT \(X\) is irreducible if for every two nonempty open sets \(U\) and \(V\) and every \(N\) there exists \(n\geq N\) such that \(\sigma^n (U)\cap V\neq \emptyset\). The entropy of \(X\) is defined as \(h(X)=\lim \frac{1}{n}\log |B_n(X)|\), where \(B_n(X)\) is the set of all words of length \(n \) that appear in some \(x\in X\).NEWLINENEWLINE Let \(X\) be an irreducible SFT of positive entropy and \(\omega\) be a random subset of \(B_n(X)\) given by choosing every word in \(B_n(X)\) independently with probability \(\alpha\). Let \(X_\omega\) be the random SFT built from the set \(\omega\). The results presented here deal with the likelihood that \(X_\omega\) is empty and with the limiting distribution of entropy of \(X_\omega\). It is also shown that the likelihood for a random SFT to have a unique irreducible component of positive entropy converges exponentially to 1 for \(\alpha\) near 1 and \(n \to \infty\).

Recommendations

Cites work

Cited in

(13)

This page was built for publication: Random subshifts of finite type

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q414282)