\documentclass{amsart}
\title{Recoverability of Random Walk Networks}
\author{Timothy DeVries}
\address{Cornell University}
\email{tdd2@cornell.edu}
\date{August 15th, 2003}

\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{graphicx}

\newenvironment{myproof}{\textbf{Proof:} \textmd}{$\Box$}

\raggedbottom

\usepackage{amsthm}
\newtheorem{lemma}{Lemma}[section]
\newtheorem{theorem}{Theorem}[section]
\newtheorem{conjecture}{Conjecture}[section]
\newtheorem{definition}{Definition}[section]

\begin{document}

\begin{abstract}
In the following paper we present and partially solve an inverse problem related to
random walks on a graph.  Given a special graph-with-boundary and a set of edge
probabilities on that graph, we can construct the transition matrix $P$ whose
entries $P_{ij}$ are the expectations that a random walk from node $v_{i}$ will be
in the direction of node $v_{j}$.  The forward problem is to calculate the
absorption matrix $B$ whose entries $B_{ij}$ are the expectations that a random walk from the $i^{\text{th}}$ interior node will terminate at node $v_{j}$.  The inverse problem, then, is to recover $P$ from $B$ and the graph.  We
present Card's Conjecture on a recoverability condition for random walk networks,
and demonstrate that the condition is necessary for recoverability.  At the end of the paper
an example random walk network is presented, whose recoverability is verified.
\end{abstract}

\maketitle

\section{Preliminaries}
Let $G = (V,V_{B},E)$ be a directed edge graph-with-boundary, where $V$ corresponds
to the set of nodes, $V_{B} \subset V$ is a proper subset of V corresponding to the
boundary nodes, and $E$ corresponds to the directed edges connecting nodes in $V$. 
Additionally, we impose the following restrictions on G:
\begin{enumerate}
\item If two nodes $v_{i}, v_{j} \in V-V_{B}$, $i \neq j$, are connected in $G$,
they are connected by exactly two edges (one for each direction).
\item If two nodes $v_{i} \in V - V_{B}$, $v_{j} \in V_{B}$ are connected in $G$,
they are connected by exactly one edge $e_{ij} \in E$ (the edge directed from node
$v_{i}$ to node $v_{j}$).
\item For all $v_{i} \in V_{B}$, the only edge from node $v_{i}$ is $e_{ii}$ (a loop
from node $v_{i}$ back to itself).
\item For all $v_{i} \in V-V_{B}$, there exists a set of directed edges linking node
$v_{i}$ to the boundary.
\end{enumerate}

For such a graph $G$, a \em transition probability \em on $G$ is a function $\rho$
which assigns to each $e_{ij} \in E$ a real number $\rho(e_{ij}), 0 < \rho(e_{ij})
\leq 1$, such that $\sum_{j, i\sim j}\rho(e_{ij})=1$ for all $i$ (where $i \sim j$ if
and only if an edge exists from $v_{i}$ to $v_{j}$).  A \em random walk network \em
$\Gamma = (G,\rho)$ is a graph $G$ (as described above) together with a transition
probability function $\rho$.

We are interested in studying random walks on such a random walk network $\Gamma$. 
The physical description of the random walk is as follows: beginning at a given
interior node, we walk from node to node along the directed edges of $G$ in a random
fashion, where the probability of walking from node $v_{i}$ to node $v_{j}$ is given
by $\rho(e_{ij})$.  By the restrictions placed on G, a walk always reaches and
remains (terminates) at a boundary node, and for this reason boundary nodes are often referred to
as \em absorbing nodes. \em As a means of characterizing our random walk network, we
create a matrix $P$ whose entries $P_{ij}$ are the probabilities given by $\rho$
that a step from $v_{i}$ will be in the direction of $v_{j}$.  Such a $P$ is known
as a \em transition matrix. \em If the boundary nodes of our network are numbered
first, then P will take the block form
\[ P = \left[\begin{array}{cc}
I & 0 \\
R & Q
\end{array}\right]\]
where the top-left block matrix is the identity because a walk beginning at a
boundary node remains at that boundary node, while the top-right block matrix has
all $0$ entries because no edges exist directed from the boundary to the interior. 
Note that the construction of the transition matrix is such that all the row sums
are equal to $1$.

Our construction of the random walk network naturally gives rise to two problems,
which will be discussed in the following sections.
\section{The Forward Problem}
The first problem associated with random walk networks is the so-called forward
problem: given $P$, we want to form the \em absorption matrix \em $B$ whose entries
$B_{ij}$ are the probabilities that a random walk starting at the $i^{\text{th}}$ interior node will terminate at node $v_{j} \in V_{B}$.  The solution is relatively straightforward.  

