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

Vol.29 No.1 (January-March 2024)

Section

Physical sciences

License

Copyright (c) 2024 Science & Technology Asia

Creative Commons License

This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.