Skip to the content

Unit IX — Stochastic Processes

UGC NET Statistics (Code 107)

Topics Covered

n-step Probabilities Initial Distribution Accessibility & Communication Irreducibility Recurrence vs Transience Periodicity Ergodic States Class Properties Existence & Uniqueness Detailed Balance Probability of Ruin (Reaching 0) Probability of Reaching N

Contents

Topic Overview — What & Why

Unit IX generalises a single random variable to families of random variables indexed by time. The structure of dependence across time enables modelling of dynamic phenomena: weather, stock prices, queues, populations, epidemics.

  • Markov chains: the future depends on the past only through the present — the simplest non-trivial form of dependence. Transition probability matrices encode the dynamics.
  • Classification of states: recurrent vs transient, periodic vs aperiodic, ergodic — determines long-run behaviour.
  • Chapman-Kolmogorov equations: state how multi-step probabilities decompose; matrix form $P^{m+n}=P^mP^n$.
  • Limiting behaviour & stationary distribution: for ergodic chains, $p_{ij}^{(n)}\to\pi_j$ regardless of starting state — long-run equilibrium.
  • Gambler's ruin & simple random walk: classic problems giving closed-form ruin probabilities and expected durations — templates for many applications.
  • Poisson process: the canonical model for random arrivals; inter-arrival times are exponential, count process has stationary independent increments.
  • Inter-arrival & waiting time distributions: Exp / Gamma; the memoryless property characterises exponential.
  • Birth and death processes: continuous-time Markov chains with nearest-neighbour transitions on $\mathbb N$; backbone of queueing and population models.
  • M/M/1 queue: single-server queue with Poisson arrivals and exponential service; performance measures via Little's Law.

1. Markov Chains: Definitions

Why this section? The Markov property — "the future is independent of the past given the present" — is one of the most powerful simplifying assumptions in probability. It makes high-dimensional dynamics tractable.

A discrete-time stochastic process $\{X_n,n\ge 0\}$ on countable state space $S$ is a Markov Chain if $$P(X_{n+1}=j\mid X_n=i,X_{n-1}=i_{n-1},\ldots,X_0=i_0)=P(X_{n+1}=j\mid X_n=i)=p_{ij}.$$ The matrix $P=(p_{ij})$ is the transition probability matrix with $p_{ij}\ge 0,\,\sum_j p_{ij}=1.$

$n$-step Probabilities

$p_{ij}^{(n)}=P(X_n=j\mid X_0=i).$ Matrix $P^n=(p_{ij}^{(n)}).$

Initial Distribution

$\pi_i^{(0)}=P(X_0=i).$ State distribution after $n$ steps: $\boldsymbol\pi^{(n)}=\boldsymbol\pi^{(0)}P^n.$
EXAMPLE 1 Weather chain with states {Sunny, Rainy} and $P=\begin{pmatrix}0.8&0.2\\0.4&0.6\end{pmatrix}.$ $P^2=\begin{pmatrix}0.72&0.28\\0.56&0.44\end{pmatrix}.$
Sunny Rainy 0.2 0.4 0.8 0.6 rows of P sum to 1
State-transition diagram. Each arrow carries the one-step probability $p_{ij}$; the probabilities leaving any state sum to 1. The long-run fractions of sunny/rainy days are the stationary distribution π = (2/3, 1/3).
EXAMPLE 2 2-state machine: Working ($W$) → Failed ($F$) with prob 0.1; $F\to W$ with prob 0.5. $P=\begin{pmatrix}0.9&0.1\\0.5&0.5\end{pmatrix}.$

🌍 Where it's used in real life

  1. Day-to-day weather modelling.
  2. Google PageRank web surfing.
  3. Board games like Snakes and Ladders.
  4. Customer state (active vs churned).
  5. Text prediction and autocomplete.

2. Classification of States

Accessibility & Communication

$j$ is accessible from $i$ ($i\to j$) if $p_{ij}^{(n)}>0$ for some $n\ge 0.$ States $i,j$ communicate ($i\leftrightarrow j$) if mutually accessible. Equivalence relation → communicating classes.

Irreducibility

Chain is irreducible if all states form one class.

Recurrence vs Transience

Let $f_{ii}=P(\text{ever return to }i\mid X_0=i).$

