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.
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).
(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.
(continuous time) | ||||
(discrete time) |
Notes on this section. In studying bounds on such as Lemma 10.12 we usually have in mind that is small. One is sometimes interested in exit times from a set with small, i.e. hitting times on where is near . In this setting one can replace inequalities using or (which parameters involve the whole chain) by inequalities involving analogous parameters for the chain restricted to 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 (i.e. an almost-bipartite graph) is irrelevant. An obvious exception arises when we consider lower bounds for in terms of , because in a bipartite graph with bipartition we have . It turns out (Alon et al [26] Proposition 2.4) that a corresponding lower bound holds in terms of .