Forward Jump Random Walk on a Cycle Graph and Its Hitting Time

Authors

  • Rachanai Kaikeaw Faculty of Science and Technology, Dhonburi Rajabhat University, Bangkok 10600, Thailand
  • Pasin Marupanthorn Department of Mathematics, Faculty of Science and Technology, Maejo University, Chiang Mai 50290, Thailand

Keywords:

Cycle graph, Hitting time, Random walk on graph

Abstract

This paper presents an investigation into a random walk on a cycle graph with restricted forward movement at most 𝑚 steps, known as the forward jump random walk. The study derives exact formulas for the probability mass function of the arriving state, the hitting time, and its expected value and variance, where those solutions can be expressed in terms of trigonometric sums. These formulas are obtained using a combinatorial method as an alternative to the eigenvector-based approach commonly used.

References

Lovász L. Random walks on graphs. Combinatorics, Paul erdos is eighty. 1993;2(1-46):4.

Das Sarma A, Nanongkai D, Pandurangan G, Tetali P. Distributed random walks. Journal of the ACM (JACM). 2013;60(1):1–31.

Peng W, Wang J, Zhang Z, Wu FX. Applications of random walk model on biological networks. Current Bioinformatics. 2016;11(2):211 20.

Xu X, Lu L, He P, Pan Z, Jing C. Protein classification using random walk on graph. In: Emerging Intelligent Computing Technology and Applications: 8th International Conference, ICIC 2012, Huangshan, China, July 25-29, 2012. Proceedings 8. Springer; 2012. p. 180–4.

Sullivan D. What is google pagerank? A guide for searchers & webmasters. Search engine land. 2007.

Sarma AD, Molla AR, Pandurangan G, Upfal E. Fast distributed pagerank computation. Theoretical Computer Science. 2015;561:113 21.

Levin DA, Peres Y. Markov chains and mixing times. vol. 107. American Mathematical Soc.; 2017.

Ikeda Y, Fukai Y, Mizoguchi Y. A property of random walks on a cycle graph. Pacific Journal of Mathematics for Industry. 2015;7(1):1–14.

Chatzigiannakis I, Nikoletseas S, Paspallis N, Spirakis P, Zaroliagis C. An experimental study of basic communication protocols in ad hoc mobile networks. In: Algorithm Engineering: 5th International Workshop, WAE 2001 Århus, Denmark, August 28–31, 2001 Proceedings 5. Springer; 2001. p. 159–71.

Chatzigiannakis I, Nikoletseas S, Spirakis P. An efficient communication strategy for ad-hoc mobile networks. In: Proceedings of the twentieth annual ACM symposium on Principles of distributed computing; 2001. p. 320–2.

Chair N. The Effective Resistance of the N-Cycle Graph with Four Nearest Neighbors. Journal of Statistical Physics. 2014;154:1177–90.

Barlow MT. Random walks and heat kernels on graphs. vol. 438. Cambridge University Press; 2017.

Kaikeaw R, Naenudorn K. A Combinatorial Proof of An Identity Involving Trigonometric Power Sums. Mathematical Journal by The Mathematical Association of Thailand Under The Patronage of His Majesty The King. 2022;67(708):25–39.

Durrett R. Essentials of stochastic processes. 3rd ed. Springer; 2016.

Beasley JD. The mathematics of games. Courier Corporation; 2013.

Dobrow RP. Introduction to stochastic processes with R. John Wiley & Sons; 2016.

Abbott SD, Richey M. Take a Walk on the Boardwalk. The College Mathematics Journal. 1997;28(3):162–71.

Bilisoly R. Using board games and mathematica to teach the fundamentals of finite stationary markov chains. arXiv preprint arXiv:14101107. 2014.

Hinebaugh JP. A board game education. R&L Education; 2009.

Downloads

Published

2024-03-29

How to Cite

Rachanai Kaikeaw, & Pasin Marupanthorn. (2024). Forward Jump Random Walk on a Cycle Graph and Its Hitting Time. Science & Technology Asia, 29(1), 29–46. Retrieved from https://ph02.tci-thaijo.org/index.php/SciTechAsia/article/view/251338

Issue

Section

Physical sciences