Skip to content

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
On this page · 9 sections
  1. The paper in one table
  2. Discrete-time chains: the basics
  3. Classification of states
  4. Absorption and gambler’s ruin
  5. Stationary distributions and limits
  6. Poisson process
  7. Continuous-time chains and birth-and-death processes
  8. Counter-examples for Part C
  9. 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):

PartGivenAttemptCorrectWrongMaximum
B4025+3−0.7575
C6020+4.75095

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

ObjectFact
Markov property\( P(X_{n+1} = j \mid X_n = i, \text{past}) = p_{ij} \)
Transition matrixstochastic: \( 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

ConceptDefinition / test
\( i \to j \)\( p_{ij}^{(n)} > 0 \) for some \( n \ge 0 \) (only the positive pattern matters)
Classcommunicating states; strongly connected component of the graph
Closed classno arrow leaves it; absorbing state: \( p_{ii} = 1 \)
Irreducibleone 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 propertiesrecurrence, 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:

WalkType
\( \mathbb{Z} \), \( p = \frac12 \)null recurrent, period 2
\( \mathbb{Z} \), \( p \ne \frac12 \)transient, \( f_{00} = 1 - \lvert p - q \rvert \)
\( \mathbb{Z}^2 \), symmetricnull recurrent
\( \mathbb{Z}^d \), \( d \ge 3 \), symmetrictransient
\( 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 target1 if \( p \le \frac12 \); \( \left(\frac{q}{p}\right)^i \) if \( p > \frac12 \)

Stationary distributions and limits

FactStatement
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 chainat least one; unique \( \iff \) exactly one closed class; \( \pi_j = 0 \) on transient states
Eigenvalue 1algebraic multiplicity = number of closed classes
Period \( d \), irreducibleeigenvalues of modulus 1 are the \( d \)-th roots of unity
Convergenceirreducible + aperiodic + positive recurrent \( \Rightarrow p_{ij}^{(n)} \to \pi_j \)
Periodicno 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 theoremfraction 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 \) statesuniform \( \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

QuantityValue
\( N(t) \)\( \text{Poisson}(\lambda t) \); mean = variance = \( \lambda t \)
\( \operatorname{Cov}(N(s), N(t)) \)\( \lambda\min(s, t) \)
gapsi.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}) \)
superpositionrates 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 Poissonmean \( \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

ObjectFact
Generator \( Q \)\( q_{ij} \ge 0 \) off the diagonal, rows sum to 0; holding time in \( i \) is \( \text{Exp}(q_i) \)
Kolmogorovbackward \( P'(t) = QP(t) \), forward \( P'(t) = P(t)Q \), \( P(t) = e^{tQ} \)
Stationary\( \pi Q = 0 \); no periodicity in continuous time
Jump chainstationary 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 \)
ModelResult
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–deathmean \( 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 claimBreaks on
irreducible \( \Rightarrow \) recurrentrandom walk on \( \mathbb{Z} \) with \( p = 0.6 \); symmetric walk on \( \mathbb{Z}^3 \)
recurrent \( \Rightarrow \) positive recurrentsymmetric walk on \( \mathbb{Z} \)
irreducible finite \( \Rightarrow P^n \) converges\( \begin{pmatrix} 0 & 1 \\ 1 & 0 \end{pmatrix} \)
unique \( \pi \Rightarrow \) irreducibleany chain with transient states and one closed class
stationary \( \Rightarrow \) detailed balancedeterministic 3-cycle
period = shortest return timereturns in 2 and 3 steps give period 1
transient states are aperiodictransient pair \( 3 \leftrightarrow 4 \) with no self-loops: period 2
\( p_{jj}^{(n)} \to 0 \Rightarrow j \) transientsymmetric walk on \( \mathbb{Z} \) (null recurrent)
\( \pi \) of CTMC = \( \pi \) of its jump chaintwo-state chain with \( \alpha \ne \beta \): jump chain has \( \left(\frac12, \frac12\right) \)
growing mean \( \Rightarrow \) survivallinear birth–death with \( \lambda > \mu \): extinction probability \( \frac{\mu}{\lambda} \)
\( N(1) \), \( N(3) \) independentcovariance \( \lambda \)
M/M/1 has a steady state for \( \lambda = \mu \)null recurrent, no \( \pi \)

Where to go next

Advertisement
Advertisement