Damped random walks and the characteristic polynomial of the weighted Laplacian on a graph
MADHAV P. DESAI\thanks{ Department of Electrical Engineering
400076
Mumbai
India
and \
HARIHARAN NARAYANAN\thanks{ Department of Computer Science
60637
chicago
USA
For $\lambda>0$, we define a $\lambda$-damped random walk to be a random walk that is started from a random vertex of a graph and stopped at each step with probability $\frac{\lambda}{1+\lambda}$, otherwise continued with probability $\frac{1}{1+\lambda}$. We use the Aldous-Broder algorithm (\cite{aldous, broder}) of generating a random spanning tree and the Matrix-tree theorem to relate the values of the characteristic polynomial of the Laplacian at $\pm \lambda$ and the stationary measures of the sets of nodes visited by $i$ independent $\lambda$-damped random walks for $i \in \N$. As a corollary, we obtain a new characterization of the non-zero eigenvalues of the Weighted Graph Laplacian.
damped_rw.tex
\documentclass[12pt]{article}

\usepackage{amsmath,amssymb, fullpage}
\usepackage{graphicx}

\setlength{\oddsidemargin}{0.25 in}
\setlength{\evensidemargin}{-0.25 in}
\setlength{\topmargin}{-0.6 in}
\setlength{\textwidth}{6.5 in}
\setlength{\textheight}{8.5 in}
\setlength{\headsep}{0.75 in}
\setlength{\parindent}{0 in}
\setlength{\parskip}{0.1 in}
\newcommand{\lecture}[4]{
   \pagestyle{myheadings}
   \thispagestyle{plain}
   \newpage
   \setcounter{page}{1}
   \noindent
}
\newtheorem{theorem}{Theorem}
\newtheorem{lemma}{Lemma}
\newtheorem{proposition}{Proposition}
\newtheorem{claim}{Claim}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{definition}{Definition}
\newtheorem{exercise}{Exercise}
\newtheorem{example}{Example}
\newtheorem{open}[theorem]{Open Question}
\newtheorem{notation}{Notation}
\newtheorem{pseudocode}[theorem]{Pseudocode}
\newtheorem{observation}{Observation}
\newtheorem{conjecture}[theorem]{Conjecture}

%% Blackboard bold symbols %%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\newcommand{\N}{\mathbb{N}}
\newcommand{\Z}{\mathbb{Z}}
\newcommand{\Q}{\mathbb{Q}}
\newcommand{\R}{\mathbb{R}}
\newcommand{\C}{\mathbb{C}}
\newcommand{\TT}{\mathbb{T}}
\newcommand{\I}{\mathbb{I}}
\newcommand{\LL}{\mathcal L}

%\def\a{{\mbox{\boldmath $\alpha$}}}
%\def\l{{\mbox{\boldmath $\lambda$}}}
%\def\m{{\mbox{\boldmath $\mu$}}}
%\def\n{{\mbox{\boldmath $\nu$}}}

\def\a{{\mathbf{\alpha}}}
\def\l{{\mathbf{\lambda}}}
\def\m{{\mathbf{\mu}}}
\def\n{{\mathbf{\nu}}}
\def\ra{{\rightarrow}}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%\def\baselinestretch{1.5}         % double space (well...almost!)   
\title{Damped random walks and the characteristic polynomial of the weighted Laplacian 
on a graph}
\author{MADHAV P. DESAI\thanks{
Department of Electrical Engineering, 
Indian Institute of Technology Bombay, 
400076, Mumbai, India,
{\tt madhav@ee.iitb.ac.in}} 
\, and \, HARIHARAN NARAYANAN\thanks{
Department of Computer Science,
University of Chicago,
60637, chicago, USA,
{\tt hari@cs.uchicago.edu}}}

\begin{document}
\maketitle
\begin{abstract}
For $\lambda>0$, we define a $\lambda$-damped random walk to be a random walk that is started from
a random vertex of a graph and stopped at each step with probability $\frac{\lambda}{1+\lambda}$, 
otherwise continued with probability $\frac{1}{1+\lambda}$.
We use the Aldous-Broder algorithm (\cite{aldous, broder}) of generating a random spanning tree and the 
Matrix-tree theorem
to relate the values of the characteristic polynomial of the Laplacian 
at $\pm \lambda$ and the stationary measures of the sets of nodes 
visited by $i$ independent $\lambda$-damped random 
walks for $i \in \N$. As a corollary, we obtain a new characterization of the
non-zero eigenvalues of the Weighted Graph Laplacian. 
\end{abstract}

\section{Introduction}

Consider a weighted graph $G$ in which vertices are labelled $1, \dots, n$.
Let the edge between
$i$ and $j$ have weight $d_{ij}$ and $\sum_j d_{ij} := d_i$. 
The laplacian $\LL$ is an operator from the space of complex valued functions on the nodes of a graph
to itself. For $$f: [n] \rightarrow \C,$$
$\LL f$ is defined by 
$$\forall i \in [n], \LL f(i) = \frac{\sum_{j \in [n]} d_{ij}(f(j)-f(i))}{d_i}.$$
Thus, the following matrix equation holds:
$$D f = D' \LL f,$$
where $D$ is 
\[\left[
\begin{array}{llll}
-d_1 & d_{12} & \cdots & d_{1n} \\
d_{21} & -d_2 & \cdots & d_{2n} \\
\vdots & \vdots &  \ddots & \vdots \\
d_{n1} & d_{n2} & \cdots & -d_n
\end{array}
\right],\]

$f = [f(1), \dots, f(n)]^T,$ 
$\LL f = [\LL f(1), \dots, \LL f(n)]^T$ and
$D'$ is the diagonal matrix whose entry in the $i^{th}$ row and $i^{th}$ column is 
$d_i$.

We consider the transition matrix $D'^{-1}\LL + I$, which is 
\[\left[
\begin{array}{llll}
0 & \frac{d_{12}}{d_1} & \cdots & \frac{d_{1n}}{d_1} \\
\frac{d_{21}}{d_2} & 0 & \cdots & \frac{d_{2n}}{d_2} \\
\vdots & \vdots &  \ddots & \vdots \\
\frac{d_{n1}}{d_n} & \frac{d_{n2}}{d_n} & \cdots & 0
\end{array}
\right],\]
Whenever we consider random walks on $G$, the transition from $i \ra j$ will have probability 
equal to the ${ij}^{th}$ entry of the 
above matrix.

The eigenvalues of the Laplacian are the roots of the polynomial
\[C(\lambda) = \det \left|
\begin{array}{llll}
-d_1(1 + \lambda) & d_{12} & \cdots & d_{1n} \\
d_{21} & -d_2(1 + \lambda) & \cdots & d_{2n} \\
\vdots & \vdots &  \ddots & \vdots \\
d_{n1} & d_{n2} & \cdots & - d_n (1 + \lambda)
\end{array}
\right|.\]

Note that $\lambda$ is an eigenvalue of the laplacian if and only if $1 + \lambda$ is an eigenvalue of the
transition matrix  $D'^{-1} \LL + I$.

Now, let  $\lambda$ take a fixed positive real value.
Consider the following procedure of gernerating a random walk:\\
\begin{enumerate}
\item[1.] Choose a vertex $i$ with probability $$\frac{d_i}{\sum_{j \in [n]} d_j}.$$
\item[2.] Toss a coin that comes up Heads with probability $\frac{\lambda}{1+\lambda}$.\\
		  If the outcome is Heads {\bf STOP}.\\
		  Else make a random transition to a neighbouring vertex with probability
		  proportional to the weight of the corresponding edge.
\item[3.] Goto 2.
\end{enumerate}

\begin{definition}
A random walk generated by the above procedure shall be called a ``$\lambda$-damped random walk".
\end{definition}

\begin{definition}\label{def:Fi}
Let $w_1, \dots, w_i, \dots$ be a sequence of independent $\lambda$-damped walks.
We define the weighted fraction of the nodes covered by the first $i$ 
walks,
$$f_i := \frac{\sum_{j \in \bigcup_{k=1}^i w_k} d_j}{\sum_{j \in [n]} d_j}.$$
Note that this is the measure of $\displaystyle{\bigcup_i w_i}$ under the stationary
distribution of the natural random walk on the graph.  
\end{definition}

\begin{theorem}\label{dw}
For $c > 0$, let $k \geq (c + 1) d_{avg}d_{min}^{-1} n \ln n$, where  $d_{avg}$ is the
arithmetic mean and $d_{min}$ is the minimum of the $d_i$ for $i \in [n]$.
Then, 
$$|E[\prod_{j=1}^{k-1} (2f_j - 1)] + \frac{C(-\lambda)}{C(\lambda)}| < \frac{2}{n^c}.$$
\end{theorem}

\begin{corollary}
The non-zero eigenvalues $-\lambda_i$ of the  laplacian (which are all negative), are characterized
by $E[\prod_{j=1}^{\infty} (2f_j - 1)] = 0$, where $f_j$ are as in definition~\ref{def:Fi} with 
$\lambda$ set to $\lambda_i$. 
\end{corollary}

\section{Kirchhoff's Matrix-tree theorem}
\begin{definition}
Let $\TT$ be the set of trees of $G$. For a tree $t$ of $G$, 
let its weight $|t|$ be the product of the weights of its edges. 
\end{definition}
\begin{theorem}\label{kirch}
The sum of the weights of spanning trees of a graph $G$ is equal to any cofactor of 
the degree matrix of $G$ minus the adjacency matrix of $G$.
\end{theorem}

In particular, Kirchhoff's matrix tree
theorem implies that 
\[ \sum_{t \in \TT} w(t) = (-1)^{n-1} \det \left|
\begin{array}{llll}
- d_{2} & d_{23} & \cdots & d_{2n} \\
d_{31} & - d_{3} & \cdots & d_{3n} \\
\vdots & \vdots &  \ddots & \vdots \\
d_{n2} & d_{n3} & \cdots & - d_{n}
\end{array}
\right|. \] 

\section{The Aldous-Broder algorithm}
\begin{definition}
Given a weighted graph $G$, let $P_\TT$ be the probability distribution on the trees of $G$, where the
probability assigned to a tree $t$ is $\frac{|t|}{\sum_{t \in \TT} |t|}$.
\end{definition}

The Aldous-Broder algorithm \cite{aldous, broder} described below 
generates a random spanning tree, from the distribution $P_\TT$. 

\begin{enumerate}
\item Simulate the random walk on the graph $G$ starting at an arbitrary vertex $s$, until every vertex
      is visited. For each $i \in [n], i \neq s$, collect the edge $(j, i)$  corresponding to the first 
	  transition to vertex $i$. 
\item Output $t$.
\end{enumerate}
Originally this algorithm was proved to give a random spanning tree of a simple graph. 
However, it has been shown by Mosbah and Saheb \cite{mosbah}, that the 
algorithm works even for a 
weighted graph provided that 
the walk makes transitions according to the transition matrix $D'^{-1}\LL + I$.

\section{Augmenting the graph} 

\begin{figure}
\includegraphics[height=1.5in]{augment.eps}
\caption{Augmenting G}
\label{fig:gaug}
\end{figure}

We now prove theorem~\ref{dw}.
\begin{definition}
Given a graph $G$ as in the Introduction, and $\lambda > 0$, 
we manufacture an augmented graph $G_\lambda$ by adding an additional node $\infty$ and for each 
$i \in [n]$, a branch joining $\infty$ and $i$ that has weight $d_i\lambda$.
\end{definition}

Figure~\ref{fig:gaug} illustrates this.

\begin{definition}
Let $\TT_\lambda$ be the set of trees of $G_\lambda$, and $P_{\TT_\lambda}$ be the probability 
distribution that assigns to a tree $t \in \TT_\lambda$, a probability proportional to the product of its 
edge weights.
\end{definition}

The determinant of the 
laplacian of $G$ is a determinant of a maximal cofacter of $G_\lambda$.
Thus by the Matrix-Tree theorem, we have
\begin{eqnarray}
C(\lambda) &=& (-1)^n \sum_{t \in \TT_\lambda} \prod_{e \in t} |e|.
\end{eqnarray}
In the above expression, by $|e|$, we mean the weight of $e$.
For a tree $t$ of $G_\lambda$, let us denote by $deg_{\infty}(t)$ the {\it unweighted} degree of 
$\infty$ in $t$. This is the number of branches of $t$ that are incident upon $\infty$.
Then, 
\begin{eqnarray}\label{eq:1}
\frac{C(-\lambda)}{C(\lambda)} &=&  \frac{\sum_{t \in \TT_\lambda} \prod_{e \in t} (-1)^{deg_\infty(t)} w(e)}{ \sum_{t \in \TT_\lambda} \prod_{e \in t} w(e)} = E[(-1)^{\text{deg}_{\infty}(t)}],
\end{eqnarray}
where the expectation is taken over the distribution $P_{\TT_\lambda}$ on $\TT_\lambda$. 

\section{Proof of Theorem~\ref{dw}}
We do an infinite random walk $w$ on the graph $G_\lambda$, $w := \infty \ra i_1 \ra i_2 \ra \dots$ on $G_\lambda$ starting
at vertex $\infty$, and generate a random tree $t$ from $w$
using the Aldous-Broder algorithm. Note that no transition that occurs after every vertex has been visited
will figure in the tree. We let the walk have infinite length just for notational benefits. 
Let us partition $w$ into visits to $\infty$ and the walks on intervals between 
these visits, which we label $w_1, w_2, \dots$.
Thus $\infty \ra 3 \ra 2 \ra 5 \ra \infty \ra 4 \ra 1 \ra \infty \ra 1 \ra 3 \ra \dots$
would be partitioned as $\infty, 3 \ra 2 \ra 5, \infty, 4 \ra 1, \infty, 1 \ra 3 \dots$,
and $w_1 := 3 \ra 2 \ra 5$, $w_2 := 4 \ra 1$, $w_3 := 1 \ra 3 \dots$.
\begin{definition}
Let $x_i$ be the random variable defined to be $0$ if the first vertex of $w_i$ was covered by one of 
the walks $w_1, \dots, w_{i-1}$, and $1$ otherwise.
\end{definition}
Note that if $t$ is the tree obtained by applying the Aldous-Broder algorithm to walk $w$,
\begin{eqnarray}
\text{deg}_\infty(t) &=& \sum_{i=1}^\infty x_i.
\end{eqnarray}
Also note that the $w_i$ are independent $\lambda$-damped walks on $G$.
Let $d_{avg}$ and $d_{min}$ be the arithmetic mean and the minimum of the weighted degrees $d_i$.
Then, the probability that the first $k := (c + 1) \frac{d_{avg}}{d_{min}} n \ln n$ walks 
do not cover a given node $j$ is less than the probability that $j$ is not the first vertex of one 
of the walks $\{w_i | i \leq k\}$, which is $(1 - \frac{d_j}{n d_{avg}})^k < \frac{1}{n^{c+1}}$.
Therefore by the union bound, the probability that every node is covered by some $w_i$, $i \leq k$
is $> 1 - \frac{1}{n^c}$.
Thus 
\begin{eqnarray}\label{eq:2}
P[\text{deg}_\infty(t) &=& \sum_{i = 1}^k x_i] > 1 - \frac{1}{n^c},
\end{eqnarray}
where  $k := (c + 1) \frac{d_{avg}}{d_{min}} n \ln n.$

\begin{eqnarray}\label{eq:2.5}
E[(-1)^{\text{deg}_\infty(t)}]  & = & E[(-1)^{\sum_{i \leq k} x_i} (-1)^{\text{deg}_\infty(t) - \sum_{i \leq k} x_i}] \nonumber\\
								& = & E[(-1)^{\sum_{i \leq k} x_i}] + E[(-1)^{\sum_{i \leq k} x_i}(-1 + (-1)^{\text{deg}_\infty(t) - \sum_{i \leq k} n_i})].  
\end{eqnarray}

However, from \ref{eq:2.5},
\begin{eqnarray}\label{eq:3}
|E[(-1)^{\sum_{i \leq k} x_i}(-1 + (-1)^{\text{deg}_\infty(t) - \sum_{i \leq k} n_i})]| &=& \nonumber\\ 
P[\text{deg}_\infty(t) > \sum_{i \leq k} n_i)] |E[(-1)^{\sum_{i \leq k} x_i}(-1 + (-1)^{\text{deg}_\infty(t) - \sum_{i \leq k} n_i})|\text{deg}_\infty(t) > \sum_{i \leq k} n_i]| &<& \nonumber\\
\frac{2}{n^c}.
\end{eqnarray}

It follows from \ref{eq:1}, \ref{eq:2} and \ref{eq:3} that
\begin{eqnarray}\label{eq:4}
|E[(-1)^{\sum_{i \leq k} x_i}] + \frac{C(-\lambda)}{C(\lambda)}| &<& \frac{2}{n^c}.
\end{eqnarray}

$x_i$ is a function of $w_1, \dots, w_i$, and is independent of 
$w_{i+1}, w_{i+2}, \dots$.
So,
\begin{eqnarray}\label{eq:5}
E_{w_1, \dots, w_i}[(-1)^{\sum_{i \leq k} x_i}] & = & E_{w_1}[(-1)^{x_1} E_{w_2, \dots, w_i}[(-1)^{\sum_{i = 2}^k x_i}|w_1] \nonumber\\ 
												& = & (-1)E_{w_1}[E_{w_2, \dots, w_k}[(-1)^{\sum_{i = 2}^k x_i} | w_1] \nonumber\\
												& = & (-1)E_{w_1}[(2 f_1 - 1) E_{w_2}[(-1)^{x_2} E_{w_3, \dots, w_k}[(-1)^{\sum_{i = 3}^k x_i}|w_1, w_2]|w_1] \nonumber\\
                                                & = & \dots \nonumber\\
                                                & = & (-1)E_{w_1, \dots, w_{k-1}}[\prod_{i=1}^{k-1}(2 f_i - 1)] , 
\end{eqnarray}
where $f_i$ are as defined in Definition~\ref{def:Fi}.
From \ref{eq:1}, \ref{eq:4} and \ref{eq:5}
Theorem~\ref{dw} now follows.

\section{Conclusion}
We used the Aldous-Broder algorithm (\cite{aldous, broder}) of generating a random spanning tree and the 
Matrix-tree theorem
to relate the values of the characteristic polynomial of the Laplacian 
at $\pm \lambda$ and the stationary measures of the sets of nodes 
visited by $i$ independent $\lambda$-damped random 
walks for $i \in \N$. As a corollary, we obtained a new characterization of the
non-zero eigenvalues of the Weighted Graph Laplacian. 
The authors are not aware of any analogue of this result for compact Riemannian manifolds.
To find such analogues, appears to be an interesting line of research. 

\begin{thebibliography}{91}
\bibitem{aldous} Aldous. D. ``The random walk construction of uniform spanning trees and uniform labelled trees."  SIAM J. Discrete Math. 3, 450-465, 1990.
\bibitem{broder} Broder. A. Z. ``Generating Random Spanning Trees." FOCS, 442-447, 1989.

\bibitem{kirchhoff} Kirchhoff, G. ``Uber die Auflsung der Gleichungen, auf welche man bei der untersuchung der linearen verteilung galvanischer Str\"ome gef\"uhrt wird." Ann. Phys. Chem. 72, 497-508, 1847.
\bibitem{mosbah} Mosbah M., Saheb N. ``Non-Uniform Random Spanning Trees on Weighted Graphs." Theor. Comput. Sci. 218(2): 263-271, 1999.

\end{thebibliography}
\end{document}
 



math0506460.extracted_bib
\begin{thebibliography}{91}
\bibitem{aldous} Aldous. D. ``The random walk construction of uniform spanning trees and uniform labelled trees."  SIAM J. Discrete Math. 3, 450-465, 1990.
\bibitem{broder} Broder. A. Z. ``Generating Random Spanning Trees." FOCS, 442-447, 1989.

\bibitem{kirchhoff} Kirchhoff, G. ``Uber die Auflsung der Gleichungen, auf welche man bei der untersuchung der linearen verteilung galvanischer Str\"ome gef\"uhrt wird." Ann. Phys. Chem. 72, 497-508, 1847.
\bibitem{mosbah} Mosbah M., Saheb N. ``Non-Uniform Random Spanning Trees on Weighted Graphs." Theor. Comput. Sci. 218(2): 263-271, 1999.

\end{thebibliography}