Hitting times for the 2-dimensional torus (Zm)2 may be deduced from its Green's function. Letting n=m2 be the number of vertices, we have the following.
In a random walk on the torus, we begin at the origin (0,0) and at each step walk one unit in any of 4 directions, chosen with equal probability. The hitting time of a target vertex (y,y') is the expected number of steps in the random walk needed to reach that vertex (y,y') for the first time. The hitting time for a vertex (y,y') for a random walk starting at (x,x') is defined as Q((x,x'),(y,y')).
Describe a vertex on the torus (Zm)2 by (v,v'), where 0<=v,v'<m. The normalied Green's function G for the torus is the pseudo-inverse to the normalized combinatorial Laplacian L, which is defined by

Using formulas for Green's functions developed in [4], based on techniques introduced in [3] it is determined that the pseudo-inverse of L, the normalized Green's function G, for 0<=x<=y<m and 0<=x'<=y'<m is given by

Tn is the Chebyshev polynomial of the first kind defined by Tn=cos nt, where x=cos t. All other values of G are determined by replacing y with max(x,y), x with min(x,y), y' with max(x',y') and x' with min(x',y'). Note that G could also be given in terms of the eigensystem of L, but that sum would involve m2 terms.
A consequence of a theorem on Q and L in [3] is that for the torus (Zm)2, the hitting time Q((x,x'),(y,y')) satisfies the following.
![]()
Because of the symmetry of the torus, we only need to look at the
hitting times from the origin, (0,0), to any point (y,y').
This gives a m by m matrix of hitting times which can
be displayed graphically. Imagine the xy-axes as the
surface of the torus laid out in 2 dimensions. The z-value
at some xy-coordinate (y,y') gives the hitting time
from the origin to the point (y,y'). The furthest point,
(24,0) has the largest hitting time of about 6680.9. In this
graph, the origin is in the center of the graph, at the bottom of the
well. Also, in the torus, a vertex on the boundary is connected
to the vertex on the opposite boundary.
The same graph may be viewed from underneath, in order to view
the hitting times near the origin more easily.
Interestingly enough, the level sets look like circles near the
origin, but begin to look like hyperbolas at the farthest points from
the origin. The following contour map shows the level sets.
All other square tori (3<=m<=90) behave similarly,
and have similar associated graphs. Strongly rectangular tori
have contours that look like air flow contours traveling from side to
side around a circular obstruction.
Consider the average of the hitting times starting and ending at
all ordered pairs of vertices on the torus. This value is
called the average hitting time of the torus. The following
plot shows the trend of average hitting times as the size of the m
by m torus gets larger. Data is given for m=3,...,40.
On p. 11 of Chapter 5 of [1], The average
hitting time is given to be Theta(n log n), where n=m2
is the number of vertices on the torus. This is
confirmed experimentally by considering the following plot of
(hitting time)/(n log n) for the same tori m=3,...,40, which
starts to stabilize around .34.
Mean commute time between two vertices is the expected number of
steps to start from one, visit the other, and return again.
Maximal mean commute time is the maximum over all mean commute times
of all pairs of vertices. On the torus, the largest hitting
time (starting at the origin) is for the point
(floor(m/2),floor(m/2)). Because of
symmetry, this point also gives the maximum mean commute time.
Here is a graph of maximal mean commute time for a size m of a
m by m torus.
It is known [2] that the maximal mean
commute time behaves asymptotically as n log n. This is
confirmed in the following graph of (maximal mean commute time)/(n
log n), which settles down towards .73.
The "first hitting time" is the hitting time from the origin (0,0) to any adjacent vertex, say, (1,0) or (0,1). Starting from the origin, this is how many steps we expect to take before reaching this adjacent vertex. All computational evidence (checked for m<=90) points to this hitting time being (m-1)(m+1).
[1] D. Aldous and J. Fill, Reversible Markov Chains and Random Walks on Graphs, manuscript http://www.stat.berkeley.edu/users/aldous/RWG/book.html,.
[2] D. Aldous, private communication.
[3] F. R. K. Chung and S.-T. Yau, Discrete Green's functions, J. Combinatorial Theory (A), 91 (2000), 191-214. (Paper available from Chung's website under "research")
[4] Discrete Green's functions for products of regular graphs, submitted (2001 AMS National Conference invited talk, special session on Graph Theory) (arXiv pdf).