Header

UZH-Logo

Maintenance Infos

First occurrence in pairs of long words: a Penney-ante conjecture of Pevzner


Stark, D (1995). First occurrence in pairs of long words: a Penney-ante conjecture of Pevzner. Combinatorics, Probability & Computing, 4(3):279-285.

Abstract

Suppose X1,X2,⋯ is a sequence of independent and identically distributed random elements taking values in a finite set S of size |S|≥2 with probability distribution P(X=s)=p(s)>0 for s∈S. P. Pevzner [Kvantl 5 (1987), 4--15; per bibl.] has conjectured that for every probability distribution P there exists an N>0 such that for every word A with letters in S whose length is at least N, there exists a second word B of the same length as A, such that the event that B appears before A in the sequence X1,X2,⋯ has greater probability than that of A appearing before B. In this paper it is shown that a distribution P satisfies Pevzner's conclusion if and only if the maximum value of P, p, and the secondary maximum c satisfy the inequality c>p(1−p)/(1+p). For |S|=2 or |S|=3, the inequality is true and the conjecture holds. If c≤p(1−p)/(1+p), then the conjecture is true when A is not allowed to consist of pure repetitions of that unique element for which the distribution takes on its mode.

Abstract

Suppose X1,X2,⋯ is a sequence of independent and identically distributed random elements taking values in a finite set S of size |S|≥2 with probability distribution P(X=s)=p(s)>0 for s∈S. P. Pevzner [Kvantl 5 (1987), 4--15; per bibl.] has conjectured that for every probability distribution P there exists an N>0 such that for every word A with letters in S whose length is at least N, there exists a second word B of the same length as A, such that the event that B appears before A in the sequence X1,X2,⋯ has greater probability than that of A appearing before B. In this paper it is shown that a distribution P satisfies Pevzner's conclusion if and only if the maximum value of P, p, and the secondary maximum c satisfy the inequality c>p(1−p)/(1+p). For |S|=2 or |S|=3, the inequality is true and the conjecture holds. If c≤p(1−p)/(1+p), then the conjecture is true when A is not allowed to consist of pure repetitions of that unique element for which the distribution takes on its mode.

Statistics

Citations

Dimensions.ai Metrics

Altmetrics

Downloads

49 downloads since deposited on 29 Nov 2010
21 downloads since 12 months
Detailed statistics

Additional indexing

Item Type:Journal Article, refereed, original work
Communities & Collections:07 Faculty of Science > Institute of Mathematics
Dewey Decimal Classification:510 Mathematics
Scopus Subject Areas:Physical Sciences > Theoretical Computer Science
Physical Sciences > Statistics and Probability
Physical Sciences > Computational Theory and Mathematics
Physical Sciences > Applied Mathematics
Language:English
Date:1995
Deposited On:29 Nov 2010 16:28
Last Modified:29 Jul 2020 19:50
Publisher:Cambridge University Press
ISSN:0963-5483
OA Status:Green
Publisher DOI:https://doi.org/10.1017/S0963548300001656
Related URLs:http://www.zentralblatt-math.org/zbmath/search/?q=an%3A0839.60019

Download

Green Open Access

Download PDF  'First occurrence in pairs of long words: a Penney-ante conjecture of Pevzner'.
Preview
Content: Published Version
Language: English
Filetype: PDF (Nationallizenz 142-005)
Size: 340kB
View at publisher