Exercises — Stochastic processes — Markov chains, steady-state, random walks

What rule? A transition matrix must be row-stochastic: every row is a list of probabilities of going somewhere, so each row must sum to $1$ (parent note, §1). Entries must also be $\ge 0$.

Check row by row:

• Row 1 (from state 1): $0.5+0.5=1$ ✔
• Row 2 (from state 2): $0.3+0.7=1$ ✔
• All entries $\ge 0$ ✔

Answer: Yes, it is a valid transition matrix.

Which product? The update rule is ${\pi }^{(t+1)}={\pi }^{(t)}P$ — a row vector times the matrix (parent, §1, "Row times P"). We sum over the current state $i$, which is the row index of $P$, and that summation is exactly a row-vector–matrix product. So the correct product is ${\pi }^{(0)}P$.

Compute (row vector rule: new $j$-th entry $={\sum }_i{\pi }_i^{(0)}{P}_{ij}$): ${\pi }_1^{(1)}=0.6(0.5)+0.4(0.3)=0.30+0.12=0.42$ ${\pi }_2^{(1)}=0.6(0.5)+0.4(0.7)=0.30+0.28=0.58$ Answer: ${\pi }^{(1)}=(0.42,0.58)$. (Sanity: it sums to $1$. Good — probability is conserved.)

What we want: the row vector $\pi$ that is unchanged by one step, i.e. $\pi =\pi P$ with $a+b=1$ (parent, §2). "In equals There."

Write out $\pi P=\pi$ component by component: $a=0.5a+0.3b(\text{inflow into state 1})$ $b=0.5a+0.7b(\text{inflow into state 2})$

