Markov Chains and Random Walks

Prev: The Probabilistic Method Next: Algebraic Techniques

Problems

6.1

Consider a random walk on the infinite line. At each step, the position of the particle is one of the integer points. At the next step, it moves to one of the two neighboring points equiprobably. Show that the expected distance of the particle from the origin after $n$ steps is $\Theta (\sqrt{n})$.

---

6.2

Consider the randomized algorithm for 2-SAT discussed in Section 6.1. Show that the analysis is tight, in that there exist satisfiable 2-SAT formulas with $n$ variables such that the expected time for this algorithm to find a satisfying truth assignment is $\Omega (n^2)$.

---

6.3

Consider a 1-dimensional random walk with a reflecting barrier, which is defined as follows. For each natural number $i$, there is a state $i$. At state $0$, with probability $1$ the walk will move to state $1$. At every other state $i>0$, the walk will move to state $i+1$ with probability $p$ and to state $i-1$ with probability $1-p$. Prove the following for the resulting Markov chain:

(a) For $p>\frac{1}{2}$, each state is transient.

(b) For $p=\frac{1}{2}$, each state is null persistent.

(c) For $p<\frac{1}{2}$, each state is non-null persistent.

---

6.4

Consider a Markov chain with the states $0,1,\dots ,N$. This Markov chain induces a sequence of random variables $X_0,X_1,\dots$, each of which takes an integer value between $0$ and $N$, i.e. $X_t$ is the state at time $t$. Suppose this sequence of random variables forms a martingale.

(a) A state $q$ is said to be an absorbing state if the transition probability $P_{qq}=1$. Identify all the absorbing states and the transient states of this Markov chain.

(b) Given that the initial state of this Markov chain is $i$, compute the probability of being absorbed into each of the absorbing states.

---

6.5

Due to C.J.H. McDiarmid [303].

Let $G$ be a 3-colorable graph. Consider the following algorithm for coloring the vertices of $G$ with 2 colors so that no triangle of $G$ is monochromatic. The algorithm begins with an arbitrary 2-coloring of $G$. While there is a monochromatic triangle in $G$, it chooses one such triangle, and changes the color of a randomly chosen vertex of that triangle. Derive an upper bound on the expected number of such recoloring steps before the algorithm finds a 2-coloring with the desired property.

---

6.6

An $n\times n$ matrix $P$ is said to be stochastic if all its entries are non-negative and for each row $i$, ${\sum }_j{P}_{ij}=1$. It is said to be doubly stochastic if, in addition, ${\sum }_i{P}_{ij}=1$.

(a) Show that for any stochastic matrix $P$, there exists an $n$-dimensional vector $\pi$ with non-negative entries such that ${\sum }_i{\pi }_i=1$ and $\pi P=\pi$.

(b) Suppose that the transition probability matrix $P$ for a Markov chain is doubly stochastic. Show that the stationary distribution for this Markov chain is necessarily the uniform distribution.

---

6.7

Consider a random walk on a graph whose edges have positive real costs: the interpretation of these costs is that every time the random walk traverses an edge $(ij)$, it incurs a given cost $c_{ij}>0$; $c_{ij}=c_{ji}$, and $c_{ii}=0$. Consider the random walk on a graph $G$ with $m$ edges that have such costs associated with them, with transition probabilities

$$P_{ij}=\frac{1/c_{ij}}{{\sum }_{k}1/c_{ik}}.$$

Let $S_{uv}$ denote the expected total cost incurred by a walk that begins at vertex $u$ and terminates upon returning to $u$ after having visited $v$ at least once. Show that

$$S_{uv}=2m{R}_{uv},$$

where $R_{uv}$ is the effective resistance between node $u$ and node $v$ in an electrical network whose underlying graph is $G$, and where the branch resistance between $i$ and $j$ is $c_{ij}$.

---

6.8

In a connected graph $G$, an edge is called a bridge if the removal of the edge disconnects the graph. Let $G$ be a connected graph with $n$ vertices and $m$ edges. Let $(u,v)$ be any edge in $G$. For the simple random walk on $G$, show that

$$h_{uv}+h_{vu}=2m$$

if and only if the edge $(u,v)$ is a bridge.

---

6.9

Due to P.C. Matthews [296, 297].

