\documentclass[12pt]{amsart}
\title{Random Walk Networks}
\author{Andrew Lewis}
\address{University of Washington\\Seattle\ \ WA}
%\email{reu@math.washington.edu}
\date{August 10, 2004}

% Check if we are compiling under latex or pdflatex, and include the
% appropriate graphics package
\ifx\pdftexversion\undefined
  \usepackage[dvips]{graphicx}
\else
  \usepackage[pdftex]{graphicx}
\fi

%from fca.sty, Copyright 2003 Bernhard Ganter
%Distributed under LaTeX Project Public License
\providecommand{\bigtimes}{\mathop{%
\mathchoice{\raisebox{-2pt}{\huge$\times$}}{\mbox{\LARGE$\times$}}%
{\raisebox{0pt}{\Large$\times$}}{\times}}\displaylimits}%

\usepackage{fullpage}

% Defines the theorem environments
\newtheorem{theorem}{Theorem}[section] % numbered like the section
\newtheorem{lemma}[theorem]{Lemma} % numbered like the theorems
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{remark}[theorem]{Remark}
\theoremstyle{definition} % styled differently... not italicized
\newtheorem{definition}[theorem]{Definition}
\newtheorem{conjecture}[theorem]{Conjecture}

% Let \sign show roman-style characters in math mode
\newcommand{\sign}{\mathop{\mathrm{sign}}}

%\raggedbottom % Makes the bottom margin more flexible (helpful for pictures)

\begin{document}

%\begin{abstract}

%\end{abstract}

\maketitle

%\tableofcontents

\section{Introduction}

In this paper, some probabilistic analogues to properties of electrical networks will be developed, based on the idea of a random walk on a directed graph.  In order to do this the precise definition of a probability space is needed.  First there must be a set $S$, sometimes called the {\it measure space} or {\it sample space}, which contains all possible outcomes being analyzed.

\begin{definition}
A set $A \subseteq \mathcal{P}(S)$ is called an {\it Algebra} if:

\begin{enumerate} \item $S \in A$
\item If $B, C \in A$ then $B - C \in A$, $B \cap C \in A$, and $B \cup C \in A$\end{enumerate}
$A$ is a {\it Borel Algebra} if, additionally:
\begin{enumerate}
\setcounter{enumi}{2}
\item If $B_n \in A$, $n \geq 1$, then $\bigcup_{n \geq 1} B_n \in A$ and $\bigcap_{n \geq 1} B_n \in A$.
\end{enumerate}
\end{definition}

If $A$ is an algebra, there is a least Borel algebra $B$ containing $A$ called the {\it Borel extension} of $A$.

\begin{definition}
A function $m : A \mapsto [1,0]$ is called a {\it Borel probability measure} if it satisfies the following requirements:

\begin {enumerate}
 \item $m(S) = 1$
\item If $B, C \in A$ and $B \cap C = \emptyset$, $m(B \cup C) = m(B) + m(C)$
\item If $B_n$ is a sequence of sets such that all $B_n \in A$ and $B_n \rightarrow \emptyset$ as $n \rightarrow \infty$, then $\lim_{n \rightarrow \infty} m(B_n) = 0$.  As a consequence of this, if $B_n \in A$, and $B_n \cap B_m = \emptyset$ when $n \neq m$, then $m\left( \bigcup_{n \geq 1} B_n \right) = \sum_{n \geq 1} m(B_n)$.
\end{enumerate} 
\end{definition}

A probability space is a 3-tuple $(S,A,m)$ of a measure space, an algebra, and a probability measure.

Any subset of $S$ that is in $A$ is called {\it measurable}, because those are the only sets where the probability measure is defined.  A function $f$ defined on $S$ is called measurable if the set $f^{-1}(q) = \{x \in S : f(x) = q\}$ is measurable for all $q$ in the range of $f$.  A measurable subset of $S$ is called an {\it event}.  A measurable function is called a {\it random variable}, and its domain the {\it state space}.  Note that a random variable is neither random nor a variable.  

Define the probability of an outcome being in a measurable subset $R$ of the measure space, $\mathbf{P}[R]$, to be the measure of that subset, and the probability that the value of a random variable $X$ equals a value $q$, $\mathbf{P}[X = q]$, to be the measure of $f^{-1}$ for that value.
\newpage
The {\it conditional probability} of an event $C$ given $D$, $\mathbf{P}[C | D]$, is fairly complicated to define precisely, using the notion of conditional expectation and characteristic functions.  It means, intuitively, the likelihood of an event $C$ occurring given that $D$ has already.  We need only the following fact about conditional probabilities:

\[
\mathbf{P}[C | D] = \frac{\mathbf{P}[C \cap D]}{\mathbf{P}[D]}
\]

A {\it random walk} on a directed graph might be supposed to be a sequence $X_i$ of random variables (in an arbitrary probability space), taking values in the set $V$ of vertices of the graph.  We would want the probability of moving from one vertex to another to depend only on the value of the present vertex:  

\[
\mathbf{P}[X_{n+1} = v | X_n = w, X_{n-1} = x, \ldots, X_1 = z ] = \mathbf{P}[X_{n+1} = v | X_n = w] = p(v,w)
\]