Use the first equation (the two are always redundant for a $2\times 2$ chain; that's why we also need normalisation): $a-0.5a=0.3b\Rightarrow 0.5a=0.3b\Rightarrow a=0.6b.$

Normalise with $a+b=1$: $0.6b+b=1\Rightarrow 1.6b=1\Rightarrow b=\frac{1}{1.6}=0.625,a=\mathrm{0.375.}$

Answer: $\pi =(0.375,0.625)=\left(\frac{3}{8},\frac{5}{8}\right)$.

Plan: apply "Row times P" twice: ${\pi }^{(1)}={\pi }^{(0)}P$, then ${\pi }^{(2)}={\pi }^{(1)}P$. (Equivalently ${\pi }^{(2)}={\pi }^{(0)}{P}^2$.)

Day 1: ${\pi }_1^{(1)}=1(0.8)+0(0.4)=0.8,{\pi }_2^{(1)}=1(0.2)+0(0.6)=\mathrm{0.2.}$ So ${\pi }^{(1)}=(0.8,0.2)$.

Day 2: ${\pi }_1^{(2)}=0.8(0.8)+0.2(0.4)=0.64+0.08=0.72,$ ${\pi }_2^{(2)}=0.8(0.2)+0.2(0.6)=0.16+0.12=\mathrm{0.28.}$

Answer: ${\pi }^{(2)}=(0.72,0.28)$. Notice it is already creeping toward the stationary $(\frac{2}{3},\frac{1}{3})\approx (0.667,0.333)$ from the parent note — convergence in action.

Let each step be $S_k\in \{+1,-1\}$ and $X_n={\sum }_{k=1}^n{S}_k$ (parent, §3).

(a) Mean. $E[S_k]=(+1)\frac{1}{2}+(-1)\frac{1}{2}=0$. Sums of means: $E[X_{100}]={\sum }_{k=1}^{100}0=\boxed{0}$.

(b) Variance. $E[S_k^2]=(+1{)}^2\frac{1}{2}+(-1{)}^2\frac{1}{2}=1$, so $\mathrm{Var}(S_k)=1-0^2=1$. Steps are independent, and variances of independent things add: $\mathrm{Var}(X_{100})={\sum }_{k=1}^{100}1=\boxed{100}$.

(c) Typical distance $=$ standard deviation $=\sqrt{\mathrm{Var}(X_{100})}=\sqrt{100}=\boxed{10}$.

Why they disagree: The mean is a signed average — leftward and rightward wanderings cancel, giving $0$. But the spread doesn't care about sign; each step contributes $+1$ to the variance whether it went left or right. So the cloud of possible positions gets wider like $\sqrt{n}$, even though its center stays glued to $0$. See figure — the center (amber line) is flat while the $\pm \sqrt{n}$ envelope (cyan) fans out.

Rearrange the recurrence to expose the shape: $h_i=\frac{1}{2}{h}_{i-1}+\frac{1}{2}{h}_{i+1}⟹2h_i=h_{i-1}+h_{i+1}⟹h_{i+1}-h_i=h_i-h_{i-1}.$

Read this out loud: the gap between consecutive values, $d_i:=h_{i+1}-h_i$, satisfies $d_i=d_{i-1}$. So every gap is the same constant $d$. A sequence with constant steps is an arithmetic progression — i.e. a straight line: $h_i=h_0+id=0+id=id$.

Pin the constant using the other boundary $h_N=1$: $h_N=Nd=1\Rightarrow d=\frac{1}{N}\Rightarrow \boxed{h_i=\frac{i}{N}}.$

The geometry: constant gaps = a ramp from $(0,0)$ to $(N,1)$. See the straight amber line below.

(a) Stationary $\pi =(a,b)$, $a+b=1$, solve $\pi P=\pi$: $\pi P=(a,b)\left(\begin{array}{cc}0& 1\\ 1& 0\end{array}\right)=(b,a).$ Set $(b,a)=(a,b)\Rightarrow a=b$. With $a+b=1$: $\boxed{\pi =(\frac{1}{2},\frac{1}{2})}$. A stationary distribution exists.

(b) Iterate from ${\pi }^{(0)}=(1,0)$: ${\pi }^{(1)}=(1,0)P=(0,1),{\pi }^{(2)}=(0,1)P=(1,0),{\pi }^{(3)}=(0,1),\dots$ It oscillates $(1,0)\to (0,1)\to (1,0)\to \cdots$ forever, never approaching $(\frac{1}{2},\frac{1}{2})$. So ${\pi }^{(t)}\nrightarrow \pi$.

(c) Which condition fails? Aperiodicity. This chain has period 2: from state 1 you can only return to state 1 after an even number of steps ($2,4,6,\dots$). The forced cycle length is $>1$, so the chain is periodic. Irreducibility holds (each state reaches the other), but the Perron–Frobenius convergence guarantee (Perron–Frobenius Theorem) needs both irreducible and aperiodic. Missing aperiodicity ⇒ a $\pi$ that exists but is never reached.

(Eigenvalue view: $P$ has eigenvalues $+1$ and $-1$. The $-1$ eigenvalue has magnitude $1$, so its contribution never decays — it flips sign each step, producing the eternal oscillation. Aperiodicity is exactly the condition that $1$ is the only eigenvalue of magnitude $1$. See Linear Algebra — Eigenvalues and Eigenvectors.)

(a) Row sums: each row has a single $1$ and two $0$s → sum $=1$. ✔ Row-stochastic.

(b) Stationary $\pi =(a,b,c)$, solve $\pi P=\pi$. Compute $\pi P$ (row vector rule, column by column):

• Column 1 of $P$ is $(0,0,1{)}^{\top }$: $(\pi P{)}_1=a(0)+b(0)+c(1)=c$.
• Column 2 is $(1,0,0{)}^{\top }$: $(\pi P{)}_2=a$.
• Column 3 is $(0,1,0{)}^{\top }$: $(\pi P{)}_3=b$.

So $\pi P=(c,a,b)$. Setting $=(a,b,c)$: $c=a,a=b,b=c\Rightarrow a=b=c.$ Normalise $a+b+c=1\Rightarrow 3a=1\Rightarrow \boxed{\pi =(\frac{1}{3},\frac{1}{3},\frac{1}{3})}$. By symmetry the frog spends equal time on each pad.

(c) Aperiodic? No. The frog is forced $1\to 2\to 3\to 1\to \cdots$; it returns to any pad only after multiples of $3$ steps. The period is 3 > 1 ⇒ periodic. So $\pi$ exists and is unique (chain is irreducible), but ${\pi }^{(t)}$ cycles rather than converges.

(a) Set up first-step analysis. From position $i$ (interior, $0<i<N$) you take one step (that's why a $+1$ appears), then land at $i-1$ or $i+1$ each with probability $\frac{1}{2}$, and by the Markov property the process restarts from wherever you land. Conditioning on that first step (law of total expectation, cousin of Law of Total Probability): $m_i=1+\frac{1}{2}{m}_{i-1}+\frac{1}{2}{m}_{i+1},m_0=0,m_N=0.$ (The $1$ = the step you just spent; the boundaries are $0$ because once absorbed, no more steps are needed.)

(b) Solve. Rearrange: $2m_i=2+m_{i-1}+m_{i+1}⟹m_{i+1}-m_i=(m_i-m_{i-1})-2.$ So the gaps $d_i=m_{i+1}-m_i$ decrease by 2 each step: $d_i=d_0-2i$ — an arithmetic progression. Summing gaps from $0$ to $i$: $m_i=m_0+{\sum }_{k=0}^{i-1}{d}_k=i{d}_0-2{\sum }_{k=0}^{i-1}k=i{d}_0-i(i-1).$ This is a quadratic in $i$; try the ansatz $m_i=Ai-i^2$ (a downward parabola vanishing sensibly). Impose $m_N=0$: $AN-N^2=0\Rightarrow A=N.$ Then $m_i=Ni-i^2=i(N-i)$. Check $m_0=0$ ✔, $m_N=N\cdot N-N^2=0$ ✔, and it satisfies the recurrence: $1+\frac{1}{2}(i-1)(N-i+1)+\frac{1}{2}(i+1)(N-i-1)=i(N-i)$ ✔. $\boxed{m_i=i(N-i)}$

(c) With $i=3,N=10$: $m_3=3(10-3)=3\times 7=\boxed{21}$ steps expected. A fair $3-vs-$10 game lasts, on average, 21 rounds — surprisingly long, because the walk lingers before either barrier catches it.

Compare with the absorption probability $h_i=i/N=3/10$ from the parent note: a linear answer for "which end," but a quadratic answer for "how long." Same first-step trick, different inhomogeneous term (the $+1$).

The web as a Markov chain. Model each web page as a state. A "random surfer" at a page clicks one of its outgoing links uniformly at random — that defines a row-stochastic transition matrix $P$ (each row = "where a click from this page can go"). The surfer is memoryless: the next click depends only on the current page. So the surfer is a random walk on a giant graph.

PageRank = stationary distribution. The importance of a page = the long-run fraction of time the random surfer spends on it = the entry of the stationary vector $\pi$ solving $\pi =\pi P$ (left eigenvector for eigenvalue $1$, parent §2). "In equals There": a page is important if lots of importance flows into it.

The ingredient Google adds — teleportation (damping). Raw web-link $P$ can be reducible (dead-end pages, disconnected clusters) and periodic, so by Exercises 4.1–4.2 a unique, reachable $\pi$ is not guaranteed. Google mixes in a small probability (about $0.15$) of jumping to a uniformly random page instead of following a link: $G=0.85P+0.15\frac{1}{N}11^{\top }.$ Now every page reaches every other in one step (irreducible) and there are no forced cycles (aperiodic). By the Perron–Frobenius Theorem, $G$ has a unique stationary $\pi$ with the power iteration ${\pi }^{(t+1)}={\pi }^{(t)}G$ converging to it from any start — exactly the guarantee Exercises 4.1–4.2 showed was missing without it.