×

zbMATH — the first resource for mathematics

A generalized Pólya urn and limit laws for the number of outputs in a family of random circuits. (English) Zbl 1262.60025
Summary: We introduce a generalized Pólya urn model with the feature that the evolution of the urn is governed by a function which may change depending on the stage of the process, and we obtain a strong law of large numbers and a central limit theorem for this model, using stochastic recurrence techniques. This model is used to represent the evolution of a family of acyclic directed graphs, called random circuits, which can be seen as logic circuits. The model provides asymptotic results for the number of outputs, that is, terminal nodes, of this family of random circuits.

MSC:
60F05 Central limit and other weak theorems
60F15 Strong limit theorems
68R10 Graph theory (including graph drawing) in computer science
05C20 Directed graphs (digraphs), tournaments
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Arthur WB (1994) Increasing returns and path dependence in the economy. University of Michigan Press, Ann Arbor
[2] Arya S, Golin MJ, Mehlorn K (1999) On the expected depth of random circuits. Comb Probab Comput 8:209–228 · Zbl 0941.68001 · doi:10.1017/S096354839900382X
[3] Chung F, Handjani S, Jungreis D (2003) Generalizations of Pólya’s urn problem. Ann Comb 7:141–153 · Zbl 1022.60005 · doi:10.1007/s00026-003-0178-y
[4] Duflo M (1997) Random iterative models. Springer, Berlin
[5] Gouet R (1997) Strong convergence of proportions in a multicolor Pólya urn. J Appl Probab 34:426–435 · Zbl 0884.60028 · doi:10.2307/3215382
[6] Higueras I, Moler JA, Plo F, San Miguel M (2006) Central limit theorems for generalized Pólya urn models. J Appl Probab 43:938–951 · Zbl 1137.60009 · doi:10.1239/jap/1165505199
[7] Janson S (2004) Functional limit theorems for multitype branching processes and generalized Pólya urns. Stoch Process Appl 110:177–245 · Zbl 1075.60109 · doi:10.1016/j.spa.2003.12.002
[8] Mahmoud HM (2002) The size of random bucket trees via urn models. Acta Inform 38:813–838 · Zbl 1034.68121 · doi:10.1007/s00236-002-0096-1
[9] Mahmoud HM (2008) Pólya urn models. Chapman & Hall, Boca Raton
[10] Mahmoud HM, Tsukiji T (2004) Limit laws for terminal nodes in random circuits. Acta Inform 41:99–110 · Zbl 1101.68069 · doi:10.1007/s00236-004-0152-0
[11] Nakata T (2009) Neclace processes via Pólya urns. J Appl Probab 46:284–295 · Zbl 1160.60303
[12] Pelletier M (1998) Weak convergence rates for stochastic approximation with application to multiple targets and simulated annealing. Ann Appl Probab 8(1):10–44 · Zbl 0965.62065 · doi:10.1214/aoap/1027961032
[13] Pemantle R, Skyrms B (2004) Time to absorption in discounted reinforcement models. Stoch Process Appl 109:1–12 · Zbl 1075.60090 · doi:10.1016/j.spa.2003.08.003
[14] Smythe RT, Mahmoud HM (1995) A survey of recursive trees. Theory Probab Math Stat 51:1–27
[15] Tsukiji T, Mahmoud HM (2001) A limit law for outputs in random recursive circuits. Algorithmica 31:403–412 · Zbl 0989.68107 · doi:10.1007/s00453-001-0044-4
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.