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 $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 $(X_{t})$ is another birth-and-death process $(Y_{t})$ which is “dual” in the sense that

$P_{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 $(X_{t})$. It is easy to see that $\tau_{1}$ for $(X_{t})$ is equivalent to $\max_{j}E_{j}T_{0,n}$ for $(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 $\tau_{2}$, and by Mazo [261], who computed the asymptotics of the unweighted average of $(E_{i}T_{j};i,j\in I)$, which in this example is asymptotically our $\tau_{0}$. Note we were able to give a one-line argument for the asymptotics of $\tau_{2}$ by relying on the general fact $\tau_{2}\leq\tau_{0}$.

Formulas for quantities associated with random walk on the $d$-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_{\bf 0}T_{\bf 1}$ lead to formulas looking different from our (5.69), for instance

$\displaystyle E_{\bf 0}T_{\bf 1}$ | $\displaystyle=$ | $\displaystyle d\sum_{i=1}^{d}2^{i-1}/i\ \ \ \ \ \ \ \ \ \ \ \ \ \ \mbox{\rm% \@@cite{[\@@bibref{Refnum}{kem61}{}{}]}, eq.~{}(4.27)}$ | ||

$\displaystyle=$ | $1\leq j\leq d$ |

Similarly, one can get different-looking expressions for $\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 $d$-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].

Generated on Mon Jun 2 14:23:48 2014 by LaTeXML