Omnibus sequences, coupon collection, and missing word counts (Q352894)

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.