Optimal sampling strategies in the coupon collectors problem with unknown population size

Tezcan, T and Dobson, G (2015) Optimal sampling strategies in the coupon collectors problem with unknown population size. Annals of Operations Research, 233 (1). pp. 77-99. ISSN 0254-5330

Abstract

In doing a six-sigma analysis of a process one must first determine the set of possible factors that potentially drive the response of interest. This stage of the the work, known as process mapping, is time consuming. Spending too much time on it wastes investigators and employees time. Yet, spending too little time may result in failing to uncover important factors that drive the process. We model this situation as a general coupon collector’s problem with N distinct coupons, where the exact value of N is not known. Our objective is to devise effective strategies to minimize the total cost incurred due to sampling in addition to the cost of unidentified coupons when the collector stops sampling. We propose a policy based on an asymptotic analysis when N is large and prove that the proposed policy is asymptotically optimal. We also illustrate the effectiveness of this policy with numerical experiments.