The Central Idea
Suppose a stochastic process is written
\[ \{X_n\}_{n\ge 0}, \]and each \(X_n\) takes values in a state space \(S\).
The process is a Markov chain when the next-state probabilities are determined by the present state once that present state is known.
\[ \boxed{ P(X_{n+1}=j\mid X_n=i,X_{n-1},\ldots,X_0) = P(X_{n+1}=j\mid X_n=i) }. \]This is the Markov property.
From State Spaces to Motion
A state space tells us the possible conditions of a stochastic system. A Markov chain adds rules describing how the system may move from one state to another.
For example, let
\[ S=\{\text{Sunny},\text{Cloudy},\text{Rainy}\}. \]The state space alone lists the possible weather conditions. A Markov model also assigns probabilities such as
\[ P(\text{Cloudy tomorrow}\mid\text{Sunny today})=0.25. \]Those conditional probabilities define the local evolution of the chain.
Why the Current State Matters
The current state is the information retained by the model for predicting the next step.
If the process is currently in state \(i\), then the chain uses the probabilities associated with state \(i\) to determine where it goes next.
The past may explain how the process reached \(i\), but under the Markov assumption it does not provide additional information about the next state once \(i\) is known.
The Markov Property Is Conditional
The Markov property does not say that successive states are independent.
In fact, the next state usually depends strongly on the current state.
What the property says is that, conditional on the present state, earlier states do not further change the probability distribution of the next state.
A Two-State Example
Consider a machine that is either
\[ S=\{W,F\}, \]where \(W\) means working and \(F\) means failed.
Suppose a working machine remains working for the next period with probability \(0.96\) and fails with probability \(0.04\).
If a failed machine is repaired before the next observation with probability \(0.70\), then
\[ P(W\mid F)=0.70,\qquad P(F\mid F)=0.30. \]These four probabilities describe one-step movement between the two states.
Transition Probabilities
For states \(i\) and \(j\), the one-step transition probability is commonly written
\[ \boxed{p_{ij}=P(X_{n+1}=j\mid X_n=i)}. \]The first subscript identifies the state we are leaving. The second identifies the state we are entering.
Thus, \(p_{ij}\) means from \(i\) to \(j\).
Outgoing Probabilities Must Sum to One
If the chain is currently in state \(i\), the next state must be somewhere in the state space.
Therefore, for a finite or countable state space,
\[ \boxed{\sum_{j\in S}p_{ij}=1}. \]Each individual transition probability must also satisfy
\[ 0\le p_{ij}\le 1. \]Example: Checking Transition Probabilities
Suppose a chain has states \(A,B,C\). From state \(A\), the proposed transition probabilities are
\[ p_{AA}=0.20,\qquad p_{AB}=0.50,\qquad p_{AC}=0.30. \]Their sum is
\[ 0.20+0.50+0.30=1. \]Therefore, these values form a valid probability distribution for the next state conditional on currently being in \(A\).
Self-Transitions
A Markov chain does not have to change states at every step.
A transition from a state back to itself is called a self-transition.
\[ p_{ii}=P(X_{n+1}=i\mid X_n=i). \]For example, if a customer remains subscribed from one month to the next with probability \(0.92\), then the subscribed state has a self-transition of \(0.92\).
Transition Diagrams
A Markov chain can be represented by a directed graph called a transition diagram.
- Each node represents a state.
- An arrow from \(i\) to \(j\) represents a possible transition.
- The arrow is labeled with \(p_{ij}\).
- A self-loop represents a possible self-transition.
The diagram makes the structure of the chain visible before any matrix calculations are introduced.
A Transition Table
The same information may be organized in a table.
| Current State | Next \(A\) | Next \(B\) |
|---|---|---|
| \(A\) | \(0.8\) | \(0.2\) |
| \(B\) | \(0.3\) | \(0.7\) |
Each row is a conditional probability distribution for the next state.
Time-Homogeneous Markov Chains
A Markov chain is time-homogeneous when its transition probabilities do not depend on the time index.
\[ P(X_{n+1}=j\mid X_n=i)=p_{ij} \]for every relevant \(n\).
In such a model, the same transition rules are applied at every step.
Time-Inhomogeneous Markov Chains
A Markov chain may still satisfy the Markov property even when transition probabilities change over time.
In that case we may write
\[ p_{ij}^{(n)} = P(X_{n+1}=j\mid X_n=i). \]The dependence is still only on the current state for the next-step prediction, but the transition rule itself may vary with \(n\).
Example: Seasonal Transition Rules
Suppose a demand model has states
\[ S=\{\text{Low},\text{High}\}. \]The probability that high demand remains high may be \(0.80\) during a peak season and \(0.55\) during an off-season.
Such a model can remain Markov while failing to be time-homogeneous.
Initial State
A Markov chain must also begin somewhere.
If the starting state is known exactly, we may specify
\[ X_0=i. \]If the starting state is uncertain, we assign an initial distribution such as
\[ P(X_0=A)=0.60,\qquad P(X_0=B)=0.40. \]The initial condition and the transition rule together determine the probabilistic evolution of the chain.
A Markov Chain Is More Than Its Transition Rule
Two chains can use the same transition probabilities but have different probability distributions at early times because they begin from different initial conditions.
A complete finite-state Markov model therefore identifies at least:
- the state space;
- the initial state or initial distribution;
- the transition probabilities.
Path Probabilities
A Markov chain generates random sequences of states.
Suppose we want the probability of the path
\[ i_0\to i_1\to i_2\to\cdots\to i_k. \]If the starting state \(i_0\) is known, the Markov property gives
\[ \boxed{ P(X_1=i_1,\ldots,X_k=i_k\mid X_0=i_0) = \prod_{r=0}^{k-1}p_{i_r i_{r+1}} }. \]Example: Probability of a Specific Path
Suppose
\[ p_{AB}=0.40,\qquad p_{BC}=0.50,\qquad p_{CA}=0.30. \]Starting from \(A\), the probability of the three-step path
\[ A\to B\to C\to A \]is
\[ 0.40(0.50)(0.30)=0.06. \]The path probability is the product of the transition probabilities along that path.
Two-Step Transitions
A chain may reach the same destination through several intermediate states.
The two-step probability of moving from \(i\) to \(j\) is found by summing over all possible intermediate states \(k\):
\[ \boxed{ P(X_{n+2}=j\mid X_n=i) = \sum_{k\in S} p_{ik}p_{kj} }. \]This is the probability version of multiply along a path, then add across alternative paths.
Example: A Two-Step Calculation
Consider states \(A\) and \(B\) with
\[ p_{AA}=0.8,\quad p_{AB}=0.2,\quad p_{BA}=0.3,\quad p_{BB}=0.7. \]Starting from \(A\), the chain can be back in \(A\) after two steps through either
\[ A\to A\to A \]or
\[ A\to B\to A. \]Therefore,
\[ P(X_2=A\mid X_0=A) = (0.8)(0.8)+(0.2)(0.3) = 0.70. \]Why Multi-Step Probabilities Require Addition
Different intermediate states represent mutually exclusive ways of reaching the same final state.
For two steps,
\[ i\to k\to j \]gives a contribution \(p_{ik}p_{kj}\). Summing those contributions over all allowed \(k\) accounts for every possible two-step route from \(i\) to \(j\).
Transition Matrices Are a Compact Representation
For a finite Markov chain, the transition probabilities can be arranged in a matrix whose \((i,j)\)-entry is \(p_{ij}\).
This gives an efficient computational language for one-step and multi-step transitions.
The next lesson develops transition matrices systematically, including matrix multiplication and powers.
Probability Distributions Over States
At time \(n\), the chain itself may be uncertain even when its transition rules are known.
If the state space is
\[ S=\{1,2,\ldots,m\}, \]we can record
\[ P(X_n=1),\; P(X_n=2),\; \ldots,\; P(X_n=m). \]Together these probabilities describe where the chain is likely to be at time \(n\).
Example: One-Step State Distribution
Suppose the chain starts in state \(A\) with certainty and
\[ p_{AA}=0.8,\qquad p_{AB}=0.2. \]Then after one step,
\[ P(X_1=A)=0.8,\qquad P(X_1=B)=0.2. \]The outgoing transition probabilities from the known starting state become the next-state distribution.
Reachability
A state \(j\) is reachable from a state \(i\) if there is some positive-probability path that begins at \(i\) and eventually arrives at \(j\).
Reachability concerns what is possible in one or more steps, not merely what is possible in the next step.
One-Step Reachability and Multi-Step Reachability
If
\[ p_{ij}>0, \]then \(j\) is reachable from \(i\) in one step.
Even when \(p_{ij}=0\), state \(j\) may still be reachable from \(i\) through intermediate states.
For example,
\[ A\to B\to C \]can make \(C\) reachable from \(A\) even if a direct transition \(A\to C\) is impossible.
Communication Between States
Two states \(i\) and \(j\) are said to communicate if each is reachable from the other.
Symbolically, we may write
\[ i\leftrightarrow j. \]Communication groups states according to the long-range connectivity of the transition structure.
Communicating Classes
A communicating class is a collection of states that communicate with one another.
For example, if
\[ A\leftrightarrow B,\qquad B\leftrightarrow C,\qquad A\leftrightarrow C, \]then \(A,B,C\) belong to the same communicating class.
Class structure can reveal portions of a chain that are mutually accessible.
Irreducible Chains
A Markov chain is irreducible when every state communicates with every other state.
In a finite irreducible chain, the entire state space forms one communicating class.
Irreducibility does not mean every direct transition is possible. It means every state can eventually be reached from every other state through some positive-probability path.
Reducible Chains
A chain is reducible when the state space separates into distinct accessibility structures rather than one communicating class.
Reducibility often appears when transitions can move in one direction between regions of the state space but cannot return.
Absorbing States
A state \(a\) is absorbing when
\[ \boxed{p_{aa}=1}. \]Once the chain enters \(a\), it remains there forever.
Failure, extinction, completion, default, and termination are frequently modeled as absorbing states.
Example: An Absorbing Completion State
Suppose a task can be
\[ S=\{\text{Not Started},\text{In Progress},\text{Complete}\}. \]If a completed task remains complete in the model, then
\[ P(\text{Complete next}\mid\text{Complete now})=1. \]The Complete state is absorbing.
Closed Sets of States
A collection of states is closed if the chain cannot leave that collection once it enters.
An absorbing state is the simplest closed set: it contains only one state.
Larger closed communicating classes can also occur.
Transient and Recurrent Behavior
Markov-chain theory distinguishes states according to whether the chain may leave and never return or is guaranteed, in an appropriate probabilistic sense, to revisit them.
These ideas are called transience and recurrence.
At this stage, the important point is that the transition structure controls not only the next move but also the kinds of long-run paths the chain can produce.
Return Times
If a chain starts in state \(i\), a natural question is how long it takes to return to \(i\).
A first return time can be written
\[ T_i=\min\{n\ge 1:X_n=i\}. \]Return times connect Markov chains to waiting-time questions and later long-run analysis.
Hitting Times
More generally, for a target state \(j\), the hitting time is the first time the chain reaches \(j\):
\[ T_j=\min\{n\ge 0:X_n=j\}. \]Hitting-time questions arise in reliability, queues, games, finance, population models, and random walks.
The Markov Property Depends on the State Definition
Whether a model is Markov can depend on how the state is chosen.
If the state omits information that affects the next transition, then the observed process may fail the Markov property.
A better state description can often restore it.
Example: Insufficient State Information
Suppose a machine's probability of failing tomorrow depends on both its current operating condition and how many consecutive days it has been operating.
If the state records only
\[ \{\text{Working},\text{Failed}\}, \]then two machines in the Working state may have different next-day failure probabilities because their operating ages differ.
The two-state description may therefore be insufficient for a Markov model.
Augmenting the State
One remedy is to expand the state so that it contains the relevant information.
For the machine example, the state might be
\[ X_n=(C_n,A_n), \]where \(C_n\) is the operating condition and \(A_n\) is the current operating age.
A larger state space can produce a simpler dependency structure.
Markov Does Not Mean Memoryless in Every Sense
Informally, Markov chains are sometimes called memoryless.
The precise statement is more careful: the current state contains all the information from the modeled past that is needed for the next-step probability law.
The present state itself may encode substantial information about earlier events.
Example: Inventory Level
Let \(X_n\) be the number of units in inventory at the end of day \(n\).
If tomorrow's inventory distribution depends only on today's inventory, together with a fixed replenishment and demand rule already built into the model, then \(\{X_n\}\) can be modeled as a Markov chain.
A possible finite state space is
\[ S=\{0,1,\ldots,C\}, \]where \(C\) is the storage capacity.
Example: Customer Status
A subscription model might use
\[ S=\{\text{Active},\text{Paused},\text{Canceled}\}. \]Monthly transition probabilities can describe retention, pausing, reactivation, and cancellation.
If cancellation is treated as permanent, the Canceled state is absorbing. If former customers may reactivate, it is not.
Example: Credit Rating Categories
A simplified credit model can use ordered states such as
\[ S=\{\text{High},\text{Medium},\text{Low},\text{Default}\}. \]Each period, an account may remain in the same category, improve, deteriorate, or enter default.
Such models illustrate how Markov chains can represent categorical changes over time.
Example: Random Walk as a Markov Chain
Let
\[ X_{n+1}=X_n+Y_{n+1}, \]where
\[ P(Y_{n+1}=1)=p,\qquad P(Y_{n+1}=-1)=1-p, \]and the increments are independent.
Given \(X_n=i\),
\[ P(X_{n+1}=i+1\mid X_n=i)=p \]and
\[ P(X_{n+1}=i-1\mid X_n=i)=1-p. \]The current position is enough to determine the next-step distribution.
Example: A Simple Queue-Length Chain
Let \(X_n\) be the number of customers in a system at observation time \(n\).
If the arrival and service rules are chosen so that the next queue-length distribution depends only on the current queue length, then \(X_n\) forms a Markov chain on
\[ S=\{0,1,2,\ldots\} \]or on a finite truncation if the system has limited capacity.
Example: Reliability States
A redundant system might have the states
\[ S=\{2,1,0\}, \]where the state records the number of functioning components.
Failure and repair probabilities can then define transitions between these states.
If the system is considered permanently failed at \(0\), then \(0\) is absorbing. If repair is allowed, it need not be.
Finite and Infinite Markov Chains
A Markov chain may have a finite, countably infinite, or more general state space.
Introductory transition-matrix methods focus mainly on finite chains, where all one-step transition probabilities fit into a finite matrix.
The Markov idea itself is broader than the finite-state case.
Discrete Time in This Lesson
A Markov chain is usually indexed by discrete steps:
\[ n=0,1,2,\ldots \]The index might represent minutes, days, transactions, generations, or simply successive updates.
Later stochastic-process models, such as Poisson processes, use continuous time.
The State Labels Need Not Be Numbers
Markov-chain states may be represented by numbers, letters, categories, vectors, or other objects.
The labels themselves do not determine the mathematics. What matters is:
- which states exist;
- which transitions are possible;
- the probabilities assigned to those transitions.
Estimating Transition Probabilities from Data
When a Markov chain is used as an empirical model, transition probabilities may be estimated from observed transitions.
If state \(i\) was observed \(N_i\) times as a current state and \(N_{ij}\) of those observations were followed by state \(j\), a natural estimate is
\[ \widehat p_{ij}=\frac{N_{ij}}{N_i}. \]This estimate reflects the observed relative frequency of the transition \(i\to j\).
Example: Estimating a Transition Probability
Suppose a system was observed in state \(A\) on \(200\) occasions. On the next observation it was in state \(B\) on \(50\) of those occasions.
Then
\[ \widehat p_{AB} = \frac{50}{200} = 0.25. \]This is an empirical estimate, not a guarantee that the true transition probability equals \(0.25\).
Model Assumption: Stable Transition Behavior
A time-homogeneous Markov model assumes that the transition mechanism remains stable over the period being modeled.
If policy changes, seasonality, aging, learning, market shifts, or other external forces change transition behavior, a single fixed transition rule may be inappropriate.
Model Assumption: The State Is Sufficient
The Markov assumption is meaningful only relative to the chosen state.
If omitted variables materially affect the next step, then transition probabilities based only on the recorded state may hide important dependence.
State design is therefore part of model validation, not merely notation.
Model Assumption: Transitions Are Probabilistic Rules
A transition probability describes uncertainty in the next state.
It does not explain why the transition occurs.
A Markov chain can be an effective predictive or descriptive model even when it is not a causal model of the underlying mechanism.
Common Error: Confusing Markov with Independent
If
\[ P(X_{n+1}=j\mid X_n=i) \]changes when \(i\) changes, then the next state depends on the current state.
This dependence is completely compatible with the Markov property.
Markov means conditional dependence on the present is sufficient, not that successive states are independent.
Common Error: Reversing Transition Subscripts
The notation
\[ p_{ij} \]means the probability of moving from \(i\) to \(j\).
In general,
\[ p_{ij}\ne p_{ji}. \]Transition probabilities are directional.
Common Error: Forgetting the Row-Sum Condition
From any current state, the next-state probabilities must form a complete probability distribution.
Therefore, values such as
\[ 0.6,\quad0.3,\quad0.2 \]cannot all be the outgoing probabilities from one state because they sum to
\[ 1.1. \]Common Error: Treating an Impossible Direct Transition as Unreachable
The condition
\[ p_{ij}=0 \]means only that \(j\) cannot be reached from \(i\) in one step.
State \(j\) may still be reachable in two or more steps through intermediate states.
Common Error: Ignoring the Initial Distribution
Transition probabilities alone do not determine the chain's probability distribution at a specific finite time.
The starting condition matters.
Always identify the initial state or initial distribution when computing probabilities involving \(X_1,X_2,\ldots\).
Common Error: Multiplying Alternative Paths
For a single specified path, multiply transition probabilities along the path.
For several mutually exclusive paths leading to the same event, add their path probabilities.
The reliable rule is:
\[ \boxed{\text{multiply along paths; add across paths}}. \]A Reliable Procedure for Building a Markov Chain
- Define the time index or sequence of observation steps.
- Choose a state that contains the information needed for the next-step model.
- Specify the state space \(S\).
- Identify which one-step transitions are possible.
- Assign a probability \(p_{ij}\) to each possible transition.
- Verify that all outgoing probabilities from each state sum to \(1\).
- Specify the initial state or initial distribution.
- Check whether the transition rule is intended to be time-homogeneous.
- Use path probabilities or multi-step calculations for later-state questions.
- Validate whether the Markov assumption is reasonable for the chosen state.
Example: Full Two-State Workflow
Suppose a customer can be Active or Inactive:
\[ S=\{A,I\}. \]Assume
\[ p_{AA}=0.85,\qquad p_{AI}=0.15, \] \[ p_{IA}=0.25,\qquad p_{II}=0.75. \]Each pair of outgoing probabilities sums to \(1\):
\[ 0.85+0.15=1,\qquad 0.25+0.75=1. \]If the customer begins Active, then
\[ P(X_1=I\mid X_0=A)=0.15. \]The probability of the two-step path
\[ A\to I\to A \]is
\[ (0.15)(0.25)=0.0375. \]The probability of being Active after two steps is
\[ (0.85)(0.85)+(0.15)(0.25) = 0.76. \]Practice 1: Identify the Markov Property
Complete the statement:
In a Markov chain, once the current state \(X_n\) is known, the probability distribution of \(X_{n+1}\) does not require knowledge of ____________________.
Practice 2: Interpret \(p_{ij}\)
Explain in words what
\[ p_{AB}=0.35 \]means.
Practice 3: Check an Outgoing Distribution
From state \(A\), a proposed model gives
\[ p_{AA}=0.45,\qquad p_{AB}=0.30,\qquad p_{AC}=0.20. \]Is this a valid complete set of outgoing transition probabilities?
Practice 4: Find a Missing Transition Probability
A three-state chain satisfies
\[ p_{BA}=0.20,\qquad p_{BB}=0.50. \]Find \(p_{BC}\).
Practice 5: Path Probability
Suppose
\[ p_{AB}=0.4,\qquad p_{BC}=0.6,\qquad p_{CA}=0.5. \]Starting from \(A\), find the probability of
\[ A\to B\to C\to A. \]Practice 6: Two-Step Probability
A two-state chain has
\[ p_{AA}=0.7,\quad p_{AB}=0.3,\quad p_{BA}=0.4,\quad p_{BB}=0.6. \]Starting from \(A\), find the probability of being in \(B\) after two steps.
Practice 7: Identify an Absorbing State
State \(C\) satisfies
\[ p_{CC}=1. \]What special type of state is \(C\)?
Practice 8: Reachability
Suppose \(p_{AC}=0\), but
\[ p_{AB}>0 \]and
\[ p_{BC}>0. \]Is \(C\) reachable from \(A\)?
Practice 9: Is the State Sufficient?
A machine's next-day failure probability depends on its present condition and its age. A proposed state records only present condition.
Explain why this state definition may fail to produce a Markov chain.
Practice 10: Estimate a Transition Probability
State \(A\) was observed \(160\) times as the current state. It was followed by state \(B\) on \(40\) of those occasions.
Estimate \(p_{AB}\).
Practice Answers
Practice 1
Once the current state is known, the next-state probability law does not require the complete earlier history:
\[ P(X_{n+1}=j\mid X_n=i,X_{n-1},\ldots,X_0) = P(X_{n+1}=j\mid X_n=i). \]Practice 2
The statement
\[ p_{AB}=0.35 \]means that, conditional on the chain currently being in state \(A\), the probability that the next state is \(B\) equals \(0.35\).
Practice 3
No. The probabilities sum to
\[ 0.45+0.30+0.20=0.95, \]not \(1\). A complete set of outgoing probabilities from one state must sum to \(1\).
Practice 4
Because the outgoing probabilities from \(B\) must sum to \(1\),
\[ 0.20+0.50+p_{BC}=1. \]Therefore,
\[ \boxed{p_{BC}=0.30}. \]Practice 5
Multiply along the specified path:
\[ (0.4)(0.6)(0.5)=0.12. \]Thus,
\[ \boxed{P(A\to B\to C\to A)=0.12}. \]Practice 6
Starting from \(A\), the chain can be in \(B\) after two steps through
\[ A\to A\to B \]or
\[ A\to B\to B. \]Therefore,
\[ (0.7)(0.3)+(0.3)(0.6) = 0.21+0.18 = \boxed{0.39}. \]Practice 7
State \(C\) is absorbing because
\[ p_{CC}=1. \]Practice 8
Yes. Even though \(C\) cannot be reached directly from \(A\), the positive-probability path
\[ A\to B\to C \]makes \(C\) reachable from \(A\) in two steps.
Practice 9
Two machines with the same recorded condition but different ages can have different next-day failure probabilities. Therefore, present condition alone does not contain all information needed for the next-step law.
The state can be augmented to include age.
Practice 10
The empirical estimate is
\[ \widehat p_{AB} = \frac{40}{160} = \boxed{0.25}. \]What to Remember
A Markov chain is a discrete-time stochastic process whose next-step probability law depends on the current state rather than the complete past:
\[ \boxed{ P(X_{n+1}=j\mid X_n=i,X_{n-1},\ldots,X_0) = P(X_{n+1}=j\mid X_n=i) }. \]- The state space lists the possible states of the chain.
- \(p_{ij}\) is the one-step probability of moving from \(i\) to \(j\).
- Outgoing probabilities from each state must sum to \(1\).
- Self-transitions are allowed.
- A time-homogeneous chain uses the same transition probabilities at every step.
- The initial state or initial distribution is part of the model.
- Multiply transition probabilities along a specified path.
- Add probabilities across mutually exclusive alternative paths.
- Reachability may require more than one step.
- Communicating states can reach one another.
- An irreducible chain has one communicating class.
- An absorbing state satisfies \(p_{ii}=1\).
- The Markov property depends on whether the chosen state contains the information needed for the next-step model.
The central modeling principle is: choose the state carefully, then describe the chain through conditional probabilities for movement from the present state to the next one.
Where We Go Next
Transition probabilities define how a Markov chain moves one step at a time. For a finite chain, those probabilities can be organized into a single algebraic object.
The next lesson, Transition Matrices, develops the matrix representation of a finite Markov chain and shows how matrix multiplication efficiently computes state distributions and multi-step transition probabilities.