\documentclass[11pt]{article}
\usepackage{latexsym}
\usepackage{amsmath,amssymb,amsthm}
\usepackage{epsfig}
\usepackage[right=0.8in, top=1in, bottom=1.2in, left=0.8in]{geometry}
\usepackage{setspace}
\usepackage{bbm}
\spacing{1.06}

\newcommand{\handout}[5]{
  \noindent
  \begin{center}
  \framebox{
    \vbox{\vspace{0.25cm}
      \hbox to 5.78in { {COMS 4995-2:\hspace{0.12cm}Advanced
          Algorithms (Spring'20)} \hfill #2 }
      \vspace{0.48cm}
      \hbox to 5.78in { {\Large \hfill #5  \hfill} }
      \vspace{0.42cm}
      \hbox to 5.78in { {#3 \hfill #4} }\vspace{0.25cm}
    }
  }
  \end{center}
  \vspace*{4mm}
}

\newcommand{\lecture}[4]{\handout{#1}{#2}{#3}{Scribes:\hspace{0.08cm}#4}{Lecture #1}}

\newtheorem{theorem}{Theorem}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{observation}[theorem]{Observation}
\newtheorem{example}[theorem]{Example}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{claim}[theorem]{Claim}
\newtheorem{fact}[theorem]{Fact}
\newtheorem{assumption}[theorem]{Assumption}

\newcommand{\E}{{\mathbb E}}
\DeclareMathOperator{\var}{Var}

\begin{document}

\lecture{9: Random walks, and the largest eigenvalue}{Feb 18,
  2020}{Instructor:\hspace{0.08cm}\emph{Alex Andoni }}{\emph{Xingyu Zhu,Yiyang Zeng}}

\section{Introduction}
In the previous lecture,we introduced the random walk, spectral graph theory and rayleigh quotient, today we continue the topic of random walk, we will apply spectral decomposition and drive some properties of diffusion and eigenvalues, and we will investigate the relationship between eigenvalue and graph connectivity. 

\section{Remainder}
\begin{itemize}
    \item we can apply spectral decomposition to a symmetric graph matrix M : M = $\sum_{i=1}^n \lambda_i v_i v_i^T$, where $v_1,v_2,...,v_n $ are n orthonormal eigenvectors such that $\vert \vert v_i \vert \vert = 1$ and $v_i^T v_j = 0$  $\forall i \neq j$.
    \item rayleigh quotient is defined as R(x)= $\dfrac{x^t M x}{{\vert \vert x \vert \vert}^2}$ and R($v_i$) = $\lambda_i$ $\forall v_i$.
\end{itemize}{}


\section{Diffusion/ Random walk}

Let $x^0 (\in R^n) = \textrm{distribution over vertices in G}$.
  \[x^t = W(x^{t-1}) = AD^{-1}x^{t-1} (t \geq 1)\]
  \begin{equation}
      x^t = AD^{-1}\cdot AD^{-1}\cdot \cdot \cdot x^0 = (AD^{-1})^t\cdot x^0
  \end{equation}

If (AD$^{-1}$) is symmetric (eg, when $D$ is diagonal of the same
number, equivalently all degrees are exactly equal)\\
e.g. when d-regular:
\begin{align*}
        AD^{-1} &= \frac{1}{d}A,  M = AD^{-1} = \sum \lambda_i v_i v_i^T\\
        M^2 & = (\sum_i \lambda_i v_i v_i^T)\cdot (\sum_j \lambda_j v_j v_j^T)\\
        & = \sum_i \lambda_i v_i (v_i^T v_i) v_i^T \lambda_i= \sum_{i=1}^n \lambda_i^2 v_i v_i^T
\end{align*}

In general:
$$M^t  = \sum_{i=1}^n \lambda_i^t v_i v_i^T \textrm{(by induction)}$$

when AD$^{-1}$ is not symmetric, we can analyze a related matrix. 
\begin{align*}
 x^t &= AD^{-1}\cdot AD^{-1}\cdot \cdot \cdot x^0 = (AD^{-1})^t\cdot x^0\\
 &= AD^{-1/2}D^{-1/2}AD^{-1/2}\cdot \cdot \cdot D^{-1/2}x^0
\end{align*}

\begin{definition}
$\hat{A} = D^{-1/2}AD^{-1/2}$
\end{definition}

\textbf{Note:}
$\hat{A_{i,j}} = \frac{A_{i,j}}{\sqrt{d_i}\sqrt{d_j}}$

\begin{definition}
$y^t = D^{-1/2}x^t $
\end{definition}

From the definition 1,2 and equation(1),we have:
\begin{equation}
    y^t = \hat{A}^t\cdot y^0.
\end{equation}

Apply spectral decomposition for $\hat{A}$:
\begin{align*}
\begin{split}
    \hat{A} &= \sum \lambda_i v_i v_i^T, \hat{A}^t = \sum \lambda_i^t v_i v_i^T\\
    y^0 &= \sum_{i=1}^n \alpha_i v_i,  \alpha_i \in R, ||y^0||_2^2 = \sum \alpha_i^2\\
    y^t = \hat{A}^t y^0 &= (\sum_{i=1}^n \lambda_i^t v_i v_i^T)(\sum_{j=1}^n \alpha_j v_j)\\
    &= \sum_{i,j} \lambda_i^t v_i v_i^T \alpha_j v_j\\
    &= \sum_i \lambda_i^t \alpha_i v_i
\end{split}{}
\end{align*}

\begin{claim}
\begin{align*}
    \textrm{If } &\lambda_i < 1 \implies \textrm{term } \lambda_i^t
    \alpha_i v_i \textrm{ disappears as t} \rightarrow \infty \\
    \textrm{If } &\lambda_{i} > 1 \implies \lambda_{i}^t  \textrm{ diverges}
\end{align*}
\end{claim}
Thus, intuitively, we must have: 
\begin{align*}
    \begin{split}
        1) \vert \lambda_{i} \vert \leq 1 ~&~\forall i\\
        2) \vert \lambda_{i} \vert = 1 ~&~ \exists i
    \end{split}
\end{align*}

\begin{theorem}
$\lambda_{1} = 1$
\end{theorem}
\begin{proof}
1) $\lambda_{1} \geq 1$ (recall $\lambda_1 = \max \ R(x) \ (x\neq0)$)\\

Let $x = (\sqrt{d_1},\sqrt{d_2},...,\sqrt{d_n})^T$: \\
\begin{align*}
    R(x) &= \dfrac{x^T \cdot \widehat{A} \cdot x}{\Vert x \Vert_2^2} \\ 
    &= \dfrac{x^T \cdot D^{-1/2} \cdot A \cdot D^{-1/2} \cdot x}{\sum_{i=1}^n d_i} \\
    &=\dfrac{\mathbbm{1}_n^T \cdot A \cdot \mathbbm{1}}{\sum_{i=1}^n d_i} \\ 
    &= \dfrac{\mathbbm{1}_n \cdot [d_1,d_2,...,d_n]^T}{\sum_{i=1}^n d_i} \\ 
    &= 1
\end{align*}
$\implies \lambda_1 \geq R(x) = 1$ \\
2) $\lambda_1 \leq 1 \Leftrightarrow R(x) \leq 1 \ \forall x \neq 0$\\
\begin{align*}
R(x)&=\dfrac{x^T \widehat{A} x}{\Vert x \Vert_2^2}\\ &=\dfrac{\sum_{ij\in E}\dfrac{A_{ij}}{\sqrt{d_i}\sqrt{d_j}} \cdot x_i x_j}{\Vert x \Vert_2^2}\\ &=\dfrac{\sum_{ij\in E}\dfrac{x_i}{\sqrt{d_i}} \cdot \dfrac{x_j}{\sqrt{d_j}}}{\Vert x \Vert_2^2}\\ &\leq \dfrac{(\sum_{ij\in E}(\dfrac{x_i}{\sqrt{d_i}})^2)^{1/2} \cdot (\sum_{ij\in E}(\dfrac{x_j}{\sqrt{d_j}})^2)^{1/2}}{\Vert x \Vert_2^2}(Cauchy-Schwartz)\\ &= \dfrac{(\sum_i \dfrac{x_i^2}{d_i} \cdot d_i)^{1/2} \cdot (\sum_j \dfrac{x_j^2}{d_j} \cdot d_j)^{1/2}}{\Vert x \Vert_2^2} \\ &= 1
\end{align*}

Cauchy-Schwartz: $p^T \cdot q \leq \Vert p \Vert^2 \cdot \Vert q \Vert^2$
\end{proof}

Remarks: 
\begin{enumerate}
    \item since $v_1 = argmax \ R(x) \Rightarrow v_1 = (\sqrt{d_1},\sqrt{d_2},...,\sqrt{d_n})$ (unique iff $\lambda_2 < 1$)
    \item $R(x) = 1$ iff CS is tight for x iff $\exists\alpha>0$
      s.t. $\dfrac{x_i}{\sqrt{d_i}}=\dfrac{x_j}{\sqrt{d_j}} \cdot
      \alpha$, $\dfrac{x_i}{\sqrt{d_i}}\cdot
      \alpha=\dfrac{x_j}{\sqrt{d_j}}$ (vector $p$ is a rescale of
      vector $q$)\\
$\Rightarrow \alpha = +1$\\
if $\alpha = +1 \Rightarrow
\dfrac{x_i}{\sqrt{d_i}}=\dfrac{x_j}{\sqrt{d_j}} \ \forall ij\in E$

Similarly $R(x)\ge -1$ always (using $p\cdot q\ge -\|p\|\cdot \|q\|$), and $R(x)=-1$ iff the above holds with $\alpha=-1$ ( $\dfrac{x_i}{\sqrt{d_i}}=-\dfrac{x_j}{\sqrt{d_j}})$\\
Applying to our diffusion/random walk example: Recall $y^t=\sum \alpha_i\lambda_i^t v_i$.\\
Given $\lambda_1=1$
if $\vert \lambda_2 \vert,...,\vert \lambda_n \vert < 1 \Rightarrow
\lim_{t \to \infty} y^t  = \alpha_1 \cdot \lambda_1^t \cdot v_1
= \alpha_1 v_1$ \\
where $v_1 = \dfrac{1}{\sum_{d_i}}(\sqrt{d_1},
\sqrt{d_2},...,\sqrt{d_n}) \textrm{ is the unique eigenvector with }
\lambda_1)$

Note that also $\alpha_1 = v_1^T\cdot y^0=\sum_i x_i^0=1$ (by the
assumption that $x^0$ is distribution). Hence $\lim_{t \to \infty} x^t
= D^{1/2}v_1= \begin{pmatrix}
  d_1\\ 
  d_2\\
  ...\\
  d_n
\end{pmatrix} \cdot  \dfrac{1}{\sum d_i}$ is the unique stationary
distribution in this case.
\end{enumerate}

\begin{theorem}
$\lambda_2 < 1 \Leftrightarrow G$ connected
\end{theorem}
\begin{proof}
G is disconnected $ \Rightarrow \lambda_2 = 1$\\

Let's say A has two components: comp1 and rest as below:
\begin{align*}
    \begin{split}
        A=\begin{pmatrix}
        comp 1 & 0\\ 
            0 & rest
    \end{pmatrix}\\
    \end{split}{}
\end{align*}

comp1 will act independently of rest meaning each component has its own eigenvalues and eigenvectors, so each component will have its own top eigenvalue,which is 1 as proven above. Say comp1 is composed of k nodes \{1,2,...,k\}, we can write $v_1=(\sqrt{d_1},...,\sqrt{d_k},0,...,0), v_2=(0,...,0,\sqrt{d_{k+1}},...,\sqrt{d_n})$.\\

Prove in other direction: If G is connected $\Rightarrow \lambda_2 < 1$\\

take $v_2 \perp v_1 ~ (v_1 = \sqrt{d_1},...,\sqrt{d_n})$, prove by
contradiction:



\begin{align*}
    \begin{split}
       \textrm{suppose }R(x = v_2)=1 &\Rightarrow \dfrac{x_i}{\sqrt{d_i}} = \dfrac{x_j}{\sqrt{d_j}} \ \forall(i,j)\\
       &\Rightarrow \dfrac{x_i}{\sqrt{d_i}}=\beta \textrm{ where }
       \beta=\dfrac{x_1}{\sqrt{d_1}} ~~ \forall i\\
         \\
       &\Rightarrow \textrm{x proportional to $v_1$}\textrm{
           (contradicted with } x \perp v_1)
    \end{split}
\end{align*}

where the middle step is since
           there's a path from node 1 to each other node, and we can
           apply the above equality to each edge on this path.
\end{proof}

\end{document}



\end{document}
