1. Torus Hitting Times and Green's Functions (Fall, '01)

Overview

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.

Hitting Times, Defined

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')).

Green's Function for the Torus

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.

Torus Hitting Times

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.

Average Hitting Times

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.

Maximal Mean Commute Time

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.

First Hitting Time

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).


References

[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).


Copyright 2001, all rights reserved. Reproduction in any media must be by express permission of the author.
Robert Ellis / rellis@math.tamu.edu