Markov chain Study Guide

📖 Core Concepts Markov property (memorylessness) – Future state depends only on the present state, not on the past. State space – The set of all possible states; can be finite, countably infinite, or uncountable. Transition matrix \(P\) – For discrete‑time chains, \(p{ij}=P(X{n+1}=j\mid Xn=i)\). Rows sum to 1 (right‑stochastic). Transition rate matrix \(Q\) – For continuous‑time chains, off‑diagonal \(q{ij}\ge0\) are instantaneous rates; rows sum to 0 because \(q{ii}= -\sum{j\neq i}q{ij}\). Stationary distribution \(\pi\) – A row vector with non‑negative entries, \(\sumi\pii=1\), satisfying \(\pi P=\pi\). It is a left eigenvector of \(P\) with eigenvalue 1. Irreducibility – Every state can reach every other state (single communicating class). Periodicity – The greatest common divisor of all return‑path lengths; period 1 ⇒ aperiodic. Recurrence vs. transience – Recurrent: return probability = 1; transient: < 1. Positive recurrent ⇒ finite expected return time; null recurrent ⇒ infinite. Ergodic state/chain – Aperiodic and positive recurrent. Guarantees convergence to \(\pi\). Embedded (jump) chain – Discrete‑time chain that records the sequence of states visited at each jump of a continuous‑time chain. --- 📌 Must Remember Markov property formula: \[ P(X{n+1}=j\mid Xn=i,\dots)=P(X{n+1}=j\mid Xn=i) \] Stationarity condition: \(\displaystyle \pi P = \pi\) (and \(\sumi \pii = 1\)). Irreducible + aperiodic + finite ⇒ unique stationary distribution (Perron–Frobenius). Convergence rate: \(\displaystyle \|P^n - \mathbf{1}\pi\| \approx \left|\frac{\lambda2}{\lambda1}\right|^{\,n}\) where \(\lambda1=1\). Continuous‑time infinitesimal probabilities: \[ P(X{t+h}=j\mid Xt=i)=q{ij}h+o(h),\; i\neq j \] \[ P(X{t+h}=i\mid Xt=i)=1-\Bigl(\sum{j\neq i}q{ij}\Bigr)h+o(h) \] Kolmogorov forward equation: \(\displaystyle \frac{dP(t)}{dt}=P(t)Q = QP(t),\; P(0)=I\). Detailed balance (reversibility): \(\pii p{ij} = \pij p{ji}\) for all \(i,j\). Absorbing state – Once entered, probability of leaving is 0 (row of \(P\) is a unit vector). --- 🔄 Key Processes Finding the stationary distribution (discrete‑time) Write \(\pi P = \pi\) → system of linear equations. Add normalization \(\sumi \pii = 1\). Solve (Gaussian elimination or eigen‑method). Checking irreducibility & periodicity Build directed graph of positive \(p{ij}\). Use BFS/DFS to see if every node reachable from every other (irreducible). Compute \(\gcd\) of lengths of cycles returning to a state → period. Continuous‑time to embedded chain Compute transition probabilities of jump chain: \(s{ij}= \dfrac{q{ij}}{-q{ii}}\) for \(i\neq j\). Find stationary distribution of \(S\) (solve \(\pi S = \pi\)). Normalize to obtain stationary distribution of the CTMC. Solving hitting‑time expectations For target set \(A\): set \(ki=0\) for \(i\in A\). For \(i\notin A\): solve \(ki = 1 + \sumj p{ij}kj\). PageRank computation (simplified) Build transition matrix from link structure, add damping factor \(d\). Solve \(\pi = d\pi P + (1-d)v\) where \(v\) is the teleport vector (usually uniform). --- 🔍 Key Comparisons Discrete‑time vs. Continuous‑time Time parameter: steps vs. real time. Matrix: transition matrix \(P\) (probabilities) vs. rate matrix \(Q\) (rates). Row sums: \(P\) rows = 1; \(Q\) rows = 0. Stationary vs. Ergodic Stationary: any \(\pi\) satisfying \(\pi P = \pi\). Ergodic: stationary and chain is aperiodic + positive recurrent → convergence to \(\pi\). Positive recurrent vs. Null recurrent Positive: finite expected return time → stationary distribution exists. Null: infinite expected return time → no normalizable stationary distribution. Absorbing vs. Transient state Absorbing: \(p{ii}=1\), never leaves once entered. Transient: probability of ever returning < 1. Reversible vs. Non‑reversible Reversible: detailed balance holds; chain looks the same forward/backward. Non‑reversible: detailed balance fails; often faster mixing but harder to analyze. --- ⚠️ Common Misunderstandings “All stationary distributions are unique.” – Uniqueness requires irreducibility and aperiodicity (finite state space). “A row‑stochastic matrix automatically yields convergence.” – Need aperiodicity and irreducibility; periodic chains oscillate. “The rate matrix \(Q\) gives probabilities directly.” – \(Q\) contains rates; probabilities are obtained via the matrix exponential \(P(t)=e^{Qt}\) or solving Kolmogorov equations. “If a state is recurrent, it must be positive recurrent.” – Not true for infinite state spaces; null recurrence is possible. “Embedding a CTMC always preserves the stationary distribution.” – You must normalize after solving \(\pi S = \pi\); the CTMC’s stationary distribution differs by the holding‑time rates. --- 🧠 Mental Models / Intuition “Memoryless” as a “forgetful” friend – The chain only cares who you are now, never your past history. Transition matrix as a “one‑step lottery” – Each row lists the odds of the next draw given the current ticket. Ergodic chain as a “well‑mixed blender” – After enough shaking (steps), every ingredient (state) appears in the same proportion (\(\pi\)). Rate matrix as “speed limits” on roads – Off‑diagonal entries tell how fast you can jump from one city to another; the diagonal is the “stay‑still” penalty ensuring total out‑flow balances. Periodic chain as a “clock” – It cycles with a fixed period; you only see certain states at multiples of that period. --- 🚩 Exceptions & Edge Cases Infinite state spaces – Perron–Frobenius may not guarantee a unique stationary distribution; null recurrence can appear. Periodic irreducible chains – Still have a stationary distribution, but \(P^n\) does not converge to a single matrix; it cycles. Non‑time‑homogeneous chains – Transition matrix varies with step; \(P^k\) no longer equals the \(k\)-step matrix. Absorbing chains with multiple absorbing states – Long‑run distribution concentrates on the absorbing class reached, not on a single \(\pi\). --- 📍 When to Use Which Discrete‑time analysis – Use when the process naturally proceeds in fixed steps (board games, daily stock ratings). Continuous‑time analysis – Use for events occurring at random real‑time intervals (chemical reactions, queue arrivals). Stationary distribution calculation – Prefer eigenvector method for small/finite chains; use power iteration for large sparse matrices (e.g., PageRank). Embedded chain – Use to simplify CTMC problems (e.g., find long‑run probabilities) when holding times are exponential. Detailed balance test – Use to quickly verify reversibility; if it holds, many calculations (e.g., Metropolis‑Hastings acceptance) simplify. Kolmogorov forward equation – Use when you need the full time‑dependent transition matrix \(P(t)\) for CTMCs. --- 👀 Patterns to Recognize Rows summing to 1 → discrete‑time transition matrix; rows summing to 0 → rate matrix. Zero diagonal entries in \(P\) with a 1 on the diagonal → absorbing state. Repeated block structure in \(P\) → possible communicating classes. Eigenvalue 1 appearing exactly once → irreducible, aperiodic finite chain (unique \(\pi\)). GCD of cycle lengths > 1 → periodic chain → expect oscillating probabilities. Symmetric \(P\) with positive entries → often reversible (detailed balance holds automatically). --- 🗂️ Exam Traps Choosing “stationary” vs. “ergodic” – A question may ask for convergence; the correct answer requires both aperiodicity and irreducibility, not just stationarity. Misreading a rate matrix as a transition matrix – Selecting probabilities from \(Q\) leads to values > 1 or negative; remember rows of \(Q\) sum to 0. Assuming any recurrent state has a stationary probability – In infinite state spaces, null recurrent states have no normalizable \(\pi\). Periodicity ignored – A periodic chain can have a stationary distribution, but powers of \(P\) do not converge; answer choices that claim convergence for a periodic chain are wrong. Confusing embedded chain transition probabilities \(s{ij}\) with original rates \(q{ij}\) – \(s{ij}=q{ij}/(-q{ii})\), not simply \(q{ij}\). PageRank damping factor mis‑application – Forgetting the teleport term \((1-d)v\) yields a non‑stochastic matrix; exam may include a choice missing this term. ---