InteractiveMap of Operations Research
Back to Uncertainty & Stochastic Systems
TheoryIntermediate03.09
Uncertainty & Stochastic Systems

Markov Chains

State-to-state stochastic models without decisions.

Overview

Markov chains describe random movement among states when the next state depends on the current state. They are foundational for stochastic-process chapters in OR textbooks and sit naturally before Markov decision processes.

They support steady-state, transient, and absorbing-state analysis for systems such as machine condition, customer migration, queues, inventory status, and service reliability.

Core ideas

Transition matrix

The transition matrix stores the probabilities of moving from each state to each possible next state.

State classification

State classification distinguishes recurrent, transient, absorbing, periodic, and communicating states.

Steady state

Steady-state probabilities describe long-run state occupancy when the chain satisfies the needed conditions.

Absorbing states

Absorbing states model endpoints such as failure, churn, completion, or default.

First passage

First-passage quantities estimate the time or probability of reaching a target state.

How to use it

  1. 1Define states so the current state contains enough information to describe the next transition.
  2. 2Estimate or elicit transition probabilities and check that each row is valid.
  3. 3Decide whether the question is transient, steady-state, absorbing, or first-passage.
  4. 4Validate transition assumptions against historical movements or domain judgment.
  5. 5Use the Markov chain as a stochastic input to queues, reliability, inventory, or MDP models when decisions enter.

Applications

ReliabilityCustomer migrationInventoryQueuesWeb ranking
  • Reliability: model degradation, repair, and failure states.
  • Customer migration: estimate churn, retention, and segment movement.
  • Inventory: describe stock-level transitions under random demand.
  • Queues: analyze embedded state transitions at arrival or departure epochs.
  • Web ranking: interpret random walks over linked pages or network states.

Common pitfalls

  • Defining states that omit important history, violating the Markov property.
  • Using steady-state probabilities before checking whether a limiting distribution is meaningful.
  • Estimating transition probabilities from sparse data without uncertainty checks.
  • Confusing Markov chains with MDPs; chains describe random movement, MDPs add controllable actions.

Resources