Skip to content
Deadline to Die

Stochastic Processes & Markov Chains

🎲 Stochastic Processes & Markov Chains

A Stochastic Process is a collection of random variables indexed by time {Xt,t∈T}\{X_t, t \in T\}. This is the foundation of Time-Series Analysis, Queueing Theory, and Reinforcement Learning.

🟢 1. Markov Chains (Discrete Time)

The Markov Property

The future depends only on the present, not the past. This “memoryless” property is defined as: P(Xn+1=j∣X0,X1,…,Xn=i)=P(Xn+1=j∣Xn=i)P(X_{n+1} = j \mid X_0, X_1, \dots, X_n = i) = P(X_{n+1} = j \mid X_n = i)

Transition Matrix (P\mathbf{P})

A matrix where PijP_{ij} represents the probability of moving from state ii to state jj.

  • Row Stochastic: Each row must sum to 1 (∑jPij=1\sum_j P_{ij} = 1).
  • Chapman-Kolmogorov Equation: P(Xn+m=j∣Xn=i)=(Pm)ijP(X_{n+m} = j \mid X_n = i) = (\mathbf{P}^m)_{ij}.

🟡 2. Equilibrium and Convergence

Stationary Distribution (π\pi)

A probability distribution that remains unchanged by the transition matrix. πP=π\pi \mathbf{P} = \pi In linear algebra terms, π\pi is a left eigenvector of P\mathbf{P} associated with the eigenvalue λ=1\lambda = 1.

Ergodicity and Limiting Distributions

A Markov chain is ergodic if it is both irreducible (can reach any state from any other) and aperiodic.

  • Fundamental Theorem: For an ergodic Markov chain, a unique stationary distribution exists, and the chain will converge to it regardless of the initial state.

🔴 3. Advanced Applications

Hidden Markov Models (HMM)

A doubly stochastic process where the underlying state sequence is “hidden” and only observable through a set of emission probabilities.

  • Filtering: Finding the current state given history.
  • Viterbi Algorithm: Most likely path of states.

Markov Chain Monte Carlo (MCMC)

Algorithms used to sample from complex distributions by constructing a Markov chain whose stationary distribution is the target distribution.

  • Metropolis-Hastings: The most general MCMC algorithm.
  • Gibbs Sampling: A special case where we sample from conditional distributions.

Poisson Processes

A continuous-time stochastic process used for modeling the number of events occurring in a fixed interval of time.

  • Properties: Independent increments and memoryless inter-arrival times.