Stochastic Processes Unit 6 Review: Continuous-time Markov Chains

Key Concepts and Definitions

• Continuous-time Markov chains (CTMCs) model stochastic processes with continuous time and discrete state spaces
• State space $S$ represents the set of possible states the process can occupy
• Transition probabilities $P_{ij}(t)$ describe the probability of moving from state $i$ to state $j$ in time $t$
• Intensity matrix $Q$ (also called infinitesimal generator matrix) contains transition rates between states
  • Off-diagonal elements $q_{ij}$ represent the rate of transition from state $i$ to state $j$
  • Diagonal elements $q_{ii}$ ensure the sum of each row in $Q$ is zero
• Sojourn time (holding time) in a state $i$ follows an exponential distribution with parameter $-q_{ii}$
• Jump chain represents the embedded discrete-time Markov chain (DTMC) of a CTMC

Markov Property and Transition Probabilities

• Markov property states that the future behavior of the process depends only on the current state, not on the past history
• Formally, for any states $i, j \in S$ and times $s, t \geq 0$, $P(X(t+s) = j | X(s) = i, X(u) = x(u), 0 \leq u < s) = P(X(t+s) = j | X(s) = i)$
• Transition probability function $P_{ij}(t) = P(X(t) = j | X(0) = i)$ satisfies the following properties:
  • $P_{ij}(t) \geq 0$ for all $i, j \in S$ and $t \geq 0$
  • $\sum_{j \in S} P_{ij}(t) = 1$ for all $i \in S$ and $t \geq 0$
  • $P_{ij}(0) = \delta_{ij}$ (Kronecker delta)
• Time-homogeneity implies that transition probabilities depend only on the time difference, not on the absolute time
• Kolmogorov forward and backward equations describe the evolution of transition probabilities over time

Chapman-Kolmogorov Equations

• Chapman-Kolmogorov equations express the relationship between transition probabilities over different time intervals
• For any states $i, j \in S$ and times $s, t \geq 0$, $P_{ij}(t+s) = \sum_{k \in S} P_{ik}(t)P_{kj}(s)$
• Intuitively, the probability of transitioning from state $i$ to state $j$ in time $t+s$ is the sum of the probabilities of transitioning from $i$ to an intermediate state $k$ in time $t$ and then from $k$ to $j$ in time $s$
• Chapman-Kolmogorov equations hold for both time-homogeneous and time-inhomogeneous CTMCs
• They provide a way to compute transition probabilities over longer time intervals using shorter ones
• The equations can be expressed in matrix form as $P(t+s) = P(t)P(s)$, where $P(t)$ is the matrix of transition probabilities at time $t$

Infinitesimal Generator Matrix

• The infinitesimal generator matrix $Q$ (also called the intensity matrix) characterizes the instantaneous transition rates of a CTMC
• For any states $i, j \in S$, the $(i, j)$-th element of $Q$ is defined as $q_{ij} = \lim_{h \to 0^+} \frac{P_{ij}(h) - \delta_{ij}}{h}$
  • Off-diagonal elements $q_{ij}$ ($i \neq j$) represent the instantaneous transition rate from state $i$ to state $j$
  • Diagonal elements $q_{ii}$ are chosen such that each row of $Q$ sums to zero, i.e., $q_{ii} = -\sum_{j \neq i} q_{ij}$
• The sojourn time (holding time) in state $i$ follows an exponential distribution with parameter $-q_{ii}$
• Kolmogorov forward and backward equations can be expressed in terms of the infinitesimal generator matrix
  • Forward equation: $\frac{d}{dt}P(t) = P(t)Q$
  • Backward equation: $\frac{d}{dt}P(t) = QP(t)$
• The matrix exponential $P(t) = e^{tQ}$ gives the transition probability matrix at time $t$

Classification of States

• States in a CTMC can be classified based on their long-term behavior and communication properties
• Accessible: State $j$ is accessible from state $i$ if $P_{ij}(t) > 0$ for some $t \geq 0$
• Communicating states: States $i$ and $j$ communicate if they are accessible from each other
• Communication classes: Sets of states that communicate with each other and no other states
  • Irreducible CTMCs have a single communication class containing all states
• Absorbing states: States with no outgoing transitions (except self-loops), i.e., $q_{ii} = 0$
• Transient states: Non-absorbing states that have a positive probability of never being revisited
• Recurrent states: Non-absorbing states that are revisited infinitely often with probability 1
  • Positive recurrent states have finite expected return times
  • Null recurrent states have infinite expected return times

Stationary Distributions

• A stationary distribution $\pi$ is a probability distribution over the state space that remains unchanged over time
• Formally, $\pi$ satisfies $\pi P(t) = \pi$ for all $t \geq 0$, or equivalently, $\pi Q = 0$ and $\sum_{i \in S} \pi_i = 1$
• Stationary distributions can be computed by solving the system of linear equations $\pi Q = 0$ subject to $\sum_{i \in S} \pi_i = 1$
• Irreducible and positive recurrent CTMCs have a unique stationary distribution
• Stationary distributions provide insight into the long-term behavior of the process
• They can be used to compute steady-state performance measures (e.g., average queue length, system utilization)

Limiting Behavior and Ergodicity

• Limiting distribution $\pi^*$ describes the long-term behavior of a CTMC, defined as $\pi^*_j = \lim_{t \to \infty} P_{ij}(t)$ (when the limit exists)
• Ergodic CTMCs converge to a unique limiting distribution regardless of the initial state
  • Irreducible, positive recurrent, and aperiodic CTMCs are ergodic
  • For ergodic CTMCs, the limiting distribution equals the stationary distribution
• Non-ergodic CTMCs may have different limiting distributions depending on the initial state or may not converge at all
• Convergence rate to the limiting distribution can be analyzed using the spectral properties of the infinitesimal generator matrix
• Ergodic theorem for CTMCs relates time averages to ensemble averages (stationary distribution)

Applications and Examples

• Queueing systems: CTMCs can model the number of customers in a queue over time (M/M/1, M/M/c queues)
• Reliability analysis: CTMCs can represent the states of a system (working, failed, under repair) and analyze its availability and reliability
• Epidemiology: CTMCs can model the spread of infectious diseases (SIR, SIS models) and evaluate intervention strategies
• Chemical reaction kinetics: CTMCs can describe the evolution of molecule counts in a chemical reaction network
• Population dynamics: CTMCs can capture the growth and interaction of different species in an ecosystem (birth-death processes)
• Finance: CTMCs can model the behavior of asset prices, interest rates, or credit ratings over time
• Genetics: CTMCs can represent the evolution of DNA sequences or the inheritance of genetic traits across generations
• Social networks: CTMCs can analyze the spread of information, opinions, or behaviors through a network of individuals