Omnibus Sequences, Coupon Collection, and Missing Word Counts

Creator(s)

Sunil Abraham, University of Oxford
Greg Brockman, Massachusetts Institute of Technology
Stephanie Sapp, University of California, Berkeley
Anant P. Godbole, East Tennessee State UniversityFollow

Document Type

Article

Publication Date

6-1-2013

Description

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 E(M).

Citation Information

Abraham, Sunil; Brockman, Greg; Sapp, Stephanie; and Godbole, Anant P.. 2013. Omnibus Sequences, Coupon Collection, and Missing Word Counts. Methodology and Computing in Applied Probability. Vol.15(2). 363-378. https://doi.org/10.1007/s11009-011-9247-6 ISSN: 1387-5841