First we note that the vector $e_{i}P$'s $j^{\text{th}}$ entry is the expectation
that a walk from $v_{i}$ will be at node $v_{j}$ after one step in the walk (where
$e_{i}$ is the row vector with a $1$ in $i^{\text{th}}$ column and $0$'s elsewhere). 
Similarly, $e_{i}P^n$ is the vector whose $j^{\text{th}}$ entry is the expectation
that a walk from $v_{i}$ will be at node $v_{j}$ after $n$ steps.  It is thus clear
that the matrix $\lim_{n\rightarrow \infty}P^n$ should give us the expectations that
a walk from some $v_{i} \in V$ will terminate at boundary node $v_{j} \in V_{B}$, as
the construction of our network guarantees that all walks terminate at the boundary after a
finite number of steps.  This fact also gives us an intuitive reason for why this limit
must ultimately converge.  Thus we examine
\[\lim_{n\rightarrow \infty}P^n = \lim_{n\rightarrow \infty} \left[\begin{array}{cc}
I & 0 \\
(I + Q + \dotsb + Q^{n-1})R & Q^{n}
\end{array}\right]\]
As the following theorem will show, the above matrix does in fact converge.
\begin{theorem}
The series $\sum_{n=0}^{\infty} Q^n$ converges for $Q$ as described in our
formulation of a random walk network.
\end{theorem}
\begin{proof}
Let $\lambda$ be an eigenvalue of $Q$ over $\mathbb{C}$, with $\upsilon$ a
corresponding eigenvector.  Then:
\[Q\upsilon = \lambda\upsilon\]
\[\Rightarrow (Q\upsilon)_{i} = \sum_{j=1}^{n} Q_{ij}\upsilon_{j} = \lambda\upsilon_{i} \text{
for all } i \in \lbrace 1,2,\dotsb,n\rbrace\]
\[\Rightarrow \lvert(Q\upsilon)_{i}\rvert = \lvert\sum_{j=1}^{n} Q_{ij}\upsilon_{j}\rvert =
\lvert\lambda\upsilon_{i}\rvert = \lvert\lambda\rvert\cdot\lvert\upsilon_{i}\rvert\]
\begin{align*}\Rightarrow \lvert\lambda\rvert& = \frac{\lvert\sum_{j=1}^{n}
Q_{ij}\upsilon_{j}\rvert}{\lvert\upsilon_{i}\rvert} \text{ for all } i \text{ such
that } \lvert\upsilon_{i}\rvert \neq 0 \\ & \leq\frac{\sum_{j=1}^{n}\lvert
Q_{ij}\rvert\cdot\lvert\upsilon_{j}\rvert}{\lvert\upsilon_{i}\rvert}=\sum_{j=1}^{n}Q_{ij}\frac{\lvert\upsilon_{j}\rvert}{\lvert\upsilon_{i}\rvert}
\end{align*}
Denote by $K = \lbrace k_{1},\dotsb,k_{m}\rbrace$ the set of indices such that
$\lvert\upsilon_{k_{i}}\rvert\geq\lvert\upsilon_{j}\rvert \text{ for all } i \in
\lbrace 1,\dotsb,m\rbrace$, $j \in \lbrace 1,\dotsb,n\rbrace$. Denote by $L =
\lbrace l_{1},\dotsb,l_{p}\rbrace$ the set of indices corresponding to interior
nodes which are not adjacent to any boundary nodes.

Now we have:
\[\lvert\lambda\rvert \leq
\sum_{j=1}^{n}Q_{ij}\frac{\lvert\upsilon_{j}\rvert}{\lvert\upsilon_{i}\rvert} \leq
\sum_{j=1}^{n}Q_{ij} \leq 1 \text{ for all } i \in K\]
The second inequality arises by observing that
$\frac{\lvert\upsilon_{j}\rvert}{\lvert\upsilon_{i}\rvert} \leq 1 \text{ for all }
j$ when $i \in K$, while the third inequality arises by the construction of $Q$. 
Thus, $\lvert\lambda\rvert \leq 1$.

Assume $\lvert\lambda\rvert = 1$
Let $k \in K$.  Then we have:
\[\lvert\sum_{j=1}^{n}Q_{kj}\upsilon_{j}\rvert = \lvert\upsilon_{k}\rvert\]
But $\sum_{j=1}^{n}Q_{kj}\cdot\lvert\upsilon_{j}\rvert \geq
\lvert\sum_{j=1}^{n}Q_{kj}\upsilon_{j}\rvert$, so we have:
\[\sum_{j=1}^{n}Q_{kj}\cdot\lvert\upsilon_{j}\rvert \geq \lvert\upsilon_{k}\rvert\]
\[\Rightarrow
\sum_{j=1}^{n}Q_{kj}\frac{\lvert\upsilon_{j}\rvert}{\lvert\upsilon_{k}\rvert} \geq
1\]
But as $k \in K$, $1 \geq \frac{\lvert\upsilon_{j}\rvert}{\lvert\upsilon_{k}\rvert}
\text{ for all } j \in \lbrace 1,\dotsb,n \rbrace$ and thus:
\[\sum_{j=1}^{n}Q_{kj} \geq 1\]
But $\sum_{j=1}^{n}Q_{kj} \leq 1$ by construction of $Q$, and so we have:
\[\sum_{j=1}^{n}Q_{kj} = 1 \text{ for all } k \in K\]
This says that the row sum of row $k$ in $Q$ is equal to $1$, which means that index
$k$ corresponds to an interior node which is not adjacent to any boundary nodes, i.e.
$k \in L$.  So we obtain:
\[K \subset L\]
Now we return to the inequality:
\[\lvert\lambda\rvert \leq
\sum_{j=1}^{n}Q_{ij}\frac{\lvert\upsilon_{j}\rvert}{\lvert\upsilon_{i}\rvert} \leq
\sum_{j=1}^{n}Q_{ij} \leq 1 \text{ for all } i \in K\]
Because $\lvert\lambda\rvert = 1$, all the above inequalities must hold as equality.
The second inequality holds as equality only if $Q_{ij} = 0$ for $j \notin K$. Thus,
we must have:
\[\lvert\lambda\rvert = 1 \Rightarrow Q_{ij} = 0 \text{ for } i \in K, j \notin K\]
But this would imply that the nodes whose indices are in $K$ connect only to other
nodes whose indices are in $K$.  Since $K \subset L$, none of the nodes whose
indices are in $K$ connect to the boundary.  This implies that the nodes whose
indices are in $K$ have no path to the boundary, which is a contradiction.  Thus:
\[\lvert\lambda\rvert < 1\]
As $\lvert\lambda\rvert < 1$ for all $\lambda \in \text{ spectrum}(Q)$, the spectral
radius of $Q$, denoted by $r$, is strictly less than 1.  By the spectral radius formula, we also know that
\[r = lim_{n\rightarrow\infty}\lvert Q^n\rvert^\frac{1}{n}\]
So for n large enough
\[\lvert Q^n\rvert^\frac{1}{n} < r' \text{, where } r < r' < 1\]
\[\Rightarrow \lvert Q^n\rvert < r'^n\]
But as $\sum_{n=0}^{\infty}r'^n$ converges, we must have that
$\sum_{n=0}^{\infty}\lvert Q^n\rvert$ converges.  So we have:
\begin{align*}
\sum_{n=0}^{\infty}\lvert Q^n\rvert \geq \lvert\sum_{n=0}^{\infty}Q^n \rvert
&\Rightarrow \lvert\sum_{n=0}^{\infty}Q^n \rvert \text{ is bounded} \\
&\Rightarrow \sum_{n=0}^{\infty}Q^n \text{ converges.}
\end{align*}
\end{proof}
Note that the matrix $\sum_{n=0}^{\infty}Q^n$ (sometimes denoted by $N$) converges
to $(I-Q)^{-1}$, as
\begin{align*}
\lim_{n \rightarrow \infty}(I-Q)\sum_{n=0}^{\infty}Q^n &= \lim_{n \rightarrow
\infty} \sum_{n=0}^{\infty}Q^n - \sum_{n=1}^{\infty}Q^n \\
&= \lim_{n \rightarrow \infty} I - Q^{n+1} \\
&= I
\end{align*}
And so we have
\[\lim_{n\rightarrow \infty}P^n = \lim_{n\rightarrow \infty} \left[\begin{array}{cc}
I & 0 \\
(I-Q)^{-1}R & 0
\end{array}\right]\]
By extension of our argument above, $e_{i}(\lim_{n \rightarrow \infty}P^n)$ is the
vector whose $j^{\text{th}}$ entry is the expectation that a walk from $v_{i}$ will
terminate at node $v_{j}$.  Thus, it is clear that $(e_{i}(I-Q)^{-1}R)_{j}$ is the
probability that a walk from $i^{\text{th}}$ interior node will terminate at node $v_{j} \in
V_{B}$, and so:
\[ B = (I-Q)^{-1}R\]
\section{The Inverse Problem}
The inverse problem associated with random walk networks is to recover the
transition matrix $P$ (or equivalently $Q$ and $R$) given a graph $G$ and the
absorption matrix $B$.  In this section, we present several results characterizing
situations in which such recovery is not possible.  Afterwards, we present an
example random walk network and demonstrate it's recoverability.
\subsection{A Note on When the Inverse Problem is Ill-Formed}
\begin{theorem}
If the diagonal of $Q$ is allowed to be non-zero, the inverse problem will be
ill-formed in the following sense:  For any matrix $B$, there will exist an infinite
family of $Q'$ and $R'$ matrices such that $B=(I-Q')^{-1} R'$.
\end{theorem}
\begin{proof}
Assume that we allow $Q$ to have non-zero entries on the diagonal.  In the physical
interpretation of the problem, this implies that we allow remaining at certain
interior nodes to be a valid step in our random walks.  We intend to show that this
possibility implies that $Q$ and $R$ are not uniquely recoverable from $B$.

Let $Q$ and $R$ be matrices corresponding to a random walk network, as described
above.  Let the number of rows in each matrix be denoted by $n$.  We assume that
$Q_{kk} \neq 0$ for some $k \in \lbrace 1,\dotsb,n\rbrace$.  Now we form the
matrices $Q'$ and $R'$ as follows:

$Q' = Q$ and $R' = R$ except on row k, where we have:
\begin{gather*}
Q'_{kk} = tQ_{kk} \text{ where } 0 < t < 1 \\
Q'_{ki} = sQ_{ki} \text{ for all } i \neq k \text{ and where }
s=\frac{1-tQ_{kk}}{1-(Q)_{kk}} \\
R'_{ki} = sR_{ki} \text{ for all } i
\end{gather*}

First we must check that these $Q'$ and $R'$ matrices make sense for our given random
walk network.  Clearly these new matrices represent the same node-to-node connections as
the original $Q$ and $R$ matrices, as $Q'$ and $R'$ were formed simply by scaling
elements of the $k^{\text{th}}$ rows of $Q$ and $R$ respectively.  Thus, we must merely
demonstrate that $Q'$ and $R'$ make sense as submatrices of a transition matrix $P$.  In other words, we must verify that:
\[\sum_{j} Q'_{ij} + \sum_{j} R'_{ij} = 1 \text{ for all } i \in \lbrace 1,\dotsb,n\rbrace\]
Clearly this holds for all $i \neq k$, so we examine the case where $i = k$:
\begin{align*}
\sum_{j} Q'_{kj} + \sum_{j} R'_{kj} &= tQ_{kk} + s\sum_{\substack{j\\j \neq
k}} Q_{kj} + s\sum_{j} R_{kj} \\
&= tQ_{kk} + s(\sum_{\substack{j\\j \neq k}} Q_{kj} + \sum_{j} R_{kj}) \\
&= tQ_{kk} + s(1-Q_{kk}) \\
&= tQ_{kk} + 1 - tQ_{kk} = 1
\end{align*}
Now, the claim is
that:
\[B=(I-Q')^{-1} R' \text{ for all } t \in \mathbb{R}, 0 < t < 1\]
where $B=(I-Q)^{-1} R$ is the $B$ matrix corresponding to the original $Q, R$ pair.

For convenience, we note that $R' = I'R$ where $I'$ differs from the
$n \times n$ identity matrix in that $I'_{kk} = s$.  Then we have:
\begin{multline*}
B=(I-Q')^{-1} R' \Leftrightarrow (I-Q')B=R' \Leftrightarrow(I-Q')B=I'R \\
\Leftrightarrow (I-Q')B=I'(I-Q)B \Leftrightarrow I'^{-1} (B - Q'B) = B - QB
\end{multline*}
The only place where the above equality may fail is at row $k$, so we examine the
elements of $I'^{-1} (B - Q'B)$ along row k:
\begin{align*}
(I'^{-1} (B - Q'B))_{ki} &= \frac{1}{s}(B_{ki} - \sum_{j} Q'_{kj}B_{ji}) \\
&= \frac{1}{s}(B_{ki} - s \sum_{\substack{j \\ j \neq k}} Q_{kj}B_{ji} -
tQ_{kk}B_{ki}) \\
&= \frac{1}{s}(B_{ki}(1-tQ_{kk}) - s\sum_{\substack{j\\j \neq k}}
Q_{kj}B_{ji}) \\
&= B_{ki}(1-Q_{kk}) - \sum_{\substack{j\\j \neq k}} Q_{kj}B_{ji} \\
&= B_{ki} - \sum_{j} Q_{kj}B_{ji} = (B - QB)_{ki}
\end{align*}
And thus $I'^{-1} (B - Q'B) = B - QB$, which implies that $B=(I-Q')^{-1} R'$ for an
infinite family of valid $Q'$ and $R'$ matrices.  Thus, $Q$ and $R$ can never be
uniquely recovered from $B$ if we allow $Q$ to be non-zero along the diagonal.
\end{proof}
Given the above information, we will assume from this point forward that a random walk network contains no on the interior nodes.
\subsection{Card's Conjecture}
\begin{conjecture} \em (Card's Conjecture) \em A random walk network is recoverable if and only if all the edges
leaving any interior node can be simultaneously extended to vertex-disjoint paths to
the boundary.
\end{conjecture}
While the formulation of the conjecture as written above is the due to Ryan Card, a conjecture made in Krenz's paper \cite{KK} relating to flow paths bears a striking similarity.  It is likely that this critereon for recoverability has been formulated in several different ways over the years, by various people invsestigating random walk networks.

Card's conjecture has yet to be proved in general, but we can provide a proof for
one direction of the statement.  Before providing this proof, however, we must first
present some terminology.
\begin{definition}
Fix an interior node $v_{i} \in V$ on a random walk network.  A \em Choke Set \em $S
\subset V$ for $v_{i}$ is a set of nodes such that any path from $v_{i}$ to the
boundary passes through at least one of the nodes in $S$.  A \em Minimal Choke Set
\em for $v_{i}$ is a choke set on $v_{i}$ of minimal order (an example choke set can be seen in Figure \ref{chokeset}).
\end{definition}
\begin{figure}[ht]
\begin{center}
\includegraphics[width=3.2in]{tdd2-2f1.eps}
\caption{An example choke set $S$ (nodes on the dashed circle).\label{chokeset}}
\end{center}
\end{figure}
We are now in a position to prove one direction of Card's Conjecture:
\begin{theorem} A random walk network is not recoverable if there exists an interior
node such that the edges leaving that node can not be simultaneously extended to
vertex-disjoint paths to the boundary.
\end{theorem}
\begin{proof}
Assume that we have a random walk network such that the edges leaving one of the
nodes, the $x^{\text{th}}$ interior node, can not be extended disjointly to the boundary.  Denote by $S
= \lbrace v_{k_{1}}, \dotsb, v_{k_{d}}\rbrace$ a minimal choke set for the $x^{\text{th}}$ interior node, and
denote by $l$ the valence of this node.  As the edges leaving the $x^{\text{th}}$ interior node can not be
extended disjointly to the boundary, we must have\footnote{While this fact may be
semi-intuitive, a rigorous proof of its verity gets ugly.  For now, we assume it to
be fact.  In future research, a Choke Lemma proving this fact would be very useful} that $d < l$ (a picture of this is provided in Figure \ref{chokeset}).  Now, we
examine the vector
\[e_{x}B = [b_{x1},\dotsb,b_{xm}]\]
where each $b_{xi}$ is the probability that a random walk starting at the $x^{\text{th}}$ interior node will
terminate at $v_{i}$, and where $e_{x}$ is the row vector with a $1$ in the $x^{\text{th}}$ column and $0$'s elsewhere.  Because we have a choke set on the $x^{\text{th}}$ interior node, we can define the
following two structures as a means for rewriting the $b_{xi}$'s.  First, let
\[\bar{p}_{x} = [\bar{p}_{xk_{1}},\dotsb,\bar{p}_{xk_{d}}]\]
where $\bar{p}_{xk_{i}}$ is the probability that $v_{k_{i}}$ will be the last
element of $S$ reached in a walk from the $x^{\text{th}}$ interior node to the boundary.  Second, let
\[C=\left[\begin{array}{ccc}
c_{k_{1}1} & \dotsb & c_{k_{1}m} \\
\vdots & & \vdots \\
c_{k_{d}1} & \dotsb & c_{k_{d}m}
\end{array}\right]\]
where $c_{k_{j}i}$ is the probability that a walk starting at node $v_{k_{j}} \in S$ will
terminate at node $v_{i} \in V_{B}$ without passing through any element of $S$.
Then we have the relation
\[b_{xi} = \bar{p}_{xk_{1}}c_{k_{1}i} + \dotsb + \bar{p}_{xk_{d}}c_{k_{d}i}\]
or
\[e_{x}B(P) = \bar{p}_{x}(P)C(P)\]
where the dependence of $B$, $C$ and $\bar{p}_{x}$ on $P$ is explicitly noted.  It
is not hard to show that the elements of $C$ have no dependency on the edge
probabilities leaving the $x^{\text{th}}$ interior node.  To see this, we can examine an arbitrary
$c_{k_{j}i}$, which is dependent on certain walks beginning at node $v_{k_{j}}$ and terminating at node $v_{i}$.  
Now, assume that one of the walks on which it depends passes through the $x^{\text{th}}$ interior node.  Then the walk must pass back through a node in $S$ to get to the boundary, and $c_{k_{j}i}$ can not depend on this path by the construction of $C$.  Thus $C$ is
independent of all edge probabilities leaving the $x^{\text{th}}$ interior node.

Now, given a fixed $P$ matrix, we examine the resultant space of $P$ matrices in
which only the edge probabilities leaving the $x^{\text{th}}$ interior node are variable.  Denote this space
by $\mathcal{X}$.  Over $\mathcal{X}$, $C$ is constant and we have
\[e_{x}B(P) = \bar{p}_{x}(P)C\]
The vector $\bar{p}_{x}$ has $d$ elements, one of which is dependent on the others (as $\sum_{i=1}^{d} \bar{p}_{xk_{i}}$ is $1$), so $\mathcal{Y}$, the range of $\bar{p}_{x}(P)C$, is at most $d-1$ dimensional.  Thus, the range of $e_{x}B(P)$ is
at most a d-1 dimensional space $\mathcal{Y}$.  Now, we examine the smooth map
\begin{align*}
\Phi = &\mathcal{X} \rightarrow \mathcal{Y} \\
&P \mapsto e_{x}B(P)
\end{align*}
Because we are varying $l-1$ free variables in $\mathcal{X}$ (the valence of the $x^{\text{th}}$ interior node with the added condition that the edge probabilities leaving the $x^{\text{th}}$ interior node sum to
1), $\mathcal{X}$ is an $l-1$ dimensional space.  As $l-1 > d-1$, $\dim(\mathcal{X})
> \dim(\mathcal{Y})$, so $\Phi$ is not even locally injective.  Thus, for each valid
$B$ matrix, there exists an infinite family of edge probabilities on the edges
leaving the $x^{\text{th}}$ interior node which yield the same $e_{x}B(P)$.  Denote this family of transition matrices by $\mathcal{P} \subset \mathcal{X}$.

Finally, we examine $e_{y}B(P)$ for $y \neq x$.  We have:
\[e_{y}B = [b_{y1},\dotsb,b_{ym}]\]
But each $b_{yi}$ can be written as a sum of two terms, one of which does not depend upon the edge
probabilities leaving the $x^{\text{th}}$ interior node and one of which does:
\begin{align*}
e_{y}B &= [b^{(x)}_{y1} + \hat{p}_{yx}b_{x1},\dotsb,b^{(x)}_{ym} +
\hat{p}_{yx}b_{xm}] \\
&= [b^{(x)}_{y1},\dotsb,b^{(x)}_{ym}] + \hat{p}_{yx}e_{x}B
\end{align*}
where $b^{(x)}_{yi}$ is the probability that a walk from the $y^{\text{th}}$ interior node terminates at
$v_{i}$ without passing through the $x^{\text{th}}$ interior node, and $\hat{p}_{yx}$ is the probability that
a walk from the $y^{\text{th}}$ interior node will reach the $x^{\text{th}}$ interior node before termination.

The first term in the above sum and the element $\hat{p}_{yx}$ clearly have no
dependency on the edge probabilities leaving the $x^{\text{th}}$ interior node, while the term $e_{x}B(P)$
is constant over the infinite family of edge probabilities in $\mathcal{P}$ described above.  Thus,
$e_{y}B(P)$ is constant for all $y$ and $P \in \mathcal{P}$, which implies
that $P$ is not uniquely recoverable from $B$.
\end{proof}
\subsection{Demonstrating Recoverability for an Example Tree}

We are now going to demonstrate the recoverability of a random walk network on a
highly symmetric binary tree graph.  Before proceeding, however, we shall prove a
lemma that will aid us in examining a network's recoverability.
\begin{lemma}
Let $A=M_{(I;J)}$ be a square submatrix of an invertible $n \times n$ matrix $M$,
where $I, J \subset K = \lbrace 1,\dotsb,n\rbrace$.  Let $B=M^{-1}_{(K-J;K-I)}$, a
square submatrix of $M^{-1}$.  Then $\det B \neq 0 \Rightarrow \det A \neq 0$.
\end{lemma}
\begin{proof}
Let $A, B$ and $M$ be matrices as described above.  Assume that $\det B \neq 0$.  We
want to show that $\det A \neq 0$.  First, we assume that our index sets $I, J$ are
such that $M$ is of the block form:
\[M = \left[\begin{array}{cc}
A & M_{1} \\ M_{2} & M_{3}
\end{array}\right]\]
(Note: if $M$ is not in the above form, $M$ can be placed in the above form by a series of matrix operations which will not change the following argument.)
Now, we know:
\[\det A \neq 0 \text{ if and only if } A\vec{x} = \vec{0} \Rightarrow \vec{x} =
\vec{0}\]
Which is equivalent to the condition:
\[\left[\begin{array}{cc}
A & M_{1} \\ M_{2} & M_{3}
\end{array}\right]\left[\begin{array}{c}
\vec{x} \\ \vec{0}
\end{array}\right] = \left[\begin{array}{c}
\vec{0} \\ \vec{z}
\end{array}\right] \Rightarrow \vec{x} = \vec{0}\]
So we assume $M \left[\begin{array}{c}
\vec{x} \\ \vec{0}
\end{array}\right] = \left[\begin{array}{c}
\vec{0} \\ \vec{z}
\end{array}\right]$.  This is true if and only if:
\[\left[\begin{array}{c}
\vec{x} \\ \vec{0}
\end{array}\right] = M^{-1}\left[\begin{array}{c}
\vec{0} \\ \vec{z}
\end{array}\right]\]
We can write $M^{-1}$ in block form as:
\[M^{-1} = \left[\begin{array}{cc}
M'_{1} & M'_{2} \\ M'_{3} & B
\end{array}\right]\]
Because $\det B \neq 0$, $B\vec{z} = \vec{0} \Rightarrow \vec{z} = \vec{0}$.  So:
\[\left[\begin{array}{cc}
M'_{1} & M'_{2} \\ M'_{3} & B
\end{array}\right]\left[\begin{array}{c}
\vec{0} \\ \vec{z}
\end{array}\right]=\left[\begin{array}{c}
\vec{x} \\ \vec{0}
\end{array}\right] \Rightarrow B\vec{z} = \vec{0} \Rightarrow \vec{z} = \vec{0}\]
But if $\vec{z} = \vec{0}$, then:
\[M^{-1}\left[\begin{array}{c}
\vec{0} \\ \vec{z}
\end{array}\right] = M^{-1}\vec{0} = \vec{0} = \left[\begin{array}{c}
\vec{x} \\ \vec{0}
\end{array}\right] \Rightarrow \vec{x} = \vec{0}\]
And thus $A\vec{x}=\vec{0} \Rightarrow \vec{x} = \vec{0}$, which is equivalent to
the condition that $\det A \neq 0$.
\end{proof}
\begin{figure}[ht]
\begin{center}
\includegraphics[width=3.8in]{tdd2-2f2.eps}
\caption{A complete binary tree network, with black circles corresponding to interior nodes.\label{tree}}
\end{center}
\end{figure}
We will now demonstrate the recoverability of the network shown in Figure
\ref{tree}.  Note that we need only demonstrate the reoverability of the edge
probabilities leaving nodes $v_{9}$, $v_{13}$ and $v_{15}$: the rest will be
recoverable by symmetry.  Now, for all $i^{\text{th}}$ interior nodes we have the following
equations:
\[B_{ik} = \sum_{\substack{j \\ i \sim j}}P_{ij}B_{jk} \text{ for all } k \text{ such that } v_{k}
\in V_{B}\]
To recover the edge probabilities leaving a node, we must use the above equations to find as many
independent equations as there are edges leaving the node.  For $v_{9}$ (the first interior node)
we examine the equations
\begin{align*}
B_{1,1} &= P_{9,1}\cdot 1 + P_{9,2}\cdot 0 + P_{9,13}\cdot B_{5,1} \\
B_{1,2} &= P_{9,1}\cdot 0 + P_{9,2}\cdot 1 + P_{9,13}\cdot B_{5,2} \\
B_{1,3} &= P_{9,1}\cdot 0 + P_{9,2}\cdot 0 + P_{9,13}\cdot B_{5,3}
\end{align*}
\[\Rightarrow\left[\begin{array}{c}
B_{1,1} \\ B_{1,2} \\ B_{1,3}\end{array}\right] = \left[\begin{array}{ccc}
1 & 0 & B_{5,1} \\
0 & 1 & B_{5,2} \\
0 & 0 & B_{5,3}
\end{array}\right]\left[\begin{array}{c}
P_{9,1} \\ P_{9,2} \\ P_{9,13}\end{array}\right]\]
Which is clearly uniquely solvable for $P_{9,1}$, $P_{9,2}$ and $P_{9,13}$.

For the fifth interior node, $v_{13}$, we have:
\[\left[\begin{array}{c}
B_{5,1} \\ B_{5,3} \\ B_{5,5}\end{array}\right] = \left[\begin{array}{ccc}
B_{1,1} & B_{2,1} & B_{7,1} \\
B_{1,3} & B_{2,3} & B_{7,3} \\
B_{1,5} & B_{2,5} & B_{7,5}
\end{array}\right]\left[\begin{array}{c}
P_{13,9} \\ P_{13,10} \\ P_{13,15}\end{array}\right] = A\left[\begin{array}{c}
P_{13,9} \\ P_{13,10} \\ P_{13,15}\end{array}\right]\]
Which is uniquely solveable if and only if $\det{A} = \det{A^{\top}} \neq 0$.  But
as $B = (I-Q)^{-1}R = NR$, we have
\begin{align*}A^{\top} &= \left[\begin{array}{ccc}
B_{1,1} & B_{1,3} & B_{1,5} \\
B_{2,1} & B_{2,3} & B_{2,5} \\
B_{7,1} & B_{7,3} & B_{7,5}
\end{array}\right] \\ &= \left[\begin{array}{ccc}
N_{1,1} & N_{1,2} & N_{1,3} \\
N_{2,1} & N_{2,2} & N_{2,3} \\
N_{7,1} & N_{7,2} & N_{7,3}
\end{array}\right]\left[\begin{array}{ccc}
R_{1,1} & 0 & 0 \\
0 & R_{2,3} & 0 \\
0 & 0 & R_{3,5}
\end{array}\right]\end{align*}
And so the edge probabilities leaving node $v_{13}$ are uniquely recoverable if and
only if $\det{L} \neq 0$, where $L$ is the submatrix of $N=(I-Q)^{-1}$ defined by
\[L = \left[\begin{array}{ccc}
N_{1,1} & N_{1,2} & N_{1,3} \\
N_{2,1} & N_{2,2} & N_{2,3} \\
N_{7,1} & N_{7,2} & N_{7,3}
\end{array}\right]
\]
By our above lemma, $\det{L} \neq 0$ if $\det{L'} \neq 0$, where $L'$ is the
submatrix of $(I-Q)$ defined by
\[\left[\begin{array}{cccc}
-Q_{4,3} & 1 & -Q_{4,5} & -Q_{4,6} \\
-Q_{5,3} & -Q_{5,4} & 1 & -Q_{5,6} \\
-Q_{6,3} & -Q_{6,4} & -Q_{6,5} & 1 \\
-Q_{7,3} & -Q_{7,4} & -Q_{7,5} & -Q_{7,6}
\end{array}\right]\]
Examining the connections of the graph above, we see that
\[\det{L'} = \left\lvert\begin{array}{cccc}
0 & 1 & 0 & -Q_{4,6} \\
0 & 0 & 1 & 0 \\
-Q_{6,3} & -Q_{6,4} & 0 & 1 \\
0 & 0 & -Q_{7,5} & -Q_{7,6}
\end{array}\right\rvert = Q_{6,4}Q_{7,6} \neq 0\]
And so the edge probabilities leaving node $v_{13}$ are uniquely recoverable.

Analogously, the task of demonstrating the edge probabilities leaving node $v_{15}$
to be recoverable can be reduced to examining a submatrix of $(I-Q)$.  By examining
equations for $B_{7,1}$ and $B_{7,5}$ in terms of $P_{15,13}$ and $P_{15,14}$, we
find that we can solve for the edge probabilities leaving node $v_{15}$ if $\det{L'}
\neq 0$, where
\[L' = \left[\begin{array}{ccccc}
-Q_{2,1} & 1 & -Q_{2,3} & -Q_{2,4} & -Q_{2,7} \\
-Q_{4,1} & -Q_{4,2} & -Q_{4,3} & 1 & -Q_{4,7} \\
-Q_{5,1} & -Q_{5,2} & -Q_{5,3} & -Q_{5,4} & -Q_{5,7} \\
-Q_{6,1} & -Q_{6,2} & -Q_{6,3} & -Q_{6,4} & -Q_{6,7} \\
-Q_{7,1} & -Q_{7,2} & -Q_{7,3} & -Q_{7,4} & 1
\end{array}\right]\]
Examining the connections of the graph above, we see that
\[\det{L'} = \left\lvert\begin{array}{ccccc}
0 & 1 & 0 & 0 & 0 \\
0 & 0 & 0 & 1 & 0 \\
-Q_{5,1} & -Q_{5,2} & 0 & 0 & -Q_{5,7} \\
0 & 0 & -Q_{6,3} & -Q_{6,4} & 0 \\
0 & 0 & 0 & 0 & 1
\end{array}\right\rvert = -Q_{5,1}Q_{6,3} \neq 0\]
Thus, the edge probabilities leaving node $v_{15}$ are recoverable, and by symmetry
the entire transition matrix $P$ is uniquely recoverable from $B$.
\begin{thebibliography}{99}
\bibitem{PD} Doyle, Peter G. \& Snell, J. Laurie.  ``Random Walks and Electric Networks.'' Washington, DC: Math.\ Assoc.\ Am.  1984.
\bibitem{KK} Krenz, Kurt.  ``Finding Internal Transitional Probabilities from Measurements of Exiting Probabilities.''  1992.
\bibitem{CP} Pellicano, Carla.  ``Recovery of Transitional Probabilities from Absorption Probabilities.''  1999.
\bibitem{KS} Schroder, Konrad.  ``Interpretation of Electrical Networks as Probability Networks (and vice versa).''  1993.
\end{thebibliography}
\end{document}