🃏Engineering Probability Unit 14 – Markov Chains in Discrete-Time Processes

What Are Markov Chains?

• Markov chains are mathematical models used to represent systems that transition between different states over time
• They are named after the Russian mathematician Andrey Markov who introduced the concept in the early 20th century
• Markov chains are stochastic processes, meaning they involve elements of randomness or probability in the transitions between states
• The key characteristic of Markov chains is the Markov property, which states that the probability of transitioning to a particular state depends only on the current state, not on the history of previous states
• Markov chains are discrete-time processes, where state transitions occur at fixed time intervals (e.g., hourly, daily, weekly)
• They are widely used in various fields, including engineering, finance, biology, and computer science, to model and analyze systems with uncertain or probabilistic behavior
• Markov chains can be represented using transition matrices or state diagrams, which describe the probabilities of moving from one state to another

Key Concepts and Terminology

• State: A distinct condition or configuration of the system being modeled by the Markov chain
• State space: The set of all possible states in a Markov chain
• Transition probability: The probability of moving from one state to another in a single time step, denoted as $p_{ij}$ for the probability of transitioning from state $i$ to state $j$
• Transition matrix: A square matrix that contains all the transition probabilities between states in a Markov chain, with rows representing the current state and columns representing the next state
• Initial state distribution: A vector that describes the probability of the system starting in each state at time $t=0$
• Stationary distribution: A probability distribution over the states that remains unchanged as the Markov chain evolves over time, denoted as $\pi$
• Absorbing state: A state that, once entered, cannot be left; it has a self-transition probability of 1 and zero probability of transitioning to any other state
• Ergodic Markov chain: A Markov chain where it is possible to reach any state from any other state in a finite number of steps

Properties of Markov Chains

• Memoryless property: The future state of a Markov chain depends only on the current state, not on the sequence of states that preceded it
  • This property simplifies the analysis and computation of Markov chains, as we only need to consider the current state to determine the probabilities of future states
• Time-homogeneous: The transition probabilities between states remain constant over time, meaning they do not change as the process evolves
• Irreducibility: In an irreducible Markov chain, it is possible to reach any state from any other state in a finite number of steps
• Periodicity: A state is periodic if it can only be revisited at regular intervals; otherwise, it is aperiodic
  • The periodicity of a Markov chain affects its long-term behavior and convergence properties
• Recurrence: A state is recurrent if, starting from that state, the chain will eventually return to it with probability 1; otherwise, it is transient
• Ergodicity: An ergodic Markov chain is both irreducible and aperiodic, and it has a unique stationary distribution

Transition Matrices and State Diagrams

• Transition matrices provide a compact representation of the transition probabilities between states in a Markov chain
  • The entry in the $i$-th row and $j$-th column, denoted as $p_{ij}$, represents the probability of transitioning from state $i$ to state $j$ in a single time step
  • The rows of a transition matrix must sum to 1, as they represent the total probability of transitioning from a given state to all possible next states
• State diagrams offer a visual representation of a Markov chain, with nodes representing states and directed edges representing transitions between states
  • The edges are labeled with the corresponding transition probabilities
  • State diagrams help in understanding the structure and behavior of the Markov chain, especially for small-scale systems
• The powers of the transition matrix, denoted as $P^n$, give the probabilities of transitioning between states after $n$ time steps
• The long-term behavior of a Markov chain can be determined by analyzing the properties of its transition matrix, such as eigenvalues and eigenvectors

Types of Markov Chains

• Finite-state Markov chains: Markov chains with a finite number of states in their state space
• Infinite-state Markov chains: Markov chains with an infinite number of states, often used to model systems with unbounded or continuous state spaces
• Absorbing Markov chains: Markov chains that contain one or more absorbing states, which are states that once entered, cannot be left
  • The analysis of absorbing Markov chains focuses on determining the probability and expected time to reach an absorbing state from any given initial state
• Ergodic Markov chains: Markov chains that are both irreducible and aperiodic, and have a unique stationary distribution
  • In the long run, an ergodic Markov chain will spend a fixed proportion of time in each state, regardless of the initial state distribution
• Time-inhomogeneous Markov chains: Markov chains where the transition probabilities between states change over time, in contrast to time-homogeneous Markov chains
• Higher-order Markov chains: Markov chains where the future state depends on a fixed number of previous states, rather than just the current state (e.g., second-order Markov chains)

Solving Markov Chain Problems

• Determine the transition matrix: Identify the states and calculate the transition probabilities between them to construct the transition matrix
• Analyze the properties of the Markov chain: Determine whether the chain is irreducible, aperiodic, and ergodic by examining the transition matrix and state diagram
• Calculate the n-step transition probabilities: Use the Chapman-Kolmogorov equations or matrix powers to find the probabilities of transitioning between states after $n$ time steps
  • The Chapman-Kolmogorov equations state that the $n$-step transition probability can be found by summing the products of the $k$-step and $(n-k)$-step transition probabilities over all intermediate states
• Find the stationary distribution: For ergodic Markov chains, solve the system of linear equations $\pi P = \pi$ to find the unique stationary distribution $\pi$
  • The stationary distribution represents the long-term proportion of time the chain spends in each state
• Compute absorption probabilities and expected times: For absorbing Markov chains, use the fundamental matrix to calculate the probability of reaching an absorbing state and the expected time to absorption from any given initial state
• Apply first-step analysis: Break down complex problems into smaller subproblems by conditioning on the first step of the Markov chain and then using the Markov property to simplify the calculations

Real-World Applications

• Speech recognition: Markov chains are used to model the probability of transitioning between phonemes or words in spoken language, enabling more accurate speech recognition systems
• Weather forecasting: Markov chains can model the transitions between different weather states (e.g., sunny, cloudy, rainy) to predict future weather patterns
• Financial modeling: Markov chains are used to model the behavior of financial markets, such as stock prices or exchange rates, and to assess investment risks
• Biology: Markov chains can model the evolution of DNA sequences, the spread of diseases, or population dynamics in ecosystems
• Machine learning: Markov chains are the foundation for more advanced models, such as hidden Markov models (HMMs) and Markov decision processes (MDPs), which are used in various machine learning applications
• Web search engines: Markov chains are used in algorithms like PageRank to rank web pages based on their importance and relevance to search queries
• Queueing theory: Markov chains can model the behavior of queueing systems, such as customer service centers or manufacturing lines, to analyze waiting times and system performance

Practice Problems and Examples

• Example 1: A weather system has three states: sunny (S), cloudy (C), and rainy (R). The transition probabilities between these states are given by the following matrix:

  	S	C	R
  S	0.6	0.3	0.1
  C	0.4	0.4	0.2
  R	0.2	0.5	0.3

  Find the probability of having a sunny day after two days, given that today is cloudy.

• Example 2: A factory produces items that can be either defective (D) or non-defective (N). The quality control process is modeled as a Markov chain with the following transition matrix:

  	D	N
  D	0.2	0.8
  N	0.1	0.9

  If the factory starts with a non-defective item, what is the probability that the third item produced will be defective?

• Example 3: A social media user can be in one of three states: browsing (B), posting (P), or inactive (I). The transition probabilities between these states are given by the following matrix:

  	B	P	I
  B	0.5	0.3	0.2
  P	0.4	0.4	0.2
  I	0.3	0.1	0.6

  Find the stationary distribution of this Markov chain.

• Example 4: A gambler plays a game where they win $1 with probability 0.4 and lose$1 with probability 0.6. The gambler starts with $5 and decides to play until they either lose all their money or reach a total of$10. Model this situation as an absorbing Markov chain and find the probability that the gambler will reach $10 before going broke.