The shortest path between two strings in product spaces

Miguel Abadi, Rodrigo Lambert

Published 2016-11-04Version 1

We consider two independent and stationary measures over $\chi^\mathbb{N}$, where $\chi$ finite or countable alphabet. For each pair of $n$-strings in the product space we define $T_n^{(2)}$ as the length of the shortest path connecting one string to the other where the paths are generating by the underlying dynamics of the measure. For ergodic measures with positive entropy we prove that, for almost every pair of realizations $(x,y)$, $T^{(2)}_n/n$ concentrates in one, as $n$ diverges. Under mild extra conditions we prove a large deviation principle. This principle is linked to a quantity that compute the similarity between the two measures that we also introduce. We further prove its existence and other properties. We also show that the fluctuations of $T_n^{(2)}$ converge (only) in distribution to a non-degenerated distribution. Several examples are provided for all results.