On the average hitting times of the squares of cycles

DOI10.1016/J.DAM.2022.01.001MaRDI QIDQ832990zbMATH OpenOpenAlexFDO

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)

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

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)

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.

Recommendations

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

Cites work

• scientific article; zbMATH DE number 3163289 (Why is no real title available?)
• Counting Trees in a Certain Class of Graphs
• Fibonacci and Lucas Numbers With Applications
• Fibonacci and Lucas Numbers with Applications
• The effective resistance of the \(N\)-cycle graph with four nearest neighbors
• Theory of resistor networks: the two-point resistance

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)