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 $\omega$ of $B_n(X)$ by independently choosing each word from $B_n(X)$ with some probability $\alpha$. Let $X_{\omega }$ be the (random) SFT built from the set $\omega$. For each $0\le \alpha \le 1$ and $n$ tending to infinity, we compute the limit of the likelihood that $X_{\omega }$ is empty, as well as the limiting distribution of entropy for $X_{\omega }$. For $\alpha$ near 1 and $n$ tending to infinity, we show that the likelihood that $X_{\omega }$ 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.

Published in at http://dx.doi.org/10.1214/10-AOP636 the Annals of Probability (http://www.imstat.org/aop/) by the Institute of Mathematical Statistics (http://www.imstat.org)

References in corpus (5)

• Approximating the largest eigenvalue of network adjacency matrices
• Critical random graphs: Diameter and mixing time
• Percolation on finite graphs and isoperimetric inequalities
• Escape Rates and Physically Relevant Measures for Billiards with Small Holes
• Approximating the Largest Eigenvalue of the Modified Adjacency Matrix of Networks with Heterogeneous Node Biases