Two particles' repelling random walks on the complete graph

Jun Chen (California Institute of Technology)

Abstract


We consider two particles' repelling random walks on complete graphs. In this model, each particle has higher probability to visit the vertices which have been seldom visited by the other one. By a dynamical approach we prove that the two particles' occupation measure asymptotically has small joint support almost surely if the repulsion is strong enough.

Full Text: Download PDF | View PDF online (requires PDF plugin)

Pages: 1-17

Publication Date: December 12, 2014

DOI: 10.1214/EJP.v19-2669

References

  • Angel, Omer; Crawford, Nicholas; Kozma, Gady. Localization for linearly edge reinforced random walks. Duke Math. J. 163 (2014), no. 5, 889--921. MR3189433
  • Benaim, Michel. A dynamical system approach to stochastic approximations. SIAM J. Control Optim. 34 (1996), no. 2, 437--472. MR1377706
  • Benaim, Michel; Raimond, Olivier; Schapira, Bruno. Strongly vertex-reinforced-random-walk on a complete graph. ALEA Lat. Am. J. Probab. Math. Stat. 10 (2013), no. 2, 767--782. MR3125746
  • Benveniste, Albert; Métivier, Michel; Priouret, Pierre. Adaptive algorithms and stochastic approximations. Translated from the French by Stephen S. Wilson. Applications of Mathematics (New York), 22. Springer-Verlag, Berlin, 1990. xii+365 pp. ISBN: 3-540-52894-6 MR1082341
  • Durrett, Rick. Probability: theory and examples. Fourth edition. Cambridge Series in Statistical and Probabilistic Mathematics. Cambridge University Press, Cambridge, 2010. x+428 pp. ISBN: 978-0-521-76539-8 MR2722836
  • Kiefer, J.; Wolfowitz, J. Stochastic estimation of the maximum of a regression function. Ann. Math. Statistics 23, (1952). 462--466. MR0050243
  • Kovchegov, Yevgeniy. Multi-particle processes with reinforcements. J. Theoret. Probab. 21 (2008), no. 2, 437--448. MR2391254
  • Kushner, Harold J.; Clark, Dean S. Stochastic approximation methods for constrained and unconstrained systems. Applied Mathematical Sciences, 26. Springer-Verlag, New York-Berlin, 1978. x+261 pp. ISBN: 0-387-90341-0 MR0499560
  • Limic, Vlada. Attracting edge property for a class of reinforced random walks. Ann. Probab. 31 (2003), no. 3, 1615--1654. MR1989445
  • Limic, Vlada; Tarrès, Pierre. Attracting edge and strongly edge reinforced walks. Ann. Probab. 35 (2007), no. 5, 1783--1806. MR2349575
  • Ljung, Lennart. Analysis of recursive stochastic algorithms. IEEE Trans. Automatic Control AC-22 (1977), no. 4, 551--575. MR0465458
  • Pemantle, Robin. Nonconvergence to unstable points in urn models and stochastic approximations. Ann. Probab. 18 (1990), no. 2, 698--712. MR1055428
  • Pemantle, Robin. A survey of random processes with reinforcement. Probab. Surv. 4 (2007), 1--79. MR2282181
  • Pemantle, Robin; Volkov, Stanislav. Vertex-reinforced random walk on ${\bf Z}$ has finite range. Ann. Probab. 27 (1999), no. 3, 1368--1388. MR1733153
  • Robbins, Herbert; Monro, Sutton. A stochastic approximation method. Ann. Math. Statistics 22, (1951). 400--407. MR0042668
  • Tarrès, Pierre. Vertex-reinforced random walk on $\Bbb Z$ eventually gets stuck on five points. Ann. Probab. 32 (2004), no. 3B, 2650--2701. MR2078554
Bookmark and Share


Creative Commons License
This work is licensed under a Creative Commons Attribution 3.0 License.