Exercises

$\mathbf{P}^{2} = \begin{pmatrix} 0.6 & 0.4 \\ 0.2 & 0.8 \end{pmatrix} \begin{pmatrix} 0.6 & 0.4 \\ 0.2 & 0.8 \end{pmatrix} = \begin{pmatrix} 0.44 & 0.56 \\ 0.28 & 0.72 \end{pmatrix}.$$

$p_{12}^{(2)} = 0.56$.

$\pi_1 = 0.6\pi_1 + 0.2\pi_2$ and $\pi_1 + \pi_2 = 1$. The first equation gives $0.4\pi_1 = 0.2\pi_2$, so $\pi_2 = 2\pi_1$.

$\pi_1 + 2\pi_1 = 1 \Rightarrow \pi_1 = 1/3, \; \pi_2 = 2/3$.

$A \to B$ (prob 1), $B \to A$ (prob 0.5) or $B \to C$ (prob 0.5), $C \to A$ (prob 1).

$A \to B$ (1 step), $A \to C$ (via $A \to B \to C$, 2 steps). $B \to A$ (1 step), $C \to A$ (1 step), so $B \to C$ and $C \to B$ (via $A$). All states communicate: the chain is irreducible.

$A \to B \to A$: 2 steps. $A \to B \to C \to A$: 3 steps. So $\{n : p_{AA}^{(n)} > 0\} \supseteq \{2, 3\}$ and $\gcd(2, 3) = 1$.

$d(A) = 1$, so the chain is aperiodic. Since it is irreducible, all states have period 1.

Column sums: $0.5 + 0 + 0 + 0.5 = 1$; $0.5 + 0.5 + 0 + 0 = 1$; $0 + 0.5 + 0.5 + 0 = 1$; $0 + 0 + 0.5 + 0.5 = 1$. Yes, doubly stochastic.

$[\boldsymbol{\pi}\mathbf{P}]_j = \sum_i \frac{1}{4} p_{ij} = \frac{1}{4} \sum_i p_{ij} = \frac{1}{4} \cdot 1 = \frac{1}{4}$. So $\boldsymbol{\pi}\mathbf{P} = \boldsymbol{\pi}$.

$\pi_0 = 0.25\pi_1$, $\pi_1 = \pi_0 + 0.5\pi_1 + \pi_2$, $\pi_2 = 0.25\pi_1$, and $\pi_0 + \pi_1 + \pi_2 = 1$.

From the first and third: $\pi_0 = \pi_2 = 0.25\pi_1$. Substituting into normalization: $0.25\pi_1 + \pi_1 + 0.25\pi_1 = 1$, so $1.5\pi_1 = 1$, giving $\pi_1 = 2/3$, $\pi_0 = \pi_2 = 1/6$.

$\boldsymbol{\pi}\mathbf{P} = (1/6, 2/3, 1/6) \begin{pmatrix} 0 & 1 & 0 \\ 0.25 & 0.5 & 0.25 \\ 0 & 1 & 0 \end{pmatrix} = (1/6, 2/3, 1/6) = \boldsymbol{\pi}$. Verified.

Let $\mathbf{A}$ and $\mathbf{B}$ be stochastic matrices. Their product $\mathbf{C} = \mathbf{A}\mathbf{B}$ has entries $c_{ij} = \sum_k a_{ik} b_{kj}$.

Since $a_{ik} \geq 0$ and $b_{kj} \geq 0$, we have $c_{ij} \geq 0$.

$\sum_j c_{ij} = \sum_j \sum_k a_{ik} b_{kj} = \sum_k a_{ik} \sum_j b_{kj} = \sum_k a_{ik} \cdot 1 = 1.$$

For a birth-death chain: $\pi_k = \pi_0 \prod_{m=0}^{k-1} \frac{b_m}{d_{m+1}}$. Here $b_0 = 1$, $b_i = p$ for $i \geq 1$, and $d_i = q$ for $i \geq 1$. So $\pi_k = \pi_0 \cdot (1/q) \cdot (p/q)^{k-1} = \pi_0 (p/q)^{k-1}/q$ for $k \geq 1$.

$\sum_{k=0}^{\infty} \pi_k < \infty$ requires $p/q < 1$, i.e., $p < q = 1-p$, i.e., $p < 1/2$.

