Maximal length of common words among random letter sequences (Q1103263)

Consider \(K_{r,s}(N)\), the length of the longest common word in at least r of s random letter sequences of length N based upon a finite alphabet. Under certain assumptions on the underlying sequences including stationarity, positivity and uniform mixing, the authors' main result establishes an interesting extremal type limit law (as \(N\to \infty)\) for \[ K_{r,s}(N)-(r \log N/(-\log \lambda)), \] where \(\lambda\) is uniquely determined by an exponential behaviour of the local match distribution. Some applications and possible extensions to related results are briefly outlined.