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.

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.

## Citations

## Altmetrics

## Additional indexing

Item Type: | Journal Article, refereed, original work |
---|---|

Communities & Collections: | 07 Faculty of Science > Institute of Mathematics |

Dewey Decimal Classification: | 510 Mathematics |

Language: | English |

Date: | 1995 |

Deposited On: | 29 Nov 2010 16:28 |

Last Modified: | 05 Apr 2016 13:27 |

Publisher: | Cambridge University Press |

ISSN: | 0963-5483 |

Publisher DOI: | https://doi.org/10.1017/S0963548300001656 |

Related URLs: | http://www.zentralblatt-math.org/zbmath/search/?q=an%3A0839.60019 |

## Download

Full text not available from this repository.View at publisher

TrendTerms displays relevant terms of the abstract of this publication and related documents on a map. The terms and their relations were extracted from ZORA using word statistics. Their timelines are taken from ZORA as well. The bubble size of a term is proportional to the number of documents where the term occurs. Red, orange, yellow and green colors are used for terms that occur in the current document; red indicates high interlinkedness of a term with other terms, orange, yellow and green decreasing interlinkedness. Blue is used for terms that have a relation with the terms in this document, but occur in other documents.

You can navigate and zoom the map. Mouse-hovering a term displays its timeline, clicking it yields the associated documents.