The chain is positive recurrent if and only if $p < 1/2$. For $p = 1/2$ it is null recurrent, and for $p > 1/2$ it is transient.

If all states were transient, each would be visited only finitely many times. But the chain must be somewhere at every time step, and there are finitely many states. By the pigeonhole principle, some state must be visited infinitely often, contradicting transience. So all states are recurrent.

For a recurrent irreducible chain, a stationary measure $\gamma_j$ exists with $\gamma_j > 0$ for all $j$. If the state space is finite, then $\sum_j \gamma_j < \infty$, so we can normalize to get a stationary distribution. This implies $\mathbb{E}_i[T_i] = 1/\pi_i < \infty$, i.e., positive recurrence.

$\mathbf{P} = \begin{pmatrix} 0 & 1 & 0 & 0 & 0 \\ 1/4 & 0 & 3/4 & 0 & 0 \\ 0 & 2/4 & 0 & 2/4 & 0 \\ 0 & 0 & 3/4 & 0 & 1/4 \\ 0 & 0 & 0 & 1 & 0 \end{pmatrix}.$$

$\pi_k = \binom{4}{k} 2^{-4} = \binom{4}{k}/16$. So $\boldsymbol{\pi} = (1/16, 4/16, 6/16, 4/16, 1/16)$.

Check $\pi_k p_{k,k+1} = \pi_{k+1} p_{k+1,k}$: $\pi_0 p_{01} = (1/16)(1) = 1/16$ and $\pi_1 p_{10} = (4/16)(1/4) = 1/16$. Holds. Similarly for all other pairs.

$\pi_G = 0.2/0.25 = 0.8$, $\pi_B = 0.05/0.25 = 0.2$.

$\text{BER} = \pi_G \epsilon_G + \pi_B \epsilon_B = 0 + (0.2)(0.5) = 0.1$.

The sojourn time in state B is $\text{Geometric}(g)$ with mean $1/g = 5$ slots.

For a chain in steady state, the transition probabilities of the reversed chain are $\hat{p}_{ij} = \frac{\pi_j p_{ji}}{\pi_i}$.

By detailed balance, $\pi_j p_{ji} = \pi_i p_{ij}$, so $\hat{p}_{ij} = \frac{\pi_i p_{ij}}{\pi_i} = p_{ij}$.

$\hat{\mathbf{P}} = \mathbf{P}$: the forward and reversed chains have the same transition matrix. The chain is reversible.

$r_i = p \, r_{i+1} + q \, r_{i-1}$ for $1 \leq i \leq N-1$, with $r_0 = 1$, $r_N = 0$. Rearranging: $p(r_{i+1} - r_i) = q(r_i - r_{i-1})$.

Let $d_i = r_i - r_{i+1}$. Then $d_i = (q/p) d_{i-1} = (q/p)^i d_0$. Now $r_0 - r_N = \sum_{i=0}^{N-1} d_i = d_0 \sum_{i=0}^{N-1} (q/p)^i = d_0 \frac{(q/p)^N - 1}{q/p - 1}$. Since $r_0 - r_N = 1$, we get $d_0 = \frac{q/p - 1}{(q/p)^N - 1}$.

$r_i = r_0 - \sum_{k=0}^{i-1} d_k = 1 - d_0 \frac{(q/p)^i - 1}{q/p - 1} = 1 - \frac{(q/p)^i - 1}{(q/p)^N - 1} = \frac{(q/p)^i - (q/p)^N}{1 - (q/p)^N}$.

Fix a recurrent state $i_0$. Let $T_1 < T_2 < \cdots$ be the successive return times to $i_0$. Set $\tau_k = T_k - T_{k-1}$ (inter-visit times). By the strong Markov property, $\{\tau_k\}_{k \geq 2}$ are i.i.d. with $\mathbb{E}[\tau_k] = \mu_{i_0} < \infty$.

Let $Y_k = \sum_{m=T_{k-1}}^{T_k - 1} f(X_m)$. The $\{Y_k\}_{k \geq 2}$ are also i.i.d. By the strong law: $\frac{1}{M} \sum_{k=1}^{M} Y_k \to \mathbb{E}[Y_2]$ and $\frac{1}{M} \sum_{k=1}^{M} \tau_k \to \mu_{i_0}$.

