Mathematical Sciences / Markov Chains and Stochastic Processes
/ Topic 4 of 4 · 4/4 Markov Chains and Stochastic Processes Formula Sheet and Short Notes One-page CSIR NET revision: Markov chain classes, recurrence, period, absorption, stationary distributions, limits of P^n, Poisson and birth-death processes.
8 min read Updated 16 Nov 2026
Share
Copy link
Print · PDF
Save Share this topic
csirnetnotes.com/mathematical-sciences/markov-chains-stochastic-processes/quick-revision
Copy link Ctrl C Pre-written message Markov Chains and Stochastic Processes Formula Sheet and Short Notes — notes, formulas and practice, free. csirnetnotes.com/mathematical-sciences/markov-chains-stochastic-processes/quick-revision
On this page · 9 sections▾ The paper in one table Discrete-time chains: the basics Classification of states Absorption and gambler’s ruin Stationary distributions and limits Poisson process Continuous-time chains and birth-and-death processes Counter-examples for Part C Where to go next Every definition, formula and counter-example from Markov Chains and Classification of States , n-Step Transition Limits and Stationary Distributions and Poisson and Birth-and-Death Processes , on one page.
The paper in one table Per the NTA information bulletin for December 2026 (Mathematical Sciences, code 704):
Part Given Attempt Correct Wrong Maximum B 40 25 +3 −0.75 75 C 60 20 +4.75 0 95
Part C: one or more options may be correct; marks only if you mark all correct options and no wrong one. No partial credit, no negative marking. Details on the Mathematical Sciences overview .
Discrete-time chains: the basics Object Fact Markov property \( P(X_{n+1} = j \mid X_n = i, \text{past}) = p_{ij} \) Transition matrix stochastic: \( p_{ij} \ge 0 \), rows sum to 1; eigenvalue 1 with right eigenvector \( \mathbf{1} \); all \( \lvert \lambda \rvert \le 1 \) Chapman–Kolmogorov \( p_{ij}^{(m+n)} = \sum_k p_{ik}^{(m)}p_{kj}^{(n)} \); \( P^{(n)} = P^n \) Distribution at time \( n \) \( \mu^{(n)} = \mu^{(0)}P^n \) (row vector on the left) Path probability \( \mu_{i_0}p_{i_0i_1}\cdots p_{i_{n-1}i_n} \)
Classification of states Concept Definition / test \( i \to j \) \( p_{ij}^{(n)} > 0 \) for some \( n \ge 0 \) (only the positive pattern matters) Class communicating states; strongly connected component of the graph Closed class no arrow leaves it; absorbing state: \( p_{ii} = 1 \) Irreducible one class Recurrent \( f_{ii} = 1 \iff \sum_n p_{ii}^{(n)} = \infty \iff \) infinitely many returns a.s. Transient \( \sum_{n \ge 1}p_{ii}^{(n)} = \frac{f_{ii}}{1 - f_{ii}} < \infty \) Positive / null recurrent \( \mu_i = E_i[T_i] < \infty \) / \( = \infty \) Period \( d(i) = \gcd\{n \ge 1 : p_{ii}^{(n)} > 0\} \); self-loop \( \Rightarrow d = 1 \) Class properties recurrence, transience, positive/null recurrence, period
Finite chains: closed class \( \iff \) recurrent, always positive recurrent; at least one recurrent state; no null recurrent states.
Random walks:
Walk Type \( \mathbb{Z} \), \( p = \frac12 \) null recurrent, period 2 \( \mathbb{Z} \), \( p \ne \frac12 \) transient, \( f_{00} = 1 - \lvert p - q \rvert \) \( \mathbb{Z}^2 \), symmetric null recurrent \( \mathbb{Z}^d \), \( d \ge 3 \), symmetric transient \( p_{00}^{(2n)} \) on \( \mathbb{Z} \) \( \binom{2n}{n}(pq)^n \sim \frac{(4pq)^n}{\sqrt{\pi n}} \)
Absorption and gambler’s ruin $$h_i = \sum_j p_{ij}h_j \ (i \notin A), \quad h = 1 \text{ on } A; \qquad k_i = 1 + \sum_j p_{ij}k_j \ (i \notin A), \quad k = 0 \text{ on } A.$$$$P = \begin{pmatrix} Q & R \\ 0 & I \end{pmatrix}: \qquad N = (I - Q)^{-1}, \quad B = NR, \quad t = N\mathbf{1}.$$
Gambler’s ruin (start \( i \), stop at 0 or \( N \)) Value \( P(\text{reach } N) \), \( p \ne q \), \( r = \frac{q}{p} \) \( \frac{1 - r^i}{1 - r^N} \) \( P(\text{reach } N) \), fair \( \frac{i}{N} \) expected duration, fair \( i(N - i) \) ruin against infinite target 1 if \( p \le \frac12 \); \( \left(\frac{q}{p}\right)^i \) if \( p > \frac12 \)
Stationary distributions and limits Fact Statement Definition \( \pi P = \pi \), \( \pi \ge 0 \), \( \sum \pi_j = 1 \) Irreducible chain \( \pi \) exists \( \iff \) positive recurrent; unique; \( \pi_j = \frac{1}{\mu_j} \) Finite chain at least one; unique \( \iff \) exactly one closed class; \( \pi_j = 0 \) on transient states Eigenvalue 1 algebraic multiplicity = number of closed classes Period \( d \), irreducible eigenvalues of modulus 1 are the \( d \)-th roots of unity Convergence irreducible + aperiodic + positive recurrent \( \Rightarrow p_{ij}^{(n)} \to \pi_j \) Periodic no limit; \( p_{jj}^{(nd)} \to d\pi_j \); Cesàro averages \( \to \pi_j \) Transient or null \( j \) \( p_{ij}^{(n)} \to 0 \) Reducible \( p_{ij}^{(n)} \to h_i(C)\pi_j \), \( j \) in aperiodic closed class \( C \) Ergodic theorem fraction of time in \( j \) \( \to \pi_j \) a.s.
Shortcuts for \( \pi \):
Chain \( \pi \) \( \begin{pmatrix} 1 - a & a \\ b & 1 - b \end{pmatrix} \) \( \left(\frac{b}{a + b}, \frac{a}{a + b}\right) \); \( P^n \) error \( \propto (1 - a - b)^n \) doubly stochastic, irreducible, \( m \) states uniform \( \frac1m \) random walk on a graph \( \frac{\deg v}{2\lvert E \rvert} \); return time \( \frac{2\lvert E \rvert}{\deg v} \) birth–death chain \( \pi_n = \pi_0\prod_{k=1}^{n}\frac{p_{k-1}}{q_k} \) reflecting walk, \( r = \frac{p}{q} < 1 \) \( (1 - r)r^n \) Ehrenfest, \( N \) balls \( \text{Bin}(N, \frac12) \); period 2; \( \mu_0 = 2^N \)
Detailed balance \( \pi_ip_{ij} = \pi_jp_{ji} \Rightarrow \) stationary (sufficient, not necessary).
$$P^n = \frac{1}{a + b}\begin{pmatrix} b & a \\ b & a \end{pmatrix} + \frac{(1 - a - b)^n}{a + b}\begin{pmatrix} a & -a \\ -b & b \end{pmatrix}$$
Poisson process Quantity Value \( N(t) \) \( \text{Poisson}(\lambda t) \); mean = variance = \( \lambda t \) \( \operatorname{Cov}(N(s), N(t)) \) \( \lambda\min(s, t) \) gaps i.i.d. \( \text{Exp}(\lambda) \), memoryless \( S_n \) \( \text{Gamma}(n, \lambda) \), mean \( \frac{n}{\lambda} \), variance \( \frac{n}{\lambda^2} \) duality \( P(S_n \le t) = P(N(t) \ge n) \) given \( N(t) = n \) arrivals = uniform order statistics; \( N(s) \sim \text{Bin}(n, \frac{s}{t}) \) superposition rates add; first event from stream 1 w.p. \( \frac{\lambda_1}{\lambda_1 + \lambda_2} \) thinning with \( p \) independent Poisson\( (\lambda p) \) and Poisson\( (\lambda(1 - p)) \) compound Poisson mean \( \lambda tE[Y] \), variance \( \lambda tE[Y^2] \) non-homogeneous \( N(t) - N(s) \sim \text{Poisson}\left(\int_s^t\lambda(u)\,du\right) \)
Continuous-time chains and birth-and-death processes Object Fact Generator \( Q \) \( q_{ij} \ge 0 \) off the diagonal, rows sum to 0; holding time in \( i \) is \( \text{Exp}(q_i) \) Kolmogorov backward \( P'(t) = QP(t) \), forward \( P'(t) = P(t)Q \), \( P(t) = e^{tQ} \) Stationary \( \pi Q = 0 \); no periodicity in continuous time Jump chain stationary law \( \propto \pi_iq_i \) Two-state \( (\alpha, \beta) \) \( p_{00}(t) = \frac{\beta}{\alpha + \beta} + \frac{\alpha}{\alpha + \beta}e^{-(\alpha + \beta)t} \) Birth–death \( \pi \) \( \pi_n = \pi_0\prod_{k=1}^{n}\frac{\lambda_{k-1}}{\mu_k} \), exists iff the sum of products is finite Forward equation \( p_n' = \lambda_{n-1}p_{n-1} - (\lambda_n + \mu_n)p_n + \mu_{n+1}p_{n+1} \) Explosion (pure birth) iff \( \sum \frac{1}{\lambda_n} < \infty \)
Model Result Yule (\( n\lambda \)), from 1 \( P(X(t) = n) = e^{-\lambda t}(1 - e^{-\lambda t})^{n-1} \), mean \( e^{\lambda t} \) Linear death (\( n\mu \)), from \( N \) \( \text{Bin}(N, e^{-\mu t}) \) Linear birth–death mean \( X(0)e^{(\lambda - \mu)t} \); extinction 1 if \( \lambda \le \mu \), else \( \left(\frac{\mu}{\lambda}\right)^{X(0)} \) M/M/1, \( \rho = \frac{\lambda}{\mu} < 1 \) \( \pi_n = (1 - \rho)\rho^n \); \( L = \frac{\rho}{1 - \rho} \); \( L_q = \frac{\rho^2}{1 - \rho} \); \( W = \frac{1}{\mu - \lambda} \); \( W_q = \frac{\rho}{\mu - \lambda} \) M/M/\( \infty \) Poisson\( \left(\frac{\lambda}{\mu}\right) \) for all rates M/M/\( c \) stable iff \( \lambda < c\mu \) M/M/1/\( K \) \( \pi_n \propto \rho^n \), \( 0 \le n \le K \) Little’s law \( L = \lambda W \), \( L_q = \lambda W_q \), \( W = W_q + \frac1\mu \)
Counter-examples for Part C Tempting claim Breaks on irreducible \( \Rightarrow \) recurrent random walk on \( \mathbb{Z} \) with \( p = 0.6 \); symmetric walk on \( \mathbb{Z}^3 \) recurrent \( \Rightarrow \) positive recurrent symmetric walk on \( \mathbb{Z} \) irreducible finite \( \Rightarrow P^n \) converges \( \begin{pmatrix} 0 & 1 \\ 1 & 0 \end{pmatrix} \) unique \( \pi \Rightarrow \) irreducible any chain with transient states and one closed class stationary \( \Rightarrow \) detailed balance deterministic 3-cycle period = shortest return time returns in 2 and 3 steps give period 1 transient states are aperiodic transient pair \( 3 \leftrightarrow 4 \) with no self-loops: period 2 \( p_{jj}^{(n)} \to 0 \Rightarrow j \) transient symmetric walk on \( \mathbb{Z} \) (null recurrent) \( \pi \) of CTMC = \( \pi \) of its jump chain two-state chain with \( \alpha \ne \beta \): jump chain has \( \left(\frac12, \frac12\right) \) growing mean \( \Rightarrow \) survival linear birth–death with \( \lambda > \mu \): extinction probability \( \frac{\mu}{\lambda} \) \( N(1) \), \( N(3) \) independent covariance \( \lambda \) M/M/1 has a steady state for \( \lambda = \mu \) null recurrent, no \( \pi \)
Where to go next Advertisement Advertisement