Omnibus Sequences, Coupon Collection, and Missing Word Counts

Sunil Abraham (), Greg Brockman (), Stephanie Sapp () and Anant P. Godbole ()
Additional contact information
Sunil Abraham: Oxford University
Greg Brockman: Massachusetts Institute of Technology
Stephanie Sapp: University of California
Anant P. Godbole: East Tennessee State University

Methodology and Computing in Applied Probability, 2013, vol. 15, issue 2, 363-378

Abstract: Abstract In this paper, we study the properties of k-omnisequences of length n, defined to be strings of length n that contain all strings of smaller length k embedded as (not necessarily contiguous) subsequences. We start by proving an elementary result that relates our problem to the classical coupon collector problem. After a short survey of relevant results in coupon collection, we focus our attention on the number M of strings (or words) of length k that are not found as subsequences of an n string, showing that there is a gap between the probability threshold for the emergence of an omnisequence and the zero-infinity threshold for ${\mathbb E}(M)$ .

Keywords: Coupon collection; Omnibus sequences; Extreme value distribution; 60C05 (search for similar items in EconPapers)
Date: 2013
References: View complete reference list from CitEc
Citations: View citations in EconPapers (2)

Downloads: (external link)
http://link.springer.com/10.1007/s11009-011-9247-6 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:metcap:v:15:y:2013:i:2:d:10.1007_s11009-011-9247-6

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/11009

DOI: 10.1007/s11009-011-9247-6

Access Statistics for this article

Methodology and Computing in Applied Probability is currently edited by Joseph Glaz

More articles in Methodology and Computing in Applied Probability from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().