On the average hitting times of the squares of cycles

DOI10.1016/J.DAM.2022.01.001zbMATH Open1485.05166arXiv2110.12614OpenAlexW4212934833MaRDI QIDQ832990FDOQ832990

Authors: Yoshiaki Doi, Norio Konno, Tomoki Nakamigawa, Tadashi Sakuma, Etsuo Segawa, Hidehiro Shinohara, Shunya Tamura, Yuuho Tanaka, Kosuke Toyota 

Publication date: 28 March 2022

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Abstract: The exact formula for the average hitting time (HT, as an abbreviation) of simple random walks from one vertex to any other vertex on the square $C_N^2$ of an $N$-vertex cycle graph $C_N$ was given by N. Chair [ extit{Journal of Statistical Physics}, extbf{154} (2014) 1177-1190]. In that paper, the author gives the expression for the even $N$ case and the expression for the odd $N$ case separately. In this paper, by using an elementary method different from Chair (2014), we give a much simpler single formula for the HT's of simple random walks on $C_N^2$. Our proof is considerably short and fully combinatorial, in particular, has no-need of any spectral graph theoretical arguments. Not only the formula itself but also intermediate results through the process of our proof describe clear relations between the HT's of simple random walks on $C_N^2$ and the Fibonacci numbers.

Full work available at URL: https://arxiv.org/abs/2110.12614

Recommendations

• An explicit formula of hitting times for random walks on graphs
• scientific article
• The hitting times of random walks on bicyclic graphs
• Simple random walks on wheel graphs
• On hitting times of random walks on trees

zbMATH Keywords

hitting timeKirchhoff indexFibonacci numbersimple random walksquare of a cycle

Mathematics Subject Classification ID

Random walks, random surfaces, lattice animals, etc. in equilibrium statistical mechanics (82B41) Random walks on graphs (05C81) Analytic circuit theory (94C05) Fibonacci and Lucas numbers and polynomials and generalizations (11B39)

Cites Work

• Title not available (Why is that?)
• Theory of resistor networks: the two-point resistance
• Counting Trees in a Certain Class of Graphs
• Fibonacci and Lucas Numbers With Applications
• The effective resistance of the \(N\)-cycle graph with four nearest neighbors
• Fibonacci and Lucas Numbers with Applications

Cited In (1)

• On the average hitting times of \(\operatorname{Cay} (\mathbb{Z}_N, \{+1, +2\})\)

This page was built for publication: On the average hitting times of the squares of cycles

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q832990)