Omnibus Sequences, Coupon Collection, and Missing Word Counts |
| |
Authors: | Sunil Abraham Greg Brockman Stephanie Sapp Anant P Godbole |
| |
Institution: | 1. Oxford University, Oxford, UK 2. Massachusetts Institute of Technology, Cambridge, MA, USA 3. University of California, Berkeley, CA, USA 4. East Tennessee State University, Johnson City, TN, USA
|
| |
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: | |
本文献已被 SpringerLink 等数据库收录! |
|