Intuition. A recurrent state is one the chain is certain to revisit (infinitely often); a transient state is eventually abandoned forever. Positive vs null recurrence is the finer question of whether the average time between visits is finite — and that is exactly what decides whether a proper long-run stationary distribution exists ($\pi_j=1/\mu_{jj}$, which is $0$ in the null-recurrent case).

Periodicity

$d(i)=\gcd\{n\ge 1:p_{ii}^{(n)}>0\}.$ State aperiodic if $d(i)=1.$

Ergodic States

Aperiodic + positive recurrent.

Class Properties

Recurrence, periodicity, transience are class properties — all states in same class share them.
EXAMPLE 1 Simple symmetric random walk on $\mathbb Z$: irreducible, period 2, all states null recurrent in 1D (recurrent but $E(\text{return})=\infty$).
EXAMPLE 2 Simple random walk in $\mathbb Z^d$ for $d\ge 3$: transient (Pólya).

🌍 Where it's used in real life

  1. Will a system return to a state? (reliability).
  2. Absorbing states like game-over or default.
  3. Which conditions are reachable long term.
  4. Detecting permanent failure states.
  5. Recurrent vs transient behaviour.

3. Chapman–Kolmogorov Equations

$$p_{ij}^{(m+n)}=\sum_{k\in S}p_{ik}^{(m)}p_{kj}^{(n)},\quad m,n\ge 0.$$ Matrix form: $P^{(m+n)}=P^{(m)}P^{(n)}.$
EXAMPLE 1 Weather chain above: $p_{SS}^{(2)}=0.8\cdot 0.8+0.2\cdot 0.4=0.72.$ ✓
EXAMPLE 2 For 3-state chain with $p_{12}^{(1)}=0.3,p_{23}^{(1)}=0.5,p_{13}^{(1)}=0.4$ and starting in state 1: $p_{13}^{(2)}=p_{11}p_{13}+p_{12}p_{23}+p_{13}p_{33}.$

🌍 Where it's used in real life

  1. Multi-step weather or market predictions.
  2. n-step transition probabilities in PageRank.
  3. Reliability over several periods.
  4. Multi-step customer-journey modelling.
  5. Genetics across several generations.

4. Limiting Behaviour of $n$-Step Probabilities

For an irreducible aperiodic positive-recurrent chain: $$\lim_{n\to\infty}p_{ij}^{(n)}=\pi_j,\,\text{independent of }i.$$ $\pi_j>0,\,\sum\pi_j=1$ — stationary distribution.

For periodic recurrent chain: limit $p_{ii}^{(nd)}$ exists. For transient: $p_{ij}^{(n)}\to 0.$

EXAMPLE 1 Weather chain: $\pi_S=\frac{0.4}{0.4+0.2}=2/3,\,\pi_R=1/3.$ $P^n\to\begin{pmatrix}2/3&1/3\\2/3&1/3\end{pmatrix}.$
EXAMPLE 2 For a 2-state chain with period 2 (e.g. $P=\begin{pmatrix}0&1\\1&0\end{pmatrix}$): $p_{11}^{(2n)}=1,p_{11}^{(2n+1)}=0$ — no limit.

🌍 Where it's used in real life

  1. Long-run market share.
  2. Steady-state page popularity.
  3. Equilibrium proportions of weather types.
  4. Long-run machine up/down time.
  5. Eventual customer distribution.

5. Stationary Distribution

$\boldsymbol\pi$ is a stationary distribution if $\boldsymbol\pi P=\boldsymbol\pi$ and $\sum\pi_j=1.$

Existence & Uniqueness

Detailed Balance

$\pi_i p_{ij}=\pi_j p_{ji}\,\forall i,j$ → reversible chain. Sufficient (not necessary) for $\boldsymbol\pi$ stationary.
EXAMPLE 1 Birth–death chain with $p_{i,i+1}=p,\,p_{i,i-1}=q,p+q=1$ on finite states $\{0,1,\ldots,N\}$. Stationary: $\pi_i=\pi_0(p/q)^i$, normalize.
EXAMPLE 2 Solve $\boldsymbol\pi P=\boldsymbol\pi$ for $P=\begin{pmatrix}0.5&0.5\\0.2&0.8\end{pmatrix}.$ $\pi_1=0.5\pi_1+0.2\pi_2,\,\pi_2=0.5\pi_1+0.8\pi_2\Rightarrow\pi_1=2/7,\pi_2=5/7.$

