Hostname: page-component-586b7cd67f-2brh9 Total loading time: 0 Render date: 2024-11-24T06:48:02.200Z Has data issue: false hasContentIssue false
  • English
  • Français

The collector's problem with group drawings

Published online by Cambridge University Press:  01 July 2016

Wolfgang Stadje
Wolfgang Stadje*
Affiliation:
University of Osnabrück
*
∗Postal address: Fachbereich Mathematik/Informatik, Universität Osnabrück, Albrechtstrasse 28, 4500 Osnabrück, W. Germany.
Get access Rights & Permissions [Opens in a new window]

Abstract

We consider sampling with replacement of equiprobable groups of a fixed size m from a finite population S. Given a subset A ⊂ S, the distributions of (a) the number of distinct elements of A in a sample of size k and (b) the sample size necessary to obtain at least say n elements of A are given. Neat formulas are given especially for the expected values of these, as well as of some related random variables. Further we derive an optimal strategy to collect all elements of S under the assumptions that sampling one group costs α monetary units and that it is possible to purchase the elements which are missing at the end of the sampling procedure at a price of β > α/m per element.

Keywords

SAMPLING WITH REPLACEMENTOPTIMAL COLLECTING STRATEGY
Type
Research Article
Information
Advances in Applied Probability , Volume 22 , Issue 4 , December 1990 , pp. 866 - 882
Copyright
Copyright © Applied Probability Trust 1990 

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

