Hostname: page-component-78c5997874-94fs2 Total loading time: 0 Render date: 2024-11-14T11:12:51.345Z Has data issue: false hasContentIssue false
  • English
  • Français

Occupancy schemes associated to Yule processes

Part of: Markov processes Special processes

Published online by Cambridge University Press:  01 July 2016

Philippe Robert  and
Florian Simatos
Philippe Robert*
Affiliation:
INRIA
Florian Simatos*
Affiliation:
INRIA
*
∗ Postal address: INRIA Paris-Rocquencourt, Domaine de Voluceau, BP 105, 78153 Le Chesnay, France.
∗ Postal address: INRIA Paris-Rocquencourt, Domaine de Voluceau, BP 105, 78153 Le Chesnay, France.
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.

An occupancy problem with an infinite number of bins and a random probability vector for the locations of the balls is considered. The respective sizes of the bins are related to the split times of a Yule process. The asymptotic behavior of the landscape of the first empty bins, i.e. the set of corresponding indices represented by point processes, is analyzed and convergences in distribution to mixed Poisson processes are established. Additionally, the influence of the random environment, the random probability vector, is analyzed. It is represented by two main components: an independent, identically distributed sequence and a fixed random variable. Each of these components has a specific impact on the qualitative behavior of the stochastic model. It is shown in particular that, for some values of the parameters, some rare events, which are identified, determine the asymptotic behavior of the average values of the number of empty bins in some regions.

Keywords

Occupancy schemePoisson processconvergence of point processesrandom environmentrare events

MSC classification

Primary: 60K20: Applications of Markov renewal processes (reliability, queueing networks, etc.)
Secondary: 60K37: Processes in random environments 60J80: Branching processes (Galton-Watson, birth-and-death, etc.)
Type
General Applied Probability
Information
Advances in Applied Probability , Volume 41 , Issue 2 , June 2009 , pp. 600 - 622
Copyright
Copyright © Applied Probability Trust 2009 

References

Athreya, K. B. and Kaplan, N. (1976). Convergence of the age distribution in the one-dimensional supercritical age-dependent branching process. Ann. Prob. 4, 38–50.CrossRefGoogle Scholar
Athreya, K. B. and Ney, P. E. (1972). Branching Processes. Springer, New York.CrossRefGoogle Scholar
Barbour, A. D., Holst, L. and Janson, S. (1992). Poisson Approximation (Oxford. Stud. Prob. 2). Clarendon Press, New York.CrossRefGoogle Scholar
Csáki, E. and Földes, A. (1976). On the first empty cell. Studia Sci. Math. Hung. 11, 373–382.Google Scholar
Dawson, D. A. (1993). Measure-valued Markov processes. In École d'Été de Probabilités de Saint-Flour XXI (Lecture Notes Math. 1541), Springer, Berlin, pp. 1–260.Google Scholar
Flajolet, P. and Martin, G. N. (1985). Probabilistic counting algorithms for data base applications. J. Comput. System Sci. 21, 182–209.CrossRefGoogle Scholar
Gnedin, A. V. (2004). The Bernoulli Sieve. Bernoulli 10, 79–96.CrossRefGoogle Scholar
Gnedin, A. V., Hansen, B. and Pitman, J. (2007). Notes on the occupancy problem with infinitely many boxes: general asymptotics and power laws. Prob. Surveys 4, 146–171.CrossRefGoogle Scholar
Gnedin, A., Iksanov, A. and Roesler, U. (2008). Small parts in the Bernoulli sieve. Discrete Math. Theoret. Computer Sci. AI, 239–246. Available at http://arxiv.org/abs/0804.3052.Google Scholar
Härnqvist, M. (1981). Limit theorems for point processes generated in a general branching process. Adv. Appl. Prob. 13, 650–668.CrossRefGoogle Scholar
Hwang, H.-K. and Janson, S. (2008). Local limit theorems for finite and infinite urn models. Ann. Prob. 36, 992–1022.CrossRefGoogle Scholar
Johnson, N. L. and Kotz, S. (1977). Urn Models and Their Application. John Wiley, New York.Google Scholar
Karlin, S. (1967). Central limit theorems for certain infinite urn schemes. J. Math. Mech. 17, 373–401.Google Scholar
Kingman, J. F. C. (1975). The first birth problem for an age-dependent branching process. Ann. Prob. 3, 790–801.CrossRefGoogle Scholar
Kolchin, V. F., Sevast'yanov, B. A. and Chistyakov, V. P. (1978). Random Allocations, V. H. Winston, Washington, D.C. Google Scholar
Liu, Q. (2001). Asymptotic properties and absolute continuity of laws stable by random weighted mean. Stoch. Process. Appl. 95, 83–107.CrossRefGoogle Scholar
Nerman, O. (1981). On the convergence of supercritical general (C-M-J) branching processes. Z. Wahrscheinlichkeitsth. 57, 365–395.CrossRefGoogle Scholar
Neveu, J. (1972). Martingales à Temps Discret. Masson et Cie, éditeurs, Paris.Google Scholar
Neveu, J. (1977). Processus ponctuels. In École d'Été de Probabilités de Saint-Flour VI (Lecture Notes Math. 598), Springer, Berlin, pp. 249–445.Google Scholar
Robert, P. (2003). Stochastic Networks and Queues (Appl. Math. 52). Springer, New York.CrossRefGoogle Scholar
Rudin, W. (1987). Real and Complex Analysis, 3rd edn., McGraw-Hill, New York.Google Scholar
Saddi, W. and Guillemin, F. (2007). Measurement based modeling of edonkey peer-to-peer file sharing system. In Proc. Internat. Teletraffic Congress 20 (Ottawa, June 2007), pp. 974–985.Google Scholar
Simatos, F., Robert, P. and Guillemin, F. (2008). A queueing system for modeling a file sharing principle. In Proc. ACM SIGMETRICS 2008, ACM Press, New York.Google Scholar
Williams, D. (1991). Probability with Martingales. Cambridge University Press.CrossRefGoogle Scholar