Exam MAS-I — Markov Chains Flashcards

The future depends on the past only through the present: $\Pr(X_{n+1}=j \mid X_n=i, X_{n-1}=i_{n-1},\dots,X_0=i_0) = \Pr(X_{n+1}=j \mid X_n=i)$. Given the current state, the next state is conditionally independent of the entire earlier history. A chain is **time-homogeneous** when this one-step probability does not depend on $n$.

$P$ is the matrix with entries $P_{ij}=\Pr(X_{n+1}=j \mid X_n=i)$, the probability of moving from state $i$ to state $j$ in one step. It is a **stochastic matrix**: every entry $P_{ij}\ge 0$, and **each row sums to $1$**, $\sum_j P_{ij}=1$, because from any state the chain must go somewhere.

$\Pr(X_1=2\mid X_0=1)=P_{12}=0.3$. Row 1 sums to $0.7+0.3=1$ and row 2 sums to $0.4+0.6=1$, all entries are $\ge 0$, so $P$ is a valid stochastic matrix. State $1$ stays put with probability $0.7$ and jumps to state $2$ with probability $0.3$.

$\Pr(X_{m+n}=j \mid X_0=i) = \sum_{k} (P^{m})_{ik}\,(P^{n})_{kj}$, i.e. $P^{(m+n)}=P^{(m)}P^{(n)}$. Consequently the $n$-step matrix is just the matrix power $P^{(n)}=P^{n}$, and $\Pr(X_n=j \mid X_0=i)=(P^{n})_{ij}$. Going from $i$ to $j$ in $m+n$ steps means passing through some intermediate state $k$ at time $m$ and summing over all such $k$.

$P^{2}=P\cdot P$. Entry by entry: $(P^2)_{11}=0.7(0.7)+0.3(0.4)=0.49+0.12=0.61$. $(P^2)_{12}=0.7(0.3)+0.3(0.6)=0.21+0.18=0.39$. $(P^2)_{21}=0.4(0.7)+0.6(0.4)=0.28+0.24=0.52$. $(P^2)_{22}=0.4(0.3)+0.6(0.6)=0.12+0.36=0.48$. So $P^{2}=\begin{pmatrix} 0.61 & 0.39 \\ 0.52 & 0.48 \end{pmatrix}$; each row still sums to $1$.

**Matrix power:** $(P^2)_{11}=0.61$ (from $P^2$ above). **Conditioning on the intermediate state** $X_1$: $\Pr(X_2=1\mid X_0=1)=P_{11}P_{11}+P_{12}P_{21}=0.7(0.7)+0.3(0.4)=0.49+0.12=0.61$. Both give $0.61$ — this is exactly Chapman–Kolmogorov, summing the path $1\to 1\to 1$ and the path $1\to 2\to 1$.

If $\alpha=(\alpha_1,\alpha_2,\dots)$ is the row vector of starting probabilities ($\Pr(X_0=i)=\alpha_i$), then the distribution after $n$ steps is the row vector $\alpha P^{n}$, whose $j$-th entry is $\Pr(X_n=j)=\sum_i \alpha_i (P^n)_{ij}$. Left-multiplying by a row vector mixes the rows of $P^n$ according to the initial state probabilities.

First the one-step distribution $\alpha P = (0.5,0.5)\begin{pmatrix} 0.7 & 0.3 \\ 0.4 & 0.6 \end{pmatrix} = (0.55,\,0.45)$. Then $X_2$: $(0.55,0.45)P = \big(0.55(0.7)+0.45(0.4),\ 0.55(0.3)+0.45(0.6)\big)$ $=(0.385+0.180,\ 0.165+0.270)=(0.565,\,0.435)$. Equivalently $\alpha P^2 = (0.5,0.5)\begin{pmatrix} 0.61 & 0.39 \\ 0.52 & 0.48 \end{pmatrix}=(0.565,0.435)$.

Start from $\alpha=(1,0)$ (Sunny today is row 1). $\alpha P = (0.8,0.2)$. $\alpha P^2 = (0.8,0.2)\begin{pmatrix} 0.8 & 0.2 \\ 0.5 & 0.5 \end{pmatrix}=(0.64+0.10,\ 0.16+0.10)=(0.74,0.26)$. $\alpha P^3 = (0.74,0.26)\begin{pmatrix} 0.8 & 0.2 \\ 0.5 & 0.5 \end{pmatrix}=(0.592+0.130,\ 0.148+0.130)=(0.722,0.278)$. So $\Pr(X_3=S)=0.722$.