The goal of this problem is to derive a cleaner version of Theorem 6.9. Consider a random permutation of the vertices of a connected graph $G$, and let $J_i$ denote the $i$th vertex in this permutation. For $1\le k\le n$, define $F_k={\max }_{i\le k}{T}_{J_i}$ to be the time by which all of $\{J_1,J_2,\dots ,J_k\}$ have been visited (in some order). Let $L_k$ be the last of the vertices in $\{J_1,J_2,\dots ,J_k\}$ to be visited. Let $\delta (ij)$ be the delta function, defined to be $1$ if $i=j$ and $0$ otherwise.

(a) Show that conditioned on the sequence of vertices visited until time $F_{k-1}$, and for a fixed set $\{J_1,J_2,\dots ,J_k\}$,

$$\mathbb{E}[F_k-F_{k-1}]=\delta (L_k{J}_k)h_{L_{k-1}{J}_k}.$$

(b) Hence infer that

$$\mathbb{E}[F_k-F_{k-1}]\ge \underset{i\ne j}{\min }{h}_{ij}\mathrm{Pr}[L_k=J_k].$$

(c) Now use the fact that the $J_i$ are randomly ordered to show that

$$\underset{u}{\min }{C}_u(G)\ge H_{n-1}\underset{i\ne j}{\min }{h}_{ij}.$$

(d) Repeat the above arguments to obtain an upper bound on cover time:

$$\underset{u}{\max }{C}_u(G)\le H_{n-1}\underset{i\ne j}{\max }{h}_{ij}.$$

---

6.10

By showing that the resistance of the complete graph $K_n$ is $\Theta (1/n)$, show that the upper bound of Theorem 6.9 cannot be improved in general.

---

6.11

Let $G$ be a regular graph with every vertex having degree $d$. Show that $C(G)$ is $O(n^2\log n)$.

Remark: This shows that regular graphs have lower cover times than graphs that have large disparities in their vertex-degrees (such as the lollipop graph, which had $C(L_n)$ as large as $\Theta (n^3)$). In fact, using a more careful argument, Kahn, Linial, Nisan, and Saks [224] show that for every regular graph, $C(G)$ is $O(n^2)$.

---

6.12

The result in Problem 6.11 can be improved for dense regular graphs. Let $G$ be a regular graph with every vertex having degree $\ge 2n/3$. Show that $C(G)$ is $O(n\log n)$. Complement this upper bound by showing that for $d<n/2$ such that $d+1$ divides $n$, there exists a $d$-regular graph whose cover time is $\Omega (n^2)$. Derive an upper bound on $U(d,n)$ for $d\ge 2n/3$.

---

6.13

Consider the two-dimensional mesh: a graph in which each vertex is a point with integer coordinates in the plane, all coordinates being in the interval $[1,n^{1/2}]$. An edge connects two vertices if they differ in one coordinate by $1$. Show that the maximum commute time in this graph is $\Theta (n\log n)$.

---

6.14

Consider next the three-dimensional mesh: a graph in which each vertex is thought of as a point with integer coordinates in three dimensions, all coordinates being in the interval $[1,n^{1/3}]$. Show that the cover time for this graph is $O(n\log n)$. Derive upper bounds for the lengths of the universal traversal sequences for labeled two-dimensional and three-dimensional meshes.

---

6.15

(a) Show that for $n=3$ and $d=2$, there exists a universal traversal sequence $U(d,n)$ of length $3$.

(b) What is the smallest UTS you can construct for the case $n=4$ and $d=2$?

---

6.16

Show that the expected time for a random walk to visit every vertex of a strongly connected directed graph is not bounded above by any polynomial function of $n$, the number of vertices. In other words, construct a directed graph that is strongly connected and where the expected cover time is super-polynomial.

---

6.17

Show that any probabilistic, log-space, polynomial-time Turing machine can be simulated by a deterministic, non-uniform, log-space, polynomial-time Turing machine. Hint: Use the ideas of Section 2.3.

---

6.18

Due to D. Zuckerman [424].

Let $G(V,E)$ be a graph with $n$ vertices such that for some constant $\alpha >0$ and every set $S\subseteq V$ with $n/2$ vertices,

$$\left|\{w\in V\mid \exists v\in S,(v,w)\in E\}\right|\ge \frac{n}{2}+\alpha n.$$

For any positive integer $k$, let $W_1,\dots ,W_k$ be subsets of $V$ of size at least $(1-\alpha )n$ each. Show that there exists a path $(v_1,\dots ,v_k)$ in $G$ such that, for $1\le i\le k$, $v_i\in W_i$.

---

6.19

Courant-Fisher equalities.

Let $A$ be an $n\times n$ symmetric matrix with real entries, and let $e_1$ denote the eigenvector corresponding to the first eigenvalue ${\lambda }_1$. Show that

