Hostname: page-component-586b7cd67f-rdxmf Total loading time: 0 Render date: 2024-11-24T14:52:02.656Z Has data issue: false hasContentIssue false
  • English
  • Français

Necklace Processes Via Pólya Urns

Part of: Limit theorems Combinatorial probability

Published online by Cambridge University Press:  14 July 2016

Toshio Nakata
Toshio Nakata*
Affiliation:
Fukuoka University of Education
*
∗Postal address: Department of Mathematics, Fukuoka University of Education, Akama-Bunkyomachi, Munakata, Fukuoka, 811-4192, Japan. Email address: [email protected]
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.

Mallows and Shepp (2008) developed the following necklace processes. Start with a necklace consisting of one white bead and one black bead, and insert, one at a time, under a deterministic rule, a white bead or a black bead between a randomly chosen adjacent pair. They studied the statistical properties of the number of white beads by investigating the nature of the moments and the expected number of gaps of given length between white beads. In this note we study the number of white beads via Pólya urns and give a classification of necklace processes for some general rules. Additionally, we discuss the number of runs, i.e. the number of consecutive same color beads, instead of the number of gaps.

Keywords

Necklace processPólya urnlaw of large numberscentral limit theorem

MSC classification

Secondary: 60C05: Combinatorial probability 60F05: Central limit and other weak theorems
Type
Research Article
Information
Journal of Applied Probability , Volume 46 , Issue 1 , March 2009 , pp. 284 - 295
Copyright
Copyright © Applied Probability Trust 2009 

Footnotes

Dedicated to Professor Izumi Kubo on the occasion of his 70th birthday.

References

[1] Bagchi, A. and Pal, A. K. (1985). Asymptotic normality in the generalized Pólya Eggenberger urn model, with an application to computer data structures. SIAM J. Algebraic Discrete Methods 6, 394–405.Google Scholar
[2] Brennan, C. A. C. and Prodinger, H. (2003). The pills problem revisited. Quaest. Math. 26, 427–439.Google Scholar
[3] Devroye, L. (1991). Limit laws for local counters in random binary search trees. Random Structures Algorithms 2, 303–315.Google Scholar
[4] Eggenberger, F. and Pólya, G. (1923). Über die Statistik vorketter vorgänge. Zeit. Angew. Math. Mech. 3, 279–289.Google Scholar
[5] Flajolet, P. and Huillet, T. (2008). Analytic combinatorics of the Mabinogion urn. Discrete Math. Theoret. Computer Sci. AI, 549–572.Google Scholar
[6] Flajolet, P., Dumas, P. and Puyhaubert, V. (2006). Some exactly solvable models of urn process theory. Discrete Math. Theoret. Computer Sci. AG, 59–118.Google Scholar
[7] Gouet, R. (1993). Martingale functional central limit theorems for a generalized Pólya urn. Ann. Prob. 21, 1624–1639.Google Scholar
[8] Mahmoud, H. (2008). Pólya Urn Models. Chapman and Hall/CRC, Boca Raton, FL.Google Scholar
[9] Mallows, C. and Shepp, L. (2008). The necklace process. J. Appl. Prob. 45, 271–278.Google Scholar
[10] Pemantle, R. (2007). A survey of random processes with reinforcement. Prob. Surveys 4, 1–79.Google Scholar
[11] Williams, D. (1991). Probability with Martingales. Cambridge University Press.CrossRefGoogle Scholar