×
Gangopadhyay, Ujan; Maulik, Krishanu

Stochastic approximation with random step sizes and urn models with random replacement matrices having finite mean. (English) Zbl 1435.62311

Ann. Appl. Probab. 29, No. 4, 2033-2066 (2019).
The article concerns a significant contribution to the stochastic approximation algorithm introduced by H. Robbins and S. Monro [Ann. Math. Stat. 22, 400–407 (1951; Zbl 0054.05901)]. The step sizes used in stochastic approximation are generally taken to be deterministic, and same is true for the drift (see [M. Benaïm, Lect. Notes Math. 1709, 1–68 (1999; Zbl 0955.62085); V. S. Borkar, Stochastic approximation. A dynamical systems viewpoint. Cambridge: Cambridge University Press; New Delhi: Hindustan Book Agency (2008; Zbl 1181.62119)]). The specific application of urn models (the original formulation due to [F. Eggenberger and G. Pólya, Z. Angew. Math. Mech. 3, 279–290 (1923; JFM 49.0382.01)]) with random replacement matrices needs to consider stochastic approximation in a setup where both the step sizes and the drift are random, but the sequence is uniformly bounded.
The paper deals with an extension to stochastic approximation algorithm for bounded sequences with random step size and drift. The result is applied to the stochastic approximation for an urn model with unbalanced random replacement matrix. It is shown that the corresponding differential equation is of Lotka-Volterra type which is able to analyze directly. It allows giving a complete analysis of urn models with balls of finitely many colors and random replacement matrix when it is assumed only that the first moment is finite.
Reviewer: Krzysztof J. Szajowski (Wrocław)

Cited in 4 Documents

MSC:

62L20 Stochastic approximation
60F15 Strong limit theorems
60G42 Martingales with discrete parameter

Keywords:

urn model; random replacement matrix; balanced replacement matrix; irreducibility; stochastic approximation; random step size; random drift; uniform integrability; Lotka-Volterra differential equation

Citations:

Zbl 0054.05901; Zbl 0955.62085; Zbl 1181.62119; JFM 49.0382.01
PDF BibTeX XML Cite
\textit{U. Gangopadhyay} and \textit{K. Maulik}, Ann. Appl. Probab. 29, No. 4, 2033--2066 (2019; Zbl 1435.62311)
Full Text: DOI arXiv Euclid

References:

[1] Athreya, K. B. and Karlin, S. (1968). Embedding of urn schemes into continuous time Markov branching processes and related limit theorems. Ann. Math. Stat.39 1801-1817. · Zbl 0185.46103
[2] Athreya, K. B. and Ney, P. E. (2004). Branching Processes. Dover, Mineola, NY. · Zbl 1070.60001
[3] Bai, Z.-D. and Hu, F. (2005). Asymptotics in randomized URN models. Ann. Appl. Probab.15 914-940. · Zbl 1059.62111
[4] Benaïm, M. (1999). Dynamics of stochastic approximation algorithms. In Séminaire de Probabilités, XXXIII. Lecture Notes in Math.1709 1-68. Springer, Berlin. · Zbl 0955.62085
[5] Borkar, V. S. (2008). Stochastic Approximation. Cambridge Univ. Press, Cambridge. · Zbl 1159.60002
[6] Dasgupta, A. and Maulik, K. (2011). Strong laws for urn models with balanced replacement matrices. Electron. J. Probab.16 1723-1749. · Zbl 1244.60031
[7] Freedman, D. A. (1965). Bernard Friedman’s urn. Ann. Math. Stat.36 956-970. · Zbl 0138.12003
[8] Gouet, R. (1997). Strong convergence of proportions in a multicolor Pólya urn. J. Appl. Probab.34 426-435. · Zbl 0884.60028
[9] Hall, P. and Heyde, C. C. (1980). Martingale Limit Theory and Its Application. Academic Press, New York. · Zbl 0462.60045
[10] Kushner, H. J. and Clark, D. S. (1978). Stochastic Approximation Methods for Constrained and Unconstrained Systems. Applied Mathematical Sciences26. Springer, New York. · Zbl 0381.60004
[11] Laruelle, S. and Pagès, G. (2013). Randomized urn models revisited using stochastic approximation. Ann. Appl. Probab.23 1409-1436. · Zbl 1429.62360
[12] Meyer, C. (2000). Matrix Analysis and Applied Linear Algebra. SIAM, Philadelphia, PA.
[13] Meyer, C. D. (2015). Continuity of the Perron root. Linear Multilinear Algebra63 1332-1336. · Zbl 1316.15012
[14] Pólya, G. (1930). Sur quelques points de la théorie des probabilités. Ann. Inst. Henri Poincaré1 117-161.
[15] Pólya, G. and Eggenberger, F. (1923). Über die Statistik verketteter Vorgänge. Z. Agnew. Math. Mech.3 279-289. · JFM 49.0382.01
[16] Renlund, H. (2010). Generalized Polya urns via stochastic approximation. Preprint. Available at arxiv:1002.3716.
[17] Renlund, H. (2011). Limit theorems for stochastic approximation algorithms. Preprint. Available at arxiv:1102.4741.
[18] Resnick, S. (1992). Adventures in Stochastic Processes. Birkhäuser, Boston, MA. · Zbl 0762.60002
[19] Robbins, H. and Monro, S. (1951). A stochastic approximation method. Ann. Math. Stat.22 400-407. · Zbl 0054.05901
[20] Seneta, E. (2006). Non-negative Matrices and Markov Chains. Springer Series in Statistics. Springer, New York. · Zbl 1099.60004
[21] Stroock, D. W. and Varadhan, S. R. S. (2006). Multidimensional Diffusion Processes. Classics in Mathematics. Springer, Berlin. Reprint of the 1997 edition. · Zbl 1103.60005
[22] Zhang, L. (2012). The Gaussian approximation for generalized Friedman’s urn model with heterogeneous and unbalanced updating. Sci. China Math.55 2379-2404. · Zbl 1268.60042
[23] Zhang, L.-X. (2016). Central limit theorems of a recursive stochastic algorithm with applications to adaptive designs. Ann. Appl. Probab.26 3630-3658. · Zbl 1358.60044
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.