How Many IID Samples does it Take to See all the Balls in a Box?

Abstract

Suppose a box contains m balls, numbered from 1 to m. A random number of balls are drawn from the box, their numbers are noted, and the balls are then returned to the box. This is done repeatedly, with the sample sizes being iid. Let X be the number of samples needed to see all the balls. This paper derives a simple but typically very accurate approximation for EX in terms of the sample size distribution. The justification of the approximation formula uses Wald's identity and Markov-chain coupling.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Oct 26, 1992
Accession Number
ADA258773

Entities

People

  • Thomas M. Sellke

Organizations

  • Stanford University

Tags

Communities of Interest

  • Materials and Manufacturing Processes

DTIC Thesaurus Topics

  • Absorption
  • Accumulators
  • Couplings
  • Identities
  • Markov Chains
  • Military Research
  • Probability
  • Random Variables
  • Sampling
  • Stationary
  • Stochastic Processes
  • Transitions
  • United States
  • United States Government
  • Universities

Fields of Study

  • Mathematics

Readers

  • Computational Modeling and Simulation
  • Linear Algebra
  • Regression Analysis.