GATE Statistics Stochastic Processes Syllabus

For a finite irreducible aperiodic Markov chain, what is guaranteed about limiting probabilities?

Such a chain is ergodic; the limits $\lim_{n\to\infty} p_{ij}^{(n)} = \pi_j$ exist, are independent of the starting state $i$, are strictly positive, and form the unique stationary distribution.

Define a stationary (invariant) distribution $\pi$ of a Markov chain.

A probability row vector $\pi=(\pi_j)$ is stationary if $$\pi = \pi P, \quad \text{i.e. } \pi_j = \sum_i \pi_i p_{ij}, \qquad \pi_j \geq 0, \ \sum_j \pi_j = 1.$$ If started in $\pi$, the chain's distribution stays $\pi$ for all time.

State the existence and uniqueness condition for a stationary distribution.

An irreducible, positive recurrent Markov chain has a unique stationary distribution $\pi$. An irreducible chain that is transient or null recurrent has no stationary distribution.

How is the stationary probability $\pi_i$ related to the mean recurrence time $m_i$?

For an irreducible positive recurrent chain, $$\pi_i = \frac{1}{m_i},$$ where $m_i$ is the expected return time to state $i$.

State the basic limit theorem relating $p_{ij}^{(n)}$ to the stationary distribution for an ergodic chain.

For an irreducible, aperiodic, positive recurrent chain, $$\lim_{n\to\infty} p_{ij}^{(n)} = \pi_j = \frac{1}{m_j} \quad \text{for all } i,$$ independent of the initial state.

For an irreducible null recurrent or transient chain, what is $\lim_{n\to\infty} p_{ij}^{(n)}$?

$$\lim_{n\to\infty} p_{ij}^{(n)} = 0 \quad \text{for all } i,j,$$ in both the null recurrent and transient cases.

What is the limiting behavior of $p_{ij}^{(n)}$ for a periodic irreducible chain with period $d>1$?

The simple limit $\lim_n p_{ij}^{(n)}$ does not exist. Instead the Cesàro average converges: $$\lim_{N\to\infty} \frac{1}{N}\sum_{n=1}^{N} p_{ij}^{(n)} = \pi_j.$$

Define detailed balance and state its consequence.

A distribution $\pi$ satisfies detailed balance if $$\pi_i p_{ij} = \pi_j p_{ji} \quad \text{for all } i,j.$$ If detailed balance holds, $\pi$ is automatically a stationary distribution and the chain is called reversible.

What is a time-reversible Markov chain?

A stationary chain is reversible if its dynamics look statistically the same forward and backward in time; equivalently the stationary distribution $\pi$ satisfies the detailed balance equations $\pi_i p_{ij}=\pi_j p_{ji}$.

State the ergodic theorem (strong law) for the long-run fraction of time in a state.

For an irreducible positive recurrent chain, the long-run fraction of time spent in state $j$ converges almost surely to $\pi_j$: $$\frac{1}{N}\sum_{n=1}^{N} \mathbf{1}\{X_n=j\} \xrightarrow{\text{a.s.}} \pi_j = \frac{1}{m_j}.$$

In a Markov chain with both transient and recurrent classes, where does the chain eventually concentrate?

With probability $1$ the chain eventually leaves the transient states and is absorbed into a recurrent (closed) communicating class, spending all long-run time there.

Describe the simple random walk on $\mathbb{Z}$ and its transition probabilities.

On the integers, $X_{n+1}=X_n+1$ with probability $p$ and $X_{n+1}=X_n-1$ with probability $q=1-p$. So $p_{i,i+1}=p$, $p_{i,i-1}=q$. It is irreducible with period $2$.

For the simple random walk on $\mathbb{Z}$, when is it recurrent versus transient?

It is recurrent iff it is symmetric, $p=q=\tfrac12$ (then null recurrent); it is transient iff $p \neq \tfrac12$. Recurrence follows from $\sum_n p_{00}^{(2n)}=\infty$ at $p=\tfrac12$.

