Discrete-Time Markov Chains

Introduction and Context

A discrete-time Markov chain is a stochastic model for a system that evolves through a finite or countable set of states at successive time points. Its defining assumption is that, conditional on the present state, the distribution of the next state does not depend on the detailed history of the process. This is the Markov property:

Here, X_t is the state of the system at time t, and i and j are possible states. The model is discrete-time because transitions occur at integer periods such as months, quarters, or years.

Markov chains are especially useful in business analytics when the current condition of a customer, borrower, machine, or market segment provides a meaningful summary of its relevant past. Applications include customer migration, credit-rating transitions, workforce planning, inventory status, equipment reliability, website navigation, and brand switching.

The Markov assumption is a modeling approximation, not a universal law. It should be tested against domain knowledge and data. If customer tenure, accumulated debt, or previous transitions materially affects future behavior, an ordinary first-order Markov chain may be inadequate.

Learning Objectives

By the end of this chapter, you should be able to:

1. Construct and interpret a transition matrix.
2. Calculate multi-step transition probabilities.
3. Classify states as transient, recurrent, absorbing, or periodic.
4. Identify communicating classes and determine whether a chain is irreducible.
5. Calculate first-passage and absorption probabilities and expected times.
6. Find stationary distributions and interpret long-run behavior.
7. Apply Markov chains to customer migration and credit-rating analysis.
8. Evaluate assumptions, governance risks, and limitations in business applications.

1. States, Transitions, and Transition Matrices

Let the state space be S={1,2,…,m} for a finite chain. The one-step transition probability from state i to state j is

For every state i, probabilities must satisfy

The transition matrix is

Each row represents the current state and each column represents the next state. Thus, P is row-stochastic. A column-stochastic convention is also used in some disciplines, but analysts must state the convention explicitly and use it consistently.

If the initial state distribution is a row vector

then the distribution after n periods is

where Pⁿ is the nth matrix power. The probability of moving from state i to state j in n steps is the (i,j) entry of Pⁿ.

Example 1: A customer-migration matrix

Suppose customers are classified as Basic, Premium, or Lost. Based on historical monthly data, the transition matrix is

The first row means that a Basic customer remains Basic with probability 0.70, upgrades with probability 0.25, and is lost with probability 0.05. Lost is absorbing: once a customer is classified as Lost, the model assumes that the customer does not return.

If all customers begin as Basic, then π⁽⁰⁾=(1,0,0). After one month,

Thus, 5% are expected to be lost after one month under the model.

2. Multi-Step Probabilities and the Chapman–Kolmogorov Relationship

The Chapman–Kolmogorov relationship states that an (r+s)-step transition probability can be obtained by summing over the intermediate state:

For a time-homogeneous chain, where transition probabilities do not change with time,

with n factors. Time homogeneity is an assumption. If economic conditions or marketing policies change, the chain may instead require matrices P₀,P₁,… that vary by period.

For the customer example, the probability that a Basic customer is Premium after two months is

The three terms correspond to being Basic, Premium, or Lost after the first month. Therefore, the two-month probability is 0.375.

3. Communication and Classification of States

State i communicates with state j, written i↔j, if each is reachable from the other in some finite number of steps. State j is reachable from i if p_ij⁽ⁿ⁾>0 for at least one n≥0.

Communication is an equivalence relation, so it partitions the state space into communicating classes. A class is closed if no transition leads from a state in the class to a state outside it. A chain is irreducible if all states communicate with one another; equivalently, it has one communicating class.

A state is:

• Absorbing if p_ii=1.
• Transient if, once left, there is a positive probability of never returning.
• Recurrent if the probability of eventual return is 1.
• Positive recurrent if its expected return time is finite.
• Null recurrent if it is recurrent but has infinite expected return time.
• Periodic with period d if returns to the state can occur only at multiples of d, where d is the greatest common divisor of all possible positive return times.
• Aperiodic if its period is 1.

