Mean Cover Times for Coupon Collectors and Star Graphs

  • Erol Pekoz
  • Sheldon M. Ross
Part of the International Series in Operations Research & Management Science book series (ISOR, volume 19)


Suppose that there are m distinct types of coupons and that each coupon collected is type; with probability P j , j = 1, ⋯, m. Let N k denote the number of coupons one needs to collect in order to have at least one of each of k distinct types. We are interested in using simulation to efficiently estimate the mean and variance of N k , for each k = 1, ⋯, m. Whereas we could simulate the successive types of coupons obtained and then utilize the observed values of N k over many runs to obtain our estimates, we will attempt to obtain estimators having smaller variances than these raw estimators.


Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.


  1. [1]
    Blom, G., and Sandell, D. Cover times for random walks on graphs. Math. Scientist 17, 111–119, 1992.MathSciNetzbMATHGoogle Scholar
  2. [2]
    Flajolet, Gardy, and Thimonier, “Birthday paradox, coupon collectors, caching algorithms, and self organizing search.” Discrete Appl. Math. 39, 207–229, 1992.MathSciNetzbMATHCrossRefGoogle Scholar
  3. [3]
    Nath, H. B. Waiting time in the coupon collector’s problem. Austral. J. Stat. 15, 132–135, 1973.MathSciNetzbMATHCrossRefGoogle Scholar
  4. [4]
    Palacios, J. L. Cover times for stars. Math. Scientist 18, 103–107, 1994.MathSciNetGoogle Scholar
  5. [5]
    Ross, S. M. Simulation. Academic Press, Cambridge, 1997.zbMATHGoogle Scholar
  6. [6]
    Stadje, W. The collector’s problem with group drawings. Adv. Appl. Prob. 22, 866–874, 1990.MathSciNetzbMATHCrossRefGoogle Scholar

Copyright information

© Springer Science+Business Media New York 1999

Authors and Affiliations

  • Erol Pekoz
  • Sheldon M. Ross

There are no affiliations available

Personalised recommendations