\noindent for all $n$ and all vertices $v$, $w$, etc.  

The function $p(v,w)$, called the {\it transition function}, induces the arcs of the graph; there is an arc connecting $v$ and $w$ whenever it is possible to move from $v$ to $w$, that is, when $p(v,w) \ne 0$.  Using the above fact about conditional probabilities, we can find the probability of moving through a particular finite sequence of vertices from a given starting point by multiplying the values of the transition function, for instance:
\begin{eqnarray*}
\mathbf{P}[X_1 = v, X_2 = w, X_3 = x | X_1 = v] &=& \mathbf{P}[X_1 = v] \cdot p(v,w) \cdot p(w,x) / \mathbf{P}[X_1 = v] \\
&=& p(v,w) \cdot p(w,x)
\end{eqnarray*} 
Using the known properties of the probability measure more complicated probabilities, such as the probability of reaching one vertex from another in a particular number of steps, can be computed.  But working in this way is inadequate to deal with more complicated events which might involve infinitely many values of the sequence.

We will simply take as our definition of a {\it random walk network} to be a set $V$ of vertices, along with a function $p: V \times V \mapsto \mathbb{R}^+$ satisfying the constraint that $\sum_{v \in V} p(u,v) = 1$ for all $u \in V$.  $p$ is simply the transition function described above.  The notation $u \sim v$ will be used to denote the existence of an arc from $u$ to $v$; $u \sim v$ if and only if $p(u,v) \ne 0$.  Next we will build a probability space where the events are sets of complete infinite processes as discussed above, which will be as powerful as is necessary to carry out the remainder of the work.

\section{The Probability Space}

We define the following measure space $S$ to represent the space of all infinite walks through the induced graph (as above, a walk being an infinite sequence of vertices, or equivalently a function from the positive integers to $V$):

\begin{equation}
S = \{\omega : \omega : \mathbb{Z}^+ \mapsto V\}
\end{equation}

%\newpage

Now define the sets $B_{k,v} \subseteq S$, for each positive integer $k$ and finite sequence $v$ of vertices:

\begin{equation}
B_{k,v} = \{ \omega : \omega(i) = v_i\ \mbox{for all } i \leq k\}
\end{equation}

Let $A$ be the closure of the set of all $B_{k,v}$ with respect to finite union.
\begin{lemma} For any set $B \in A$, $B = \bigcup_{i=1}^n B_{k,s_i}$ where $k$ is a constant and all $s_i$ are unique sequences of $k$ vertices.
\label{union-lemma}
\end{lemma}

{\it Proof: } Each set $B_{j,v} = \bigcup_{b \in V} B_{j+1,vb}$, where $vb$ denotes the sequence of $j+1$ vertices such that $vb_i = v_i$ for $i \leq j$ and $vb_{j+1} = b$.  That is because for any $\omega \in B_{j,v}$, $\omega(j+1) \in V$ and so $\omega \in B_{j,vb}$ for some $b \in V$ and therefore $\omega \in \bigcup_{b \in V} B_{j+1,vb}$.  On the other hand, any $\omega \in B_{j+1,vb}$ for some $b \in V$ must satisfy the requirement that $\omega(i) = v_i$ for $i \leq j$, so by definition $\omega \in B_{j,v}$.  Repeating this for each of the subsets in the union to an arbitrary depth, $B_{j,v}$ can be expressed as a union of the form above for any $k \geq j$.

Any $B \in A$ is a finite union of the form $\bigcup^n_{i=1} B_{j_i,s_i}$ by definition of $A$.  Let $k = \max\{j_i\}$.  We have already shown that each of those terms can be expressed as a union of the form $\bigcup^{n_i}_{j=1} B_{k,s_j}$.  Combining all of those unions and eliminating identical terms, we have an expression for $B$ in the desired form.

\begin{theorem} $A$ is an algebra. \end{theorem}

{\it Proof:}  By definition of $A$, all finite unions of sets in $A$ are also in $A$.  

$\omega(0) \in V$ for any $\omega$, so each $\omega \in S$ is contained in $B_{0,v}$ for some $v \in V$, and each $B_{0,v}$ is a subset of $S$ by definition, so $S = \bigcup^{n}_{i = 1} B_{0,v_i}$ where $V = \{v_1,\dots,v_n\}$.  Therefore, since $S$ is a finite union of elements of $A$, $S \in A$.

$S$ itself is clearly the union of the sets $B_{k,v}$ for all possible unique sequences $v$ of $k$ vertices, so any $\omega \not \in B$ is clearly in some set $B_{k,v}$ that does not appear in the union expression for $B$ shown to exist in Lemma \ref{union-lemma}, and any member of a set $B_{k,v}$ that does not appear in that expression must differ from the sequence $s_i$ defining any set that does appear in the union expression at some index $i \leq k$.  This proves that $S - B$ equals the union of all of the $B_{k,v}$ that do not appear in the above union expression for $B$, a finite union of elements of $A$, so $S - B \in A$ for any $B \in A$.

Any finite intersection can be expressed in terms of unions and complements, so all finite intersections of sets in $A$ are also in $A$.

Therefore $S \in A$ and $A$ is closed with respect to finite union, finite intersection, and complement, so $A$ is an algebra.
\\

