Periods and borders of random words

DOI10.4230/LIPICS.STACS.2016.44zbMATH Open1388.68244arXiv1509.05240WikidataQ105468635 ScholiaQ105468635MaRDI QIDQ4601896FDOQ4601896

Authors: Štěpán Holub, Jeffrey Shallit 

Publication date: 24 January 2018

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.

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

Recommendations

• Maximal unbordered factors of random strings
• Maximal unbordered factors of random strings
• 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

zbMATH Keywords

periodrandom wordword border

Mathematics Subject Classification ID

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

Cited In (13)

• A natural bijection for contiguous pattern avoidance in words
• Borders, palindrome prefixes, and square prefixes
• Density dichotomy in random words
• The expected number of runs in a word
• The recurrence function of a random Sturmian word
• Fully bordered words
• On the shortest common superstring of NGS reads
• HV-Palindromes in Two-Dimensional Words
• The number of distinct subpalindromes in random words
• Maximal unbordered factors of random strings
• Self-alignments in words and their applications
• Dyck words, lattice paths, and abelian borders
• Title not available (Why is that?)

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)