Start $\alpha=(1,0,0)$. Year 1: $\alpha P = (0.2,\,0.8,\,0)$ — row 1 of $P$. Year 2: $(0.2,0.8,0)P$: Level $0\%$: $0.2(0.2)+0.8(0.1)+0(0)=0.04+0.08=0.12$. Level $20\%$: $0.2(0.8)+0.8(0)+0(0.1)=0.16$. Level $40\%$: $0.2(0)+0.8(0.9)+0(0.9)=0.72$. Distribution after $2$ years: $(0.12,\,0.16,\,0.72)$, summing to $1$.

By the Markov property the joint probability factors into one-step transitions: $\Pr(X_0=i_0,X_1=i_1,\dots,X_n=i_n)=\alpha_{i_0}\,P_{i_0 i_1}\,P_{i_1 i_2}\cdots P_{i_{n-1} i_n}$. Multiply the initial probability by each successive one-step transition along the path. For example, with $\alpha_{i_0}=1$, $\Pr(\text{path } 1\to 2\to 2 \mid X_0=1)=P_{12}\,P_{22}$.

The path is $S\to R\to R$ with $X_0=S$ given (probability $1$). $\Pr = P_{SR}\cdot P_{RR}=0.2 \times 0.5 = 0.10$. Multiply the one-step probabilities along the path; there is no sum because we fixed the entire sequence rather than just the endpoint.

State $j$ is **accessible** from $i$ (written $i\to j$) if $(P^n)_{ij}>0$ for some $n\ge 0$ — the chain can reach $j$ from $i$ in finitely many steps. States $i$ and $j$ **communicate** ($i\leftrightarrow j$) if each is accessible from the other. Communication is an **equivalence relation** (reflexive, symmetric, transitive), so it partitions the state space into **communicating classes**.

A chain is **irreducible** if all states communicate — there is a single communicating class, so every state can reach every other. A communicating class $C$ is **closed** if no state outside $C$ is accessible from inside $C$ (once the chain enters $C$ it never leaves). A single state $i$ with $P_{ii}=1$ is an **absorbing** state — a closed class by itself.

Let $f_i$ be the probability that, starting in $i$, the chain ever returns to $i$. **Recurrent:** $f_i=1$ — return is certain, so $i$ is visited infinitely often and the expected number of visits is infinite. **Transient:** $f_i<1$ — there is positive probability of never returning, the number of visits is geometric with finite mean $\frac{1}{1-f_i}$. In a **finite** chain, recurrence/transience is a class property: every state in a class is of the same type, and at least one class is recurrent.

In a finite Markov chain: - States in a **closed** communicating class are **recurrent**. - States in a class that is **not closed** (the chain can leave and not come back) are **transient**. Every finite chain has at least one closed class, so recurrent states always exist. Absorbing states (closed singletons) are recurrent; states that can reach an absorbing state but cannot be re-entered are transient.

From the nonzero entries: - $1\leftrightarrow 2$ and $\{1,2\}$ is **closed** (rows 1,2 have no mass on $3,4$) → class $\{1,2\}$ is **recurrent**. - State $4$ reaches $1$ (and $3$); state $3$ reaches $4$; so $3\leftrightarrow 4$. But from $4$ the chain can leave to $\{1,2\}$ and never return, so class $\{3,4\}$ is **not closed** → **transient**. Thus $\{1,2\}$ recurrent, $\{3,4\}$ transient.

$d(i)=\gcd\{\,n\ge 1 : (P^n)_{ii}>0\,\}$ — the greatest common divisor of the step-counts at which return to $i$ is possible. A state is **aperiodic** if $d(i)=1$ (e.g. any state with $P_{ii}>0$ is automatically aperiodic). Period is a class property: all communicating states share the same period. A chain is aperiodic if every state has period $1$.

From state $1$ the chain goes $1\to 2\to 3\to 1$, returning only after $3,6,9,\dots$ steps, so $(P^n)_{11}>0$ exactly when $n$ is a multiple of $3$. $d(1)=\gcd\{3,6,9,\dots\}=3$. By symmetry $d(2)=d(3)=3$. The chain is irreducible with **period $3$** (periodic, not aperiodic), so a single limiting distribution does not exist even though a stationary distribution does.

A row vector $\pi=(\pi_1,\pi_2,\dots)$ is **stationary** if it is unchanged by one transition: $\pi = \pi P$, with $\pi_j\ge 0$ and the normalization $\sum_i \pi_i = 1$. If the chain starts with distribution $\pi$, then $X_n\sim\pi$ for every $n$. The component equations are $\pi_j=\sum_i \pi_i P_{ij}$ for each $j$, plus the normalizing constraint.