State the recurrence/transience result for the symmetric simple random walk on $\mathbb{Z}^d$ (Pólya's theorem).

The symmetric simple random walk is recurrent in dimensions $d=1$ and $d=2$, and transient for all $d \geq 3$. ("A drunk man returns home, a drunk bird may not.")

What is a branching (Galton–Watson) process?

A Markov chain where each individual independently produces a random number of offspring with common distribution; $X_n$ is the population size in generation $n$, $$X_{n+1}=\sum_{k=1}^{X_n} Z_k,$$ with $Z_k$ i.i.d. offspring counts.

State the extinction criterion for a Galton–Watson branching process in terms of mean offspring $\mu$.

Let $\mu=E[Z]$. Extinction is certain (probability $1$) iff $\mu \leq 1$ (with $P(Z=1)<1$). If $\mu > 1$ extinction probability is the smallest root $s\in[0,1)$ of $s=G(s)$, where $G$ is the offspring p.g.f.

Define a Poisson process with rate $\lambda$.

A counting process $\{N(t),t\geq 0\}$ with $N(0)=0$, independent stationary increments, and $N(t+s)-N(s) \sim \text{Poisson}(\lambda t)$. So $$P(N(t)=k)=e^{-\lambda t}\frac{(\lambda t)^k}{k!}.$$

What is the distribution of interarrival times in a Poisson process of rate $\lambda$?

The interarrival times are i.i.d. exponential with rate $\lambda$: $$f(t)=\lambda e^{-\lambda t}, \quad t\geq 0,$$ with mean $1/\lambda$. The $n$-th arrival time is Gamma$(n,\lambda)$.

For a continuous-time Markov chain, what is the holding time in a state and its distribution?

The time spent in state $i$ before a jump is exponentially distributed with rate $q_i$ (mean $1/q_i$), independent of the next state chosen, reflecting the memoryless property of continuous-time chains.

What is the generator (rate) matrix $Q$ of a continuous-time Markov chain?

$Q=(q_{ij})$ where $q_{ij}\geq 0$ ($i\neq j$) is the transition rate from $i$ to $j$, and $q_{ii}=-\sum_{j\neq i} q_{ij}$, so each row of $Q$ sums to $0$.

How is the stationary distribution $\pi$ of a continuous-time Markov chain characterized?

It satisfies the global balance equation $$\pi Q = 0, \qquad \sum_i \pi_i = 1,$$ equivalently rate of probability flow into each state equals rate out.

What is the relation between the limiting distribution and the stationary distribution for an ergodic chain?

For an ergodic (irreducible, aperiodic, positive recurrent) chain the limiting distribution exists, is unique, and equals the stationary distribution $\pi$, independent of the initial state.

Can a limiting distribution exist while a stationary distribution is not unique? Explain.

If a chain is reducible there may be several stationary distributions and the limit depends on the starting state. A unique limiting distribution independent of the start requires irreducibility plus aperiodicity and positive recurrence.

Compare positive recurrent, null recurrent, and transient chains by their stationary distribution and limit of $p_{ij}^{(n)}$.

Positive recurrent: unique stationary $\pi$ exists, $p_{ij}^{(n)}\to\pi_j>0$ (if aperiodic). Null recurrent: no stationary distribution, $p_{ij}^{(n)}\to 0$, return certain but $m_i=\infty$. Transient: no stationary distribution, $p_{ij}^{(n)}\to 0$, return uncertain.

What is the doubly stochastic matrix property and its consequence for the stationary distribution?

$P$ is doubly stochastic if both rows and columns sum to $1$. For a finite irreducible doubly stochastic chain with $N$ states, the stationary distribution is uniform: $\pi_i = \tfrac{1}{N}$ for all $i$.

What is the expected number of visits to a transient state $j$ starting from $i$?

It is the $(i,j)$ entry of the fundamental matrix $N=(I-Q)^{-1}$, where $Q$ is the substochastic matrix of transitions among transient states. The total expected visits is finite because $j$ is transient.

State Kolmogorov's forward (master) equation for a continuous-time Markov chain.

For transition probabilities $P(t)$, $$\frac{d}{dt}P(t) = P(t)\,Q,$$ with solution $P(t)=e^{tQ}$. The backward equation is $\frac{d}{dt}P(t)=Q\,P(t)$.

For a two-state Markov chain with $P=\begin{pmatrix}1-a & a\\ b & 1-b\end{pmatrix}$, what is the stationary distribution?

$$\pi = \left(\frac{b}{a+b}, \ \frac{a}{a+b}\right),$$ valid when $a+b>0$. The chain is ergodic for $0<a,b<1$ and $p_{ij}^{(n)}\to\pi_j$.

What characterizes a martingale $\{X_n\}$ with respect to a filtration?

A martingale satisfies $E[|X_n|]<\infty$ and $$E[X_{n+1}\mid X_0,\dots,X_n] = X_n.$$ A submartingale has $\geq$ and a supermartingale has $\leq$ in place of equality; the future conditional mean equals the present.

Summarize the conditions of the fundamental limit theorem for Markov chains (when $\pi_j=\lim_n p_{ij}^{(n)}$).

If the chain is irreducible, aperiodic, and positive recurrent, then for all $i,j$, $\lim_{n\to\infty}p_{ij}^{(n)}=\pi_j=1/m_j$, where $\pi$ is the unique stationary distribution and $m_j$ the mean return time to $j$.