Edit distance in substitution systems

Andrew Best, Yuval Peres

Let $\sigma$ be a primitive substitution on an alphabet $\mathcal{A}$, and let ${\mathcal{W}}_n$ be the set of words of length $n$ determined by $\sigma$ (i.e., $w\in {\mathcal{W}}_n$ if $w$ is…