×

Omnibus sequences, coupon collection, and missing word counts. (English) Zbl 1278.60016

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.

MSC:

60C05 Combinatorial probability
94A60 Cryptography
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Adler I, Ross S (2001) The coupon subset collection problem. J Appl Probab 38:737-746 · Zbl 0994.60007 · doi:10.1239/jap/1005091036
[2] Adler I, Oren S, Ross S (2003) The coupon collector’s problem revisited. J Appl Probab 40:513-518 · Zbl 1030.60006 · doi:10.1239/jap/1053003560
[3] Aldous D (1989) Probability approximations via the poisson clumping heuristic. Springer, New York · Zbl 0679.60013 · doi:10.1007/978-1-4757-6283-9
[4] Badus A, Godbole A, LeDell E, Lents N (2003) Some contributions to the coupon collector problem. In: Extended abstract, 2003 permutation patterns conference, Dunedin, New Zealand. Manuscript in preparation · Zbl 0092.35502
[5] Barbour A, Holst L (1989) Some applications of the Stein-Chen method for proving Poisson convergence. Adv Appl Probab 21:74-90 · Zbl 0673.60023 · doi:10.2307/1427198
[6] Barbour A, Holst L, Janson S (1992) Poisson approximation. Oxford University Press, New York · Zbl 0746.60002
[7] Erdős P, Rényi A (1961) On a classical problem of probability theory. Magy Tud Akad Mat Kut Intez Közl 6:215-220 · Zbl 0102.35201
[8] Feller W (1968) An introduction to probability theory and its applications, vol 1. Wiley, New York · Zbl 0155.23101
[9] Flajolet P, Sedgewick R (2009) Analytic combinatorics. Cambridge University Press, Cambridge · Zbl 1165.05001 · doi:10.1017/CBO9780511801655
[10] Foata D, Zeilberger D (2003) The collector’s brotherhood problem using the Newman-Shepp symbolic method. Algebra Univers 49:387-395 · Zbl 1091.05004 · doi:10.1007/s00012-003-1815-3
[11] Foata D, Han GN, Lass B (2001) Les nombres hyperharmoniques et la fratrie du collectionneur de vignettes. Sém Lothar Combin 47:B47a. http://www.combinatorics.org/Volume_15/PDF/v15i1n31.pdf · Zbl 0981.05008
[12] Gould HW (1972) Combinatorial identities. Morgantown, WV · Zbl 0241.05011
[13] Holst L (1986) On birthday, collectors. Occupancy and other classical urn problems. Int Stat Rev 54:15-27 · Zbl 0594.60014 · doi:10.2307/1403255
[14] Kendall M, Smith BB (1938) Randomness and random sampling numbers. J R Stat Soc 101:147-166 · doi:10.2307/2980655
[15] Kuonen D (2001) Computer-intensive statistical methods: saddlepoint approximations with applications in bootstrap and robust inference. Doctoral dissertation, École Polytechnique Fédérale, Lausanne · Zbl 0994.60007
[16] Martinez S (2004) Some bounds on the coupon collector problem. Random Struct Algorithms 25:208-226 · Zbl 1063.60008 · doi:10.1002/rsa.20019
[17] May R (2008) Coupon collecting with quotas. Electron J Comb 15(31) · Zbl 1182.05005
[18] Myers A, Wilf H (2003) Some new aspects of the coupon collector’s problem. SIAM J Discrete Math 17:1-17 · Zbl 1038.05002 · doi:10.1137/S0895480102403076
[19] Nadarajah S (2008) Exact distribution of the linear combination of p Gumbel random variables. Int J Comp Math 85:1355-1362 · Zbl 1143.62306 · doi:10.1080/00207160701536370
[20] Neal P (2008) The generalised coupon collector problem. J Appl Probab 45:621-629 · Zbl 1151.60315 · doi:10.1239/jap/1222441818
[21] Newman D, Shepp L (1960) The double dixie cup problem. Am Math Mon 67:58-61 · Zbl 0092.35502 · doi:10.2307/2308930
[22] Steele J (1997) Probability theory and combinatorial optimization. SIAM, Philadelphia · Zbl 0916.90233 · doi:10.1137/1.9781611970029
[23] Von Schelling H (1954) Coupon collecting for unequal probabilities. Am Math Mon 61:306-311 · Zbl 0055.37003 · doi:10.2307/2307466
[24] Zeilberger D (2001) How many singles, doubles, triples, etc. should the coupon collector expect? http://www.math.rutgers.edu/ zeilberg/mamarim/mamarimPDF/coupon.pdf. Accessed 16 Aug 2011 · Zbl 1091.05004
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.