STOCHASTIC PROCESSES 06

Discrete-Time Markov Chains

A DTMC moves between states at fixed time steps according to transition probabilities that depend on the current state.

The process

A discrete-time Markov chain is written

\[X_0,X_1,X_2,\ldots\]

with state space \(S\).

1. One-step transition probabilities

Define

\[\boxed{p_{ij}=P(X_{n+1}=j\mid X_n=i)}\]

for a time-homogeneous chain.

2. Probabilities from one state sum to one

\[\sum_j p_{ij}=1.\]

At the next step the chain must be in one of its possible states.

3. Example

Suppose a process has states \(0,1,2\). From state \(1\), it may move to \(0\), remain at \(1\), or move to \(2\). The three probabilities must sum to one.

4. One trajectory

To simulate the chain, generate a uniform random number \(U\sim U(0,1)\) and divide \([0,1]\) into intervals with lengths equal to the possible transition probabilities.

5. Distribution versus trajectory

A simulated chain gives one random path. Matrix calculations can instead propagate the full probability distribution over all states.

6. Multi-step behaviour

Repeated one-step transitions determine probabilities several steps into the future. This leads naturally to transition matrices and matrix powers.

\[\boxed{\text{current state}+\text{transition probabilities}\rightarrow\text{next random state}}\]