5 Examples: Special Graphs and Trees (April 23 1996)

5.4 Notes on Chapter 5

Most of the material seems pretty straightforward, so we will give references sparingly.

Introduction. The essential edge lemma is one of those oft-rediscovered results which defies attribution.

Section 5.1.2. One can of course use the essential edge lemma to derive the formula for mean hitting times in the general birth-and-death process. This approach seems more elegant than the usual textbook derivation. Although we are fans of martingale methods, we didn’t use them in Proposition 5.3(b), because to define the right martingale requires one to know the answer beforehand!

For a birth-and-death chain the spectral representation involves orthogonal polynomials. This theory was developed by Karlin and McGregor in the 1950s, and is summarized in Chapter 8 of Anderson [31]. It enables one to write down explicit formulas for Pi(Xt=j)P_{i}(X_{t}=j) in special cases. But it is less clear how to gain qualitative insight, or inequalities valid over all birth-and-death chains, from this approach.

An alternative approach which is more useful for our purposes is based on Siegmund duality (see e.g. [31] Section 7.4). Associated with a birth-and-death process (Xt)(X_{t}) is another birth-and-death process (Yt)(Y_{t}) which is “dual” in the sense that

Pi(Xtj)=Pj(Yti) for all i,j,tP_{i}(X_{t}\leq j)=P_{j}(Y_{t}\geq i)\mbox{ for all }i,j,t

and whose transition rates have a simple specification in terms of those of (Xt)(X_{t}). It is easy to see that τ1\tau_{1} for (Xt)(X_{t}) is equivalent to maxjEjT0,n\max_{j}E_{j}T_{0,n} for (Yt)(Y_{t}), for which there is an explicit formula. This gives an alternative to (5.16).

Section 5.2.

That the barbell is a good candidate for an “extremal” graph with respect to random walk properties was realized by Landau and Odlyzko [220], who computed the asymptotics of τ2\tau_{2}, and by Mazo [261], who computed the asymptotics of the unweighted average of (EiTj;i,jI)(E_{i}T_{j};i,j\in I), which in this example is asymptotically our τ0\tau_{0}. Note we were able to give a one-line argument for the asymptotics of τ2\tau_{2} by relying on the general fact τ2τ0\tau_{2}\leq\tau_{0}.

Formulas for quantities associated with random walk on the dd-cube and with the Ehrenfest urn model have been repeatedly rediscovered, and we certainly haven’t given all the known results. Bingham [51] has an extensive bibliography. Palacios [275] uses the simple “resistance” argument used in the text, and notes that the same argument can be used on the Platonic graphs. Different methods of computing E𝟎T𝟏E_{\bf 0}T_{\bf 1} lead to formulas looking different from our (5.69), for instance

E𝟎T𝟏\displaystyle E_{\bf 0}T_{\bf 1} =\displaystyle= di=1d2i-1/i       [216], eq. (4.27)\displaystyle d\sum_{i=1}^{d}2^{i-1}/i\ \ \ \ \ \ \ \ \ \ \ \ \ \ \mbox{\rm% \@@cite{[\@@bibref{Refnum}{kem61}{}{}]}, eq.~{}(4.27)}
=\displaystyle= d1jd1\leq j\leq djj oddj-1(dj)      [51].\displaystyle d\sum_{\mbox{\rm\scriptsize$1\leq j\leq d$, $j$ odd}}j^{-1}{d% \choose j}\ \ \ \ \ \ \ \ \ \@@cite{[\@@bibref{Refnum}{bin91}{}{}]}.

Similarly, one can get different-looking expressions for τ0\tau_{0}. Wilf [337] lists 54 identities involving binomial coefficients—it would be amusing to see how many could be derived by calculating a random walk on the dd-cube quantity in two different ways!

Comparing our treatment of dense regular graphs (Example 5.16) with that in [272] should convince the reader of the value of general theory.

Section 5.3. An early reference to formulas for the mean and variance of hitting times on a tree (Theorem 5.20) is Moon [264], who used less intuitive generating function arguments. The formulas for the mean have been repeatedly rediscovered.

Of course there are many other questions we can ask about random walk on trees. Some issues treated later are

xxx list.

xxx more sophisticated ideas in Lyons [250].