The Number of Distinct Subpalindromes in Random Words
| Autor: | Rubinchik, Mikhail, Shur, Arseny M. |
|---|---|
| Rok vydání: | 2015 |
| Předmět: | |
| Druh dokumentu: | Working Paper |
| DOI: | 10.3233/FI-2016-1366 |
| Popis: | 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}E(n,k)/\sqrt{n}$ does not exist for any $k\ge2$, $\liminf_{n\to\infty}E(n,k)/\sqrt{n}=\Theta(1)$, and $\limsup_{n\to\infty}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. Comment: 14 pages, 1 figure; submitted to FI (Special issue of RuFiDiM 2014) |
| Databáze: | arXiv |
| Externí odkaz: |
|