For an **irreducible, aperiodic** (ergodic) finite chain there is a unique stationary $\pi$ and $\lim_{n\to\infty}(P^n)_{ij}=\pi_j$ for every starting state $i$ — the long-run fraction of time spent in $j$, independent of where you start. The **mean recurrence time** (expected number of steps to return to $j$) is $m_{jj}=\frac{1}{\pi_j}$. If the chain is periodic, $\pi$ still exists as the long-run time-average but $(P^n)_{ij}$ need not converge.

Write $\pi=(\pi_1,\pi_2)$ with $\pi=\pi P$ and $\pi_1+\pi_2=1$. First component: $\pi_1 = 0.7\pi_1 + 0.4\pi_2 \Rightarrow 0.3\pi_1 = 0.4\pi_2 \Rightarrow \pi_1=\tfrac{4}{3}\pi_2$. Normalize: $\tfrac{4}{3}\pi_2 + \pi_2 = 1 \Rightarrow \tfrac{7}{3}\pi_2=1 \Rightarrow \pi_2=\tfrac{3}{7}$, $\pi_1=\tfrac{4}{7}$. So $\pi=\left(\tfrac{4}{7},\tfrac{3}{7}\right)\approx(0.5714,\,0.4286)$.

The expected number of steps to return to a state is the reciprocal of its stationary probability: $m_{11}=\frac{1}{\pi_1}=\frac{1}{4/7}=\frac{7}{4}=1.75$ steps. $m_{22}=\frac{1}{\pi_2}=\frac{1}{3/7}=\frac{7}{3}\approx 2.33$ steps. State $1$, being visited more often in the long run, returns to itself sooner on average.

$\pi=\pi P$ with $\pi_S+\pi_R=1$. $\pi_S = 0.8\pi_S + 0.5\pi_R \Rightarrow 0.2\pi_S=0.5\pi_R \Rightarrow \pi_S=2.5\pi_R$. Normalize: $2.5\pi_R+\pi_R=1 \Rightarrow 3.5\pi_R=1 \Rightarrow \pi_R=\frac{1}{3.5}=\frac{2}{7}\approx 0.2857$, $\pi_S=\frac{5}{7}\approx 0.7143$. Long-run, about $28.6\%$ of days are rainy.

Solve $\pi=\pi P$ (column equations) with $\pi_3=1-\pi_1-\pi_2$. State $1$: $\pi_1=0.5\pi_1+0.1\pi_2+0.2\pi_3$. Substitute $\pi_3=1-\pi_1-\pi_2$: $0.5\pi_1-0.1\pi_2-0.2(1-\pi_1-\pi_2)=0 \Rightarrow 0.7\pi_1+0.1\pi_2=0.2$. State $2$: $\pi_2=0.3\pi_1+0.6\pi_2+0.3\pi_3$. Substitute: $-0.3\pi_1+0.4\pi_2-0.3(1-\pi_1-\pi_2)=0 \Rightarrow 0.7\pi_2=0.3 \Rightarrow \pi_2=\tfrac{3}{7}\approx 0.4286$. Back into the first: $0.7\pi_1=0.2-0.1(0.4286)=0.15714 \Rightarrow \pi_1\approx 0.2245$. $\pi_3=1-0.2245-0.4286\approx 0.3469$. So $\pi\approx(0.2245,\,0.4286,\,0.3469)$.

Solve $\pi=\pi P$, $\pi_1+\pi_2+\pi_3=1$ (states $1,2,3$ = $0\%,20\%,40\%$). Col 1: $\pi_1=0.2\pi_1+0.1\pi_2 \Rightarrow 0.8\pi_1=0.1\pi_2 \Rightarrow \pi_2=8\pi_1$. Col 3: $\pi_3=0.9\pi_2+0.9\pi_3 \Rightarrow 0.1\pi_3=0.9\pi_2 \Rightarrow \pi_3=9\pi_2=72\pi_1$. Normalize: $\pi_1(1+8+72)=1 \Rightarrow 81\pi_1=1 \Rightarrow \pi_1=\tfrac{1}{81}\approx 0.0123$. $\pi_2=\tfrac{8}{81}\approx 0.0988$, $\pi_3=\tfrac{72}{81}=\tfrac{8}{9}\approx 0.8889$. Long-run, about $88.9\%$ of policyholders sit at the $40\%$ discount.

