Stochastic Processes

🔀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.

Got a Unit Test this week?

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 SS represents the set of possible states the process can occupy
  • Transition probabilities Pij(t)P_{ij}(t) describe the probability of moving from state ii to state jj in time tt
  • Intensity matrix QQ (also called infinitesimal generator matrix) contains transition rates between states
    • Off-diagonal elements qijq_{ij} represent the rate of transition from state ii to state jj
    • Diagonal elements qiiq_{ii} ensure the sum of each row in QQ is zero
  • Sojourn time (holding time) in a state ii follows an exponential distribution with parameter qii-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,jSi, j \in S and times s,t0s, t \geq 0, P(X(t+s)=jX(s)=i,X(u)=x(u),0u<s)=P(X(t+s)=jX(s)=i)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 Pij(t)=P(X(t)=jX(0)=i)P_{ij}(t) = P(X(t) = j | X(0) = i) satisfies the following properties:
    • Pij(t)0P_{ij}(t) \geq 0 for all i,jSi, j \in S and t0t \geq 0
    • jSPij(t)=1\sum_{j \in S} P_{ij}(t) = 1 for all iSi \in S and t0t \geq 0
    • Pij(0)=δijP_{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,jSi, j \in S and times s,t0s, t \geq 0, Pij(t+s)=kSPik(t)Pkj(s)P_{ij}(t+s) = \sum_{k \in S} P_{ik}(t)P_{kj}(s)
  • Intuitively, the probability of transitioning from state ii to state jj in time t+st+s is the sum of the probabilities of transitioning from ii to an intermediate state kk in time tt and then from kk to jj in time ss
  • 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)P(t+s) = P(t)P(s), where P(t)P(t) is the matrix of transition probabilities at time tt

Infinitesimal Generator Matrix

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

Classification of States

  • States in a CTMC can be classified based on their long-term behavior and communication properties
  • Accessible: State jj is accessible from state ii if Pij(t)>0P_{ij}(t) > 0 for some t0t \geq 0
  • Communicating states: States ii and jj 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=0q_{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 πP(t)=π\pi P(t) = \pi for all t0t \geq 0, or equivalently, πQ=0\pi Q = 0 and iSπi=1\sum_{i \in S} \pi_i = 1
  • Stationary distributions can be computed by solving the system of linear equations πQ=0\pi Q = 0 subject to iSπi=1\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 πj=limtPij(t)\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


© 2024 Fiveable Inc. All rights reserved.
AP® and SAT® are trademarks registered by the College Board, which is not affiliated with, and does not endorse this website.

© 2024 Fiveable Inc. All rights reserved.
AP® and SAT® are trademarks registered by the College Board, which is not affiliated with, and does not endorse this website.