Periods and borders of random words

DOI10.4230/LIPICS.STACS.2016.44MaRDI QIDQ4601896zbMATH OpenWikidataFDO

Authors Štěpán Holub, Jeffrey Shallit

Publication date 24 January 2018

Full work available at URL https://arxiv.org/abs/1509.05240

zbMATH Keywords

periodrandom wordword border

Mathematics Subject Classification ID

Permutations, words, matrices (05A05) Combinatorics on words (68R15)

Abstract: We investigate the behavior of the periods and border lengths of random words over a fixed alphabet. We show that the asymptotic probability that a random word has a given maximal border length $k$ is a constant, depending only on $k$ and the alphabet size $ell$. We give a recurrence that allows us to determine these constants with any required precision. This also allows us to evaluate the expected period of a random word. For the binary case, the expected period is asymptotically about $n-1.641$. We also give explicit formulas for the probability that a random word is unbordered or has maximum border length one.

Recommendations

• The number of distinct subpalindromes in random words
• Threshold properties of some periodic factors of words over a finite alphabet
• The expected number of runs in a word

Cited in

(12)

• The expected number of runs in a word
• The number of distinct subpalindromes in random words
• scientific article; zbMATH DE number 1400046 (Why is no real title available?)
• Density dichotomy in random words
• The recurrence function of a random Sturmian word
• Self-alignments in words and their applications
• On the shortest common superstring of NGS reads
• Borders, palindrome prefixes, and square prefixes
• HV-Palindromes in Two-Dimensional Words
• Fully bordered words
• A natural bijection for contiguous pattern avoidance in words
• Dyck words, lattice paths, and abelian borders

This page was built for publication: Periods and borders of random words

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4601896)