\documentclass{beamer}
\mode<presentation>
{
\usetheme{Hannover}
}


\usepackage{graphicx}
\usepackage{amsfonts}


\title{An ``Electric'' Story of a Drunkard}
\author[Ramprasad Saptharishi]{Ramprasad Saptharishi
}
\institute{
  Chennai Mathematical Institute\\Third Year B.Sc Mathematics
}
\date{September 1, 2006}



\AtBeginSection[]{
\begin{frame}<beamer> 
\frametitle{Outline}
\tableofcontents[currentsection]
\end{frame}
}

\begin{document}
\begin{frame}
\titlepage
\end{frame}

\section{Introduction}
\begin{frame}
\frametitle{The Problem Statement}

{\bf Random Walk:} You are placed at some point in a $d-$dimensional integer lattice. 

\texttt{\noindent
\textit{Repeat \{}\\
Pick one of your neighbours uniformly at random and move to them\\
\textit{\}}
}
\vskip 0.5in
\pause

Question: What is the probability that you return to the starting point infinitely often?

\end{frame}

\begin{frame}
\frametitle{The Theorem of Polya}

\begin{theorem}
  A random walk on an d-dimensional integer lattice will return to the
  starting point infinitely often with probability $1$ if $d = 1$ or $2$.
  The probability is $0$ if $d \geq 3$.
\end{theorem}

\vskip 0.5in
\pause
{\bf Drunkard:} Will I ever get home again?

{\bf Polya:} You can't miss, just keep walking, and stay out of $3D$!!!

\end{frame}

\begin{frame}
\frametitle{Structure of this Talk}

\begin{itemize}
\item Establish certain electrical networks
\pause
\item Estimate the effective resistance of the electrical networks
\pause
\item Show the relation between electrical parameters of the networks and random walks
\pause 
\item Use the effective resistance of networks to prove Polya's theorem.
\end{itemize}
\end{frame}

\begin{frame}
\frametitle{Ohm...Kirchoff$\bar{a}$ya Namah$\bar{a}$}