Take the $\pi$-weighted average of the discount levels: $E[\text{discount}]=\tfrac{1}{81}(0\%)+\tfrac{8}{81}(20\%)+\tfrac{8}{9}(40\%)$. $=0 + \tfrac{8}{81}(20)+\tfrac{72}{81}(40)=\tfrac{160}{81}+\tfrac{2880}{81}=\tfrac{3040}{81}\approx 37.5\%$. So in steady state the average policyholder enjoys about a $37.5\%$ no-claims discount.

Reorder states so absorbing states come first and transient states last: $P = \begin{pmatrix} I & 0 \\ R & Q \end{pmatrix}$. - $I$ — identity block: absorbing states stay put. - $0$ — absorbing states never move to transient states. - $Q$ — transient-to-transient transition probabilities. - $R$ — transient-to-absorbing transition probabilities. The interesting dynamics live in $Q$ and $R$.

$N=(I-Q)^{-1}=I+Q+Q^2+\cdots$. The entry $N_{ij}$ is the **expected number of visits** to transient state $j$, starting from transient state $i$, before absorption (counting the initial occupation when $i=j$). The series converges because $Q^n\to 0$ — from any transient state absorption is eventually certain.

**Expected time to absorption** from transient state $i$: the $i$-th row sum of $N$, $t_i=\sum_j N_{ij}$, i.e. $t=N\mathbf{1}$ where $\mathbf{1}$ is a column of ones. **Absorption probabilities:** $B=NR$, where $B_{ik}$ is the probability of being absorbed in absorbing state $k$ starting from transient state $i$. Each row of $B$ sums to $1$.

$I-Q=\begin{pmatrix} 0.6 & -0.3 \\ -0.2 & 0.5 \end{pmatrix}$. Determinant $=0.6(0.5)-(-0.3)(-0.2)=0.30-0.06=0.24$. Inverse $=\frac{1}{0.24}\begin{pmatrix} 0.5 & 0.3 \\ 0.2 & 0.6 \end{pmatrix}$. $N=\begin{pmatrix} 0.5/0.24 & 0.3/0.24 \\ 0.2/0.24 & 0.6/0.24 \end{pmatrix}=\begin{pmatrix} 2.0833 & 1.25 \\ 0.8333 & 2.5 \end{pmatrix}$.

Expected time to absorption is the row sum of $N$: From state $1$: $t_1=2.0833+1.25=3.3333$ steps. From state $2$: $t_2=0.8333+2.5=3.3333$ steps. So regardless of whether you start in transient state $1$ or $2$, the expected number of steps until absorption in state $3$ is about $3.33$.

With one absorbing state, every transient start is absorbed there with probability $1$, so $B$ should be a column of ones. $B=NR=\begin{pmatrix} 2.0833 & 1.25 \\ 0.8333 & 2.5 \end{pmatrix}\begin{pmatrix} 0.3 \\ 0.3 \end{pmatrix}$. Row 1: $2.0833(0.3)+1.25(0.3)=0.625+0.375=1.0$. Row 2: $0.8333(0.3)+2.5(0.3)=0.25+0.75=1.0$. $B=\begin{pmatrix} 1 \\ 1 \end{pmatrix}$ — absorption is certain, as expected.

$I-Q=\begin{pmatrix} 1 & -0.5 \\ -0.5 & 1 \end{pmatrix}$. Determinant $=1(1)-(-0.5)(-0.5)=1-0.25=0.75$. $N=(I-Q)^{-1}=\frac{1}{0.75}\begin{pmatrix} 1 & 0.5 \\ 0.5 & 1 \end{pmatrix}=\begin{pmatrix} 1.3333 & 0.6667 \\ 0.6667 & 1.3333 \end{pmatrix}$. This is the expected-visits matrix for the symmetric random walk on $\{1,2\}$ with absorbing barriers at $0$ and $3$.

$B=NR=\begin{pmatrix} 1.3333 & 0.6667 \\ 0.6667 & 1.3333 \end{pmatrix}\begin{pmatrix} 0.5 & 0 \\ 0 & 0.5 \end{pmatrix}=\begin{pmatrix} 0.6667 & 0.3333 \\ 0.3333 & 0.6667 \end{pmatrix}$. Starting in state $1$: absorbed at $0$ with prob $\tfrac{2}{3}$, at $3$ with prob $\tfrac{1}{3}$. Starting in state $2$: at $0$ with prob $\tfrac{1}{3}$, at $3$ with prob $\tfrac{2}{3}$. Each row sums to $1$ — you reach the nearer barrier more often, the classic gambler's-ruin pattern.

