ISSN 0869-6632 (Print)
ISSN 2542-1905 (Online)


For citation:

Krivonosov M. I., Tikhomirov S. Н. Strategies and first-absorption times in the random walk game. Izvestiya VUZ. Applied Nonlinear Dynamics, 2023, vol. 31, iss. 3, pp. 334-350. DOI: 10.18500/0869-6632-003043, EDN: SWQCCC

This is an open access article distributed under the terms of Creative Commons Attribution 4.0 International License (CC-BY 4.0).
Full text PDF(Ru):
Full text PDF(En):
Language: 
English
Article type: 
Article
UDC: 
519.837
EDN: 

Strategies and first-absorption times in the random walk game

Autors: 
Krivonosov Mikhail Igorevich, Lobachevsky State University of Nizhny Novgorod
Tikhomirov Sergei Николаевич, Lobachevsky State University of Nizhny Novgorod
Abstract: 

Purpose of this work is to determine the average time to reach the boundaries, as well as to identify the strategy in the game between two players, controlling point movements on the finite square lattice using an independent choice of strategies. One player wants to survive, i. e., to stay within the interior of the square, as long as possible, while his opponent wants to reach the absorbing boundary. A game starts from the center of the square and every next movement of the point is determined by independent strategy choices made by the players. The value of the game is the survival time that is the number of steps before the absorption happens. In addition we present series of experiments involving both human players and an autonomous agent (bot) and analysis of the survival time probability distributions.

Methods. In this work, methods of the theory of absorbing Markov chains were used to analyze strategies and absorption times, as well as the Monte Carlo method to simulate trajectories. Additionally, a large-scale field experiment was conducted using the developed mobile application.

Results. The players’ strategies are experimentally obtained for the cases of playing against an autonomous agent (bot), as well as human players against each other. A comparison with optimal strategies and a random walk is made: the difference between the experimental strategies and the optimal ones is shown, however, the resulting strategies show a much better result of games than a simple random walk. In addition, especially long-running games do not show the Markovian property in case of the simulation corresponding strategies.

Conclusion. The sampled histograms indicate that the game-driven walks are more complex than a random walk on a finite lattice but it can be reproduced with a Markov Chain model.

Acknowledgments: 
The authors are thankful to Sergey Denisov (Oslo Metropolitan University), who suggested the idea of experiment and designed the game. The reported study was funded by RFBR, project number No. 20-31-90121
Reference: 
  1. Coolidge JL. The gambler’s ruin. Annals of Mathematics. 1909;10(4):181–192. DOI: 10.2307/ 1967408.
  2. Fller WD. An Introduction to Probability Theory and Its Applications. Wiley: New York; 1950. 704 p.
  3. Redner S. A Guide to First-Passage Processes. Cambridge: Cambridge University Press; 2001. 312 p. DOI: 10.1017/CBO9780511606014.
  4. Hausner M. Games of Survival. Report No. RM-776. Santa Monica: The RAND Corporation; 1952. 7 p.
  5. Peisakoff MP. More on Games of Survival. Report No. RM-884. Santa Monica: The RAND Corporation; 1952. 20 p.
  6. Kmet A, Petkovsek M. Gambler’s ruin problem in several dimensions. Advances in Applied Mathematics. 2002;28(2):107–118. DOI: 10.1006/aama.2001.0769.
  7. Romanovskii IV. Game-type random walks. Theory of Probability & Its Applications. 1961;6(4): 393–396. DOI: 10.1137/1106051.
  8. Nisan N, Roughgarden T, Tardos E, Vazirani VV. Algorithmic Game Theory. Cambridge: Cambridge University Press; 2007. 754 p. DOI: 10.1017/CBO9780511800481.
  9. Pearson K. The problem of the random walk. Nature. 1905;72:294. DOI: 10.1038/072294b0.
  10. Zaburdaev V, Denisov S, Klafter J. Levy walks. Reviews of Modern Physics. 2015;87(2):483–530. DOI: 10.1103/RevModPhys.87.483.
  11. Benichou O, Loverdo C, Moreau M, Voituriez R. Intermittent search strategies. Reviews of Modern Physics. 2011;83(1):81–129. DOI: 10.1103/RevModPhys.83.81.
  12. Rhee I, Shin M, Hong S, Lee K, Kim SJ, Chong S. On the Levy-walk nature of human mobility. IEEE/ACM Transactions on Networking. 2011;19(3):630–643. DOI: 10.1109/TNET.2011.2120618.
  13. Fauchald P. Foraging in a hierarchical patch system. The American Naturalist. 1999;153(6): 603–613. DOI: 10.1086/303203.
  14. Scanlon TM, Caylor KK, Levin SA, Rodriguez-Iturbe I. Positive feedbacks promote power-law clustering of Kalahari vegetation. Nature. 2007;449(7159):209–212. DOI: 10.1038/nature06060.
  15. Reynolds A, Ceccon E, Baldauf C, Karina Medeiros T, Miramontes O. Levy foraging patterns of rural humans. PLOS ONE. 2018;13(6):e0199099. DOI: 10.1371/journal.pone.0199099.
  16. Pyke GH. Understanding movements of organisms: it’s time to abandon the Levy foraging hypothesis. Methods in Ecology and Evolution. 2015;6(1):1–16. DOI: 10.1111/2041-210X.12298.
  17. LaScala-Gruenewald DE, Mehta RS, Liu Y, Denny MW. Sensory perception plays a larger role in foraging efficiency than heavy-tailed movement strategies. Ecological Modelling. 2019;404:69–82. DOI: 10.1016/j.ecolmodel.2019.02.015.
  18. Krivonosov MI, Tikhomirov SN. Random Walk Game [Electronic resource]. 2020. Available from: https://play.google.com/store/apps/details?id=com.scigames.RWGame (Google Play Store), https://apps.apple.com/us/app/random-walk/id1564589250 (AppStore).
  19. Taylor HM, Karlin S. An Introduction to Stochastic Modeling. San Diego: Academic Press; 2008. 648 p.
  20. Kemeny JG, Snell JL. Finite Markov Chains. New York: Springer-Verlag; 1983. 226 p.
  21. Darroch JN, Seneta E. On quasi-stationary distributions in absorbing discrete-time finite Markov shains. Journal of Applied Probability. 1965;2(1):88–100. DOI: 10.2307/3211876.
  22. Zhang J, Calabrese C, Ding J, Liu M, Zhang B. Advantages and challenges in using mobile apps for field experiments: A systematic review and a case study. Mobile Media & Communication. 2018;6(2):179–196. DOI: 10.1177/2050157917725550. 
Received: 
22.10.2022
Accepted: 
05.04.2023
Available online: 
15.05.2023
Published: 
31.05.2023