The time average $\frac{1}{n} \sum_{k=0}^{n-1} f(X_k) \to \frac{\mathbb{E}[Y_2]}{\mu_{i_0}}$. One can show $\mathbb{E}[Y_2] = \mu_{i_0} \sum_i \pi_i f(i)$ by expanding, giving the desired limit $\sum_i \pi_i f(i)$.

$\alpha(1,2) = \min(1, 0.2/0.1) = 1$, $\alpha(1,3) = 1$, $\alpha(1,4) = 1$. $\alpha(2,1) = \min(1, 0.1/0.2) = 0.5$, $\alpha(2,3) = 1$, $\alpha(2,4) = 1$. $\alpha(3,1) = 1/3$, $\alpha(3,2) = 2/3$, $\alpha(3,4) = 1$. $\alpha(4,1) = 1/4$, $\alpha(4,2) = 1/2$, $\alpha(4,3) = 3/4$.

$p_{ij} = q_{ij} \alpha(i,j) = \frac{1}{4} \alpha(i,j)$ for $j \neq i$.

$p_{ii} = 1 - \sum_{j \neq i} p_{ij}$.

Row 1: $p_{12} = 1/4$, $p_{13} = 1/4$, $p_{14} = 1/4$, $p_{11} = 1/4$. Row 2: $p_{21} = 1/8$, $p_{23} = 1/4$, $p_{24} = 1/4$, $p_{22} = 3/8$. Row 3: $p_{31} = 1/12$, $p_{32} = 1/6$, $p_{34} = 1/4$, $p_{33} = 1/2$. Row 4: $p_{41} = 1/16$, $p_{42} = 1/8$, $p_{43} = 3/16$, $p_{44} = 5/8$.

$\mathbf{P} = 0.85 \mathbf{L} + 0.0375 \mathbf{J}$. Row 1: $(0.0375, 0.4625, 0.4625, 0.0375)$. Row 2: $(0.0375, 0.0375, 0.8875, 0.0375)$. Row 3: $(0.3208, 0.3208, 0.0375, 0.3208)$. Row 4: $(0.0375, 0.0375, 0.8875, 0.0375)$.

By power iteration (or solving the linear system), the stationary distribution is approximately $\boldsymbol{\pi} \approx (0.139, 0.228, 0.461, 0.172)$.

Page 3 has the highest PageRank (0.461) because it receives links from all other pages. The teleportation factor ensures the chain is irreducible and aperiodic.

Let $m, \ell > 0$ with $p_{ij}^{(m)} > 0$ and $p_{ji}^{(\ell)} > 0$. Then $p_{ii}^{(m+\ell)} \geq p_{ij}^{(m)} p_{ji}^{(\ell)} > 0$, so $d(i) \mid (m + \ell)$.

For any $n$ with $p_{jj}^{(n)} > 0$: $p_{ii}^{(m + n + \ell)} \geq p_{ij}^{(m)} p_{jj}^{(n)} p_{ji}^{(\ell)} > 0$, so $d(i) \mid (m + n + \ell)$. Since $d(i) \mid (m + \ell)$, we get $d(i) \mid n$. This holds for all $n$ in the return set of $j$, so $d(i) \mid d(j)$.

By symmetry, $d(j) \mid d(i)$. Since both are positive integers, $d(i) = d(j)$.

Let $X_n$ start at state $i$ and $Y_n \sim \boldsymbol{\pi}$ (stationary). At each step, couple them: with probability $\sum_k \min(p_{X_n,k}, p_{Y_n,k})$ they meet; given meeting, they agree on the next state.

Since $p_{ij}^{(1)} \geq p_\star$ for all $i, j$, the probability of meeting in one step is at least $\sum_k \min(p_{X_n,k}, p_{Y_n,k}) \geq M p_\star \cdot (1/M) = p_\star$. (More carefully: $\sum_k \min(p_{i,k}, p_{j,k}) \geq p_\star$ since each term is at least $p_\star$ and there are $M$ terms, but the sum is at most 1.)

Hence $\mathbb{P}(\text{not met by step } n) \leq (1 - p_\star)^n$.

