Analysis of a generalized Friedman’s urn with multiple drawings.

*(English)*Zbl 1292.60012Summary: We study a generalized Friedman’s urn model with multiple drawings of white and blue balls. After a drawing, the replacement follows a policy of opposite reinforcement. We give the exact expected value and variance of the number of white balls after a number of draws, and determine the structure of the moments. Moreover, we obtain a strong law of large numbers, and a central limit theorem for the number of white balls. Interestingly, the central limit theorem is obtained combinatorially via the method of moments and probabilistically via martingales. We briefly discuss the merits of each approach. The connection to a few other related urn models is briefly sketched.

##### MSC:

60C05 | Combinatorial probability |

##### Keywords:

Pólya urn; urn model; combinatorial probability; limiting distribution; method of moments; martingale; martingale central limit theorem
PDF
BibTeX
XML
Cite

\textit{M. Kuba} et al., Discrete Appl. Math. 161, No. 18, 2968--2984 (2013; Zbl 1292.60012)

Full Text:
DOI

##### References:

[1] | Arya, S.; Golin, M.; Mehlhorn, K., On the expected depth of random circuits, Combinatorics, Probability and Computing, 8, 209-228, (1999) · Zbl 0941.68001 |

[2] | Chen, M.-R.; Wei, C.-Z., A new urn model, Journal of Applied Probability, 42, 4, 964-976, (2005) · Zbl 1093.60007 |

[3] | Chern, H.-H.; Hwang, H.-K., Phase changes in random \(m\)-ary search trees and generalized quicksort, Random Structures and Algorithms, 19, 316-358, (2001) · Zbl 0990.68052 |

[4] | Freedman, D., Bernard friedman’s urn, The Annals of Mathematical Statistics, 36, 956-970, (1965) · Zbl 0138.12003 |

[5] | Friedman, B., A simple urn model, Communications in Pure and Applied Mathematics, 2, 59-70, (1949) · Zbl 0033.07101 |

[6] | Graham, R.; Knuth, D.; Patashnik, O., Concrete mathematics, (1994), Addison-Wesley Reading |

[7] | Hall, P.; Heyde, C., Martingale limit theory and its application, (1980), Academic Press New York · Zbl 0462.60045 |

[8] | Hill, B.; Lane, D.; Sudderth, W., A strong law for some generalized urn processes, Annals of Probability, 8, 214-226, (1980) · Zbl 0429.60021 |

[9] | Johnson, N.; Kotz, S., Urn models and their applications: an approach to modern discrete probability theory, (1977), Wiley New York · Zbl 0352.60001 |

[10] | Johnson, N.; Kotz, S.; Mahmoud, H., Pólya-type urn models with multiple drawings, Journal of the Iranian Statistical Society, 3, 165-173, (2004) · Zbl 06657086 |

[11] | Kotz, S.; Balakrishnan, N., Advances in urn models during the past two decades, (Advances in Combinatorial Methods and Applications to Probability and Statistics, (1997), Birkhäuser Boston, MA), 203-257 · Zbl 0888.60014 |

[12] | Loève, M., Probability theory I, (1977), Springer New York · Zbl 0359.60001 |

[13] | Mahmoud, H., Pólya urn models, (2008), Chapman-Hall Boca Raton |

[14] | Moler, J.; Plo, F.; Urmeneta, H., A generalized Pólya urn and limit laws for the number of outputs in a family of random circuits, Test, 22, 46-61, (2013) · Zbl 1262.60025 |

[15] | Tsukiji, T.; Mahmoud, H., A limit law for outputs in random circuits, Algorithmica, 31, 403-412, (2001) · Zbl 0989.68107 |

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.