🌍 Where it's used in real life

  1. Long-run fraction of sunny days.
  2. Equilibrium market shares.
  3. Steady-state PageRank scores.
  4. Long-run queue occupancy.
  5. Equilibrium genotype frequencies.

6. Gambler's Ruin Problem

Gambler starts with Rs. $i$, plays until reaching Rs. $0$ (ruin) or Rs. $N$ (target). Each round: wins Re. $1$ with probability $p$, loses Re. $1$ with probability $q=1-p.$ States: $\{0,1,\ldots,N\}$, with $0$ and $N$ absorbing.

Probability of Ruin (Reaching 0)

$$P_i=\begin{cases}\dfrac{(q/p)^i-(q/p)^N}{1-(q/p)^N},&p\ne q,\\[6pt]\dfrac{N-i}{N},&p=q=1/2.\end{cases}$$

Probability of Reaching $N$

$Q_i=1-P_i.$

Expected Duration

For $p=q=1/2$: $D_i=i(N-i).$ For $p\ne q$: $D_i=\frac{1}{q-p}\Big[i-N\frac{1-(q/p)^i}{1-(q/p)^N}\Big].$
EXAMPLE 1 Fair coin ($p=q=0.5$), $i=20,N=50$: $P(\text{ruin})=30/50=0.6.$ Expected duration $20\cdot 30=600.$
EXAMPLE 2 $p=0.4,q=0.6,i=10,N=20.$ $r=q/p=1.5.$ $P_{10}=(1.5^{10}-1.5^{20})/(1-1.5^{20})\approx (57.7-3325)/(1-3325)=0.983.$ Almost certain ruin.

🌍 Where it's used in real life

  1. A casino gambler's chance of going broke.
  2. Risk of ruin for a trading account.
  3. An insurer's chance of insolvency.
  4. Win/lose streaks in sport.
  5. How long a startup's cash lasts.

7. Simple Random Walk

$X_n=X_0+\sum_{i=1}^n Z_i,$ where $Z_i$ iid with $P(Z_i=1)=p,P(Z_i=-1)=q.$

Properties

First Passage Time

For symmetric random walk, $T_a=\inf\{n:X_n=a\}.$ Reflection principle: $P(\max_{k\le n}X_k\ge a)=2P(X_n\ge a)-P(X_n=a).$
EXAMPLE 1 $P(X_4=2)$ for symmetric SRW from 0: needs 3 up,1 down in 4 steps. $\binom{4}{3}/2^4=4/16=1/4.$
EXAMPLE 2 $P(\text{ever return to 0})=1$ for 1D and 2D, $<1$ for $d\ge 3.$

🌍 Where it's used in real life

  1. Stock-price movements.
  2. Diffusion of particles in physics.
  3. Animal foraging paths.
  4. Randomised search algorithms.
  5. Spread of a pollutant.

8. Poisson Process

$\{N(t),t\ge 0\}$ is a Poisson process with rate $\lambda>0$ if:
  1. $N(0)=0.$
  2. Independent increments.
  3. $N(t+s)-N(s)\sim\text{Poisson}(\lambda t).$

Equivalent Definitions

Stationary independent increments with $P(N(h)=1)=\lambda h+o(h),\,P(N(h)\ge 2)=o(h).$

Properties

EXAMPLE 1 Calls to a switchboard $\sim$ Poisson, $\lambda=3$/hr. $P(N(2)=4)=e^{-6}6^4/4!=0.1339.$
EXAMPLE 2 Two independent Poisson processes (red, blue cars) at rates 4, 6 per minute. Total $\sim$ Poisson(10). Probability next arrival is red: $4/10=0.4.$

🌍 Where it's used in real life

  1. Calls arriving at a call centre.
  2. Customers entering a store.
  3. Website hits per minute.
  4. Radioactive-decay events.
  5. Accidents at a junction per month.

9. Inter-arrival and Waiting Time Distributions

Inter-arrival Times

$T_n$ = time between $(n-1)$th and $n$th event. $T_n\overset{\text{iid}}{\sim}\text{Exp}(\lambda)$ — memoryless property.