(1) ${\lambda }_1=\max \{x^{T}Ax\}$, where the max is taken over $x$ such that $\Vert x\Vert =1$.

(2) ${\lambda }_n=\min \{x^{T}Ax\}$, where the min is taken over $x$ such that $\Vert x\Vert =1$.

(3) ${\lambda }_2=\max \{x^{T}Ax\}$, where the max is taken over $x$ such that $\Vert x\Vert =1$ and $x^T{e}_1=0$.

---

6.20

Let $G(V,E)$ be a connected, $d$-regular, undirected (multi)graph with $n$ vertices. Show that for the adjacency matrix $A(G)$, ${\lambda }_1=d$ and $e_1=\frac{1}{\sqrt{n}}(1,1,1,\dots ,1)$.

---

6.21

Let $G(V,E)$ be a connected, $d$-regular, undirected (multi)graph. Show that for the adjacency matrix $A(G)$, each eigenvalue ${\lambda }_i$ has absolute value bounded by $d$.

---

6.22

Show that a connected graph $G$ with maximum eigenvalue ${\lambda }_1$ is bipartite if and only if $-{\lambda }_1$ is also an eigenvalue.

---

6.23

Show that a graph $G$ is bipartite if and only if for every eigenvalue $\lambda$, there is an eigenvalue $-\lambda$ of the same multiplicity.

---

6.24

Consider the setting of Definition 6.14 and the following measures of deviation from the limit. Let $S$ denote the set of states of the Markov chain under consideration. The total variation distance is defined as

$$\overline{\Delta }(t)=\underset{T\subseteq S}{\max }\left|\sum _{i\in T}{q}_i^{(t)}-\sum _{i\in T}{\pi }_i\right|.$$

(a) Define the $L_1$ distance as

$$\Vert q^{(t)}-\pi {\Vert }_1=\sum _i\left|q_i^{(t)}-{\pi }_i\right|.$$

Determine the relation between the $L_1$ distance and the total variation distance.

(b) Suppose that the relative pointwise distance is bounded by $ϵ$ at time $t$. Give the tightest bound you can on the total variation distance at time $t$.

(c) Suppose that the total variation distance at time $t$ is bounded by $ϵ$. What can you say about the relative pointwise distance at time $t$?

---

6.25

Does Theorem 6.21 hold true if the relative pointwise distance is replaced by the total variation distance defined in Problem 6.24?

---

6.26

Let $G$ be $d$-regular, and define the matrix

$$Q=(I+A(G)/d)/2.$$

Show that if the $i$th eigenvalue of $A(G)$ is ${\lambda }_i$, then the $i$th eigenvalue of $Q$ equals $(1+{\lambda }_i/d)/2$.

---

6.27

Due to N. Alon and F.R.K. Chung [20].

Let $G(X,Y,E)$ be a $d$-regular, connected, bipartite (multi)graph. Show that for any sets $S\subseteq X$ and $T\subseteq Y$, the number of edges connecting $S$ and $T$ is at least

$$\frac{{\lambda }_1|S||T|}{n}-{\lambda }_2\sqrt{|S||T|}.$$

Hint: Consider the adjacency matrix of $G$ premultiplied by the characteristic vector of $S$, and postmultiplied by the characteristic vector of $T$. The characteristic vector of $S$ is a vector with a $1$ in every position corresponding to a member of $S$, and $0$ everywhere else.

Remark: Note that in a random $d$-regular graph, the expected number of edges from $S$ to $T$ is $d|S||T|/n$, which is ${\lambda }_1|S||T|/n$. This result can be viewed as bounding the deviation from the behavior of a random graph in terms of the eigenvalue ${\lambda }_2$, thereby adding to the intuition that an expander “looks” like a random graph.

---

6.28

Due to M. Ajtai, J. Komlós, and E. Szemerédi [9].

Let $G$ be an $(n,d,c)$-expander. Show that there exist constants $\beta$, $\delta >0$ such that for any “bad” set of vertices $B$ of cardinality at most $\delta n$, the following property holds: the probability that, starting from a vertex chosen uniformly at random, a random walk of length $\ell$ does not visit any vertex outside of $B$ is at most $\exp (-\delta \ell )$. Exactly what properties of $G$ are essential for your proof of this fact?

---

6.29

Using the result in Problem 6.28, obtain a probability amplification result for $RP$ algorithms similar to that obtained in Section 6.8 for $BPP$ algorithms.

Remark: While it is an easy consequence of the result for $BPP$ algorithms, this problem requires you to derive a direct proof based only on the property stated in Problem 6.28.