Omnibus sequences, coupon collection, and missing word counts

DOI10.1007/S11009-011-9247-6zbMATH Open1278.60016arXiv0905.4517OpenAlexW2084356989MaRDI QIDQ352894FDOQ352894

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)

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.

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

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

zbMATH Keywords

asymptotic behaviorextreme value distributioncoupon collection

Mathematics Subject Classification ID

Cryptography (94A60) Combinatorial probability (60C05)

Cites Work

• Title not available (Why is that?)
• Probability approximations via the Poisson clumping heuristic
• Analytic combinatorics
• Title not available (Why is that?)
• Title not available (Why is that?)
• Exact distribution of the linear combination ofpGumbel random variables
• Title not available (Why is that?)
• The Double Dixie Cup Problem
• Title not available (Why is that?)
• Coupon Collecting for Uneqal Probabilities
• Coupon collecting with quotas
• The collector's brotherhood problem using the Newman-Shepp symbolic method
• The coupon subset collection problem
• Some bounds on the coupon collector problem
• The Generalised Coupon Collector Problem
• On Birthday, Collectors', Occupancy and Other Classical Urn Problems
• Some applications of the Stein-Chen method for proving Poisson convergence
• The coupon-collector's problem revisited
• Some New Aspects of the Coupon Collector's Problem
• 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)