Define a measure $f_a$ on $A$ for each $a \in V$, computed according to the following rules:

\begin{eqnarray}
f_a(B_{k,v}) &=&  \left \{ \begin{array}{ll} 1 \cdot p(v_0,v_1) \cdot \ldots \cdot p(v_{k-1},v_k) &\mbox{if } v_0 = a \\ 0 & \mbox{if } v_0 \ne a
\end{array} \right.   \\
f_a\left(\bigcup_{j = 1}^n B_j\right) &=& \sum_{j=1}^n f_a(B_j)\ \mbox{if}\ B_j \in A,\ B_k \cap B_l=\emptyset \ \mbox{when } k \neq l
\end{eqnarray}

$f_a$ has been defined to agree with the basic probabilities of events described in the first section; by the first rule, the measure of a finite sequence of transitions is the product of the transition probabilities.  The second rule defines the measure of disjoint unions in the manner in which they would be computed were $f_a$ a probability measure.  However, $f_a$ is effectively defined above as a function of set-theoretic expressions.  Before it can be argued that $f_a$ is a Borel probability measure, it must be shown that $f_a$ as defined is in fact a function on sets, which assigns a unique value to each set in $A$ which is independent of the expression chosen to represent it.

Below, the symbol $=_L$ will be used to denote lexical equality between set-theoretic expressions (that is, they are exactly the same string of characters).  Otherwise the $=$ sign will denote set equality or numeric equality, depending on the type of the operands, as usual.

\begin{lemma}  For every set-theoretic expression $E$ defining a set in $A$ as a union of sets $B_{k,v}$, there is an expression $N_k(E)$ with the following properties:

\begin{enumerate}
\item $N_k(E) =_L B_{k,s_1} \cup B_{k,s_2} \cup \cdots \cup B_{k,s_n}$ for $n$ finite and $s_1 \dots s_n$ distinct sequences of $k$ vertices.
\item $N_k(E) = E$
\item $f_a(N_k(E)) = f_a(E)$
\end{enumerate}
\label{normal-form-lemma}
 \end{lemma}

{\it Proof: } Let $M =_L \bigcup_{i=1}^n B_{k,s_i}$ (written as a long string of binary unions of the form listed above) be the expression for the union proven to exist in Lemma \ref{union-lemma}.  It clearly meets the first two requirements, so we need only show that the operation of replacing a term $B_{j,v}$ with $\bigcup_{b \in V} B_{j+1,vb}$, through repetition of which $E$ can be obtained from the original expression from the set, does not change the value of $f_a$.  By the first rule specifying the computation of $f_a$ (assuming we are dealing only with sets of non-zero measure, all elements of which must begin with $a$),

\begin{eqnarray*} f_a(B_{j+1,vb}) &=& p(a,v_2) \cdot p(v_2,v_3) \cdot \ldots \cdot p(v_j,b)\\
&=& f_a(B_{j,v}) p(v_j,b)
\end{eqnarray*}

So:

\begin{eqnarray*}
 \sum_{b \in V}f_a(B_{j+1,vb}) &=&  \sum_{b \in V}f_a(B_{j,v}) p(v_j,b)\\
&=& f_a(B_{j,v})\sum_{b \in V}p(v_j,b)\\
&=& f_a(B_{j,v})
\end{eqnarray*}

Since all of the operations producing $M$ from the original expression $E$ were of that type,

\begin{equation}
f_a(M) = f_a(E)
\end{equation}

So $N_k(E) = M$.

\begin{corollary} For an expression $B$ defining a set in $A$ such that $N_k(B)$ exists where $f_a(N_k(B)) = f_a(B)$, an expression $N_j(B)$ also exists for any $j > k$, and preserves the value of $f_a$.
\label{normal-form-corollary}
\end{corollary}
{\it Proof:}  Applying the process for producing $N_k(B)$ further all terms are $B_{i,v}$ with $i=j$ must produce an expression with the desired property.
 
\begin{lemma}  If $B,C$ are expressions for sets in $A$, and $B = C$, then $f_a(B) = f_a(C)$.
\end{lemma}
{\it Proof: } By Lemma \ref{normal-form-lemma}, $N_{k_1}(B)$ and $N_{k_2}(C)$ exist for $B$ and $C$, and so by Corollary \ref{normal-form-corollary} $N_k(B)$ and $N_k(C)$ exist where $k = \max\{k_1,k_2\}$.  Since $B=C$, each of those two expressions must contain exactly the same terms, because all of the sets $B_{k,v}$ are disjoint so any element of $B$ can be contained in exactly one such set, and any expression representing $B$ in terms only of those sets must contain any set which contains elements of $B$.  But if they contain exactly the same terms then by the rules for computing $f_a$ they must have the same value of $f_a$, and because the generation of those expressions preserves $f_a$ values, $f_a(B) = f_a(C)$.

This is sufficient to show that $f_a$ has a single well-defined value for each set in $A$.  By Lemma \ref{union-lemma} every set in $A$ can be expressed as a union of disjoint $B_{k,v}$, and the value of $f_a$ on that set can be computed only in terms of a representation in terms of such an expression.  It has been shown that every possible such expression will have the same $f_a$ value if it defines the same set, and that is the unique value of $f_a$ for that set.
\\

We now establish some properties of sets in $A$ which will make it possible to prove that $f_a$ is a Borel probability measure, by way of topology.  A {\it topological space} is a pair $\langle Y,\mathcal{T} \rangle$, where $Y$ is a non-empty set and $\mathcal{T}$ satisfies the following properties:

\begin{enumerate}
\item $Y \in \mathcal{T}$ and $\emptyset \in \mathcal{T}$
\item If $B, C \in \mathcal{T}$, $B \cap C \in \mathcal{T}$
\item If $B_{\alpha} \in \mathcal{T}$, then $\bigcup_{\alpha} B_{\alpha} \in \mathcal{T}$ (The index set need not be countable)
\end{enumerate}

The elements of $\mathcal{T}$ are called {\it open sets}, and any complement of an open set is a {\it closed set}.  Some useful topological theorems and definitions follow (proven in \cite{royden}):

\begin{theorem}
The set of closed sets in a topological space is closed under finite union and intersection.
\end{theorem}

\begin{theorem}
\label{compact}
A topological space $X$ is {\it compact} if and only if for every collection of closed sets $\mathcal{F}$, if the intersection of the sets in every finite subset of $\mathcal{F}$ is non-empty, then the intersection of all sets in $\mathcal{F}$ is non-empty.
\end{theorem}

\begin{definition}
If $X_{\alpha} = \langle Y_{\alpha}, \mathcal{T}_{\alpha} \rangle$ is an indexed set of topological spaces, the product topology on $\bigtimes_{\alpha} Y_{\alpha}$ has as its basis all sets of the form $\bigtimes_{\alpha} O_{\alpha}$, where $O_{\alpha} = Y_{\alpha}$ except for finitely many $\alpha$.  The basis for a topology is a subset of the topology, and any element of the topology can be formed by a union of intersections of elements of the basis.  The space consisting of $\bigtimes_{\alpha} Y_{\alpha}$ and the product topology will be denoted by $\bigtimes_{\alpha} X_{\alpha}$.
\end{definition}

\begin{theorem}[Tychonoff]
If $X_{\alpha}$ is an indexed family of compact topological spaces, then the product space $\bigtimes_{\alpha} X_{\alpha}$ is compact.
\end{theorem}

The set $S$ can be thought of as the infinite-dimensional Cartesian product $\bigtimes_{i=1}^{\infty} V$; an infinite sequence is effectively the same thing as an infinite-dimensional tuple.  Using the discrete topology $\mathcal{P}(V)$ as the topology for $V$, consider the topological space 

\[
X = \bigtimes_{i = 1}^{\infty} \langle V, \mathcal{P}(V) \rangle = \langle S, \mathcal{T} \rangle
\]

\begin{lemma} Every set in $A$ is a closed set in $X$.
\end{lemma}

{\it Proof: } First we show that the sets $\{\omega : \omega(j) = v\}$ are closed sets in $X$, for arbitrary $j \in \mathbb{Z}^+$ and $v \in V$.  This is equivalent to the statement that the complement, $\{\omega: \omega(j) \in V - \{v\}\}$, is in $\mathcal{T}$.  That statement is true, because the complement is equal to the set $\bigtimes_{i = 1}^{\infty} X_i$ where $X_j = V - \{v\}$ and $X_i = V$ for $i \ne j$, which is an element of the basis for $\mathcal{T}$.

Then $B_{k,v} = \bigcap_{i = 1}^k \{\omega: \omega(i) = v_i\}$ is also a closed set, because the set of closed sets in $X$ is closed under finite intersection.  Every set in $A$ is a closed set because each can be expressed as a finite union of $B_{k,v}$ and the set of closed sets in $X$ is closed under finite union.

\begin{lemma} For every sequence of non-empty sets $B_i \in A$, $\lim_{i \rightarrow \infty} B_i \ne \emptyset$.
\label{non-empty-lemma}
\end{lemma}

{\it Proof: } $\langle V,\mathcal{P}(V) \rangle$ is a compact space.  The set of closed sets in that space is also $\mathcal{P}(V)$, because it includes the complement of every subset of $V$, which is itself the set of all subsets of $V$.  Any possible intersection of a collection of sets in $\mathcal{P}(V)$ is finite, so for any given collection the collection itself is one of its finite subsets and if the intersection of any finite subset is non-empty the intersection of all elements must be non-empty.  By Tychonoff's theorem $X$ is therefore compact.  Then $B_i$, as a sequence of closed, non-empty sets which are subsets of each other (and therefore all finite intersections of them are non-empty), must have a non-empty intersection by Lemma \ref{compact}: $\lim_{i \rightarrow \infty} B_i = \bigcap_{i = 1}^{\infty} B_i \ne \emptyset$.  Therefore, if $\lim_{i \rightarrow \infty} f_a(B_i) \ne 0$, $\lim_{i \rightarrow \infty} B_i \ne \emptyset$.

There is a simple consequence of Lemma \ref{non-empty-lemma} which bears noting.
\begin{corollary}If $B_i$ is a sequence of non-empty sets, $C = \lim_{i \rightarrow \infty} B_i \not \in A$.\end{corollary}  

{\it Proof: } Otherwise, the sequence $D_i = B_i - C$ (or $C - B_i$ if the convergence is from below) would be a sequence of non-empty sets in $A$ converging to $\emptyset$, contradicting Lemma \ref{non-empty-lemma}.

Now we can show the following:

\begin{theorem} $f_a$ is a Borel probability measure. \end{theorem}
    {\it Proof: }

\begin{enumerate} \item Since $S = \bigcup^{n}_{i = 1} B_{0,v_i}$ as shown above,  
\[f_a(S) = \sum^{n}_{i = 1} f_a(B_{0,v_i}) = f_a(B_{0,a}) = 1\] 
because by definition $f_a(B_{0,v}) = 0$ when $v \ne a$ and $f_a(B_{0,a}) = 1$ since no terms appear in the product after the first, which is 1.

\item Satisfied by definition.
\item Suppose $\lim_{i \rightarrow \infty} f_a(B_i) \ne 0$.  This implies that $B_i \ne \emptyset$ for all $i$, as otherwise at that $i$, and for all greater $i$, $f_a(B_i)$ would be zero and thus $\lim_{i \rightarrow \infty} f_a(B_i)$ would be zero.  Then, by Lemma \ref{non-empty-lemma}, $\lim_{i \rightarrow \infty} B_i \ne \emptyset$, the contrapositive of which is that, if $\lim_{i \rightarrow \infty} B_i = \emptyset$, then $\lim_{i \rightarrow \infty} f_a(B_i) = 0$.
\end{enumerate}

The Kolmogorov extension theorem states the existence of a Borel probability measure $m_a$ defined on $B$, the Borel extension of $A$, which agrees with $f_a$ for sets in $A$.  The remainder of this paper will user $(S,B,m_a)$ as the probability space.

\section{Basic Random Variables}

 \begin{definition} The probability of a random variable assuming a given value, under measure $m_a$, will be denoted as:
\begin{equation}
\mathbf{P}_a[X = c] = m_a(X^{-1}(c))
\end{equation}
\end{definition}

\begin{definition}  If $X$ is a number-valued random variable the {\it expected value} of $X$ under measure $m_a$ is defined as follows:
\begin{equation}
\mathbf{E}_a[X] = \sum_{x} x P_a[X = x]
\end{equation}
\end{definition}

Now define $X_j : S \mapsto V$ by $X_j(\omega) = \omega(j)$, $j \in \mathbb{Z}^+$.

\begin{theorem}$X_j$ is a random variable \end{theorem}

{\it Proof:} We must show that the set $X_j^{-1}(q) = \{\omega : \omega(j) = q\}$ is measurable.  For every possible sequence $s$ of $j$ vertices, define $s'$ to be a sequence of $j+1$ vertices with $s_i' = s_i$ when $i < j$ and $s_j' = q$.  Every element of $X_j^{-1}(q)$ has elements of $V$ at positions $0$ through $j-1$, so it is an element of the set $B_{j,s'}$ for some $s'$ defined above, and $X_j^{-1}(q) \subseteq \bigcup_{s'} B_{j,s'}$.  And every element of any of the sets $B_{j,s'}$ is an element of $X_j^{-1}(q)$ by definition since it has $q$ as its $j$th vertex, so $X_j^{-1}(q) \supseteq \bigcup_{s'} B_{j,s'}$ and therefore $X_j^{-1}(q) = \bigcup_{s'} B_{j,s'}$.  Because it is a union of elements of $B$, it is measurable.
\\