For a finite Markov chain, every recurrent class is positive recurrent. In a finite irreducible chain, all states are positive recurrent. A finite chain may still contain transient states, as the Basic and Premium states do in the customer example because they can eventually move to the closed Lost state.

An absorbing state is a special case of a recurrent state. An absorbing chain contains at least one absorbing state, and every state can reach an absorbing state in the usual definition used in applications.

Why classification matters

Classification determines whether long-run proportions exist, whether a system eventually exits a state, and whether an intervention can have a permanent effect. For example, a closed class of high-risk credit ratings may indicate persistent risk, while an absorbing “default” state may be suitable for a lifetime-loss model but unsuitable if recovery is possible.

4. First-Passage and Hitting Times

The first-passage time from state i to state j is

when the process starts in state i. For a target set A, define

The hitting probability is h_i=P_i(T_A<∞). For a target state j, these probabilities satisfy

with boundary condition h_j=1. If some states cannot reach the target, their appropriate boundary value is 0.

The expected hitting time m_i=E_i[T_A] satisfies, for states outside A,

with m_i=0 for i∈A. The added 1 counts the first transition. These equations are solved simultaneously.

Absorbing-chain matrix method

Reorder the states so transient states come first and absorbing states last. The transition matrix then has canonical form

where Q contains transitions among transient states, R contains transitions from transient to absorbing states, I is the identity matrix, and the zero block represents the impossibility of leaving an absorbing state.

The fundamental matrix is

provided absorption occurs with probability 1. The entry N_ij is the expected number of visits to transient state j when starting in transient state i, including the initial visit.

The matrix of absorption probabilities is

and the vector of expected times to absorption is

where 1 is a column vector of ones.

Example 2: A simple risk-transition model

Consider transient states Healthy and Stressed, with Default absorbing:

Here,

The determinant of I-Q is

so

Consequently,

This result is impossible because absorption probabilities cannot exceed 1. The reason is that the proposed transition matrix is not valid: the second row sums to 1.00, but the first row also sums to 1.00; checking the calculation reveals that det(I-Q)=(0.20)(0.30)−(−0.15)(−0.10)=0.045, while multiplication gives first entry 6.6667(0.05)+3.3333(0.20)=1.0000, not 0.6667. Thus

Both transient states eventually lead to Default with probability 1. The example illustrates an important validation practice: absorption probabilities must lie between 0 and 1 and each row of B must sum to 1 when absorption is certain.

The expected time to default is

Therefore, the expected time to default is 10 periods from Healthy and approximately 6.67 periods from Stressed, under the model assumptions.

5. Stationary Distributions and Long-Run Behavior

A probability vector π=(π₁,…,π_m) is stationary if

The stationary distribution is an equilibrium distribution: if π⁽⁰⁾=π, then π⁽ⁿ⁾=π for every n. It does not necessarily describe the distribution at a particular finite time, nor does every initial distribution necessarily converge to it.

For a finite irreducible chain, at least one stationary distribution exists and is unique. If the chain is also aperiodic, then

where 1 is a column vector of ones and every row of the limiting matrix equals π. Consequently, π⁽⁰⁾Pⁿ→π for every initial distribution. This is the standard ergodic long-run result.

If a chain is irreducible but periodic, a stationary distribution still exists, but ordinary convergence of Pⁿ may fail because probabilities oscillate. Time averages may nevertheless converge under standard finite-state conditions.

If a chain has multiple closed classes, the long-run result can depend on the initial state. A single stationary distribution may not summarize all possible behavior. In an absorbing chain, stationary distributions are concentrated on absorbing classes; they do not generally describe transient-period operating performance.

Solving for a stationary distribution

For a two-state chain

where 0<a,b≤1, let π=(π₁,π₂). Solving πP=π and π₁+π₂=1 gives

The formula applies to this irreducible two-state model. It should not be used when one of a or b is zero without separately analyzing absorbing or non-irreducible behavior.

