🔀Stochastic Processes Unit 6 – Continuous-time Markov Chains
Continuous-time Markov chains model stochastic processes with continuous time and discrete states. They're characterized by transition probabilities, intensity matrices, and sojourn times. The Markov property ensures future behavior depends only on the current state, not past history.
These models are used in queueing systems, reliability analysis, epidemiology, and finance. Key concepts include Chapman-Kolmogorov equations, infinitesimal generator matrices, state classifications, stationary distributions, and ergodicity. Understanding these elements helps analyze complex systems' long-term behavior and performance measures.
we crunched the numbers and here's the most likely topics on your next test
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 Pij(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 qij represent the rate of transition from state i to state j
Diagonal elements qii ensure the sum of each row in Q is zero
Sojourn time (holding time) in a state i follows an exponential distribution with parameter −qii
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∈S and times s,t≥0, P(X(t+s)=j∣X(s)=i,X(u)=x(u),0≤u<s)=P(X(t+s)=j∣X(s)=i)
Transition probability function Pij(t)=P(X(t)=j∣X(0)=i) satisfies the following properties:
Pij(t)≥0 for all i,j∈S and t≥0
∑j∈SPij(t)=1 for all i∈S and t≥0
Pij(0)=δ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∈S and times s,t≥0, Pij(t+s)=∑k∈SPik(t)Pkj(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∈S, the (i,j)-th element of Q is defined as qij=limh→0+hPij(h)−δij
Off-diagonal elements qij (i=j) represent the instantaneous transition rate from state i to state j
Diagonal elements qii are chosen such that each row of Q sums to zero, i.e., qii=−∑j=iqij
The sojourn time (holding time) in state i follows an exponential distribution with parameter −qii
Kolmogorov forward and backward equations can be expressed in terms of the infinitesimal generator matrix
Forward equation: dtdP(t)=P(t)Q
Backward equation: dtdP(t)=QP(t)
The matrix exponential P(t)=etQ 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 Pij(t)>0 for some t≥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., qii=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 π is a probability distribution over the state space that remains unchanged over time
Formally, π satisfies πP(t)=π for all t≥0, or equivalently, πQ=0 and ∑i∈Sπi=1
Stationary distributions can be computed by solving the system of linear equations πQ=0 subject to ∑i∈Sπ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 π∗ describes the long-term behavior of a CTMC, defined as πj∗=limt→∞Pij(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