Omnibus sequences, coupon collection, and missing word counts

DOI10.1007/S11009-011-9247-6MaRDI QIDQ352894zbMATH OpenOpenAlexFDO

Authors Sunil Abraham, Greg Brockman, Stephanie Sapp, Anant P. Godbole

Publication date 5 July 2013

Published in Methodology and Computing in Applied Probability (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/0905.4517

zbMATH Keywords

asymptotic behaviorextreme value distributioncoupon collection

Mathematics Subject Classification ID

Cryptography (94A60) Combinatorial probability (60C05)

Abstract: An {it Omnibus Sequence} of length $n$ is one that has each possible "message" of length $k$ embedded in it as a subsequence. We study various properties of Omnibus Sequences in this paper, making connections, whenever possible, to the classical coupon collector problem.

Recommendations

• On the Distribution of the Number of Missing Words in Random Texts
• Universal arrays
• Maximal length of common words among random letter sequences
• A new method of approximating the probability of matching common words in multiple random sequences
• Exact distribution of word occurrences in a random sequence of letters

Cites work

• scientific article; zbMATH DE number 3167451 (Why is no real title available?)
• scientific article; zbMATH DE number 52632 (Why is no real title available?)
• scientific article; zbMATH DE number 3249395 (Why is no real title available?)
• scientific article; zbMATH DE number 3380631 (Why is no real title available?)
• scientific article; zbMATH DE number 964350 (Why is no real title available?)
• Analytic combinatorics
• Coupon Collecting for Uneqal Probabilities
• Coupon collecting with quotas
• Exact distribution of the linear combination ofpGumbel random variables
• On Birthday, Collectors', Occupancy and Other Classical Urn Problems
• Probability approximations via the Poisson clumping heuristic
• Some New Aspects of the Coupon Collector's Problem
• Some applications of the Stein-Chen method for proving Poisson convergence
• Some bounds on the coupon collector problem
• The Double Dixie Cup Problem
• The Generalised Coupon Collector Problem
• The collector's brotherhood problem using the Newman-Shepp symbolic method
• The coupon subset collection problem
• The coupon-collector's problem revisited
• The hyperharmonic numbers and the phratry of the coupon collector

Cited in

(5)

• Limit theorem for the Robin Hood game
• Waiting time distribution for the emergence of superpatterns
• Some results on superpatterns for preferential arrangements
• Universal cycle packings and coverings for \(k\)-subsets of an \(n\)-set
• Preferential arrangement superpatterns

This page was built for publication: Omnibus sequences, coupon collection, and missing word counts

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q352894)