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

reportActive / Technical Report | Accession Number: ADA258773 | Open PDF

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 Walds identity and Markov-chain coupling.

Author(s):
Sellke, Thomas M.
Author Organization(s):
STANFORD UNIV CA DEPT OF STATISTICS
Descriptive Note:
Technical rept.
Pagination:
0026

Security Markings

DOCUMENT & CONTEXTUAL SUMMARY

Distribution:
Approved For Public Release
Distribution Statement:
Approved For Public Release; Distribution Is Unlimited.

RECORD

Collection: TR
Identifying Numbers
Report Number(s):
TR-460
Contract/Grant Number(s):
N00014-92-J-1264
Monitor Series:
ONR
 Subject Terms
Joint Capability Areas:
JCA_1_Force Support; JCA_5_Command and Control; JCA_5.3_Planning; JCA_1.3_Human Capital Management; JCA_1.2_Force Preparation; JCA_1.3.2_Personnel Management
Communities of Interest:
Materials and Manufacturing Processes
Descriptor(s):
*STATISTICAL SAMPLES, DISTRIBUTION, PROBABILITY, NUMBERS, IDENTITIES, COUPLINGS, CHAINS, BOXES
Field(s)/Group(s):
Statistics and Probability
Keyword(s):
BALLS, WUNR042267
Report Date:
1992 Oct 26