6. Business Application: Customer Migration

Customer migration models estimate how accounts move among segments such as low-value, standard, premium, dormant, and churned. A transition matrix supports:

• forecasting segment populations;
• estimating customer lifetime and churn;
• valuing retention campaigns;
• planning service capacity;
• comparing acquisition and retention strategies.

Suppose a firm has 100,000 customers, with 60% Basic, 30% Premium, and 10% Lost or inactive. If the firm applies a monthly transition matrix, the expected segment counts after one period are obtained by multiplying the row vector of counts by P. Expected counts need not be integers; they represent averages across repeated or hypothetical populations.

A key managerial distinction is between descriptive and prescriptive use. A historical matrix describes observed migration. It does not prove that a marketing intervention caused an upgrade. To estimate intervention effects, analysts should use experiments, causal models, or carefully designed quasi-experimental methods.

Customer models also require attention to censoring and observation windows. A customer labeled “churned” may return later, and a short observation period may understate eventual churn. The state definition should therefore reflect the business decision and the data-generating process.

7. Business Application: Credit Ratings

Credit-rating agencies and banks often model transitions among ratings such as AAA, AA, A, BBB, speculative grade, and Default. A one-year transition matrix can support expected-loss analysis, portfolio stress testing, capital planning, and scenario analysis.

If exposure at default is EAD, loss-given-default is LGD, and the probability of default over a specified horizon is PD, a simplified expected-loss calculation is

The units are monetary units because PD and LGD are dimensionless proportions and EAD is monetary exposure. A Markov chain can estimate PD over multiple periods through the relevant entry of Pⁿ, but the simplified formula assumes that the probability, loss severity, and exposure definition are compatible with the same horizon and portfolio scope.

Credit models often require a time-inhomogeneous or macroeconomic regime-switching structure. Transition probabilities during a recession may differ substantially from those during expansion. A single long-run average matrix can conceal this variation and understate tail risk.

8. Detailed Illustrative Case: Subscription-Service Retention

Background

A fictional subscription company classifies accounts as Trial, Standard, Premium, and Churned. Management wants to estimate the effect of a retention program and determine whether the program changes long-run customer value.

Problem

Historical monthly data produce a transition matrix. However, the data combine customers who received different offers, and the Churned state is treated as absorbing even though some customers reactivate.

Analysis

The analytics team first verifies row sums, missing-state definitions, and the observation window. It separates customers by treatment exposure and estimates matrices for the treatment and comparison groups. It also creates a Reactivated state rather than assuming permanent churn.

The team calculates P⁶ to forecast six-month segment distributions and uses the fundamental matrix to estimate expected time before churn for each starting segment. It compares results with a survival model that includes tenure and customer characteristics. The Markov model is attractive for operational forecasting, whereas the survival model better captures duration dependence.

Approach and solution

Management adopts a segmented, time-inhomogeneous model:

• one matrix for ordinary months;
• a recession matrix for adverse economic conditions;
• separate matrices for treatment and comparison groups;
• a nonabsorbing reactivation state;
• quarterly recalibration and out-of-sample validation.

The company reports both transition probabilities and uncertainty intervals, rather than presenting point forecasts as facts.

Outcome

The retention program appears to reduce immediate churn, but its effect is smaller for long-tenure customers because their baseline churn was already low. The revised model predicts greater reactivation than the original absorbing model and produces more realistic lifetime-value estimates.

Learning points

1. State definitions determine managerial conclusions.
2. A convenient absorbing state may be substantively wrong.
3. Historical transitions do not automatically identify causal effects.
4. Segmenting by treatment and economic regime can improve decision relevance.
5. Model validation must include both arithmetic checks and business plausibility checks.

9. Estimation, Validation, and Implementation

For observed transitions, the maximum-likelihood estimate of p_ij is

