×

The simple harmonic urn. (English) Zbl 1262.60070

Authors’ abstract: We study a generalized Pólya urn model with two types of balls. If the drawn ball is red, it is replaced together with a black ball, but, if the drawn ball is black, it is replaced and a red ball is thrown out of the urn. When only black balls remain, the roles of the colors are swapped and the process restarts. We prove that the resulting Markov chain is transient but that, if we throw out a ball every time the colors swap, the process is recurrent. We show that the embedded process obtained by observing the number of balls in the urn at the swapping times has a scaling limit that is essentially the square of a Bessel diffusion. We consider an oriented percolation model naturally associated with the urn process, and obtain detailed information about its structure, showing that the open subgraph is an infinite tree with a single end. We also study a natural continuous-time embedding of the urn process that demonstrates the relation to the simple harmonic oscillator; in this setting, our transience result addresses an open problem in the recurrence theory of two-dimensional linear birth and death processes due to Kesten and Hutton. We obtain results on the area swept out by the process. We make use of connections between the urn process and birth-death processes, a uniform renewal process, the Eulerian numbers, and Lamperti’s problem on processes with asymptotically small drifts; we prove some new results on some of these classical objects that may be of independent interest. For instance, we give sharp new asymptotics for the first two moments of the counting function of the uniform renewal process. Finally, we discuss some related models of independent interest, including a “Poisson earthquakes” Markov chain on the homeomorphisms of the plane.

MSC:

60J10 Markov chains (discrete-time Markov processes on discrete state spaces)
60J25 Continuous-time Markov processes on general state spaces
60K05 Renewal theory
60K35 Interacting random processes; statistical mechanics type models; percolation theory
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Asmussen, S. (2003). Applied Probability and Queues , 2nd ed. Applications of Mathematics ( Stochastic Modelling and Applied Probability ) 51 . Springer, New York. · Zbl 1029.60001
[2] Aspandiiarov, S. and Iasnogorodski, R. (1997). Tails of passage-times and an application to stochastic processes with boundary reflection in wedges. Stochastic Process. Appl. 66 115-145. · Zbl 0889.60045 · doi:10.1016/S0304-4149(96)00118-4
[3] Aspandiiarov, S., Iasnogorodski, R. and Menshikov, M. (1996). Passage-time moments for nonnegative stochastic processes and an application to reflected random walks in a quadrant. Ann. Probab. 24 932-960. · Zbl 0869.60036 · doi:10.1214/aop/1039639371
[4] Athreya, K. B. and Karlin, S. (1968). Embedding of urn schemes into continuous time Markov branching processes and related limit theorems. Ann. Math. Statist. 39 1801-1817. · Zbl 0185.46103 · doi:10.1214/aoms/1177698013
[5] Athreya, K. B. and Ney, P. E. (1972). Branching Processes. Die Grundlehren der mathematischen Wissenschaften 196 . Springer, New York. · Zbl 0259.60002
[6] Bóna, M. (2004). Combinatorics of Permutations . Chapman & Hall/CRC, Boca Raton, FL. · Zbl 1052.05001
[7] Churchill, R. V. (1937). The inversion of the Laplace transformation by a direct expansion in series and its application to boundary-value problems. Math. Z. 42 567-579. · Zbl 0016.25904 · doi:10.1007/BF01160095
[8] Cox, D. R. (1962). Renewal Theory . Methuen, London. · Zbl 0103.11504
[9] Feller, W. (1941). On the integral equation of renewal theory. Ann. Math. Statist. 12 243-267. · Zbl 0026.23001 · doi:10.1214/aoms/1177731708
[10] Feller, W. (1968). An Introduction to Probability Theory and Its Applications. Vol. I , 3rd ed. Wiley, New York. · Zbl 0155.23101
[11] Feller, W. (1971). An Introduction to Probability Theory and Its Applications. Vol. II , 2nd ed. Wiley, New York. · Zbl 0219.60003
[12] Fisch, R., Gravner, J. and Griffeath, D. (1991). Cyclic cellular automata in two dimensions. In Spatial Stochastic Processes. Progress in Probability 19 171-185. Birkhäuser, Boston, MA. · Zbl 0737.60088 · doi:10.1007/978-1-4612-0451-0_8
[13] Flajolet, P., Gabarró, J. and Pekari, H. (2005). Analytic urns. Ann. Probab. 33 1200-1233. · Zbl 1073.60007 · doi:10.1214/009117905000000026
[14] Gut, A. (2005). Probability : A Graduate Course . Springer, New York. · Zbl 1076.60001
[15] Harris, T. E. (1952). First passage and recurrence distributions. Trans. Amer. Math. Soc. 73 471-486. · Zbl 0048.36301 · doi:10.2307/1990803
[16] Hoffman, J. R. and Rosenthal, J. S. (1995). Convergence of independent particle systems. Stochastic Process. Appl. 56 295-305. · Zbl 0816.60066 · doi:10.1016/0304-4149(94)00075-5
[17] Hutton, J. (1980). The recurrence and transience of two-dimensional linear birth and death processes. Adv. in Appl. Probab. 12 615-639. · Zbl 0453.60080 · doi:10.2307/1426423
[18] Janson, S. (2004). Functional limit theorems for multitype branching processes and generalized Pólya urns. Stochastic Process. Appl. 110 177-245. · Zbl 1075.60109 · doi:10.1016/j.spa.2003.12.002
[19] Jensen, U. (1984). Some remarks on the renewal function of the uniform distribution. Adv. in Appl. Probab. 16 214-215. · Zbl 0532.60088 · doi:10.2307/1427232
[20] Johnson, N. L. and Kotz, S. (1977). Urn Models and Their Application : An Approach to Modern Discrete Probability Theory . Wiley, New York. · Zbl 0352.60001
[21] Karlin, S. and Taylor, H. M. (1981). A Second Course in Stochastic Processes . Academic Press, New York. · Zbl 0469.60001
[22] Kesten, H. (1976). Recurrence criteria for multi-dimensional Markov chains and multi-dimensional linear birth and death processes. Adv. in Appl. Probab. 8 58-87. · Zbl 0336.60059 · doi:10.2307/1426022
[23] Kingman, J. F. C. (1999). Martingales in the OK Corral. Bull. London Math. Soc. 31 601-606. · Zbl 0933.60007 · doi:10.1112/S0024609399006098
[24] Kingman, J. F. C. and Volkov, S. E. (2003). Solution to the OK Corral model via decoupling of Friedman’s urn. J. Theoret. Probab. 16 267-276. · Zbl 1022.60007 · doi:10.1023/A:1022294908268
[25] Kotz, S. and Balakrishnan, N. (1997). Advances in urn models during the past two decades. In Advances in Combinatorial Methods and Applications to Probability and Statistics 203-257. Birkhäuser, Boston, MA. · Zbl 0888.60014 · doi:10.1007/978-1-4612-4140-9_14
[26] Lamperti, J. (1960). Criteria for the recurrence or transience of stochastic process. I. J. Math. Anal. Appl. 1 314-330. · Zbl 0099.12901 · doi:10.1016/0022-247X(60)90005-6
[27] Lamperti, J. (1962). A new class of probability limit theorems. J. Math. Mech. 11 749-772. · Zbl 0107.35602
[28] Lamperti, J. (1963). Criteria for stochastic processes. II. Passage-time moments. J. Math. Anal. Appl. 7 127-145. · Zbl 0202.46701 · doi:10.1016/0022-247X(63)90083-0
[29] MacPhee, I. M. and Menshikov, M. V. (2003). Critical random walks on two-dimensional complexes with applications to polling systems. Ann. Appl. Probab. 13 1399-1422. · Zbl 1055.60071 · doi:10.1214/aoap/1069786503
[30] Mahmoud, H. M. (2009). Pólya Urn Models . CRC Press, Boca Raton, FL. · Zbl 1149.60005
[31] Menshikov, M. V., Èĭsymont, I. M. and Yasnogorodskiĭ, R. (1995). Markov processes with asymptotically zero drift. Problemy Peredachi Informatsii 31 60-75; translated in Probl. Inf. Transm. 31 248-261.
[32] Menshikov, M. V., Vachkovskaia, M. and Wade, A. R. (2008). Asymptotic behaviour of randomly reflecting billiards in unbounded tubular domains. J. Stat. Phys. 132 1097-1133. · Zbl 1157.82036 · doi:10.1007/s10955-008-9578-z
[33] Pakes, A. G. (1971). On the critical Galton-Watson process with immigration. J. Austral. Math. Soc. 12 476-482. · Zbl 0249.60045 · doi:10.1017/S1446788700010375
[34] Pemantle, R. (2007). A survey of random processes with reinforcement. Probab. Surv. 4 1-79 (electronic). · Zbl 1189.60138 · doi:10.1214/07-PS094
[35] Pemantle, R. and Volkov, S. (1999). Vertex-reinforced random walk on Z has finite range. Ann. Probab. 27 1368-1388. · Zbl 0960.60041 · doi:10.1214/aop/1022677452
[36] Pittel, B. (1987). An urn model for cannibal behavior. J. Appl. Probab. 24 522-526. · Zbl 0637.60017 · doi:10.2307/3214275
[37] Robert, P. (2003). Stochastic Networks and Queues , French ed. Applications of Mathematics ( Stochastic Modelling and Applied Probability ) 52 . Springer, Berlin. · Zbl 1038.60091
[38] Smith, W. L. (1954). Asymptotic renewal theorems. Proc. Roy. Soc. Edinburgh Sect. A 64 9-48. · Zbl 0055.12402
[39] Smith, W. L. (1959). On the cumulants of renewal processes. Biometrika 46 1-29. · Zbl 0088.36501 · doi:10.1093/biomet/46.1-2.1
[40] Stone, C. (1965). On moment generating functions and renewal theory. Ann. Math. Statist. 36 1298-1301. · Zbl 0135.18903 · doi:10.1214/aoms/1177700003
[41] Ugrin-Šparac, G. (1990). On a distribution encountered in the renewal process based on uniform distribution. Glas. Mat. Ser. III 25 221-233. · Zbl 0725.60016
[42] Watson, R. K. (1976). An application of martingale methods to conflict models. Operations Res. 24 380-382. · Zbl 0324.90094 · doi:10.1287/opre.24.2.380
[43] Williams, D. and McIlroy, P. (1998). The OK Corral and the power of the law (a curious Poisson-kernel formula for a parabolic equation). Bull. London Math. Soc. 30 166-170. · Zbl 0933.60006 · doi:10.1112/S0024609397004062
[44] Zubkov, A. M. (1972). Life-periods of a branching process with immigration. Teor. Verojatnost. i Primenen. 17 179-188; translated in Theor. Probab. Appl. 17 174-183. · Zbl 0267.60084 · doi:10.1137/1117018
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.