{\bf Ohm's Law:} The current flowing through a wire is directly proportional to potential across it. 
\medskip

{\bf Kirchoff's Law:}Current in  =  current out, for any point in the interior of the circuit. 

Net potential drop across a loop is zero
\end{frame}

\section{Some Electrical Networks and their Effective Resistance}
\begin{frame}
\frametitle{Circuit $1$}
\includegraphics[width=3.5in]{im1.png} 
\pause
\bigskip

Effective Resistance 
$$\rho_n=\frac{rn}{2}$$
\bigskip

\pause

$$\rho_n \rightarrow \infty \mbox{~as~} n\rightarrow \infty$$
\end{frame}
\begin{frame}
\frametitle{Circuit $2$}
\includegraphics[width=4in]{im2.png} 

\end{frame}

\begin{frame}
\frametitle{Hard to calculate? Estimate growth}

Difficult to find a closed form answer
\pause
\bigskip

But what happens to $\rho_n$ as $n\rightarrow \infty$?
\pause
\vskip 0.5in

Find an easier circuit with effective resistance $\rho'<\rho$ and see if you can show that $\rho'$ is infinite.
\end{frame}
 
\begin{frame}
\frametitle{An Easier Circuit}
\includegraphics[width=3in]{im3.png} 
\end{frame}

\begin{frame}
\frametitle{...which is equivalent to}
\includegraphics[width=3.5in]{im4.png} 

\pause
$$
\rho'_n = \sum_{k=1}^n \frac{r}{8k-4}
$$
\pause

Hence, we have $\rho'_n \rightarrow \infty$ as $n \rightarrow \infty$
\pause , which implies that $\rho_n \rightarrow \infty$ as $n \rightarrow \infty$. 
\end{frame}

\begin{frame}
\frametitle{Circuit $3$: The $3D$ version}

\pause
Again, difficult to find a closed form solution
\bigskip

\pause
What can you say about $\rho_n$ as $n\rightarrow \infty$?
\pause
\bigskip

\bigskip

{\em Can you show that it is finite?}
\end{frame}

\begin{frame}
\frametitle{Approach}
\pause
Can't short resistors, won't help in showing that it is finite.
\pause

\bigskip

\bigskip

Remove some resistors, equivalent to saying increase some resistances to infinity
\pause

Show that the effective resistance of the new circuit is bounded. 
\end{frame}

\begin{frame}
\frametitle{Getting Back to $2D$}
\includegraphics[width=3in]{im9.png} 
\end{frame}
\begin{frame}
\frametitle{...which is equivalent to}
\includegraphics[width=2in]{im5.png} 
\pause

All {\em Generation $i$} nodes are of the same potential; can connect them without changing effective resistance.
\end{frame}
\begin{frame}
\frametitle{...which is equivalent to}
\includegraphics[width=3.5in]{im6.png} 
\end{frame}

\begin{frame}
\frametitle{Back to $3D$}

\begin{itemize}
\pause
\item Take the planes $x+y+z=2^i -1$ and do the same thing.
\pause
\item Every time a line of resistance hits such a plane, it forks in the $x$, $y$ and the $z$ direction.
\pause
\item Establish the tree again
\end{itemize}
\end{frame}

\begin{frame}
\frametitle{The Tree}
\includegraphics[width=3in]{im7.png} 
\end{frame}

\begin{frame}
\frametitle{...which is equivalent to}
\includegraphics[width=3.5in]{im8.png} 
\end{frame}

\begin{frame}
\frametitle{Effective resistance}
$$
\rho_n' = \frac{r}{3} + \frac{2r}{9} + \ldots + \frac{2^{n-1}r}{3^n} 
$$
$$
= \left( 1-\left( \frac{2}{3}\right)^n\right)r
$$
\pause
\bigskip

$$
\therefore \lim_{n\rightarrow \infty}\rho_n' = r
$$
\pause

\bigskip

Hence $\rho$ for circuit 3 is finite.
\end{frame}
\begin{frame}
\frametitle{Circuit $d$: $d>3$}

\begin{itemize}
\item Use the same approach, draw the corresponding planes
\item Branch whenever it the lines hit the plane
\end{itemize}
\pause
?????
\pause

Finite for $d=3 \Rightarrow $ finite for $d>3$
\end{frame}
\section{Connection between Electrical Networks and Random Walks}
\begin{frame}
\frametitle{$2$ 'different' problems}
\begin{itemize}
  \pause {\item Let G be a graph, with two special nodes
    $\alpha,\beta$.  Suppose we start at some node $x$, what is the
    probability $p(x)$ that a simple random walk starting from $x$
    reaches $\alpha$ before $\beta$.}  \pause

  {\item Take that graph, put a resistance of $r$ on every edge in the
    graph. Give $\alpha$ a potential of $1$, and $\beta$ a potential
    of $0$. What is the potential of the point $x$?}
\end{itemize}
\bigskip

\pause
{\bf Claim:} Both are the same!

\end{frame}

\begin{frame}
\frametitle{Some Notations}
\begin{tabular}{lll}
$R_{xy}$ & : & Resistance of the edge $\{x,y\}$\\
$C_{xy}$ & : & Conductance of the edge, defined as $\frac{1}{R_{xy}}$\\
$C_x$ & : & Conductance of the vertex, defined as $\sum_{y\in \Gamma(x)}C_{xy}$\\
$i_{xy}$& : & Current through the edge $\{x,y\}$\\
$v(x)$& : & Potential at the point $x$ \\
$i_\alpha$ & : & Net current flowing through the circuit\\
\end{tabular}
\end{frame}

\begin{frame}
\frametitle{Some Equations}
$$
i_{xy} = \frac{v(y)-v(x)}{R_{xy}}= \left(v(y)-v(x)\right) C_{xy}
$$
\pause
\bigskip

Summing over all neighbours $y$ of $x$
$$
\sum_{y\in \Gamma(x)}v(x)C_{xy} = v(x)C_x = \sum_{y\in \Gamma(x)}v(y)C_{xy}
$$
\pause
\bigskip

$$
v(x)= \sum_{y\in \Gamma(x)}v(y)\frac{C_{xy}}{C_x}
$$
\pause
And of course, $v(\alpha)=1,v(\beta)=0$.

\end{frame}

\begin{frame}
\frametitle{Defining Equations for $p(x)$}

$$
P(x) = %\left\{\begin{array}{ll}
\begin{cases}
\frac{1}{\mbox{\# of vertices adjacent to }x} & \mbox{if $y$ adjacent to $x$}\\
0 & \mbox{otherwise}\\
\end{cases}
%\end{array}\right
$$
\bigskip

... the probability that you reach $y$ from $x$ in $1$ step. 
\end{frame}

\begin{frame}
\frametitle{Defining Equations for $p(x)$}

Now we have:
$$
p(x)=\sum_{y\in \Gamma(x)}p(y)P_{xy};p(\alpha)=1;p(\beta)=1
$$
\bigskip

\pause
Hey, this looks familiar...
\pause

$$
v(x)= \sum_{y\in \Gamma(x)}v(y)\frac{C_{xy}}{C_x};v(\alpha)=1;v(\beta)=0
$$
\end{frame}

\begin{frame}
\frametitle{Bingo!}
If,
$$P_{xy}=\frac{C_{xy}}{C_x}$$
 then we have 
$$p(x)=v(x)$$
\bigskip

\pause
...connection established!
\end{frame}

\section{Proving Polya's Theorem}
\begin{frame}
\frametitle{What are we looking for?}

We are interested in finding the probability that we return to the starting point $\alpha$ before reaching $\beta$
\pause

This is as good as saying, we go out $\alpha$, then get back from there to $\alpha$ before reaching $\beta$. 
\pause
\bigskip

Thus we are hunting for
$$
\xi=\sum_{y\in \Gamma(\alpha)}p(y)P_{\alpha y}
$$
\end{frame}

\begin{frame}
\frametitle{Net Current}
\begin{eqnarray*}
i_\alpha & = & \sum_{y\in \Gamma(x)}\left(v(\alpha)-v(y)\right)C_{\alpha y}\\\pause
        & = & v(\alpha)\sum_{y\in \Gamma(x)}C_{\alpha{y}} - \sum_{y\in \Gamma(x)}v(y)C_{\alpha y}\\\pause
        & = & C_\alpha - C_\alpha\sum_{y\in \Gamma(x)}p(y)P_{\alpha y}\\\pause
        & = & C_\alpha\left(1-\sum_{y\in \Gamma(x)}p(y)P_{xy}\right)\pause
\end{eqnarray*}
$$
\therefore \sum_{y\in \Gamma(x)}p(y)P_{xy} = \xi = 1 - \frac{i_\alpha}{C_\alpha}\pause = 1 - \frac{1}{\rho C_\alpha}
$$
\end{frame}

\begin{frame}
\frametitle{Thus...}
$$
\xi = 1 - \frac{1}{\rho C_\alpha}
$$
\pause

For $d=1$ or $2$, we have $\rho = \infty$ and hence $\xi = 1$.
$$
\therefore lim_{n\rightarrow \infty}\xi^n = 1
$$
\pause
\bigskip

For $d\geq 3$, we have a finite $\rho$ and hence $0< \xi <1$.
$$
\therefore lim_{n\rightarrow \infty}\xi^n = 0
$$ 
\pause
\qed
\end{frame}
\section{Conclusion}
\begin{frame}
\frametitle{End Notes}

In probability jargon, it is said that a simple random walk is
recurrent in 2 or lower dimensions, and is transient in 3 or higher
dimensions.  

The original question was asked and solved by George
Polya in a celebrated paper in 1921. This method of looking at the
question through electrical networks is based on a monograph by Doyle
and Snell, where besides the question of transience and recurrence,
many other questions of simple random walks are addressed.
\end{frame}
\title[An ``Electric'' Story of a Drunkard]{Thank You}
\author[Ramprasad Saptharishi]{Slides and TeX files are available at \texttt{$\sim$ramprasad/studenttalks/drunkard/}.}
\institute{}
\date{}
\begin{frame}
\titlepage
\end{frame}
\end{document}