Chapter 3 — Markov Chains and Stochastic Processes
Random systems with a one-step memory: Markov chains in discrete time, the classification of their states, their long-run equilibrium, and the Poisson and birth–death processes that run in continuous time.
Chapters 1 and 2 studied random variables one at a time, or as independent sequences. Most random systems in the real world are neither: they evolve, and what happens next depends on where the system is now. The length of the queue at a hospital pharmacy, the credit rating of a company, the number of copies of a gene in a population, the page a web surfer is reading and the state of a machine that breaks and is repaired all change step by step, with the present state carrying all the information about the future that matters. This "memory of one step" is the Markov property. It is weak enough to fit an enormous range of applications and strong enough to give a complete theory: from a single matrix of transition probabilities we can compute the distribution at any future time, decide which states are visited infinitely often and which only finitely often, find absorption probabilities and expected durations, and determine the long-run equilibrium.
The chapter has three parts. Section 3.1 builds the discrete-time theory: transition matrices and the Chapman–Kolmogorov equations, communicating classes, recurrence and transience, periodicity, absorption, and the random walk that returns home with certainty on a line and a plane but not in space. Section 3.2 studies the long run: stationary distributions, mean return times, convergence of $P^n$ and the ergodic theorem, reversibility, and the chains on infinitely many states that can be positive recurrent, null recurrent or transient. Section 3.3 moves to continuous time with the Poisson process, the model of arrivals at random instants, and with birth–death processes, which lead directly to the queueing models of Chapter 9.
- decide whether a process is a Markov chain, write down its transition matrix, and compute $n$-step probabilities and the distribution of $X_n$ with the Chapman–Kolmogorov equations;
- find the communicating classes of any chain, decide which are closed, recurrent or transient, and find the period of each class;
- use the criteria $f_{ii}=1$ and $\sum_np_{ii}^{(n)}=\infty$, prove that the simple random walk on $\mathbb{Z}$ is recurrent exactly when it is symmetric, and state Pólya's theorem;
- compute absorption probabilities and expected absorption times by first-step analysis and the fundamental matrix, including the gambler's ruin;
- find stationary distributions, using doubly stochastic matrices, detailed balance and random walks on graphs where possible, and use $\pi_i=1/\mu_i$;
- state and apply the convergence theorem and the ergodic theorem, and explain with counterexamples why irreducibility, aperiodicity and positive recurrence are each needed;
- classify birth–death chains on $\{0,1,2,\dots\}$ as positive recurrent, null recurrent or transient;
- work with the Poisson process (its equivalent definitions, exponential inter-arrival times, thinning and superposition), continuous-time Markov chains and birth–death processes, and find their steady-state probabilities.
How this is examined
Markov chains appear in almost every CSIR NET Unit 4 paper, and Poisson processes very often. Typical Part B questions ask for one number: a two-step transition probability, the period of a state in a given diagram, a stationary distribution or mean return time, an absorption probability or expected time to absorption, the probability of $k$ Poisson arrivals in an interval, the distribution of a waiting time, or a steady-state probability of a birth–death process. Part C questions, where more than one option may be correct, present a transition matrix or a family of chains and ask which statements hold. Is a given state recurrent? Is the chain irreducible, aperiodic, reversible? Does $P^n$ converge, and to what? Does a stationary distribution exist, and is it unique? Is the random walk recurrent in this dimension or for this bias? Is the superposition or thinning of Poisson processes again Poisson? The wrong options are built from the counterexamples in the ⚠️ boxes: periodic chains, reducible chains, infinite chains without equilibrium, and null recurrence. GATE ST asks similar questions in numerical-answer and multiple-select formats.
Sections in this chapter
Markov Chains and Classification of States
The Markov property, transition matrices and Chapman–Kolmogorov, communicating classes and closed sets, recurrence and transience, random walks on $\mathbb{Z}$ and $\mathbb{Z}^d$, periods, absorption probabilities, the fundamental matrix and the gambler's ruin.
Limiting Behaviour and Stationary Distributions
Stationary distributions, positive and null recurrence and $\pi_i=1/\mu_i$, the convergence theorem by coupling, periodic chains and the ergodic theorem, doubly stochastic matrices, detailed balance and reversibility, random walks on graphs, birth–death chains.
Poisson and Birth–Death Processes
Counting processes and three definitions of the Poisson process, exponential inter-arrival and gamma arrival times, thinning and superposition, compound Poisson processes, continuous-time Markov chains, birth–death processes, the Kolmogorov equations and steady states.
This chapter uses conditional probability, the law of total probability and the gambler's ruin problem from §1.2, expectations and the tail formula $E[X]=\sum_{n\ge0}P(X\gt n)$ from §1.3, conditional expectation from §1.4, the geometric, exponential, gamma and Poisson laws from §2.1, and the strong law of large numbers from §2.3. From linear algebra you need matrix multiplication, inverses, eigenvalues and eigenvectors (a stationary distribution is a left eigenvector for the eigenvalue $1$). From analysis you need power series, generating functions and Stirling's formula $n!\sim\sqrt{2\pi n}\,(n/e)^n$. If these are rusty, revise them from the sister course CSIR NET Unit 1: Analysis and Linear Algebra; Section 3.3 also uses linear differential equations, which are covered in CSIR NET Unit 3.