zbMATH — the first resource for mathematics

Necklace processes via Pólya urns. (English) Zbl 1160.60303
Summary: C. Mallows and L. Shepp [J. Appl. Probab. 45, No. 1, 271–278 (2008; Zbl 1213.60027)] 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.
Reviewer: Reviewer (Berlin)

60C05 Combinatorial probability
60F05 Central limit and other weak theorems
Full Text: DOI
[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. · Zbl 0568.60010 · doi:10.1137/0606041
[2] Brennan, C. A. C. and Prodinger, H. (2003). The pills problem revisited. Quaest. Math. 26, 427–439. · Zbl 1054.05004 · doi:10.2989/16073600309486073
[3] Devroye, L. (1991). Limit laws for local counters in random binary search trees. Random Structures Algorithms 2, 303–315. · Zbl 0728.60027 · doi:10.1002/rsa.3240020305
[4] Eggenberger, F. and Pólya, G. (1923). Über die Statistik vorketter vorgänge. Zeit. Angew. Math. Mech. 3, 279–289. · JFM 49.0382.01
[5] Flajolet, P. and Huillet, T. (2008). Analytic combinatorics of the Mabinogion urn. Discrete Math. Theoret. Computer Sci. AI, 549–572. · Zbl 1358.60014
[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. · Zbl 1193.60011 · www.dmtcs.org
[7] Gouet, R. (1993). Martingale functional central limit theorems for a generalized Pólya urn. Ann. Prob. 21, 1624–1639. · Zbl 0788.60044 · doi:10.1214/aop/1176989134
[8] Mahmoud, H. (2008). Pólya Urn Models . Chapman and Hall/CRC, Boca Raton, FL. · Zbl 1149.60005
[9] Mallows, C. and Shepp, L. (2008). The necklace process. J. Appl. Prob. 45, 271–278. · Zbl 1213.60027 · doi:10.1239/jap/1208358967
[10] Pemantle, R. (2007). A survey of random processes with reinforcement. Prob. Surveys 4, 1–79. · Zbl 1189.60138 · doi:10.1214/07-PS094 · eudml:232071
[11] Williams, D. (1991). Probability with Martingales . Cambridge University Press. · Zbl 0722.60001 · doi:10.1017/CBO9780511813658
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.