Barbour, A. D. and Holst, L. (1989) Some applications of the Stein-Chen method for proving Poisson convergence. Adv. Appl. Prob. 21, 74–89.CrossRefGoogle Scholar
Baum, L. E. and Billingsley, P. (1965) Asymptotic distributions for the coupon collector's problem. Ann. Math. Statist. 36, 1835–1839.CrossRefGoogle Scholar
Boyce, W. M. (1973) On a simple optimal stopping problem. Discrete Math. 5, 297–312.CrossRefGoogle Scholar
Brayton, R. K. (1963) On the asymptotic behavior of the number of trials necessary to complete a set with random selection. J Math. Anal. Appl. 7, 31–61.CrossRefGoogle Scholar
Chen, R. and Hwang, F. K. (1984) On the values of an (m, p) urn. Congr. Numer. 41, 75–84.Google Scholar
Chen, W. C. and Starr, N. (1980) Optimal stopping in an urn. Ann. Prob. 8, 451–469.CrossRefGoogle Scholar
Darling, D. A. (1986) Convergence rates for iterative solutions to optimal stopping problems. IMS Lecture Notes and Monographs Ser. 8, Inst. Math. Statist., Hayward, CA, 18–28.CrossRefGoogle Scholar
Eicker, P. J., Siddiqui, M. M. and Mielke, P. W. Jr. (1972) A matrix occupancy problem. Ann. Math. Statist. 43, 988–996.CrossRefGoogle Scholar
Euler, L. (1785) Solutio quarundam quaestionum difficiliorum in calculo probabilium. Opuscula Analytica , Vol. 2, 331–346.Google Scholar
Gittelsohn, A. M. (1969) An occupancy problem. Amer. Statist. 23, 11–12.Google Scholar
Harris, B., Marden, M. and Park, C. J. (1987) The distribution of the number of empty cells in a generalized random allocation scheme. In Random Graphs '85, Ann. Discrete Math. 33, ed. Karonski, M. and Palka, Z., North-Holland, Amsterdam, 77–90.Google Scholar
Holst, L. (1971) Limit theorems for some occupancy and sequential occupancy problems. Ann. Math. Statist. 42, 1671–1680.CrossRefGoogle Scholar
Holst, L. (1972) Asymptotic normality in a generalized occupancy problem. Z. Wahrscheinlichkeitsth. 21, 109–120.CrossRefGoogle Scholar
Holst, L. (1980) On matrix occupancy, committee, and capture-recapture problems. Scand. J. Statist. 7, 139–146.Google Scholar
Holst, L. (1986) On birthday, collectors', occupancy, committee and other classical urn problems. Internat. Statist. Rev. 54, 15–27.CrossRefGoogle Scholar
Johnson, N. L. and Kotz, S. (1977) Urn Models and Their Application . Wiley, New York.Google Scholar
Kolchin, V. F., Sevast'Yanov, B. A. and Chistyakov, V. P. (1978) Random Allocations. Winston, Washington D.C.Google Scholar
Laplace, P. S. (1774) Mémoire sur les suites récurro-récurrentes et leurs usages dans la théorie des hasards. Mém. Acad. Roy. Sci. Paris , 6, 353–371.Google Scholar
Laplace, P. S. (1812) Théorie Analytique des Probabilités . Courcier, Paris.Google Scholar
Majumdar, A. A. K. (1983) Optimal stopping based on success runs for an urn with three types of balls. Ganit 3, 1–30.Google Scholar
Majumdar, A. A. K. (1984a) Optimal stopping for plus-cancel urn problem with random termination. Ganit 4, 1–13.Google Scholar
Majumdar, A. A. K. (1984b) Optimal stopping based on success runs for an urn with three types of balls under drawings with replacement. Ganit 4, 75–86.Google Scholar
Majumdar, A. A. K. and Sakaguchi, M. (1983a) Optimal stopping for the urn problem based on success runs. J. Inform. Optim. Sci. 4, 1–20.Google Scholar
Majumdar, A. A. K. and Sakaguchi, M. (1983b) Optimal stopping for the urn problem with random termination. Math. Japan. 28, 271–285.Google Scholar
Mallet, (1772) Sur le calcul des probabilités. Acta Helvetica 7, 133–163.Google Scholar
Mantel, N. (1974) Approaches to a health research occupancy problem. Biometrics 30, 355–362.Google ScholarPubMed
Mantel, N. and Pasternack, B. (1968) A class of occupancy problems. Amer. Statist. 22, 23–24.Google Scholar
Mikhailov, V. G. (1977a) A Poisson limit theorem in a scheme for group allocation of particles. Theory Prob. Appl. 22, 152–156.CrossRefGoogle Scholar
Mikhailov, V. G. (1977b) An estimate for the rate of convergence to the Poisson distribution in group allocation of particles. Theory Prob. Appl. 22, 554–562.CrossRefGoogle Scholar
Mikhailov, V. G. (1980) Asymptotic normality of the number of empty cells for group allocation of particles. Theory Prob. Appl. 25, 82–90.CrossRefGoogle Scholar
Mikhailov, V. G. (1981) Convergence to a multi-dimensional normal law in an equiprobable scheme for group allocation of particles. Math. USSR-Sb. 39, 145–168.CrossRefGoogle Scholar
Mielke, P. W. and Siddiqui, M. M. (1965) A combinatorial test for independence of dichotomous responses. J. Am. Statist. Assoc. 60, 437–441.CrossRefGoogle Scholar
Moivre, A. de (1711) De mensura sortis, seu, de probabilitate eventuum in ludis a casu fortuito pendentibus. Phil. Trans. Roy. Soc. London A 27, 213–264.Google Scholar
Moivre, A. de (1718) The Doctrine of Chances: or, a Method of Calculating the Probabilities of Events in Play . London. Reprint of the posthumous third edition by Chelsea, New York, 1967.Google Scholar
Nath, H. B. (1973) Waiting time in the coupon-collector's problem. Austral. J. Statist. 15, 132–135.CrossRefGoogle Scholar
Nath, H. B. (1974) On the collector's sequential sample size. Trab. Estad. 25, 85–88.CrossRefGoogle Scholar
Park, C. J. (1981) On the distribution of the number of unobserved elements when m-samples of size n are drawn from a finite population. Comm. Statist., A—Theory Methods 10, 371–383.CrossRefGoogle Scholar
Pólya, G. (1930) Eine Wahrscheinlichkeitsaufgabe in der Kundenwerbung. Z. Angew. Math. Mech. 10, 96–97.CrossRefGoogle Scholar
Renyi, A. (1962) Three new proofs and a generalization of a theorem of Irving Weiss. Publ. Math. Hung. Acad. Sci. 7, 203–214.Google Scholar
Rosén, B. (1969) Asymptotic normality in a coupon collector's problem. Z. Wahrscheinlickeitsth. 13, 256–279.CrossRefGoogle Scholar
Rosén, B. (1970) On the coupon collector's waiting time. Ann. Math. Statist. 41, 1952–1969.CrossRefGoogle Scholar
Samuel-Cahn, E. (1974) Asymptotic distribution for occupancy and waiting time problems with positive probability of falling through the cells. Ann. Prob. 2, 515–521.CrossRefGoogle Scholar
Sevastyanov, B. A. (1966) Limit theorems in a scheme for allocation of particles in cells. Theory Prob. Appl. 11, 614–619.CrossRefGoogle Scholar
Sprott, D. A. (1969) A note on a class of occupancy problems. Amer. Statist. 23, 12–13.Google Scholar
Stadje, W. (1989) Die Wartezeitverteilung für ein verallgemeinertes Sammlerproblem. Did. d. Math. 17, 313–320.Google Scholar
Todhunter, I. (1865) A History of the Mathematical Theory of Probability. Cambridge. Unaltered reprint of the first edition by Chelsea, New York, 1965.Google Scholar
Treiber, D. (1988) Die mittlere Wartezeit, bis jede mögliche Gewinnzahl im Lotto mindestens einmal gezogen ist. Praxis. d. Math. 30, 409–413.Google Scholar
Trembley, (1794/95) Recherches sur une question relative au calcul des probabilités. Mém. Acad. Berlin , 69–108.Google Scholar
Vatutin, V. A. and Mikhailov, V. G. (1982) Limit theorems for the number of empty cells in an equiprobable scheme for group allocations of particles. Theory Prob. Appl. 27, 734–743.CrossRefGoogle Scholar
Walter, S. D. (1976) A generalization of a matrix occupancy problem. Biometrics 32, 471–475.CrossRefGoogle ScholarPubMed
White, C. (1971) The committee problem. Amer. Statist. 25, 25–26.Google Scholar