Next, define $\tau_{p}(\omega) : S \mapsto \mathbb{Z}^+$ by $\tau_{p}(\omega) = \min \{ k: \omega(k) = p$\}, $p \in V$.  

\begin{theorem} 
$\tau_p$ is a random variable. 
\label{stop-time}
\end{theorem}

{\it Proof:}  We will show that the sets $T_k = \{\omega: \tau_{p}(\omega) \leq k\}$ are measurable.  Then 
\[\tau_p^-1(k) = \{\omega: \tau_p(\omega) = k\} = T_k - T_{k-1}\] 
will also be measurable and $\tau_p$ will be a random variable.

\begin{eqnarray*}
T_k &=& \{\omega: \tau_p(\omega) \leq k\} \\
&=& \{\omega: \min \{j: \omega(j) = p\} \leq k\} \\
&=& \{\omega: \omega(i) = p\ \mbox{for some } i \leq k\} \\
&=& \bigcup^{k}_{i=0} \{\omega: \omega(i) = p\} 
\end{eqnarray*}
Since the sets $\{\omega: \omega(i) = p\}$ were shown to be measurable above, and the sets $T_k$ are finite unions of the those sets, they are also measurable.

$\tau_P$ for a set of vertices $P$ is defined similarly, and is a random variable since the set $\tau_P^{-1}(v)$ is the union of the corresponding sets for each $p \in P$, which are measurable as shown above.

