文章基本信息

标题：Periods and Borders of Random Words
本地全文：下载
作者：v{S}}tep{\'a}n Holub ; Jeffrey Shallit
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2016
卷号：47
页码：44:1-44:10
DOI：10.4230/LIPIcs.STACS.2016.44
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：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.
关键词：random word; period; word border