# On the Moments of Hitting Times for Random Walks on Trees

Authors: José Luis Palacios
Journal: Journal of Probability and Statistics
 (2009)

---

## Abstract

Using classical arguments we derive a formula for the moments of hitting times for an ergodic Markov chain. We apply this formula to the case of simple random walk on trees and show, with an elementary
electric argument, that all the moments are natural numbers.


---

## Body

## 1. Introduction

On a connected undirected graphG=(V,E) such that the edge between vertices i and j is given a resistance rij (or equivalently, a conductance Cij=1/rij), we can define the general random walk (GRW) on G as the Markov chain Xn,n≥0, that from its current vertex v jumps to the neighboring vertex w with probability pvw=Cvw/C(v), where C(v)=∑w:w~vCvw, and w~v means that w is a neighbor of v. There may be a conductance Czz from a vertex z to itself, giving rise to a transition probability from z to itself, though the most studied case of these random walks on graphs, the simple random walk (SRW), excludes the loops and considers all rij's to be equal to 1.The hitting timeTb of the vertex b is the number of jumps that the walk takes until it lands on b, and its kth moment when the walk starts at a is denoted by EaTbk. Chen and Zhang [1] found a closed-form formula for the expected hitting times of SRW on trees that yielded as a corollary the fact that these expected times are all natural numbers. Furthermore, Chen [2] studied the moment generating function of hitting times for SRW on trees and showed that the second moments are also natural numbers.The purpose of this note is to give a recursive formula for the moments of the hitting times of any ergodic finite Markov chain, using as tools classical material found in Kemeny and Snell [3] and Chung [4]. When this formula is applied to the case of SRW on trees, an elementary argument from the electrical approach found in Doyle and Snell [5] shows that all these moments are natural numbers.To ease the notation, let us assume thatV={1,2,…,N} and that we are interested in finding EiTNk for k≥1 and 1≤i≤N-1. We consider the vectors ETNk=[E1TNk,E2TNk,…,EN-1TNk]t,k≥1, and c=[1,1,…,1]t, where the superscript t means “transpose.” The classical approach to finding ETN in an ergodic Markov chain with state space V, due to Kemeny and Snell [3], consists of considering the matrix Q which results from deleting the N-th row and column of the transition probability matrix and finding the “fundamental matrix” (I-Q)-1 which yields(1.1)ETN=(I-Q)-1c,
on account of the fact that the (i,j) entry of the fundamental matrix is the expected number of visits to state j, n(j), by the walk started at i before hitting the state N. We can write this fact as(1.2)(I-Q)ij-1=Ein(j).
An additional fact that we will need regarding the matrix Q can be found in Kemeny and Snell [3, page 49]:(1.3)(I-Q)-1Q=(I-Q)-1-I.Of the electrical approach we will quote the fact that(1.4)Ein(j)=C(j)vj,
where C(j)=∑i~jCij is the sum of all conductances emanating from j and vj is the voltage at j when a battery is placed between i and N such that the current entering at j is 1 and the voltage at N is 0. The details can be found in Doyle and Snell [5, Section 3.3, page 49].


## 2. The Formula and Its Corollaries

In the spirit of Corollary2 in Chung [4, page 64] we find a recurrence for the moments of the hitting times of an ergodic Markov chain. Our formula differs from that of Chung in that his is presented neither as a recurrence nor in vector form, and more importantly, in that it involves neither taboo probabilities nor mean recurrence times, and this latter fact is crucial for our purposes, because for SRW on graphs the mean recurrence time EiTi of a vertex i is given by 2|E|/d(i), where d(i) is the number of neighbors of i, and for the case of a tree this expression becomes 2(N-1)/d(i) which may or may not be a natural number, and we need that all coefficients in the vectors and matrices of our formula to be natural numbers. This recurrence should perhaps be better known and we present it here in the followingTheorem 2.1.
For any ergodic Markov chain with state spaceV={1,2,…,N} one has
(2.1)ETNk=ETN+∑s=1k-1(ks)[(I-Q)-1-I]ETNs,
for k≥2.Proof.
For anyk≥1 and any i,1≤i≤N-1, conditioning gives us
(2.2)EiTNk=piN+∑j≠NpijEj(1+TN)k=1+∑s=1k(ks)∑j≠NpijEjTNs.
In vector form the above set of equations yields
(2.3)ETNk=c+∑s=1k(ks)QETNs.
For k=1, (2.3) becomes (1.1). For k≥2, from (2.3) we obtain
(2.4)(I-Q)ETNk=c+∑s=1k-1(ks)QETNs.
Solving for ETNk and using (1.1) in (2.4) we get
(2.5)ETNk=ETN+∑s=1k-1(ks)(I-Q)-1QETNs.
Finally using (1.3) in (2.5) finishes the proof.Now we can give sufficient conditions for all moments to be natural numbers.Corollary 2.2.
Under the hypotheses of the theorem, ifETN is a vector of natural numbers and all the entries of the fundamental matrix are natural numbers, then for all k≥1, ETNk is a vector of natural numbers.Proof.
Use induction and the recursion (2.1), and verify that all the summands in the right-hand side of (2.1), under the hypotheses, turn out to be natural numbers.Corollary 2.3.
In the case of SRW on trees,ETNk is a vector of natural numbers for all k≥1.Proof.
It is known [1] that ETN is a vector of natural numbers. By the previous corollary if suffices to prove that all entries of the fundamental matrix are natural numbers. But (1.2) and (1.4) tell us that (I-Q)ij-1=C(j)vj, and for SRW C(j) is just the number of neighbors of j, so all that is left to check is that the voltage vj is a natural number, when a battery is placed between i and N such that the current entering i is 1 and the voltage vN=0. Since the graph is a tree, it is immediate from Ohm's law that for all vertices x in the unique path P from i to N, vx=d(x,N), the distance from x to N. Also, if we denote by E(P) the set of edges in the path P, it is plain to see that all vertices in the connected component of G-E(P) that contains x share the same voltage vx=d(x,N). So the voltages in all vertices are natural numbers and we are done.The condition in Corollary2.2 that all the entries of (I-Q)-1 are natural numbers is not necessary. For example, in the case of SRW in the complete graph KN,N≥3 we have that(2.6)(I-Q)-1=N-1N(211⋯1121⋯1112⋯1⋮⋮⋮⋱⋮111⋯2),
so that no entry of the fundamental matrix is a natural number. However, (1.1) gives us that ETN=(N-1,N-1,…,N-1)t. Moreover, by symmetry, ETNs=(cs,cs,…,cs)t for some constant cs, and it is plain to see that (I-Q)-1ETNs=((N-1)cs,(N-1)cs,…,(N-1)cs)t. Therefore, induction and formula (2.1) imply that all moments in this case are natural numbers, which can be given explicitely: c2=(N-1)(2N-3),c3=(N-1)(6N2-18N+13), c4=(N-1)(24N3-108N2+158N-75), and so forth.



---

*Source: 241539-2009-10-26.xml*