Computing hitting times via fluid approximation: application to the coupon collector problem

Nicolas GastarXiv 2011 · arXiv

Introduction

The classic "coupon collector problem" is a staple of probability theory, asking how many random draws are required to collect a full set of $N$ distinct items. While the basic version is well-understood, variations—such as collecting multiple sets or analyzing distributed randomized protocols—often lead to complex combinatorial challenges.

A powerful tool for analyzing large stochastic systems is the "fluid limit," where the average behavior of a system is modeled using a deterministic Ordinary Differential Equation (ODE). However, a fundamental gap exists: a finite stochastic system reaches its absorbing state in finite time, whereas its continuous ODE approximation only approaches equilibrium asymptotically, taking infinite time to reach it. This paper bridges this gap by formally linking finite hitting times to the convergence properties of fluid approximations.

Methodology: The $1/N$ Heuristic

The author models the generalized problem as a system of $N$ identical, independent Markov chains. To reconcile the difference between discrete completion and continuous convergence, the paper introduces a $1/N$ threshold.

Since the ODE takes infinite time to reach the exact absorbing state (where the proportion of completed chains equals 1), the author defines a threshold time $t_N$. This is the time required for the ODE to reach a distance of $1/N$ from equilibrium (i.e., a proportion of $1 - 1/N$). By utilizing discrete and continuous phase-type distributions, the author rigorously proves that this intuitive heuristic provides a tight bound for the actual stochastic hitting time.

Comparison of the stochastic process and its limiting ODE for $N=20$ and $N=1000$. The dashed line $y=1-1/N$ represents the threshold where the fluid approximation effectively 'completes'.

Spectral Properties and Hitting Time Bounds

A key insight of the research is that the asymptotic bounds of the hitting time are dictated by the spectral properties of the underlying Markov chain. Specifically, the constants in the hitting time bounds depend on the eigenvalue of the transition matrix with the greatest real part and its multiplicity.

For systems where the hitting time of a single chain is uniformly bounded, the author employs potential functions (Lyapunov-style drift analysis) to derive explicit, simplified bounds. This framework allows for a unified treatment of various coupon collector problems without the need for the "combinatorial gymnastics" typically required in such proofs.

Key Results and Applications

The paper establishes several significant bounds for the expected time $E[T_N]$ for all $N$ chains to reach the absorbing state:

  • General Bound: $E[T_N]$ is bounded by $c_1 N \log N + c_2 N \log \log N + O(N)$, where $c_1$ and $c_2$ are derived from the transition matrix eigenvalues.
  • Classic Recovery: The framework successfully recovers known results for collecting $T$ sets of $N$ coupons: $N(\log N + (T - 1) \log \log N + O(1))$.
  • Bounded Chains: If the hitting time is uniformly bounded by $T$ from any initial state, the bound tightens to $TN \log N + 2NT + 1$.

Beyond theoretical probability, these results have practical implications for distributed algorithms, such as calculating the convergence time for wireless radio channel allocation protocols among multiple users.

Limitations and Future Outlook

While the $1/N$ approach is robust, the simplified bounds (Theorems 3 and 4 in the paper) can be looser than the precise ODE-derived bounds because they occasionally ignore the specific geometry or topology of the Markov chain.

Future research may extend this $1/N$ distance approach to non-linear stochastic approximation algorithms. Such an extension would be invaluable for understanding extinction times in complex models, ranging from biological population dynamics to the eradication of epidemics in network environments.

Summary updated

Abstract

In this paper, we show how to use stochastic approximation to compute hitting time of a stochastic process, based on the study of the time for a fluid approximation of this process to be at distance 1/N of its fixed point. This approach is developed to study a generalized version of the coupon collector problem. The system is composed by N independent identical Markov chains. At each time step, one Markov chain is picked at random and performs one transition. We show that the time at which all chains have hit the same state is bounded by a N log N + b N log log N + O(N) where a and b are two constants depending on eigenvalues of the Markov chain.
BibTeX
@misc{gast2011computing,
  author = {Nicolas Gast},
  title = {{Computing hitting times via fluid approximation: application to the coupon collector problem}},
  year = {2011},
  eprint = {1107.3385},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1107.3385},
}
Figure