Waiting Time

$W_n=T_1+\cdots+T_n\sim\text{Gamma}(n,\lambda)$ (Erlang). pdf: $$f_{W_n}(t)=\frac{\lambda^n t^{n-1}e^{-\lambda t}}{(n-1)!},\,t\ge 0.$$ $E(W_n)=n/\lambda,\,V(W_n)=n/\lambda^2.$

Memoryless

$P(T>s+t\mid T>s)=P(T>t).$ Only continuous distribution with this property.
EXAMPLE 1 Bus arrivals Poisson with $\lambda=0.5$/min. $P(\text{wait}>5\text{ min})=e^{-2.5}\approx 0.082.$
EXAMPLE 2 $\lambda=2$/hr; expected wait for 5th customer: $5/2=2.5$ hr; SD $=\sqrt{5}/2=1.118.$

🌍 Where it's used in real life

  1. Time between customer arrivals.
  2. Time until the next machine failure.
  3. Waiting time for a bus or train.
  4. Time between website visits.
  5. Time between insurance claims.

10. Birth and Death Processes

Continuous-time Markov chain on $\{0,1,2,\ldots\}$ with transitions $i\to i+1$ at rate $\lambda_i$ (birth) and $i\to i-1$ at rate $\mu_i$ (death). $\lambda_i,\mu_i\ge 0,\,\mu_0=0.$

0123λ₀μ₁λ₁μ₂λ₂μ₃… Birth–death process (state = population size)
Nearest-neighbour transitions. From state $i$ the chain moves up at birth rate $\lambda_i$ (green) or down at death rate $\mu_i$ (orange); an M/M/1 queue is the special case $\lambda_i=\lambda,\ \mu_i=\mu$.

Stationary Distribution

For positive recurrent process: $$\pi_n=\pi_0\prod_{k=0}^{n-1}\frac{\lambda_k}{\mu_{k+1}},\quad \pi_0=\Big[1+\sum_{n=1}^\infty\prod_{k=0}^{n-1}\frac{\lambda_k}{\mu_{k+1}}\Big]^{-1}.$$ Stationary distribution exists iff series converges.

Pure Birth (Yule)

$\mu_i=0,\lambda_i=i\lambda$ → linear birth process. $E(N(t))=N_0 e^{\lambda t}.$

Pure Death

$\lambda_i=0,\,\mu_i=i\mu$ → linear death process.

Linear Birth–Death

$\lambda_i=i\lambda,\,\mu_i=i\mu.$ Population grows or dies depending on $\lambda$ vs $\mu.$
EXAMPLE 1 $\lambda_i=\lambda,\mu_i=\mu$ for all $i\ge 1$ — M/M/1 queue. Stationary requires $\rho=\lambda/\mu<1.$
EXAMPLE 2 Pure birth $\lambda_i=\lambda$: $N(t)\sim$ Poisson process — $E(N(t))=\lambda t.$

🌍 Where it's used in real life

  1. Population growth and decline.
  2. Changing queue length.
  3. Spread of an epidemic.
  4. Count of machines in service vs failed.
  5. Bacteria-colony dynamics.

11. M/M/1 Queue

Single-server queue with Poisson arrivals at rate $\lambda$ and exponential service at rate $\mu.$ Traffic intensity $\rho=\lambda/\mu.$

Stationary Distribution (when $\rho<1$)

$\pi_n=(1-\rho)\rho^n,\,n=0,1,2,\ldots$ — geometric.

Performance Measures (Little's Law)

Distribution of Wait Times

Wait in system: exponential with rate $\mu-\lambda.$
EXAMPLE 1 $\lambda=8$/hr, $\mu=10$/hr, $\rho=0.8.$ $L=0.8/0.2=4,L_q=0.64/0.2=3.2,W=1/2$ hr, $W_q=0.8/2=0.4$ hr.
EXAMPLE 2 ATM: arrivals 12/hr, service mean 4 min ($\mu=15$/hr), $\rho=0.8.$ Probability of $\ge 5$ in system = $\rho^5=0.328.$

🌍 Where it's used in real life

  1. A single-teller bank queue.
  2. One-server supermarket checkout.
  3. A single printer's job queue.
  4. A single-lane toll booth.
  5. A help-desk with one agent.