By the coupling inequality: $\|\mathbf{P}^{n}(i, \cdot) - \boldsymbol{\pi}\|_{\text{TV}} \leq \mathbb{P}(X_n \neq Y_n) \leq (1 - p_\star)^n$.

$[\boldsymbol{\pi}\mathbf{P}]_v = \sum_{u: (u,v) \in E} \frac{d_u}{2|E|} \cdot \frac{1}{d_u} = \sum_{u: (u,v) \in E} \frac{1}{2|E|} = \frac{d_v}{2|E|} = \pi_v$.

For $(u,v) \in E$: $\pi_u p_{uv} = \frac{d_u}{2|E|} \cdot \frac{1}{d_u} = \frac{1}{2|E|}$. Similarly $\pi_v p_{vu} = \frac{1}{2|E|}$. Equal. For $(u,v) \notin E$: both sides are 0.

On $C_M$: if $M$ is even, the walk alternates between two sets (bipartite), so $d = 2$. If $M$ is odd, the walk can return in $M$ steps (full cycle) or $2$ steps (there and back, impossible on a cycle without self-loops or multi-edges). Actually, from any vertex, return times include $M$ and $2$ (if $M$ is odd, $\gcd(M, M) = M$ ... wait: you cannot return in 2 steps on a cycle). Return times are $M, 2M, 3M, \ldots$ so $d = M$ if $M$ is odd? No: you can also return in $2$ steps? No, on a cycle the minimum return time is $M$ since there is only one path in each direction.

Correct analysis: $p_{ii}^{(n)} > 0$ only when $n$ is a multiple of... On $C_M$, the walk can return to $i$ in $M$ steps (going around the cycle). Also in $2M$ steps, etc. But also: go $k$ steps right and $k$ steps left for total $2k$ steps. So $p_{ii}^{(2)} > 0$ iff there exists a path of length 2 from $i$ to $i$. On $C_M$ with $M \geq 3$, there is no self-loop and the only length-2 path from $i$ returns via a neighbor: $i \to j \to i$ with probability $(1/2)(1/2) = 1/4 > 0$. Wait: on $C_3$, from vertex 1, go to 2 (prob 1/2) then back to 1 (prob 1/2). Yes! So $p_{ii}^{(2)} > 0$.

For $C_M$ with $M \geq 3$: $p_{ii}^{(2)} = 2 \cdot (1/2)(1/2) = 1/2 > 0$ (go to either neighbor and come back). And $p_{ii}^{(M)} > 0$ (go around). So $d = \gcd(2, M)$. If $M$ is odd: $d = 1$ (aperiodic). If $M$ is even: $d = 2$ (periodic).

Write $\mathbf{P} = \sum_{k=1}^{M} \lambda_k \mathbf{v}_k \mathbf{u}_k^T$ where $\mathbf{u}_k, \mathbf{v}_k$ are left/right eigenvectors. Then $\mathbf{P}^{n} = \mathbf{1}\boldsymbol{\pi} + \sum_{k=2}^{M} \lambda_k^n \mathbf{v}_k \mathbf{u}_k^T$.

$\|p_i^{(n)} - \boldsymbol{\pi}\|_2 = \|\sum_{k=2}^{M} \lambda_k^n [\mathbf{e}_i^T \mathbf{v}_k] \mathbf{u}_k^T\|_2 \leq |\lambda_2|^n \cdot C_i$

where $C_i$ depends on the eigenvector components. Since $|\lambda_2| = 1 - \gamma$, we get $\|p_i^{(n)} - \boldsymbol{\pi}\|_2^2 \leq C_i^2 (1 - \gamma)^{2n}$.

$\mathbf{P} = \frac{1}{2}\mathbf{I} + \frac{1}{2M}\mathbf{J}$. Eigenvalues of $\frac{1}{M}\mathbf{J}$: one eigenvalue $1$ (eigenvector $\mathbf{1}$) and $M-1$ eigenvalues $0$. So eigenvalues of $\mathbf{P}$: $\lambda_1 = 1$ and $\lambda_k = 1/2$ for $k = 2, \ldots, M$. Spectral gap: $\gamma = 1/2$.

Mixing time: $t_{\text{mix}} = O(\log M)$.