\begin{theorem} $X_{\tau_S}$ is a random variable, $S \subset V$. \end{theorem}

{\it Proof:}  {
\begin{eqnarray*}
X_{\tau_S}^{-1}(v) &=& \{ \omega : \omega(\tau_S(\omega)) = v \}\\
&=& \{ \omega: \tau_S(\omega) = n, \omega(n) = v\ \mbox{for some } n \in \mathbb{Z}^+\}\\
&=& \bigcup_{n \geq 0} \{ \omega: \tau_S(\omega) = n, \omega(n) = v\}\\
&=& \bigcup_{n \geq 0} \{  \omega: \tau_S(\omega) = n\} \cap \{\omega: \omega(n) = v\}
\end{eqnarray*}

Each of the two terms of inner intersection were shown to be measurable previously, so as the countable union of intersections of such terms, the entire set is measurable.
\\

For a function $\phi$ defined on $S$, $\phi(X_{\tau_S})$ is also a random variable; the inverse set for a value $k$ of $\phi$ (there are finitely many if $S$ is finite) is the union of the inverse sets of $X_{\tau_S}$ for each vertex on which $\phi(v) = k$, which is a finite union of measurable sets and therefore measurable.

If $\phi$ is real-valued, the expected value of $\phi(X_{\tau_S})$ is well-defined for each measure $m_a$. 



\section{$\gamma$-harmonic functions and the Dirichlet Problem}

We now consider the particular case of graphs with designated boundaries, where the $V$ is partitioned into disjoint subsets $\partial V$ and $\mbox{int } V$.  For definitions of $\gamma$-harmonicity and related concepts, see \cite{mc}.

To show that a function is $\gamma$-harmonic, it is sufficient to show that it satisfies the mean value property:

\begin{equation}
f(u) =\frac{ \sum_{v: u \sim v} \gamma(u,v) f(v)}{\sum_{v: u \sim v} \gamma(u,v)}
\end{equation}


\begin{theorem} For fixed $w \in \partial V$, $u(v) = \mathbf{P}_v[X_{\tau_{\partial V}}=w]$, $v \in \mbox{int } V$, is $\gamma$-harmonic with $\gamma(u,v) = p(u,v)$ 
\label{harmonic-1}
\end{theorem}

{\it Proof: } The set being measured is the union of sets $B_{k,s}$ where all of the $B_{k,s}$ have the property that the first boundary vertex that occurs in the sequence $s$ is $w$.  These individual sets are disjoint as long as the sequences $s$ are not equal to or subsequences of each other, because if that is the case then, as all $\omega$ in each set equal $s$ for the first $k$ vertices, all $\omega$ in one set must differ from all in another somewhere in initial segment.  And sets defined by sequences equal to, or subsequences of, the sequence defining another set make no contribution to the measure computation since they are subsets of other sets in the union.  Let $P$ be the set of disjoint sequences formed by taking the set of sequences defining components in the union above, and removing any sequences equal to or subsequences of other sequences in $P$, because those will not make any contribution to the measure.  Then by the definition of $m_v$,

\begin{equation*}
\mathbf{P}_v[X_{\tau_{\partial V}}=w] = \sum_{s \in P} m_v(B_{|s|,s})
\end{equation*}

Let $S_u = \{\omega \in S: \omega(1) = u\}$.  $B_{|s|,s} \subseteq S$, and $S =  \bigcup_{u \in V} S_u$, so $B_{|s|,s} = \bigcup_{u \in V} S_u \cap B_{|s|,s}$.  Then:

\[
\sum_{s \in P} m_v(B_{|s|,s}) = \sum_{s \in P} \sum_{u \in V} m_v(S_u \cap B_{|s|,s}) = \sum_{u \in V}\sum_{s \in P} m_v(S_u \cap B_{|s|,s})
\]

Let $Q_u = \{s \in P: S_u \cap B_{|s|,s} \cap \{\omega: \omega(0) = v\} \neq \emptyset, m_v(B_{|s|,s}) \ne 0\}$.  $m_v(S_u \cap B_{|s|,s})$ is only non-zero if $s \in Q_u$, because if either the measured set is empty, or it consists entirely of paths not beginning at $v$, the measure will be zero.  If that is the case $S_u \cap B_{|s|,s} =  B_{|s|,s}$ because $v$ must be the first element and $u$ the next in $s$.  Therefore:

\begin{eqnarray*}
 \sum_{u \in V}\sum_{s \in P} m_v(S_u \cap B_{|s|,s}) &=& \sum_{u \in V}\sum_{s \in Q_u}m_v(B_{|s|,s})\\
&=&  \sum_{u \in V}p(v,u)\sum_{s \in Q_u}\frac{m_v(B_{|s|,s})}{p(v,u)}
\end{eqnarray*}

Each sequence $s$ in $Q_u$ begins with $u$, so $p(v,u)$ appears as a factor in the product expansion of $m_v(B_{|s|,s})$, and the remainder of  $m_v(B_{|s|,s})$ is a product of transition probabilities along a particular finite subsequence of vertices starting at $u$ and ending at a boundary vertex, with only interior vertices in between.  This remainder equals $m_u(B_{|s'|,s'})$ for the sequence $s'$ consisting of the remaining vertices in $s$ other than $u$.  There must be one in the sum for each sequence $s'$ in $P$ where $m_u(B_{|s'|,s'}) \ne 0$, because otherwise there would be a measurable set of paths between $v$ and the boundary passing through only interior vertices not accounted for in the original sum, contradicting the definition of $P$.  Then:

\[
\sum_{u \in V}p(v,u)\sum_{s \in Q_u}\frac{m_v(B_{|s|,s})}{p(v,u)} = \sum_{u \in V} p(v,u)\sum_{s \in P}m_u(B_{|s|,s})
\]
%\newpage
Noting that $p(v,u) = 0$ when $v \not \sim u$, and applying the definition of the set $P$:

\begin{equation}
\mathbf{P}_v[X_{\tau_{\partial V}}=w] = \sum_{u: v \sim u}p(v,u) \mathbf{P}_u[X_{\tau_{\partial V}}=w]
\end{equation}

Which, as $\sum_{u: v \sim u} p(v,u) = 1$, establishes $\gamma$-harmonicity.
\\

Given a cutset $C$ between $v$ and $\partial V$, we can extend this result to the following:
\begin{corollary} $\mathbf{P}_v[X_{\tau_{\partial V}}=w] = \sum_{u \in C}\mathbf{P}_v[X_{\tau_C} = u] \mathbf{P}_u[X_{\tau_{\partial V}}=w]$
\end{corollary}

{\it Proof: } Since $C$ is a cutset between $v$ and $\partial V$, any measurable $\omega$ must contain some occurrence of an element of $C$ before any element of $\partial V$.  Then every $\omega$ in a measurable set can be divided into three parts; one, before the first occurrence of a vertex in $C$, two, between there and the first vertex in $\partial V$, and third, after $\partial V$ is reached.  Grouping the expression for $\mathbf{P}_v[X_{\tau_{\partial V}}=w]$ depending on the value of the first vertex $u$ in $C$, and factoring out the part of the product terms occurring before $C$ is reached, we must have all products of transition probabilities for sequences of vertices beginning at $u$ and reaching $w$ before any other vertex in $\partial V$, which is the definition of $\mathbf{P}_u[X_{\tau_{\partial V}}=w]$.  And the terms factored out must contain all products of transition probabilities for sequences of vertices beginning at $v$ and reaching $u$ before any other vertex in $C$, which is the definition of $P_v[X_{\tau_C} = u]$.  Taking the sum of expressions for all $u \in C$ yields the final result.

This version is consistent with Theorem \ref{harmonic-1} when $C = \{u: v \sim u\}$, as then\\ 
$\mathbf{P}_v[X_{\tau_C} = u] = p(v,u)$.
\\

We can pose a Dirichlet problem on random walk networks, given a partition of $V$ into disjoint sets $\mbox{int } V$ and $\partial V$:  For a real-valued function $\phi$ defined on $\partial V$, find a function defined on all of $V$ which is $\gamma$-harmonic on $\mbox{int } V$ and equals $\phi$ on $\partial V$, with $\gamma(u,v)=p(u,v)$.

\begin{theorem} $u(v) = \mathbf{E}_v[\phi(X_{\tau_{\partial V}})]$ for $v \in \mbox{int } V$ solves the Dirichlet problem for $\phi$ defined on $\partial V$ 
\label{harmonic-2}
\end{theorem}

{\it Proof:}  Let $B$ be the set of values of $\phi$; it is finite because there are finitely many boundary vertices.

\begin{equation} 
\mathbf{E}_v[\phi(X_{\tau_{\partial V}}) =  \sum_{x \in B} x \mathbf{P}_v[\phi(X_{\tau_{\partial V}}) = x]
\end{equation}

$\mathbf{P}_v[\phi(X_{\tau_{\partial V}}) = x]$ is the measure of the union of sets where $X_{\tau_{\partial V}} = v$ for some boundary vertex $v$ where $\phi(v) = x$.  Each of those sets is disjoint, because if one vertex is the first boundary vertex to occur in a sequence, another one cannot be, and therefore their measure is just the sum of the measure of those sets.  Then:

\begin{eqnarray*}
\mathbf{P}_v[\phi(X_{\tau_{\partial V}}) = k] &=& \sum_{w: \phi(w) = k} \mathbf{P}_v[X_{\tau_{\partial V}} = w]\\
&=&\sum_{w: \phi(w) = k} \sum_{u: v \sim u}p(v,u) \mathbf{P}_u[X_{\tau_{\partial V}}=w]
\end{eqnarray*}

The last substitution being valid because of the previous theorem.

\begin{eqnarray*}
\mathbf{E}_v[\phi(X_{\tau_{\partial V}})] = \sum_{x \in B} x \sum_{w: \phi(w) = x} \sum_{u: v \sim u}p(v,u) \mathbf{P}_u[X_{\tau_{\partial V}}=w] \\
= \sum_{u: v \sim u}p(v,u)\sum_{x \in B} x \sum_{w: \phi(w) = x} \mathbf{P}_u[X_{\tau_{\partial V}}=w]
\end{eqnarray*}

Or, by definition:

\begin{equation}
\mathbf{E}_v[\phi(X_{\tau_{\partial V}})] =  \sum_{u: v \sim u}p(v,u)\mathbf{E}_u[\phi(X_{\tau_{\partial V}})]
\end{equation}

Therefore, $u(v)$ is $\gamma$-harmonic on $\mbox{int }V$ and trivially equals $\phi$ on the boundary, hence it is a solution to the Dirichlet problem.  Relying on the known uniqueness of these solutions, we have another interpretation of a harmonic function on a weighted graph; interpreting the graph as a probability transition network, the values of the function represent the expected value of the function at the first boundary vertex in a sequence of transitions beginning at each interior vertex.
\\

\section{Other Results}

For a fixed $v \in \mbox{int } V$, the function $\mu_v(w) = P_v[X_{\tau_{\partial V}}=w]$ defined for $w \in \partial V$ is the {\it harmonic measure} of $w$ with respect to $v$.  It is a valid probability measure on $\mathcal{P}(\partial V)$.  Because different values of $\tau_{\partial V}$ correspond to disjoint events, it must satisfy the second and third requirements above by definition of $m_v$.  To see that for each $v$ $\sum_{w \in \partial V} \mu_v(w) = 1$, consider the function $h(v) = \sum_{w \in \partial V} P_v[X_{\tau_{\partial V}}=w]$.  It is harmonic in $\mbox{int } V$ because each term of the sum is, and also equals $\sum_{w \in \partial V} \mu_v(w) = 1$ at each $v \in \mbox{int } V$.  And because $P_v[X_{\tau_{\partial V}}=w] = 1$ at $w$ and 0 on $\partial V - \{w\}$, $h$ is 1 at each boundary vertex, and so by uniqueness must be uniformly 1 at every vertex.
\\

Define another function, $\tau_p^+(\omega): S \mapsto \mathbb{Z}^+$ by $\tau_p^+(\omega) = \min \{ k > 0: \omega(k) = p\}$, $p \in V$.  It can be shown to be a random variable by an analogous argument to that used to prove Theorem \ref{stop-time}, using $T_k^+ = \{\omega: \tau_p^+(\omega) \leq k\} = \bigcup^k_{i=1} \{\omega: \omega(i) = p\}$ in place of $T_k$.  $X_{\tau_{\partial V}^+}$ therefore is also a random variable.

Consider the function (on $V$) $f(v) = \mathbf{P}_v[X_{\tau_{\partial V}^+}=w]$.  At any interior vertex, $f$ must equal $\mathbf{P}_v[X_{\tau_{\partial V}}=w]$, because any path beginning at an interior vertex must make at least one transition before reaching the boundary and the only measure sets of paths at that interior vertex are those beginning at it.  At boundary nodes, using a similar method to the proof of Theorem \ref{harmonic-1} it can be shown that:

\begin{equation}
\mathbf{P}_v[X_{\tau_{\partial V}^+}=w] = \sum_{u: v \sim u}p(v,u) \mathbf{P}_u[X_{\tau_{\partial V}}=w]
\end{equation}

Noting that for $v \in \partial V - \{w\}$, $\mathbf{P}_v[X_{\tau_{\partial V}}=w]= 0$, the above quantity, interpreted in an electrical sense, equals the current out of $v$ due to the potential $u(v) = \mathbf{P}_v[X_{\tau_{\partial V}}=w]$ on the network.  As $\mathbf{P}_w[X_{\tau_{\partial V}}=w] = 1$, the potential difference between $v$ and $w$ is 1, and there is no potential difference between $v$ and other boundary vertices, so all of the current must be due to $w$ and $f(w)$ also equals the effective conductance between $w$ and $v$.  And by a similar argument to Theorem \ref{harmonic-2}, the ``current'' at a boundary vertex $v$ due to an arbitrary potential $\phi$ on $\partial V$ can be shown to equal $\mathbf{E}_v[\phi(X_{\tau_{\partial V}^+})]$.


\section{Inverse Problems}

For now see \cite{krenz} and \cite{dv} for information on recovering transition probabilities from interior-boundary absorption probabilities.

The results of \cite{lust} and \cite{dip} can be applied to random walk networks to solve the analogue of the electrical inverse problem, keeping in mind the above interpretation of response matrix entries (effective conductances).  The restrictions on values of transition probabilities lead to some networks being recoverable.
\newpage
\begin{thebibliography}{99}
\bibitem{mc}Curtis, Edward B., and James A. Morrow, {\it Inverse Problems for Electrical Networks}, World Scientific, Singapore, 2000
\bibitem{dv}DeVries, Timothy,  ``Recoverability of Random Walk Networks'', 2003.\bibitem{dip}DiPalatino, Dominic, ``Properties of Vertex Conductivities and Directed Edge Conductivity Networks'', 2002.
\bibitem{ito} Ito, K., and H. P. McKean, {\it Diffusion Processes and Their Sample Paths}, Springer-Verlag, New York, 1974.
\bibitem{krenz} Krenz, Kurt, ``Finding Internal Transitional Probabilities from Measurements of Exiting Probabilities'', 1992.
\bibitem{lust} Lust, Jaime, ``Directed Graphs'', 2001.
\bibitem{lyons} Lyons, Russell, and Yuval Peres, {\it Probability on Trees and Networks}, Cambridge University Press, Cambridge, 2005 (forthcoming)
\bibitem{royden} Royden, H. L., {\it Real Analysis}, Macmillan, New York, 1988.
\end{thebibliography}
\end{document}