Collecting Coupons with Random Initial Stake

Benjamin Doerr, Carola DoerrarXiv 2013 · OpenReview

TL;DR

This paper precisely analyzes a variation of the classic coupon collector problem where the collector starts with a random subset of coupons. They show that this "random initial stake" scenario is surprisingly about half a round faster than starting with a fixed, known subset of half the coupons. This finding has direct implications for the runtime analysis of randomized local search algorithms optimizing monotonic functions.

What Problem Does This Paper Address?

The classic coupon collector problem asks for the expected number of draws to collect a full set of $n$ distinct coupons. This problem has a well-understood solution involving harmonic numbers, resulting in an expected $nH_n$ draws. However, in many practical scenarios, especially in the context of randomized search heuristics, the starting state isn't a clean slate. This paper tackles a variation where the collector begins with a random set of coupons, where each of the $n$ types is present with a probability of 1/2, independently. The core question is: how does this random starting point affect the expected number of draws needed to complete the collection, and how does it compare to starting with a known, fixed number of coupons? This is particularly relevant for analyzing algorithms like Randomized Local Search (RLS) which, when applied to monotonic functions, can be mapped to this coupon collector variant.

Methods

The authors provide a rigorous mathematical analysis of the coupon collector problem with a random initial stake. They leverage the properties of harmonic numbers and binomial distributions. The proof strategy involves:

  • Decomposition by initial state: The expected runtime is broken down based on the number of distinct coupons the collector starts with, using the binomial distribution of the initial state.
  • Symmetry argument: For even $n$, they exploit the symmetry of the binomial distribution, showing that the average runtime for starting with $n/2 + a$ or $n/2 - a$ coupons doesn't deviate significantly from starting with exactly $n/2$ coupons. This is quantified by defining an "error term" $\epsilon_a$.
  • Bounding the deviation: The core of the proof involves bounding the sum of these deviations multiplied by their probabilities. This is achieved by carefully estimating $\epsilon_a$ from both below and above, using inequalities and properties of variance.
  • Handling odd $n$: The proof for odd $n$ is shown to be very similar, adapting the definitions of the initial state and the deviation terms.

The analysis is precise, aiming for bounds that are sharp up to additive $o(1)$ terms, meaning the dominant term is accurately captured.

Datasets

Not discussed in the paper. The paper is a theoretical analysis of a probabilistic problem and does not involve empirical evaluation on datasets.

Key Insights and Ideas

  • The "random initial stake" is faster: The most striking insight is that starting with a random set of coupons (where each type is present with probability 1/2) leads to a faster expected completion time compared to starting with a fixed set of $n/2$ coupons.
  • The speedup is precisely 1/2: The paper quantifies this speedup as an additive term of $-1/2$ in the expected number of rounds, leading to the formula $nH_{n/2} - 1/2 \pm o(1)$. This is a surprisingly clean and specific result.
  • Connection to Randomized Local Search: The paper highlights a direct mapping between this coupon collector variant and the runtime analysis of Randomized Local Search (RLS) on monotonic functions. This means the theoretical result directly translates to a more precise understanding of how quickly RLS finds optimal solutions for a broad class of problems.
  • Symmetry is key: The proof heavily relies on the symmetry of the binomial distribution for the initial state, allowing for elegant bounding techniques.

Key Results

The main result is a precise formula for the expected number of rounds in the coupon collector problem with a random initial stake:

  • For even $n$, the expected number of rounds is $nH_{n/2} - 1/2 \pm o(1)$.
  • For odd $n$, the expected number of rounds is $nH_{\lfloor n/2 \rfloor} + \frac{1}{2}H_{\lceil n/2 \rceil} - 1/2 \pm o(1)$. (Note: The paper uses $H_{n/2}$ notation for both even and odd cases, with specific definitions provided).

This is equivalent to $n \ln(n/2) + \gamma n + 1/2 \pm o(1)$, where $\gamma$ is the Euler-Mascheroni constant.

This result implies that the expected number of iterations for Randomized Local Search to find the optimum of any monotonic function on bit-strings of length $n$ is $nH_{n/2} - 1/2 \pm o(1)$.

Limitations and Future Work

  • Asymptotic analysis: The results are asymptotic, expressed in terms of $o(1)$ terms. While this provides a very precise dominant term, the exact behavior for small $n$ might differ slightly.
  • Generalization to other initial distributions: The paper focuses on the specific case where each coupon type is present with probability 1/2. It would be interesting to explore how the expected runtime changes for different initial probability distributions of coupons.
  • Other search heuristics: While the paper connects to RLS, exploring the implications for other randomized search heuristics that might exhibit similar "random initial state" behaviors could be a future direction.
  • Non-monotonic functions: The current result is specific to monotonic functions. Analyzing RLS or similar algorithms on more complex, non-monotonic fitness landscapes remains a significant challenge.

Summary updated

Abstract

Motivated by a problem in the theory of randomized search heuristics, we give a very precise analysis for the coupon collector problem where the collector starts with a random set of coupons (chosen uniformly from all sets). We show that the expected number of rounds until we have a coupon of each type is $nH_{n/2} - 1/2 \pm o(1)$, where $H_{n/2}$ denotes the $(n/2)$th harmonic number when $n$ is even, and $H_{n/2}:= (1/2) H_{\lfloor n/2 \rfloor} + (1/2) H_{\lceil n/2 \rceil}$ when $n$ is odd. Consequently, the coupon collector with random initial stake is by half a round faster than the one starting with exactly $n/2$ coupons (apart from additive $o(1)$ terms). This result implies that classic simple heuristic called \emph{randomized local search} needs an expected number of $nH_{n/2} - 1/2 \pm o(1)$ iterations to find the optimum of any monotonic function defined on bit-strings of length $n$.
BibTeX
@misc{doerr2013collecting,
  author = {Benjamin Doerr and Carola Doerr},
  title = {{Collecting Coupons with Random Initial Stake}},
  year = {2013},
  eprint = {1308.6384},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1308.6384},
}

Loading related content...

Figure