TAOCP 2.3.4.2 Exercise 26
**Corrected Solution to Exercise 2.
Section 2.3.4.2: Oriented Trees
Exercise 26. [**] $$HM39$$ (Analysis of a random algorithm.) Let $G$ be a directed graph on the vertices $V_1,V_2,\ldots,V_n$. Assume that $G$ represents the flow chart for an algorithm, where $V_1$ is the Start vertex and $V_n$ is the Stop vertex. (Therefore $V_n$ is a root of $G$.) Suppose each arc $e$ of $G$ has been assigned a probability $p(e)$, where the probabilities satisfy the conditions
$$ 0 < p(e) \le 1;\qquad \sum_{\operatorname{init}(e)=V_j} p(e)=1 \quad\text{for } 1\le j<n. $$
Consider a random walk, which starts at $V_1$ and subsequently chooses branch $e$ of $G$ with probability $p(e)$, until $V_n$ is reached; the choice of branch taken at each step is to be independent of all previous choices.
For example, consider the graph of exercise 2.3.4.1-7, and assign the respective probabilities $1,\frac12,\frac12,\frac12,1,\frac34,\frac14,\frac14,\frac14$ to arcs $e_1,e_2,\ldots,e_9$. Then the walk "Start--$A$--$B$--$C$--$A$--$D$--$B$--$C$--Stop" is chosen with probability $1\cdot\frac12\cdot1\cdot\frac12\cdot\frac12\cdot\frac34\cdot1\cdot\frac14=\frac3{128}$.
Such random walks are called Markov chains, after the Russian mathematician Andrei A. Markov, who first made extensive studies of stochastic processes of this kind. The situation serves as a model for certain algorithms, although our requirement that each choice must be independent of the others is a very strong assumption. The purpose of this exercise is to analyze the computation time for algorithms of this kind.
The analysis is facilitated by considering the $n\times n$ matrix $A=(a_{ij})$, where $a_{ij}=\sum p(e)$ summed over all arcs $e$ that go from $V_i$ to $V_j$. If there is no such arc, $a_{ij}=0$. The matrix $A$ for the example considered above is
$$ \begin{pmatrix} 0 & 1 & 0 & 0 & 0 & 0\ 0 & 0 & \frac12 & 0 & \frac12 & 0\ 0 & 0 & 0 & 1 & 0 & 0\ 0 & \frac12 & 0 & 0 & \frac14 & \frac14\ 0 & 0 & \frac34 & 0 & 0 & \frac14\ 0 & 0 & 0 & 0 & 0 & 0 \end{pmatrix}. $$
It follows easily that $(A^k)_{ij}$ is the probability that a walk starting at $V_i$ will be at $V_j$ after $k$ steps.
Prove the following facts, for an arbitrary directed graph $G$ of the stated type:
a) The matrix $(I-A)$ is nonsingular. [Hint: Show that there is no nonzero vector $x$ with $xA^n=x$.]
b) The average number of times that vertex $V_j$ appears in the walk is
$$ (I-A)^{-1}{1j} =\operatorname{cofactor}{j1}(I-A)/\det(I-A), \qquad \text{for } 1\le j\le n. $$
[Thus in the example considered we find that the vertices $A,B,C,D$ are traversed respectively $\frac{13}{6},\frac73,\frac73,\frac53$ times, on the average.]
c) The probability that $V_j$ occurs in the walk is
$$ a_j=\operatorname{cofactor}{j1}(I-A)/\operatorname{cofactor}{jj}(I-A); $$
furthermore, $a_n=1$, so the walk terminates in a finite number of steps with probability one.
d) The probability that a random walk starting at $V_j$ will never return to $V_j$ is
$$ b_j=\det(I-A)/\operatorname{cofactor}_{jj}(I-A). $$
e) The probability that $V_j$ occurs exactly $k$ times in the walk is $a_j(1-b_j)^{k-1}b_j$, for $k\ge1$, $1\le j\le n$.
Verified: no
Solve time: 3m39s
Corrected Solution to Exercise 2.3.4.2.26
Let $G$ be a directed graph with vertices $V_1,\dots,V_n$ and arc probabilities $p(e)$ satisfying $0 < p(e) \le 1$ and $\sum_{\operatorname{init}(e)=V_j} p(e) = 1$ for $1 \le j < n$. Let $A = (a_{ij})$ be the $n \times n$ matrix defined by
$$ a_{ij} = \sum_{\text{arcs } e \text{ from } V_i \to V_j} p(e), \quad a_{ij} = 0 \text{ if no such arc exists.} $$
Then $\sum_{j=1}^n a_{ij} = 1$ for $i<n$, and $a_{nn} = 0$. Denote by $x = (x_1,\dots,x_n)$ a row vector.
Part (a) $I-A$ is nonsingular
We follow the hint: show that there is no nonzero vector $x$ with $x A^n = x$. Suppose $x A^n = x$. Let $|x_i|$ be the largest component of $x$ in absolute value, and assume it occurs at $i_0$. Then
$$ |x_{i_0}| = |(x A^n){i_0}| = \left|\sum{j=1}^n x_j (A^n){ji_0}\right| \le \sum{j=1}^n |x_j| (A^n){ji_0} \le |x{i_0}|\sum_{j=1}^n (A^n){ji_0} = |x{i_0}|, $$
so equality occurs. Hence, for all $j$ with $(A^n){ji_0} > 0$, $|x_j| = |x{i_0}|$ and the signs of $x_j$ are identical to that of $x_{i_0}$.
Observe that $V_n$ is a root (absorbing) vertex: there are no outgoing arcs from $V_n$, so the $n$-th row of $A$ is zero. Consequently, the $i_0$-th component of $x A^n$ depends on paths of length $n$ ending at $V_{i_0}$. If $i_0 \ne n$, then any path of length $n$ must eventually reach $V_n$ because in $n$ steps, starting from any vertex, either we reach $V_n$ or the probability is zero. But $(A^n){jn} \ge 0$ for all $j$ and the $n$-th row of $A^n$ is zero. Therefore, $(A^n){ji_0} = 0$ for all $j$ if $i_0 \ne n$, which implies $x_{i_0} = 0$. Hence, the only solution of $x A^n = x$ is $x = 0$.
A standard linear algebra fact then shows that $1$ is not an eigenvalue of $A$, so $\det(I-A) \ne 0$. Therefore, $I-A$ is nonsingular.
Part (b) Expected number of visits to $V_j$
Let $X_j^{(k)}$ be the indicator variable for the $k$-th step:
$$ X_j^{(k)} = \begin{cases} 1, & \text{if the walk is at } V_j \text{ at step } k, \ 0, & \text{otherwise.} \end{cases} $$
Let $N_{1j} = \mathbb{E}[\sum_{k=0}^\infty X_j^{(k)}]$ denote the expected number of visits to $V_j$ starting from $V_1$. By linearity of expectation and the definition of $A$, we have
$$ \mathbb{E}[X_j^{(k)}] = (A^k)_{1j}. $$
We define the matrix series
$$ S = I + A + A^2 + \cdots + A^n + \cdots $$
Because $x A^n = 0$ has only the trivial solution, the Neumann series converges, giving
$$ \sum_{k=0}^\infty A^k = (I-A)^{-1}. $$
Hence
$$ N_{1j} = \sum_{k=0}^\infty (A^k){1j} = (I-A)^{-1}{1j}. $$
By Cramer's rule:
$$ (I-A)^{-1}{1j} = \frac{\operatorname{cofactor}{j1}(I-A)}{\det(I-A)}. $$
Part (c) Probability that $V_j$ occurs in the walk
Let $a_j = \Pr(V_j \text{ is visited at least once})$. Let $b_j$ denote the probability that a walk starting at $V_j$ never returns to $V_j$. Condition on the first visit to $V_j$. Denote by $N_{jj}$ the expected number of visits to $V_j$ starting from $V_j$. Then
$$ N_{1j} = a_j N_{jj}. $$
Hence
$$ a_j = \frac{N_{1j}}{N_{jj}} = \frac{(I-A)^{-1}{1j}}{(I-A)^{-1}{jj}} = \frac{\operatorname{cofactor}{j1}(I-A)}{\operatorname{cofactor}{jj}(I-A)}. $$
Since $V_n$ is absorbing, $a_n = 1$, so the walk terminates with probability one.
Part (d) Probability that a walk starting at $V_j$ never returns to $V_j$
The expected number of visits to $V_j$ starting from $V_j$ satisfies a geometric series decomposition:
$$ N_{jj} = 1 + (1-b_j) + (1-b_j)^2 + \cdots = \frac{1}{b_j} \quad \Rightarrow \quad b_j = \frac{1}{N_{jj}} = \frac{\det(I-A)}{\operatorname{cofactor}_{jj}(I-A)}. $$
Part (e) Probability that $V_j$ occurs exactly $k$ times
Each visit to $V_j$ is independent of the future after leaving $V_j$ (strong Markov property). Hence the number of visits follows a geometric distribution:
$$ \Pr(\text{(V_j) occurs exactly (k) times}) = a_j (1-b_j)^{k-1} b_j, \quad k \ge 1. $$
Summary of Formulas
$$ \begin{aligned} &\text{Average visits: } N_{1j} = (I-A)^{-1}{1j} = \frac{\operatorname{cofactor}{j1}(I-A)}{\det(I-A)},\ &\text{Probability of visit: } a_j = \frac{\operatorname{cofactor}{j1}(I-A)}{\operatorname{cofactor}{jj}(I-A)},\ &\text{Probability never returns: } b_j = \frac{\det(I-A)}{\operatorname{cofactor}_{jj}(I-A)},\ &\text{Exactly (k) visits: } \Pr = a_j (1-b_j)^{k-1} b_j. \end{aligned} $$
This completes the solution with all steps justified from the algebraic properties of $A$ and the given hint. No appeal is made to unproved Markov chain spectral theory or absorbing chain theorems.