\documentclass[10pt]{article}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{epsfig}
\usepackage{graphicx}
\usepackage{float}
\newcommand{\defn}[1]           {{\textit{\textbf{\boldmath #1}}}}
\newcommand{\id}[1]             {\ifmmode\mathit{#1}\else\textit{#1}\fi}
\newcommand{\card}[1]           {\left| #1\right|}
\newcommand{\cover}{{\cal C}}
\newcommand{\dego}{{\rm deg_{\rm out}}}
\newcommand{\degi}{{\rm deg_{\rm in}}}
\newcommand{\degg}{{\rm deg}}

\oddsidemargin=0.15in
\evensidemargin=0.15in
\topmargin=-.5in
\textheight=9in
\textwidth=6.25in

\begin{document}
\input{preamble.tex}



\lecture{6}{April 22, 2009}{Ronitt Rubinfeld}{Ido Trivizki
and Mille Gandelsman}


\section{Today's Lecture}

\textbf{Markov Chains:}

\begin{itemize}
\item The stationary distribution.
\item Special Case of random walks on graphs.
\item Cover Times. 
\item An application to complexity: $STConn\in RL$.
\end{itemize}

\section{Definition of Markov Chains}

\begin{definition}
Let $\Omega$ be the ground set of states. A \defn{Markov chain}
(in the following, referred to as MC) is a sequence of random variables $X_{0},X_{1},\ldots,X_{t}\in\Omega$
that fulfill the 'Markovian Property': \[
\Pr[X_{t+1}=y|X_{0}=x_{0},X_{1}=x_{1},\ldots,X_{t}=x_{t}]=\Pr[X_{t+1}=y|X_{t}=x_{t}].\]
$\Omega$ can be infinite in the general case, but for the purposes
of this class is always finite, so we can think of it as the set of
nodes in a graph (usually denoted by $V$).
\end{definition}
The definition mathematically describes a situation where given the present state, future states are not reliant upon past states. 

Without loss of generality we can assume that the transitions are
independent in time. This is convenient because it allows discussing
the chain in the terms of the joint probability function $P(x,y)$
defined for every $x,y\in\Omega$ as: \[
P(x,y)=\Pr[X_{t+1}=y|X_{t}=x]\]
The set of transition probabilities $P(x,y)$ can be described as
a directed graph, where the edges are labeled by the probabilities
of going from one state to the other, or by a \defn{transition matrix}:
\begin{definition}
The \defn{transition matrix} $P$ of a set of transition probabilities $P(x,y)$ is a matrix $P$ where P(x,y) denotes the probability that a system in state x transitions to state y.
\end{definition}

\section{t-step Distribution}

We call the initial probability distribution over all states \defn{initial
distribution}, and denote it by $\Pi^{0}$. 
\begin{definition}
The \defn{t-step distribution}, denoted by $\Pi^{t}$, is the distribution obtained after taking $t$ steps from the initial distribution. 
\end{definition}
Using matricidal notation: $\Pi^{t}=\Pi^{0}P^{t}$,
where $P^{t}$ is the transition matrix raised to the $t$-th power.
It is easy to show that $P^{t}(x,y)$ is exactly the probability
to start at $x$ and end at $y$ after taking $t$ steps. Indeed,
consider a $t$-step path from $x$ to $y$ by first taking a single
step to some vertex $z$, and then taking $t-1$ steps to $y$. Thus
we have: \[
P^{t}(x,y)=\begin{cases}
P(x,y) & \text{ if $t=1$}\\
\sum_{z\in\Omega}P(x,z)P^{t-1}(z,y) & \text{ if $t>1$}\end{cases}\]


\section{The Stationary Distribution}
\begin{definition}
The \defn{stationary distribution} is a distribution $\Pi$ such
that for every $y\in\Omega$: \[
\Pi(y)=\sum_{x\in\Omega}\Pi(x)P(x,y)\]
\end{definition}

Note that the last is naturally not true for a general distribution.

\underbar{Comments:}
\begin{enumerate}
\item Not all graphs have a stationary distribution.
\item Some graphs have more than one stationary distribution.
\item Different graphs have different stationary distributions.
\end{enumerate}

\section{Which Graphs Have Unique Stationary Distributions?}

\begin{definition}
A Markov chain is said to be \defn{ergodic} if $\exists t_{0}$
such that $\forall t>t_{0}$ and $\forall x,y\in\Omega$: $P^{t}(x,y)>0$.
\end{definition}

Let us mention without a proof the following theorem, which states
a couple of conditions which are sufficient and essential for a Markov
chain to be ergodic:

\begin{theorem} A finite Markov chain is \defn{ergodic} if and only if it
is \defn{irreducible} and \defn{aperiodic}.
\end{theorem} 

Recall that: 

\begin{definition}
A Markov chain is said to be \defn{irreducible} if $\forall x,y\in\Omega$: $\exists t=t(x,y)$ such that $P^{t}(x,y)>0$.
\end{definition}

\begin{definition}
A Markov chain is said \defn{aperiodic} if $\forall x\in\Omega$: $\gcd\{t|P^{t}(x,x)>0\}=1$.
\end{definition}

An important class of Markov chains is the ones in which a stationary
distribution exists and is unique. It turns out ergodicity is sufficient
to guarantee a stationary distribution, as stated by the following
theorem: \begin{theorem} Every ergodic Markov chain has a unique
stationary distribution. \end{theorem}


\section{Random Walk on a Graph}
\begin{definition}
A \defn{random walk} on a graph $G=(V,E)$ is a sequence
of nodes $s_{0},s_{1},...$ where $s_{0}$ is the \defn{start node} and
at each step $i$, $s_{i+1}$is picked by choosing a transition uniformly
at random from $N(s_{i})$, the set of edges outgoing form $s_{i}.$
\end{definition}

Note that we pick the next state uniformly at random from the edges
outgoing from the current state and not from the neighbors of the
current state (it is not the same, as one can see for example in the
case of double edges or self loops). 

For a random walk on a graph, $P(i,j)$ is easy to compute. Let$E(i,j)$
denote the number of edges outgoing from $i$ to $j$ and let $\dego(i)$
denote the total number of outgoing edges from a node $i$. Then:

\[
P(i,j)=\frac{|E(i,j)|}{\dego(i)}\]


Note that indeed $\forall i$: $\sum_{j}P(i,j)=1$, or in other words
$P$ is stochastic, which is required because the rows of $P$ specify
a probability of transition. 

\underbar{Reminder:}
\begin{itemize}
\item \begin{definition} A matrix is said to be \defn{stochastic} if the entries in each row sum to one. \end{definition}
\item \begin{definition} A matrix is said to be \defn{doubly stochastic} if both the entries in each row sum to one and the entries in each column sum to one. \end{definition}
\end{itemize}

\begin{definition} A Graph is said to be \defn{doubly stochastic} if it's transition matrix is doubly stochastic. 
\end{definition}

An example of a doubly stochastic directed graph is one where $\degi(i)=\dego(i)=d$,
where $d$ is the same for all nodes $i\in V$. For undirected graphs,
a $d$-regular graph is doubly stochastic. 

Note, by the way, that the stationary distribution for the random
walk on an undirected graph looks like $(\frac{\deg(x_{1})}{2m},\frac{\deg(x_{2})}{2m},...)$,
where $m$ is the total number of edges.


\begin{theorem}
\label{doublystochasticuniform}
A stationary distribution of a Markov chain with a doubly stochastic transition matrix
is the uniform distribution.
\end{theorem}


\section{Cover Times}
For the general case, we define the \defn{hitting time of $i$ to
$j$} as follow: 
\begin{definition}
The \defn{hitting time of $i$ to $j$}, denoted by $h_{ij}$ is the expected time to reach the state $j$ when starting from the state $i$.
\end{definition}

\begin{theorem} \label{hittingtimedist} The expected time for a random walk on an ergodic Markov chain starting at state
$i$ to return to $i$, denoted by $h_{ii}$, is $\frac{1}{\Pi(i)}$\end{theorem} 

\begin{definition}
Denote:
\[
    \mathcal{C}_u(G) = \mathbb{E}[\mbox{number of steps to visit all the nodes in } G \mbox{ when start at } u]
\]

And based on that, we'll define the \defn{cover time of a graph} to be:
\[
    \mathcal{C}(G) = max_u \mathcal{C}_u(G)
\]
\end{definition}

\subsection{Examples}
\begin{enumerate}
\item{$K_n^*$ - the complete graph on $n$ nodes and self loops at each node.}

\begin{fact}[Cover time of $K_n^*$]
\[
\mathcal{C}(K_n^*) = \Theta(n\cdot\ln n)
\]
\end{fact}

The calculation is the same as \textit{$n$ coupons collection}:
Let us define a new markov chain as follow:
\begin{itemize}
\item Let state $j$ be the state at which you've already collected $j$ coupons.
\item Let $I_j$ be the expected number of coupons you should collect in order to get from state $j$ to state $j+1$.
\item $I_j = 1/\mathbb{P}[\mbox{the next coupon you'll take will be new when you have } j \mbox{ coupons}] = \frac{n}{n-j} $
\item $\mathcal{C}(K_n^*) = \sum_{j=0}^{n-1} I_j = n \cdot \sum_{j=1}^n \frac{1}{j}$
\item We known that $\sum_{i=1}^n \frac{1}{i} = \Theta(\ln n) $
\item Therefore $\mathcal{C}(K_n^*) = \Theta(n \cdot \ln n) $
\end{itemize}

\item{$L_n$ - \textit{line $n$-graph}}

\begin{fact}[Cover time of $L_n$]
\[
\mathcal{C}(L_n) = \Theta(n^2)
\]
\end{fact}

\begin{figure}[H]
 \setlength{\epsfysize}{60pt} \vspace{3mm}
 \centerline{\epsfbox{linegraph}}
\caption{A line $n$-graph}
\end{figure}

\item{\textit{$n$ nodes lollipop-graph} - a $L_{\frac{n}{2}}$ graph connected at one end to a $K_{\frac{n}{2}}^*$ graph.}

\begin{fact}[Cover time of \textit{$n$ nodes lollipop-graph}]
\[
\mathcal{C}(n \mbox{\textit{ nodes lollipop-graph}}) = \Theta(n^3)
\]
\end{fact}
\begin{figure}[H]
 \setlength{\epsfysize}{70pt} \vspace{3mm}
 \centerline{\epsfbox{lollipop}}
\caption{A lollipop graph}
\end{figure}

\end{enumerate}

\subsection{An upper bound on the cover time of an undirected graph}

\begin{theorem}
\label{covertimebound}
Let $G(V,E)$ be an undirected, connected graph with no multiedges, with $m$ undirected edges,
and $n$ nodes. Then:
\[
\mathcal{C}(G) \le 2(m+n)(n-1) \le 4m(n-1)  = O(n^3)
\]

\end{theorem}

Notice that:
\[
2(m+n)(n-1) = O(n^3)
\]
follows from the fact that $m = O(n^2)$.

\begin{observation}
If $G$ is an undirected graph, and $\delta G$ is $G$ with a self-loop on every node, the cover time
of $\delta G$ is at least the cover time of $G$, since walks on $\delta G$ are the same as walks on $G$, except
they might "spend" some steps on the self loops.
\end{observation}

By using the observation, we can prove the theorem by assuming $G$ has a self-loop on every node,
and showing a bound on its cover time that is $2m(n-1)$.
Then, notice that for the general case, we could look at $\delta G$, which has at most $m+n$ edges, 
and the upper bound on its cover time, which is $2(m+n)(n-1)$ is an upper bound on the cover time of $G$.


\begin{proof}{of Theorem 21}
\begin{definition}
\[
C_{i,j} = \mathbb{E}[\mbox{number of steps for a random-walk starting at $i$ to hit $j$ and return to $i$}]
\]

By linearity of expectations we can see that:
\[
C_{i,j} = h_{ij} + h_{ji}
\]

\end{definition}

\begin{lemma}
\label{cuvbound}
\[
\forall(u,v) \in E: C_{u,v} \le 2m
\]
\end{lemma}

\begin{proof}{\textbf{(of lemma)}}
A traversal on the graph in which $(u,v)$ is traversed twice:\newline
$(u,v),(v,w) \ldots (u,v) $ is a commute from $u$ to $v$ and back to $u$.
Therefore, an upper bound on the expected length of such a traversal will also be
an upper bound on $C_{u,v}$.
\newline
We now want to show that
\[
\mathbb{E}[\mbox{time between two visits to } (u,v)] \le 2m
\]

Denote $P$ as the transition matrix for a random walk over $G$.
Observe that $P_{u,v} = \frac{1}{d(u)}$.

Let's define a new directed graph $G'(V',E')$:
\begin{itemize}
\item $V'$ will have two nodes for each undirected edge $(u,v) \in E$: a node $(u,v)$, and a node ${(v,u)}$.
\item $E'$ will have edges to connect each pair of adjacent egdes in $G$. i.e. $(a,b),(c,d) \in E' \iff b = c$'.
\item $Q$ is a transition matrix for $G'$ defined as follows:
\[
Q_{(u,x),(v,w)} = \begin{cases}
P_{v,w} = \frac{1}{d(v)}, & \mbox{if } (u,x),(v,w) \in E'\\
0, & \mbox{otherwise}
\end{cases}
\]
\end{itemize}

Let's take a look at an example of building $G'$ from $G$ and $Q$ from $P$.\newline
Let $G$ be the graph:

\begin{figure}[H]
 \setlength{\epsfysize}{70pt} \vspace{3mm}
 \centerline{\epsfbox{exampleg}}

\caption{Example undirected graph $G$}
\end{figure}

The random walk transition matrix for $G$, $P$ will be:
\[
    \begin{array}{c|cc|}
      & 1 & 2 \\ \hline
      1 & \frac{1}{2} & \frac{1}{2}\\
      2 & 1 & 0\\ \hline
    \end{array}
\]
$Q$ will therefore be:

\[
    \begin{array}{c|ccc|}
      & (1,1) & (1,2) & (2,1) \\ \hline
      (1,1) & \frac{1}{2} & \frac{1}{2} & 0\\
      (1,2) & 0 & 0 & 1 \\
      (2,1) & \frac{1}{2} & \frac{1}{2} & 0 \\ \hline
    \end{array}
\]
\newpage

And $G'$:\newline
\begin{figure}[H]
 \setlength{\epsfysize}{70pt} \vspace{2mm}
 \centerline{\epsfbox{examplegprime}}

\caption{$G'$ as built according to $G$}
\end{figure}






It's easy to see that $G'$ defined that way is a Markov Chain.
We can also show that $Q$ is \textit{doubly stochastic}:
\begin{itemize}
\item{rows sum to $1$}:
Fix $(u,v) \in E$
\[
\sum_{a\in V, b\in \Gamma(a)} Q_{(u,v),(a,b)} = 
\sum_{b\in \Gamma(v)} Q_{(u,v),(v,b)} = 
\sum_{b\in \Gamma(v)} P_{v,b} = 
\sum_{b\in \Gamma(v)} \frac{1}{d(v)} = 
d(v) \cdot \frac{1}{d(v)} = 1
\]

\item{columns sum to $1$}: 
Fix $(u,v) \in E$
\[
\sum_{b\in V, a\in \Gamma(b)} Q_{(a,b),(u,v)} = 
\sum_{a\in \Gamma(u)} Q_{(a,u),(u,v)} = 
\sum_{a\in \Gamma(u)} P_{u,v} = 
\sum_{a\in \Gamma(u)} \frac{1}{d(u)} = 
d(u) \cdot \frac{1}{d(u)} = 1
\]
\end{itemize}

Since by assumption, $G$ has a self loop on every node, $G'$ also has a self loop on every node (by construction), and therefore,
since it's irreducible and aperiodic, it's ergodic.\newline 
Therefore, according to Theorem \ref{hittingtimedist} in $G'$:
\[
h_{(a,b),(a,b)} = 2m
\]

Which means that the expected time between two visits of $(u,v)$ is $2m$, as we wanted to show.

\end{proof}{\textbf{(of lemma)}}

In order to continue with the proof of the theorem, let $T$ be some spanning tree of $G$, with root
$v_0 \in V$.
$T$ has $n-1$ edges. A \textit{depth first search} traversal on $T$ would give us $v_0,v_1,\ldots,v_{2n-2}$,
s.t $v_{2n-2} = v_0$, and the traversal traverses every edge of $T$ exactly once in each direction.
In addition, $\forall v\in V: v \in \{v_0, v_1, \ldots, v_{2n-2}\}$.
Therefore, if we look at a random walk that visits $\{v_0, v_1, \ldots, v_{2n-2}\}$ (in that order), its expected length is an upper bound
on $\mathcal{C}_{v_0}(G)$. So:
\[
\mathcal{C}_{v_0}(G) \le \sum_{j=0}^{2n-3} h_{v_j,v_j+1} = \sum_{(u,v) \in T} C_{u,v}
\]

But according to Lemma \ref{cuvbound},
\[
C_{u,v} \le 2m
\]

And therefore, as $T$ has $n-1$ edges:
\[
\mathcal{C}_{v_0}(G) \le 2m(n-1)
\]

That's true for every choice of $v_0$, and thus:
\[
\mathcal{C}(G) \le 2m(n-1)
\]

\end{proof}

\begin{itemize}
\item Notice that the theorem doesn't work for graphs that aren't connected, as those can't be covered.
\item Also note that we demanded $G$ to be undirected. For directed graphs the bound isn't true, and
moreover, there are examples of directed graphs with exponential cover time.\newline
For example, see the graph in Figure 5.
\begin{figure}[H]
\label{graphexpo}
 \setlength{\epsfysize}{100pt} \vspace{3mm}
 \centerline{\epsfbox{exponential}}
\caption{A directed graph with exponential cover time}
\end{figure}

However, for \textit{d-regular} directed graphs, the theorem does hold.
\end{itemize}

\section{An application to complexity: $STConn\in RL$}

$STConn$ is the problem of determining, given a graph $G$ and two vertexes $s$ and $t$, whether $s$ and $t$ are connected.
The problem can be solved in linear time. The question is, however, whether we could solve it in logarithmic space.\newline
$USTConn$ is $STConn$ for an undirected graph $G$.
\begin{definition}
\defn{$RL$} is the class of problems that are solvable in logarithmic space, with random bits.
\end{definition}

Given an algorithm $\mathcal{A}(G,s,t)$, we'll say that it solves $USTConn$ in $RL$ if:
\begin{enumerate}
\item $\mathbb{P}[\mathcal{A}(G,s,t) = \mbox{yes}] \ge \frac{3}{4}$ if $s$ and $t$ are connected in $G$.
\item $\mathbb{P}[\mathcal{A}(G,s,t) = \mbox{no}] = 1$ otherwise.
\end{enumerate}

\begin{theorem}
\[
USTConn \in RL
\]
\end{theorem}

\begin{proof}
We'll use the following algorithm:
\begin{enumerate}
\item Given $G(V,E)$, $s, t \in V$, take a random walk, starting at $s$ for $4 \cdot B$ steps, with $B = 4m(n-1)$.
\item If the random walk visited $t$, output "yes", otherwise, output "no".
\end{enumerate}

The algorithm only uses space to save the current state of the walk, and to count the steps, and therefore
it uses logarithmic space.\newline

If $s$ and $t$ are not connected, the random walk will never visit $t$ and "no" will be returned. Therefore:
$\mathbb{P}[\mathcal{A}(G,s,t) = \mbox{no}] = 1$ \newline.

If $s$ and $t$ are connected, "no" is returned if $t$ was not visited, therefore:
\[
\mathbb{P}[\mathcal{A}(G,s,t) = \mbox{no}] \le \mathbb{P}[\mbox{ we didn't cover the graph in 4B $steps$}] 
\]

But according to Theorem \ref{covertimebound}:  $4B \ge 4 \cdot \mathbb{E}[\mbox{number of steps to cover G}]$.
And therefore, using Markov's inequality:
\[
\mathbb{P}[\mathcal{A}(G,s,t) = \mbox{no}] \le \frac{1}{4}
\]

Therefore: $\mathbb{P}[\mathcal{A}(G,s,t) = \mbox{yes}] \ge \frac{3}{4}$\newline
\end{proof}
A very recent important result has shown that this algorithm can be de-randomized."

\end{document}



