# 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_{\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) $\displaystyle P_{\pi}(T_{A}>t)$ $\displaystyle\leq\exp(-t\pi(A)/\tau_{2}),\ t\geq 0$ (discrete time) $\displaystyle P_{\pi}(T_{A}\geq t)$ $\displaystyle\leq(1-\pi(A)/\tau_{2})^{t},\ t\geq 0.$

Notes on this section. In studying bounds on $T_{A}$ such as Lemma 10.12 we usually have in mind that $\pi(A)$ is small. One is sometimes interested in exit times from a set $A$ with $\pi(A)$ small, i.e. hitting times on $A^{c}$ where $\pi(A^{c})$ is near $1$. In this setting one can replace inequalities using $\tau_{2}$ or $\tau_{c}$ (which parameters involve the whole chain) by inequalities involving analogous parameters for the chain restricted to $A$ 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$ (i.e. an almost-bipartite graph) is irrelevant. An obvious exception arises when we consider lower bounds for $P_{\pi}(T_{A}>t)$ in terms of $|A|$, because in a bipartite graph with bipartition $\{A,A^{c}\}$ we have $P(T_{A}>1)=0$. It turns out (Alon et al [26] Proposition 2.4) that a corresponding lower bound holds in terms of $\tau_{n}\equiv 1/(\lambda_{n}+1)$.

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