The Number of Distinct Subpalindromes in Random Words
Mikhail Rubinchik, Arseny M. Shur · Fundamenta Informaticae · 2016
We prove that a random word of length n over a k-ary fixed alphabet contains, on expectation, Θ(n) distinct palindromic factors. We study this number of factors, E(n, k), in detail, showing that the limit limn→∞Ε(n,k)/n does not exist for any k ≥ 2, liminfn→∞Ε(n,k)/n=Θ(1), and limsupn→∞Ε(n,k)/n=Θ(k ). Such a complicated behaviour stems from the asymmetry between the palindromes of even and odd length. We show that a similar, but much simpler, result on the expected number of squares in random words holds. We also provide some experimental data on the number of palindromic factors in random words.