\documentclass[11pt]{article}
\usepackage{amsfonts}
\usepackage{amsthm}
\usepackage{amsmath}
\usepackage{latexsym}
\usepackage{verbatim}
\usepackage[pdftex]{graphicx}
\usepackage{url}
\usepackage[table]{xcolor}
\usepackage[all,arc]{xy}
\usepackage{color, colortbl}
\usepackage{mathrsfs}
\usepackage{hyperref}
\hypersetup{colorlinks=true}
\setlength{\oddsidemargin}{.15in}
\setlength{\evensidemargin}{.15in}
\setlength{\textwidth}{6.2in}
\setlength{\topmargin}{-0.5in}
\setlength{\textheight}{8.6in}


\input{preamble.tex}

\begin{document}

\homework{4: More Random Walks}{Due Friday, Week 3}

Do \textbf{three} of the following \textbf{five} problems!

\begin{enumerate}
\item In class, we proved that the probability of escape on $\mathbb{Z}^3$ was at least 1/6.  Improve this bound by proving that $p_{\textrm{esc}}(\mathbb{Z}^3) \geq 1/3$.  
\item Prove $p_{\textrm{esc}}(\mathbb{Z}^3) \leq 5/6$ (i.e.\ find an upper bound for our probability of escape!)
\item Take any finite collection $p_1, \ldots p_n$ of polygons.  A \textbf{tiling} of $\mathbb{R}^2$ with such polygons is any way to place copies of these polygons in the plane, so that they ``cover'' $\mathbb{R}^2$ and only overlap on their edges. (Formally, you can phrase this property as the request that every point in $\mathbb{R}^2$ is either contained within the edge of at least one polygon, or within the interior of exactly one polygon.)

Given any such tiling, we can form a graph, where our vertices are the corners of our polygons, and we connect two vertices with a graph-edge if there is a polygonal edge connecting them with no other vertices in between.  So, for example, a tiling of the plane with side-length 1 squares corresponds to the $\mathbb{Z}^2$-graph.

Is there any polygonal tiling of $\mathbb{R}^2$ whose associated graph has a nonzero probability of escape?  Or must a random walker on any polygonal tiling graph return to wherever they start with probability 1?
\item Similarly to the above; define a ``polytopal tiling'' of $\mathbb{R}^3$ with finitely many three-dimensional polytopes $p_1, \ldots p_n$ as a way to cover $\mathbb{R}^3$ with polytopes that only overlap on their edges and faces, and turn these objects into graphs as well.  (So, the tiling of $\mathbb{R}^3$ with cubes of side length 1 is precisely the $\mathbb{Z}^3$-graph.)

Is there any polytopal tiling of $\mathbb{R}^3$ whose associated graph has a \textbf{zero} probability of escape?  Or, given any polytopal tiling of $\mathbb{R}^3$, does a random walker always have a nonzero chance of escape?

\item Take any graph $G$ with distinguished source vertex $s$ and sink vertex $t$.  Define a \textbf{flow} on $G$ as any function $j: V \times V \to \mathbb{R}$ on the edges of $G$ that satisfies Kirchoff's laws at every vertex other than $s, t$: that is,
\begin{itemize}
\item For any $y \in V(G), y \neq s,t$, $\displaystyle \sum_{y \in N(x)} j_{xy} = 0.$
\item If $\{x,y \} \notin E(G)$, then $j_{xy} = 0$.
\end{itemize}
\begin{enumerate}
\item Show that for any circuit $C$, the current is a flow.
\item Prove the following ``conservation of energy'' property: if $w: V(G) \to \mathbb{R}$ is any function defined on the vertices of our graph and $j$ is any flow on our graph from source $s$ to sink $t$ such that $j_s = \sum_{y \in N(s)} j_{sy} = 1$, then
\begin{align*}
w_s - w_t = \frac{1}{2}\sum_{x, y\in V(G)}(w_x - w_y)\cdot j_{xy}.
\end{align*}
\item Take any circuit $C$.  Define the \textbf{energy dissipation} of this circuit with respect to any flow $j: V \times V \to \mathbb{R}$ as the following sum:
\begin{align*}
\frac{1}{2}\sum_{x,y \in V(G)} j_{xy}^2 \cdot R_{xy}.
\end{align*}
Show that the current ``minimizes'' the total energy dissipation: that is, that if $j$ is any flow on our circuit with $j_s = \sum_{s \in N(y)} j_{sy} = i_s$, then 
\begin{align*}
\frac{1}{2}\sum_{x,y \in V(G)} i_{xy}^2 \cdot R_{xy} \leq \frac{1}{2}\sum_{x,y \in V(G)} j_{xy}^2 \cdot R_{xy}.
\end{align*}
\end{enumerate}
\item Use problem 5 to prove Rayleigh's Monotonicity Theorem: 
\begin{theorem}
If any of the individual resistances in a circuit increase, then the overall effective resistance of the circuit can only increase or stay constant; conversely, if any of the individual resistances in a circuit decrease, the overall effective resistance of the circuit can only decrease or stay constant. 
\end{theorem}
\item[Bonus!]  Find the exact value of $p_{\textrm{esc}}(\mathbb{Z}^3)$.
\end{enumerate}



\end{document}