where N_ij is the number of observed transitions from i to j, and N_i=∑_jN_ij. This estimator assumes transitions are appropriately sampled and that the relevant transition mechanism is stable over the estimation period.

Small samples can produce unstable estimates, especially for rare transitions such as default. Analysts may use Bayesian smoothing, pooling across similar states, or hierarchical models, but these methods introduce assumptions that must be documented.

Validation should include:

• row-sum and nonnegativity checks;
• comparison of predicted and observed migration counts;
• back-testing across time periods;
• sensitivity analysis under alternative state definitions;
• confidence or credible intervals;
• stress testing under adverse regimes;
• monitoring for drift after deployment.

Software implementation should preserve the state order, matrix convention, data dictionary, estimation period, and version history. A numerically correct matrix can still produce an incorrect forecast if rows and columns are accidentally reversed.

10. Limitations, Ethics, and Governance

The Markov property may fail when history matters beyond the current state. Examples include customer tenure, repeated missed payments, cumulative product usage, and prior complaints. Higher-order chains, expanded states, semi-Markov models, hidden Markov models, or covariate-based transition models may be more appropriate.

Other limitations include:

• State aggregation: materially different customers may be grouped together.
• Nonstationarity: probabilities may change with prices, regulation, competition, or economic conditions.
• Selection bias: observed transitions may reflect who remains observable.
• Rare events: limited default or churn observations create high uncertainty.
• Feedback effects: decisions based on predictions can change future transitions.
• Absorbing-state assumptions: recovery or reactivation may be ignored.

In credit and customer analytics, governance is especially important. A transition model may influence pricing, credit access, service quality, or collections. Analysts should assess disparate impact across protected groups, document legitimate business purposes, protect personal data, and provide appropriate explanations. A model should not be treated as objective merely because it is expressed as a matrix. Historical discrimination can be encoded in transition estimates.

Artificial intelligence can assist with feature engineering, anomaly detection, and drift monitoring, but it does not remove the need for transparent state definitions, causal reasoning, validation, and human oversight. More complex predictive systems should be compared with interpretable Markov benchmarks rather than adopted solely for marginal accuracy gains.

Chapter Summary

A discrete-time Markov chain models movement among states at successive periods under the assumption that the current state contains the relevant information needed to determine the next-state distribution. Its transition matrix is row-stochastic, and matrix powers provide multi-step probabilities. Communicating classes reveal structural connectivity, while transient, recurrent, absorbing, and periodic classifications determine long-run behavior. First-passage equations and the fundamental matrix quantify hitting probabilities, expected visits, and expected absorption times. Stationary distributions describe equilibrium behavior, with convergence requiring suitable irreducibility and aperiodicity conditions. In business analytics, Markov chains support customer migration, credit-rating, reliability, and workforce models. Their usefulness depends on valid state definitions, appropriate estimation, careful validation, and governance of causal, ethical, and nonstationary risks.

Key Terms

Markov property: The next-state distribution depends on the current state, not the full prior history.

State: A condition or category occupied by the modeled system.

State space: The set of all possible states.

Transition probability: The probability of moving from one state to another in one period.

Transition matrix: A matrix containing one-step transition probabilities.

Row-stochastic matrix: A matrix whose entries are nonnegative and whose rows sum to one.

Communicating states: Two states each reachable from the other.

Communicating class: A maximal set of mutually communicating states.

Closed class: A class from which no transition leads outside the class.

Irreducible chain: A chain in which every state communicates with every other state.

Transient state: A state that may be left permanently.

Recurrent state: A state to which the process eventually returns with probability one.

Absorbing state: A state that, once entered, cannot be left.

Period: The greatest common divisor of possible positive return times.

First-passage time: The first time the process reaches a specified state or set.

Stationary distribution: A probability distribution unchanged by multiplication by the transition matrix.

