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, Θ(√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.