Markov Chains
Open in the Padhaiko app5.1 Key features of Markov chains
A stochastic process is a family of random variables indexed by time . When the index set is discrete () and the state space is finite or countable, a process that satisfies the memoryless (Markov) property is called a discrete-time Markov chain (DTMC).
Markov Property and Transition Matrix
A stochastic process taking values in state space is a Markov chain if for all and all states :
In words, the future state depends only on the present state , not on the past history. For a time-homogeneous chain, the one-step transition probabilities form an stochastic transition probability matrix satisfying:
- Non-negativity: for all .
- Row normalization: for every row .
Multi-Step Transitions and Chapman–Kolmogorov Equations
Chapman–Kolmogorov Equations & n-Step Matrix
Let denote the -step transition probability from state to state . Summing over all intermediate states after steps yields:
which in matrix form simply means the -step transition matrix is the -th matrix power of :
Furthermore, if the initial probability row vector is , then the state probability vector after steps is:
Classification of States and Chains
| Term | Definition |
|---|---|
| Accessible / Communicating States | State is accessible from () if for some . If and , they communicate (). |
| Irreducible Chain | Every state communicates with every other state (only one communication class). |
| Absorbing State | A state with (and for ): once entered, it can never be left. |
| Recurrent vs. Transient State | A state is recurrent if, starting from , the chain is certain to return to (probability ); otherwise it is transient (may never return). |
| Periodicity & Aperiodic State | The period . If , state is aperiodic. |
| Ergodic Chain | An irreducible, aperiodic, positive-recurrent Markov chain; guaranteed to converge to a unique steady-state distribution independent of initial state. |
Steady-State (Stationary) Distribution
For an ergodic Markov chain, as , every row of converges to the same limiting probability row vector , which satisfies the stationary balance equations:
Here represents both the long-run probability of being in state and the long-run fraction of time the process spends in state .
5.2 Markov process with examples
A Markov process generalizes the Markov property to either discrete time (Markov chains) or continuous time (Continuous-Time Markov Chains — CTMCs, where holding times in each state are exponentially distributed with transition rate matrix ).
Classic Markov Chain Examples
- Two-State Weather / Channel Model: Each day is either Sunny () or Rainy (), with . Knowing today's weather determines tomorrow's probability distribution without needing last week's history.
- Gambler’s Ruin / Absorbing Random Walk: A player bets per round with fortune . States (bankrupt) and (target reached) are absorbing states, while are transient states. Arranging the transition matrix in canonical form with absorbing states first and transient states second:
the fundamental matrix is :
- Entry gives the expected number of visits to transient state starting from transient state .
- Expected steps until absorption from state : row sum .
- Absorption probability matrix into absorbing states: .
- Continuous-Time Markov Process (Birth–Death Process): Used to derive and queuing systems, where arrivals occur at rate and departures at rate , and exponentially distributed holding times preserve the Markov property continuously in time.
5.3 Applications of Markov chains
Markov chains are among the most versatile modeling tools across computer engineering, operations research, and data science:
| Domain | States & Transitions | Key Metric Computed |
|---|---|---|
| Computer & Network Queuing | Queue occupancy ; arrival/departure events | Steady-state buffer overflow probability , throughput, utilization |
| Web Search (PageRank) | Web pages as states; hyperlinks as transition probabilities (plus random teleportation) | Stationary distribution gives page authority/rank |
| Hardware Reliability & Availability | System status (Active, Degraded, Failed/Repair); failure & repair probabilities | Long-run uptime availability and mean time to failure |
| Brand Switching & Market Share | Customer brand choices per month; loyalty vs. switching matrix | Equilibrium market shares |
| Speech Recognition & Bioinformatics (HMMs) | Hidden phoneme or DNA motif states emitting observed symbols | Most likely hidden state sequence (Viterbi / Forward-Backward) |
| Inventory Control | End-of-day stock level under replenishment | Expected holding cost and stockout probability |
Worked Out Examples
1
Two mobile telecom providers, Operator A and Operator B, compete in a city. Each month, of Operator A's subscribers stay with A and switch to B, while of Operator B's subscribers stay with B and switch to A.
- Write the one-step transition matrix and find the two-step transition matrix .
- If a subscriber starts with Operator A in Month (), what is the probability she uses Operator A after months?
- Find the long-run steady-state market shares .
Forming and computing : Ordering states as :
State distribution after 2 months:
So the probability of using Operator A after months is ().
Solving with :
Using normalization :
- , .
- Probability of Operator A after months: ().
- Steady-state market shares: () and ().
2
At the end of each day, a compute server is classified into one of three states: Healthy (), Degraded (), or Down (). Its daily transition matrix is:
Determine the steady-state probability vector and the long-run percentage of days the server is Healthy.
Writing the stationary balance equations :
Solving any two independent balance equations with :
From the first equation (dividing by ):
Substitute into the second equation:
Then .
Normalizing to find :
Hence and .
The steady-state distribution is . In the long run, the server is Healthy of the time.
3
A software project moves weekly among four states: Deployed () and Cancelled () (absorbing), and Coding () and Testing () (transient), with canonical transition matrix:
Starting in Coding ():
- Find the fundamental matrix .
- Find the expected number of weeks before the project finishes (absorption).
- Find the probability that the project ends up Deployed ().
Computing the fundamental matrix :
Computing expected time to absorption: Summing the first row of (for starting state Coding):
Computing absorption probabilities :
Entry is the probability of Deployment starting from Coding.
- Fundamental matrix .
- Expected duration from Coding until absorption: .
- Probability of eventual Deployment from Coding: .
Exercises
Practice Exercises — Markov Chains
Define a Markov chain and the Markov property. Explain what makes a transition matrix stochastic, and distinguish between recurrent, transient, absorbing, and ergodic states/chains.
Markov Property and Stochastic Matrix: A discrete-time stochastic process satisfies the Markov property if . Its transition matrix is stochastic because every entry satisfies and every row sums to ().
State and Chain Classifications:
- Recurrent state: Guaranteed eventual return (return probability ).
- Transient state: Non-zero probability of never returning once left.
- Absorbing state: A state with self-transition that can never be exited.
- Ergodic chain: Irreducible (all states communicate), aperiodic (), and positive recurrent—ensuring a unique steady-state distribution .
A Markov chain is a memoryless discrete-time stochastic process governed by a non-negative row-stochastic transition matrix . Recurrent states are revisited with probability , transient states may be permanently left, absorbing states satisfy , and ergodic chains converge to a unique steady-state distribution.
State the Chapman–Kolmogorov equations for a discrete-time Markov chain and describe three real-world engineering applications of Markov chains.
Chapman–Kolmogorov Equations: For any , the -step transition probability satisfies:
Three Engineering Applications:
- PageRank / Web Graph Ranking: Models a random web surfer following links; the stationary vector ranks page importance.
- Hardware Reliability & Availability: Tracks states like Operational, Degraded, and Under Repair to compute long-run system availability.
- Network Queuing & Packet Buffers: Models packet occupancy transitions at discrete slots or continuous time to size buffers and bound packet loss.
The Chapman–Kolmogorov equations state (matrix power ). Key applications include Google PageRank, hardware availability modeling, and network buffer queuing analysis.
A wireless link is modeled as a two-state Markov chain with states Good () and Bad () each millisecond:
- If the link is Bad at , find the probability that it is Good at .
- Find the long-run steady-state probabilities and .
Computing and state distribution from Bad ():
Starting in Bad (), , so .
Computing steady-state probabilities:
With : , .
- ().
- Steady-state probabilities: and .
Find the steady-state probability distribution of the three-state Markov chain with transition matrix:
Setting up stationary equations :
Solving with : From the first equation:
Since , we immediately get , and . Substituting and into the second equation:
The steady-state probability distribution is .
In a two-stage packet processing pipeline, transient states and transition to an absorbing state (Completed) with submatrices:
Compute the fundamental matrix and find the expected number of time steps until completion starting from state .
Computing and its inverse :
Computing expected steps to completion from : Summing the first row of :
The fundamental matrix is , and the expected time until completion starting from is .