15.2 Continuous-time Markov chains

Continuous-Time Markov Chains (CTMCs) model systems that change randomly over time. They're used in queueing, reliability, and epidemiology to predict how things like customer lines, machine failures, or disease spread evolve.

CTMCs use transition rate matrices to show how quickly states change. By solving equations, we can find both short-term and long-term probabilities of being in different states. This helps us make predictions and improve real-world systems.

Continuous-Time Markov Chains (CTMCs)

Concept of continuous-time Markov chains

Top images from around the web for Concept of continuous-time Markov chains

• 

  Continuous-time Markov chain - Wikipedia View original

  Is this image relevant?

• 

  Markov Chains View original

  Is this image relevant?

• 

  Markov chain - Simple English Wikipedia, the free encyclopedia View original

  Is this image relevant?

• 

  Continuous-time Markov chain - Wikipedia View original

  Is this image relevant?

• 

  Markov Chains View original

  Is this image relevant?

1 of 3

Top images from around the web for Concept of continuous-time Markov chains

• 

  Continuous-time Markov chain - Wikipedia View original

  Is this image relevant?

• 

  Markov Chains View original

  Is this image relevant?

• 

  Markov chain - Simple English Wikipedia, the free encyclopedia View original

  Is this image relevant?

• 

  Continuous-time Markov chain - Wikipedia View original

  Is this image relevant?

• 

  Markov Chains View original

  Is this image relevant?

1 of 3

• Models the evolution of a system over continuous time where the system can be in one of a finite or countable number of states (healthy, infected, recovered)
• Transitions between states occur randomly according to exponentially distributed holding times (average time spent in each state before transitioning)
• Satisfies the Markov property where the future state of the system depends only on the current state, not on the past states
  • Mathematically expressed as $P(X(t+s) = j | X(s) = i, X(u) = x(u), 0 \leq u < s) = P(X(t+s) = j | X(s) = i)$
• Utilizes the memoryless property of the exponential distribution to enable the Markov property in continuous time
  • The holding time in each state is exponentially distributed with parameter $\lambda_i$, where $i$ represents the current state (failure rate, recovery rate)

Transition rate matrices for CTMCs

• Describes the rates at which the process moves between states using the transition rate matrix $Q = (q_{ij})$
  • $q_{ij}$ represents the rate of transition from state $i$ to state $j$, where $i \neq j$ (infection rate, repair rate)
  • The diagonal entries $q_{ii}$ are defined as $-\sum_{j \neq i} q_{ij}$ to ensure the row sums are zero
• Satisfies the following properties:
  • $q_{ij} \geq 0$ for $i \neq j$
  • $q_{ii} \leq 0$
  • $\sum_{j} q_{ij} = 0$ for all $i$
• Allows for the derivation of the embedded discrete-time Markov chain (DTMC) from the CTMC
  • The transition probability matrix $P = (p_{ij})$ of the embedded DTMC is given by $p_{ij} = \frac{q_{ij}}{-q_{ii}}$ for $i \neq j$ and $p_{ii} = 0$

Probabilities in CTMCs

• Transient probabilities $p_{ij}(t)$ represent the probability of being in state $j$ at time $t$, given that the process started in state $i$ at time $0$
  • Described by the Kolmogorov forward equations: $\frac{d}{dt}p_{ij}(t) = \sum_{k} p_{ik}(t)q_{kj}$
  • The matrix form of the forward equations is $\frac{d}{dt}P(t) = P(t)Q$, where $P(t) = (p_{ij}(t))$
• Steady-state probabilities $\pi_j$ represent the long-run proportion of time the process spends in state $j$
  • Satisfy the global balance equations: $\sum_{i} \pi_i q_{ij} = 0$ for all $j$
  • Must also satisfy the normalization condition $\sum_{j} \pi_j = 1$
  • Solving the global balance equations and the normalization condition yields the steady-state distribution $\pi = (\pi_1, \pi_2, \ldots)$

Applications of CTMCs

• Queueing systems model the number of customers in a queue over time (bank, supermarket)
  • Construct the transition rate matrix using arrival and service rates
  • Derive performance measures such as average queue length and waiting time from the steady-state probabilities
• Reliability analysis models the failure and repair of components in a system (machines, power plants)
  • States represent the operational status of the components (working, failed)
  • Calculate reliability metrics such as availability and mean time to failure using the transient and steady-state probabilities
• Epidemiology models the spread of infectious diseases in a population (COVID-19, influenza)
  • States represent the health status of individuals (susceptible, infected, recovered)
  • Transition rates capture the disease transmission and recovery processes
  • Estimate the prevalence of the disease and evaluate intervention strategies using the model