2026-07-23T00:21:45Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:5745 2024-03-06T10:36:59Z ddc:004 open_access

Periods and Borders of Random Words Holub, Štepán Shallit, Jeffrey random word period word border 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 l. 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Štepán Holub and Jeffrey Shallit 2016 Is Part Of LIPIcs, Volume 47, 33rd Symposium on Theoretical Aspects of Computer Science (STACS 2016) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.STACS.2016.44 urn:nbn:de:0030-drops-57453 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2016.44 eng https://creativecommons.org/licenses/by/3.0/legalcode