For a symmetric random walk on $\{0,1,\dots,N\}$ with absorbing barriers at $0$ and $N$ ($p=q=\tfrac12$), the probability of reaching $N$ (winning) starting from $i$ is $\Pr(\text{reach }N \mid i)=\frac{i}{N}$. Gambler with $\$2$, target $N=5$: $\Pr(\text{win})=\frac{2}{5}=0.4$, and $\Pr(\text{ruin})=1-0.4=0.6$. The linear formula matches the $NR$ computation for the absorbing chain.

For the symmetric walk on $\{0,\dots,N\}$ ($p=q=\tfrac12$), the expected number of steps to absorption starting from $i$ is $E[\text{duration} \mid i]=i(N-i)$. With $i=2$, $N=5$: $E=2(5-2)=2\cdot 3 = 6$ steps. This equals the row sum of the fundamental matrix $N$ for the corresponding $4\times 4$ transient block.

From each interior state the walk moves $\pm 1$ with probability $\tfrac12$. Order transient states $1,2,3$; absorbing $0$ and $4$. $Q=\begin{pmatrix} 0 & 0.5 & 0 \\ 0.5 & 0 & 0.5 \\ 0 & 0.5 & 0 \end{pmatrix}$ (transient $\to$ transient). $R=\begin{pmatrix} 0.5 & 0 \\ 0 & 0 \\ 0 & 0.5 \end{pmatrix}$ (columns = absorb at $0$, at $4$); only states $1$ and $3$ can step directly to a barrier.

$I-Q=\begin{pmatrix} 1 & -0.5 & 0 \\ -0.5 & 1 & -0.5 \\ 0 & -0.5 & 1 \end{pmatrix}$, $\det = 1(1-0.25)-(-0.5)(-0.5)= 0.75-0.25=0.5$. Inverting (tridiagonal) gives $N=\begin{pmatrix} 1.5 & 1.0 & 0.5 \\ 1.0 & 2.0 & 1.0 \\ 0.5 & 1.0 & 1.5 \end{pmatrix}$. Check: row sums $=3,4,3$, matching expected durations $i(N-i)=1\cdot 3,\,2\cdot 2,\,3\cdot 1 = 3,4,3$ from states $1,2,3$.

$B=NR$; the first column gives absorption at $0$. From state $1$: $1.5(0.5)+1.0(0)+0.5(0)=0.75$. From state $2$: $1.0(0.5)+2.0(0)+1.0(0)=0.50$. From state $3$: $0.5(0.5)+1.0(0)+1.5(0)=0.25$. Ruin probabilities $\left(\tfrac34,\tfrac12,\tfrac14\right)$ match $\frac{N-i}{N}=\frac{4-i}{4}$ for $i=1,2,3$.

$I-Q=\begin{pmatrix} 0.5 & -0.3 \\ -0.2 & 0.4 \end{pmatrix}$, $\det=0.5(0.4)-(-0.3)(-0.2)=0.20-0.06=0.14$. $N=\frac{1}{0.14}\begin{pmatrix} 0.4 & 0.3 \\ 0.2 & 0.5 \end{pmatrix}=\begin{pmatrix} 2.857 & 2.143 \\ 1.429 & 3.571 \end{pmatrix}$. Expected active years from $A$ = row-1 sum $=2.857+2.143=5.0$ years. (From $B$ it is $1.429+3.571=5.0$ years as well.)

The expected number of visits to transient state $B$ starting from $A$ is the entry $N_{AB}$. $N_{AB}=2.143$ years. The diagonal entry $N_{AA}=2.857$ is the expected time spent in $A$ itself, so of the $5.0$ total active years, about $2.86$ are spent in $A$ and $2.14$ in $B$.

For an absorbing chain every transient state reaches absorption with positive probability, so the spectral radius of $Q$ is $<1$ and $Q^n\to 0$; the Neumann series therefore converges to $(I-Q)^{-1}$. Interpretation: $(Q^n)_{ij}$ is the probability of being in transient state $j$ exactly $n$ steps after starting in $i$ (still un-absorbed). Summing over $n=0,1,2,\dots$ gives the **expected number of visits** to $j$, which is precisely $N_{ij}$.

**Stationary distribution $\pi=\pi P$:** used for an irreducible chain that keeps moving forever; it gives long-run time fractions, limiting probabilities (if aperiodic), and mean recurrence times $1/\pi_j$. **Fundamental matrix $N=(I-Q)^{-1}$:** used when the chain has absorbing states; it answers "how long until absorption" (row sums of $N$), "expected visits before absorption" ($N_{ij}$), and "which absorbing state" ($B=NR$). A chain with absorbing states has no positive stationary distribution over the transient states — eventually all probability mass collapses onto the absorbing states.