Fundamental matrix: N=(I−Q)^{-1 for the transient block of an absorbing chain.

Time-homogeneous chain: A chain whose transition probabilities do not vary with time.

Time-inhomogeneous chain: A chain whose transition probabilities vary across periods.

Review Questions

Short Answer Questions

1. State the Markov property in words and mathematical notation.
2. Why must every row of a transition matrix sum to one?
3. Distinguish an absorbing state from a transient state.
4. What does a stationary distribution represent?
5. Define a closed communicating class.

Long Answer Questions

1. Explain how Pⁿ is used to obtain multi-period forecasts. Include the assumptions required for this interpretation.
2. Describe the classification of states in a finite Markov chain and explain why classification matters for long-run analysis.
3. Derive the equations for expected first-passage times to a target set.
4. Explain the canonical form of an absorbing-chain transition matrix and interpret the fundamental matrix.
5. Critically evaluate the use of a Markov chain for credit-rating migration.

Analytical / Application Questions

1. A three-state customer chain has states Active, Dormant, and Churned, with Churned absorbing. Explain how you would calculate the probability of churn within six periods and the expected time to churn.
2. A transition matrix estimated during an economic expansion is used to forecast defaults during a recession. Identify the modeling risks and propose a validation and stress-testing strategy.
3. A retention campaign changes customers’ transition probabilities. Explain why comparing transition matrices before and after the campaign may not establish causality, and design a stronger evaluation approach.

Multiple Choice Questions with Answers

Question 1

Which condition defines the Markov property?

A. The process must have exactly two states.

B. The next-state distribution depends only on the current state.

C. Every state must eventually become absorbing.

D. All transition probabilities must be equal.

Correct Answer: B. The next-state distribution depends only on the current state.

Question 2

In a row-stochastic transition matrix, what does row i represent?

A. Probabilities of previous states given state i

B. Long-run frequencies only

C. Probabilities of next states conditional on current state i

D. Expected time spent in each state

Correct Answer: C. Probabilities of next states conditional on current state i

Question 3

If π^(0) is a row-vector initial distribution, which expression gives the distribution after n periods?

A. π^(0)+P^n

B. P^n−π^(0)

C. π^(0)P^n

D. Pπ^(0)P

Correct Answer: C. π^(0)P^n

Question 4

A state i is absorbing when:

A. p_ii=0

B. p_ii=1

C. p_ij=1 for every j

D. It communicates with no state

Correct Answer: B. p_ii=1

Question 5

What is required for a finite chain to be irreducible?

A. Every state must be absorbing.

B. There must be no transient states.

C. Every state must communicate with every other state.

D. The matrix must be diagonal.

Correct Answer: C. Every state must communicate with every other state.

Question 6

For an absorbing chain with transient block Q, the fundamental matrix is:

A. N=Q−I

B. N=I+Q

C. N=(I−Q)^−1

D. N=R−Q

Correct Answer: C. N=(I−Q)^−1

Question 7

Which equation characterizes a stationary distribution π?

A. πP=π

B. Pπ=0 only

C. π+P=1

D. πP=Pπ for every vector π

Correct Answer: A. πP=π

Question 8

For a two-state chain with transition probabilities a from state 1 to 2 and b from state 2 to 1, the stationary probability of state 1 is:

A. a/(a+b)

B. b/(a+b)

C. 1−a−b

D. ab

Correct Answer: B. b/(a+b)

Question 9

If p̂_ij=N_ij/N_i, what does N_i represent?

A. The number of states in the model

B. The number of observed transitions from state i

C. The number of absorbing states

D. The number of periods in the forecast

Correct Answer: B. The number of observed transitions from state i

Question 10

Why can a historical transition matrix fail to measure the causal effect of a retention campaign?

A. Transition matrices cannot contain probabilities.

B. The campaign may be associated with customer selection and other confounding factors.

C. Matrix powers always eliminate treatment effects.

D. Causal effects require an absorbing state.

Correct Answer: B. The campaign may be associated with customer selection and other confounding factors.