Matching strings in encoded sequences (Q2174991)

Let \(\chi, \tilde\chi \) be alphabets. An encoder is a measurable function on strings \(f\colon \chi ^{\mathrm{N}} \to \tilde\chi^{\mathrm{N}}\). For any \(x,y \in \chi^{\mathrm{N}}\) the longest common substring between encoded strings is \[ M_n^f(x,y) = \max \{ k:f(x)_i^{i + k - 1} = f(y)_j^{j + k - 1},\ 0 \le i,j \le n - k\}. \] Here it is proved an almost sure convergence of \(M_n^f\). The result is applied to generalize some earlier results for stochastic scrabble, stochastic noise and for analysis of the behaviour of the shortest distance between observed orbits of a dynamical system.