Omnibus sequences, coupon collection, and missing word counts (Q352894)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Omnibus sequences, coupon collection, and missing word counts |
scientific article |
Statements
Omnibus sequences, coupon collection, and missing word counts (English)
0 references
5 July 2013
0 references
Let \(A_n=(a_1,\dotsc,a_n)\) be a sequence of letters from some alphabet. It is called \(k\)-omni (omnibus) if any sequence of length \(k\) from this alphabet can be found as a subsequence of \(A_n\). A criterion is established for the \(k\)-omni property in terms of the coupon collector problem. The authors investigate behavior of the probability \(p_{n,k}\) that a random sequence of i.i.d. uniform variables \(A_n\) is \(k\)-omni as \(n\to\infty\) and \(k\to\infty\). Then, the number \(M_{n,k}\) of missing subsequences in \(\{A_n\}\) is investigated. It is shown that, for \(n/k=r=\mathrm{const}\), there is a threshold value for \(r\) at which a sudden change in the asymptotic behavior exists for \(P_{n,k}\) and \(M_{n,k}\). Applications to cryptography, randomness tests and linguistics are discussed.
0 references
coupon collection
0 references
extreme value distribution
0 references
asymptotic behavior
0 references