\documentclass{article}
\include{macros}

\usepackage{epsfig}
\usepackage{graphicx}
\usepackage{epsfig}
\usepackage{fullpage,url}
\usepackage[dvips]{hyperref}
 \usepackage[all,graph,poly]{xy} % for complicated commutative diagrams

\newtheorem{Lemma}{Lemma}
%\newtheorem{definition}[Lemma]{Definition}
\newtheorem{Proposition}[Lemma]{Proposition}
\newtheorem{Algorithm}[Lemma]{Algorithm}
\newtheorem{Theorem}[Lemma]{Theorem}
\newtheorem{Conjecture}[Lemma]{Conjecture}
\newtheorem{Problem}[Lemma]{Problem}
\newtheorem{Example}[Lemma]{Example}
\newtheorem{OP}[Lemma]{Open Problem}
\newtheorem{Hypothesis}[Lemma]{Hypothesis}
\newtheorem{Construction}[Lemma]{Construction}
\newtheorem{Corollary}[Lemma]{Corollary}
\newtheorem{ex}[Lemma]{Exercise}
%\newcommand{\F}{\mathcal{F}_G}
% newcommands for xy-pic : edge, node and labels
%
\newcommand{\e}[1]{\ar@{-}[#1]}
%
\newcommand{\ed}[1]{\ar@{--}[#1]}
\newcommand{\ee}[1]{\ar@{=}[#1]}
\newcommand{\er}[1]{\ar@{-}[#1] |-{\SelectTips{cm}{}\object@{<}} |{\SelectTips{eu}{}\object@{}}}
\newcommand{\el}[1]{\ar@{-}[#1] |-{\SelectTips{cm}{}\object@{>}} |{\SelectTips{eu}{}\object@{}}}
\newcommand{\edr}[1]{\ar@{--}[#1] |-{\SelectTips{cm}{}\object@{<}} |{\SelectTips{eu}{}\object@{}}}
\newcommand{\edl}[1]{\ar@{--}[#1] |-{\SelectTips{cm}{}\object@{>}} |{\SelectTips{eu}{}\object@{}}}
%
\newcommand{\n}{*+[o][F-]{ }} 
%
\newcommand{\nn}[1]{*+[o][F-]{#1}}
\newcommand{\nnn}[1]{*++[o][F=]{#1}}
%
\newcommand{\lul}[1]{\ar@{}[l]_<<{#1}}
\newcommand{\rrul}[1]{\ar@{}[r]^<<<<{#1}}
\newcommand{\rul}[1]{\ar@{}[r]^<<{#1}}
\newcommand{\ldl}[1]{\ar@{}[l]^<<{#1}}
\newcommand{\rdl}[1]{\ar@{}[r]_<<{#1}}
\newcommand{\dl}[1]{\ar@{}[d]_<<{#1}}
\newcommand{\dll}[1]{\ar@{}[dd]_{#1}}
%
%*****************************************************************************

\begin{document}
% lecture number : lecture title : scribe

%\include{macros.tex}
\lecture{2}{Overview of the course -Continued }{Shankar Bhamidi}{shanky@stat}

We will continue with the pre-survey started in the previous class and give a brief overview of some of the other topics that shall be considered in the course. Before we begin please take a look at the end of this note to see what the difficulty level of various exercises (usually accompanied with a rational number of stars ) means.

\section{Cutoff problem in Markov Chains}
Consider a sequence of reversible Markov Chains growing to $\infty$ in some sense. For e.g. consider the delayed Random walk on the hypercube $\{0,1\}^n$ in n dimensions where the transitions are given by  
\begin{eqnarray*}
	p_n(x,y) &=& \frac{1}{2n} \mbox{if x,y differ in 1 bit} \\
	 &=& 1/2 \forall \mbox{  } x \\
	 &=& 0 \mbox{  otherwise } 
\end{eqnarray*}

Note that the delay of 1/2 which is imposed at each site is mainly to get rid of periodicity issues. What we are interested in is the asymptotics of the total variation distance from the stationary distribution namely 
\begin{definition}
For an irreducible aperiodic Markov chain (we will usually be dealing with finite state Markov Chains) with stationary distribution $\pi(.)$ define the total variation distance
\[||p^t(x,.) - \pi(.)||_{TV} = 1/2 \sum_{y} |p^t(x,y)-\pi(y)| \]
where $p^t(.,.)$ as usual defines the t step transition probability for the chain.
Define for a fixed $\epsilon < 1$ the mixing time
\[\tau_n(\epsilon) = \min \{t:\max_x ||p^t(x,.) - \pi(.)||_{TV} < \epsilon\}\] 
\end{definition}

Now we come to the main definition of this section:

\begin{definition}
In the asymptotic analysis of the above chain by cutoff phenemenon we mean that $\forall 0<\epsilon < 1/2 $
\begin{equation}
\label{cutoff:eqn}
\frac{\tau_n(\epsilon)}{\tau_n(1-\epsilon)} \rightarrow 1
\end{equation}
as $n\rightarrow \infty$
\end{definition}
Intuitively the pictures we have in mind for the cutoff phenemenon is the following:



\includegraphics[height=60mm]{cutoff.jpg}

The above picture was taken from \cite{dia} where a very nice introduction of the cutoff phenomenon can also be found. This picture describes distance to stationarity in riffle shuffles with $n$ cards which seems to have a cutoff at $3/2\log{n}$.

An example of chain without a cutoff is the delayed random walk on the n cycle where we have the transitions

\begin{eqnarray*}
	p_n(x,x-1)&=& 1/4 \\
	p_n(x,x)&=& 1/2\\
	p_n(x,x+1)&=& 1/4  
\end{eqnarray*}
where of course all operations are done modulo n. Here what can be shown is that 
\[\tau_n(\epsilon) = c(\epsilon) n^2\]
for some constants which explicitly depend on $\epsilon$ and so Eqn \ref{cutoff:eqn} cannot hold.

{\bf Some Applied problems where there is no cutoff:} Choosing contingency tables with fixed row and coloumn sums. Again see \cite{dia}

Early examples where such a phenemenon occured was the hypercube(Aldous) and Random Transpositions of cards (Diaconis and Shahshani). All in all around 20 different families of examples are known where the above happens but there seems to be no general theory as to why the above happens.

Before we come to the main conjecture we need the following fact about reversible Markov Chains

{\bf Fact}: For reversible (aperiodic) Markov Chains the transition matrix has all reall eigen values
\[\lambda_1=1 >  \lambda_2 \geq \lambda_3 \ldots \geq \lambda_n > -1 \]
The quantity $1-\lambda_2$ is called the spectral gap and is one of the quantities that determines the rate of convergence to stationarity. Check the Aldous and Fill book on the web if you are not familiar with this quantity.
\begin{Conjecture}[Yuval(****)]
A simple criterion for cutoff: Assume the chain is transitive i.e. $\forall \mbox{ states } v,w $ $\exists$ a map $\phi_{v,w}$ such that
\begin{enumerate}
	\item $\phi_{v,w}(v) w$
	\item $p(x,y) = p(\phi_{v,w}(x),\phi_{v,w}(y)) \mbox{  } \forall x,y$
	 For a family of transitive aperiodic irreducible finite state space markov chains:
	
\begin{equation}
	\mbox{cutoff} \Leftrightarrow (1-\lambda_2^n)\tau_n(1/2) \rightarrow \infty
\end{equation}
\end{enumerate}
\end{Conjecture}

\begin{ex}[**]
 Give a counter example to the above conjecture when we do not have a transitive markov chain.
\end{ex}
\begin{OP}[***]
suppose we have n cards. Pick a card at random and put it back at a random position (note that there is a 1/n chance that the chosen card goes back to it's original place). What is known is that 
\[1/4 n\log{n} \tau(1/2) \leq 4n\log{n}\]

Does it exhibit a cutoff ?
\end{OP}

\begin{OP}[***]
Consider transitive fixed degree expander graphs. Show that the delayed random walk on these graphs exhibits a cutoff.
\end{OP}

\section{Sidorenko's Conjecture}
We shall describe a special case in this note albeit there are many general versions.
\begin{Conjecture}
start with a finite bipartite graph with vertex set $V=V_0 \sup V_1$ with edge set $E\subset V_0 X V_1$. Suppose A is an even which depends on 2 events namely $A\subset [0,1]^2$. Then 

\begin{equation}
\int_{[0,1]^V} \Pi_{(i,j) \in E} 1_A(x_i,y_j) \mathbf{dx} \mbox{  }  \mathbf{dy} \geq \left(\int 1_A(x,y) dx\mbox{ } d y\right)^{|E|}
\end{equation}
\end{Conjecture}


\subsection{Exercises}
Consider the set 
\[A=\{(x,y): 1/4 <x+y < 3/4\} \cap [0,1]^2\]
\begin{ex}[1/2*]
Verify the conjecture for A and the Graph 1.

\begin{figure*}
\centerline{
\xymatrix{
&\n  \rul{x_1} \e{ddr}  & & \n  \rul{x_2}   \e{ddl}               & \\
 & & &  &\\
 &  &\n  \rdl{y_1}    &  & \\
  &          &          \mbox{Graph 1}             &           & 
}
}
\end{figure*}
\end{ex}
\begin{ex}[*]
Verify the conjecture for A and the Graph 2 
\begin{figure*}
\centerline{
\xymatrix{
 &\n  \rul{x_1} \e{ddr}  & & \n  \rul{x_2}   \e{ddl} \e{ddr} & & \n \rul{x_3} \e{ddl} \e{ddr}                && \\
 & & &  & &&&\\
 &  &\n  \rdl{y_1}    &  & \n \rdl{y_2}  & & \n \rdl{y_3} &\\
  &          &         &  \mbox{Graph 2}  &           &           & & 
}
}
\end{figure*}
\end{ex}

{\bf Fact:} The point of the above 2 exercises is that Sodorenko's conjecture has been proved for paths.

\begin{ex}[**]
Verify the conjecture for the hypercube and the A described above.
\end{ex}

The point of the conjecture is that introducing the structure of a Bipartite graph increases the correlation. {\bf Important} Note that the above conjecture cannot be true for a graph which has an odd cycle, for example take the graph G to be 
\[\mbox{G = a triangle} \]

and the event A to be 

\[A=\{x,y : x<1/2 y>1/2\} \cup \{x,y: x>1/2, y<1/2\}\]
\section{Minimal Spanning forests}
Recall: In an infinite connected locally finite graph G = (V,E) the FMSF $\F$, using the IID uniform weights $u_e,e\in E $ as 
\[\F = \{e: \mbox{$u_e$  is not the largest edge label in a finite cycle}\}\]
We argued that all the components of $\F$ have infinitely many vertices , a.s..
\begin{OP}
Find the \# of components of $\F$ when $G= \mathbf{Z}^d$ for d$\geq 3$.
\end{OP} 
\begin{Theorem}[Lyons,P,Schramm]
Fix any infinite connected locally finite graph G.
Fix $\epsilon > 0$ . Adjoin to $\F$ every $e \notin \F$ indep with prob $\epsilon$. Then the resulting edge set defines a connected graph a.s.

\end{Theorem}
\emph{Pf:} The idea of the proof is to use the original labels $u_e$ in the construction of the edges that are added on to $\F$. For a an edge $e=(u,v)$ define
\[Z(e) = \inf_{\phi \in P_{u,v}, \phi=\{e_1,\ldots,e_k\}} \max_i u(e_i)\]

where $P_{u,v}$ are the set of all paths from u to v which do not contain the edge e=(u,v)

Now note that 
\[\F= \{e: u(e) < Z(e)\}\]

Further since for any edge e $Z(e)$ is a function of $\{u(e^*) :e^* \neq e\}$ thus conditional on Z(e) and the event that e $\notin \F$ we know that 
\[u(e) \sim Unif[Z(e),1]\]
The idea which will be properly described in the next class is to use the above to generate the new edges which are adjoined to $\F$ and prove that any 2 adjacent nodes u,v are connected in the new graph.  

\section{Exercise difficulty level and implications}
\begin{itemize}
\item[*] reasonably challenging: If you turn in 4-5 of these exercises then that is enough to get a grade in the course (i.e. a talk is not necessary)
\item[**] hard: 1 exercise along with the accompanying latex writeup enough to get a grade in the course
\item[***] Very hard: Also Yuval does not know a solution
\item[****] Very very hard and also (according to Yuval) is an important problem in probability. These problems Yuval believes could constitute a Phd thesis or more. 
\end{itemize}
Also note that although the above gradation has only integer valued stars we might be dealing sometimes with rational valued stars (e.g. **1/2 means 2 and 1/2 stars). All the rules of arithmetic will then apply to the above setup in star space.
\begin{thebibliography}{99}

\bibitem{dia} Diaconis, Persi (1996), The cutoff phenomenon in finite {M}arkov chains, {\em Proc. Nat. Acad. Sci. U.S.A.} {\bf 93} no. 4 1659--1664.


\end{thebibliography}
\end{document}