The Number of Distinct Subpalindromes in Random Words

Abstract

We prove that a random word of length n over a k-ary fixed alphabet contains, on expectation, $\Theta (\sqrt{n})$ distinct palindromic factors. We study this number of factors, E(n, k), in detail, showing that the limit ${\lim }_{n\to \infty }{\rm E}(n,k)/\sqrt{n}$ does not exist for any k ≥ 2, $\lim {\inf }_{n\to \infty }{\rm E}(n,k)/\sqrt{n}=\Theta (1)$, and $\lim {\sup }_{n\to \infty }{\rm E}(n,k)/\sqrt{n}=\Theta (\sqrt{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.