10 Some Graph Theory and Randomized Algorithms (September 1 1999)

10.7 Material belonging in other chapters

10.7.1 Large deviation bounds

yyy Somewhere in the book we need to discuss the results on explicit large deviation bounds for occupation measure / empirical averages: [167, 125, 204, 230]. In section 10.4.1 we used the following bound from Gillman [167] Theorem 2.1.

Theorem 10.11
Pμ(Nn(B)/n-π(B)>γ)(1+γn10τ2)iμi2/πiexp(-γ2n20τ2).P_{\mu}\left(N_{n}(B)/n\ -\pi(B)>\gamma\right)\leq\left(1+\frac{\gamma n}{10% \tau_{2}}\right)\ \sqrt{\sum_{i}\mu_{i}^{2}/\pi_{i}}\ \exp\left(\frac{-\gamma^% {2}n}{20\tau_{2}}\right).

10.7.2 The probabilistic method in combinatorics

yyy This is to be moved to Chapter 6, where we do the “universal traversal sequences” example.

Suppose one wants to show the existence of a combinatorial object with specified properties. The most natural way is to give an explicit construction of an example. There are a variety of settings where, instead of a giving an explicit construction, it is easier to argue that a randomly-chosen object has a non-zero chance of having the required properties. The monograph by Alon and Spencer [28] is devoted to this topic, under the name the probabilistic method. One use of this method is below. Two more example occur later in the book: random construction of expander graphs (Chapter 30 Proposition 1) (yyy 7/9/96 version), and the random construction of an objective function in an optimization problem (Chapter 9 section 4.2) (yyy this version).

10.7.3 copied to Chapter 4 section 6.5

(yyy 10/11/94 version) Combining Corollary 31 with (62) gives the continuous time result below. Recasting the underlying theory in discrete time establishes the discrete-time version.

Lemma 10.12
(continuous time) Pπ(TA>t)\displaystyle P_{\pi}(T_{A}>t) exp(-tπ(A)/τ2),t0\displaystyle\leq\exp(-t\pi(A)/\tau_{2}),\ t\geq 0
(discrete time) Pπ(TAt)\displaystyle P_{\pi}(T_{A}\geq t) (1-π(A)/τ2)t,t0.\displaystyle\leq(1-\pi(A)/\tau_{2})^{t},\ t\geq 0.

Notes on this section. In studying bounds on TAT_{A} such as Lemma 10.12 we usually have in mind that π(A)\pi(A) is small. One is sometimes interested in exit times from a set AA with π(A)\pi(A) small, i.e. hitting times on AcA^{c} where π(Ac)\pi(A^{c}) is near 11. In this setting one can replace inequalities using τ2\tau_{2} or τc\tau_{c} (which parameters involve the whole chain) by inequalities involving analogous parameters for the chain restricted to AA and its boundary. See Babai [36] for uses of such bounds.

On several occasions we have remarked that for most properties of random walk, the possibility of an eigenvalue near -1-1 (i.e. an almost-bipartite graph) is irrelevant. An obvious exception arises when we consider lower bounds for Pπ(TA>t)P_{\pi}(T_{A}>t) in terms of |A||A|, because in a bipartite graph with bipartition {A,Ac}\{A,A^{c}\} we have P(TA>1)=0P(T_{A}>1)=0. It turns out (Alon et al [26] Proposition 2.4) that a corresponding lower bound holds in terms of τn1/(λn+1)\tau_{n}\equiv 1/(\lambda_{n}+1).

Pπ(TA>t)(max(0,1-|A|nτn))t.P_{\pi}(T_{A}>t)\geq\left(\max(0,1-{\textstyle\frac{|A|}{n\tau_{n}}})\right)^{% t}.