On the average hitting times of the squares of cycles
On the average hitting times of the squares of cycles
复制标题
周期平方的平均击中次数
DOI：
10.1016/j.dam.2022.01.001
复制
发表时间：
2022
影响因子：
1.1
通讯作者：
Toyota Kosuke
中科院分区：
文献类型：
--
作者：
Doi Yoshiaki;Konno Norio;Nakamigawa Tomoki;Sakuma Tadashi;Segawa Etsuo;Shinohara Hidehiro;Tamura Shunya;Tanaka Yuuho;Toyota Kosuke
Chair（2014）给出了N顶点循环图cn的平方cn2上从一个顶点到任何其他顶点的简单随机游走的平均命中时间（简称HT）的确切公式。文中分别给出了偶数N和奇数N情况下的表达式。在本文中，通过使用与Chair（2014）不同的基本方法，我们给出了c2上简单随机游动的HT的更简单的单一公式。我们的证明是相当简短和完全组合的，特别是不需要任何谱图理论论证。不仅公式本身，而且通过我们的证明过程的中间结果描述了n2上简单随机游动的HT与斐波那契数之间的清晰关系。
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 Chair (2014). 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.