Markov Chains
In many real-world models, we assume deterministic outcomes based on formulas. However, many systems involve random variation.
A stochastic model uses probability to predict outcomes where randomness is present.
A Markov chain is a specific type of stochastic model that describes a sequence of events where the probability of each event depends only on the state attained in the previous event. This is known as the memoryless or Markov property.
A stochastic model uses probability to predict outcomes where randomness is present.
A Markov chain is a specific type of stochastic model that describes a sequence of events where the probability of each event depends only on the state attained in the previous event. This is known as the memoryless or Markov property.
Markov Chain
Definition
A Markov chain is a sequence of random variables describing a system that transitions between different states. The key property is that the probability of moving to the next state depends only on the current state and not on the sequence of events that preceded it.
Definition Transition Diagram
A transition diagram illustrates the states of a system and the probabilities of moving from one state to another.
- States are represented by circles (nodes).
- Arrows show movement (transitions) between states.
- Each arrow is labelled with a transition probability.
- The sum of probabilities on outgoing arrows from any state must equal 1.
Example
- If it is Sunny today, there is a \(0.9\) probability it will be Sunny tomorrow (loop) and \(0.1\) probability it will be Rainy.
- If it is Rainy today, there is a \(0.5\) probability it will be Sunny tomorrow and \(0.5\) probability it will be Rainy.
Matrix Representation
A powerful method for studying Markov chains is to represent the probabilities and states using matrices. This allows for rapid calculation of future states using matrix multiplication.
Definition State Vector
The state vector \(\mathbf{s}_n\) is a column vector that shows the probability distribution of the system at time step \(n\).
- It represents the probability or proportion of being in each state.
- The sum of the elements in a state matrix is always 1.
- The initial state is denoted by \(\mathbf{s}_0\).
Example
If today is certainly Sunny, the initial state matrix is \(\mathbf{s}_0 = \begin{pmatrix} 1 \\ 0 \end{pmatrix}\).
Definition Transition Matrix
The transition matrix \(\mathbf{T}\) organizes the transition probabilities into a square matrix.
In a transition matrix \(\mathbf{T} = (t_{ij})\):
In a transition matrix \(\mathbf{T} = (t_{ij})\):
- The columns represent the current state (From).
- The rows represent the next state (To).
- The entry \(t_{ij}\) represents the probability of moving to state \(i\) from state \(j\).
- The sum of each column must be 1.
Example
For the weather example:
State Vectors and Future Probabilities
Method Calculating Future States
To predict the probability distribution of the system after \(n\) steps, we multiply the transition matrix by the state vector repeatedly.
The general formula is:$$ \mathbf{s}_n = \mathbf{T}^n \mathbf{s}_0 $$where \(\mathbf{T}\) is the transition matrix and \(\mathbf{s}_0\) is the initial state vector.
The general formula is:$$ \mathbf{s}_n = \mathbf{T}^n \mathbf{s}_0 $$where \(\mathbf{T}\) is the transition matrix and \(\mathbf{s}_0\) is the initial state vector.
- \(\mathbf{s}_1 = \mathbf{T} \mathbf{s}_0\) (State after 1 step)
- \(\mathbf{s}_2 = \mathbf{T} \mathbf{s}_1 = \mathbf{T}(\mathbf{T}\mathbf{s}_0) = \mathbf{T}^2 \mathbf{s}_0\) (State after 2 steps)
Example
Using the weather matrix \(\mathbf{T} = \begin{pmatrix} 0.9 & 0.5 \\ 0.1 & 0.5 \end{pmatrix}\) and assuming it is Sunny today (\(\mathbf{s}_0 = \begin{pmatrix} 1 \\ 0 \end{pmatrix}\)), calculate the probabilities for the weather in 2 days.
$$ \mathbf{s}_2 = \mathbf{T}^2 \mathbf{s}_0 = \begin{pmatrix} 0.9 & 0.5 \\
0.1 & 0.5 \end{pmatrix}^2 \begin{pmatrix} 1 \\
0 \end{pmatrix} $$$$ \mathbf{T}^2 = \begin{pmatrix} 0.9 & 0.5 \\
0.1 & 0.5 \end{pmatrix} \begin{pmatrix} 0.9 & 0.5 \\
0.1 & 0.5 \end{pmatrix} = \begin{pmatrix} 0.81+0.05 & 0.45+0.25 \\
0.09+0.05 & 0.05+0.25 \end{pmatrix} = \begin{pmatrix} 0.86 & 0.70 \\
0.14 & 0.30 \end{pmatrix} $$$$ \mathbf{s}_2 = \begin{pmatrix} 0.86 & 0.70 \\
0.14 & 0.30 \end{pmatrix} \begin{pmatrix} 1 \\
0 \end{pmatrix} = \begin{pmatrix} 0.86 \\
0.14 \end{pmatrix} $$Interpretation: There is an \(86\pourcent\) chance it will be Sunny and a \(14\pourcent\) chance it will be Rainy in 2 days.
Steady State
Definition Steady State Vector
For many regular Markov chains, as the number of steps increases (\(n \to \infty\)), the state matrix \(\mathbf{s}_n\) converges to a constant vector \(\mathbf{s}\), regardless of the initial state \(\mathbf{s}_0\).
This vector \(\mathbf{s}\) is called the steady state vector (or stationary distribution).
It satisfies the equilibrium equation:$$ \mathbf{T} \mathbf{s} = \mathbf{s} $$Algebraically, \(\mathbf{s}\) is an eigenvector of \(\mathbf{T}\) corresponding to the eigenvalue \(\lambda = 1\). The sum of the elements of \(\mathbf{s}\) must be 1.
This vector \(\mathbf{s}\) is called the steady state vector (or stationary distribution).
It satisfies the equilibrium equation:$$ \mathbf{T} \mathbf{s} = \mathbf{s} $$Algebraically, \(\mathbf{s}\) is an eigenvector of \(\mathbf{T}\) corresponding to the eigenvalue \(\lambda = 1\). The sum of the elements of \(\mathbf{s}\) must be 1.
Method Finding the Steady State
To find the steady state vector \(\mathbf{s} = \begin{pmatrix} x \\ y \end{pmatrix}\):
- Set up the matrix equation \(\mathbf{T}\mathbf{s} = \mathbf{s}\).
- Convert this into a system of linear equations.
- Use the additional constraint \(x + y = 1\) (for a 2-state system) to solve for \(x\) and \(y\).
A city operates a bike-sharing system with two main zones: the City Center (C) and the Train Station (S).
Bikes are rented and returned daily. The transition matrix \(\mathbf{T}\) represents the probability of a bike moving between zones or staying in the same zone by the end of the day:$$ \mathbf{T} = \begin{pmatrix} 0.8 & 0.3 \\ 0.2 & 0.7 \end{pmatrix} $$
Bikes are rented and returned daily. The transition matrix \(\mathbf{T}\) represents the probability of a bike moving between zones or staying in the same zone by the end of the day:$$ \mathbf{T} = \begin{pmatrix} 0.8 & 0.3 \\ 0.2 & 0.7 \end{pmatrix} $$
- Find the steady state vector \(\mathbf{s} = \begin{pmatrix} x \\ y \end{pmatrix}\) algebraically.
- If the city owns \(1000\) bikes in total, determine how they should be distributed between the City Center and the Train Station in the long run to meet demand.
- Find an eigenvector for \(\lambda = 1\):
$$\begin{aligned} \mathbf{T}\mathbf{s} &= \mathbf{s}\\ \begin{pmatrix} 0.8 & 0.3 \\ 0.2 & 0.7 \end{pmatrix}\begin{pmatrix} x \\ y \end{pmatrix} &= \begin{pmatrix} x \\ y \end{pmatrix}\\ \begin{pmatrix} 0.8x+0.3y \\ 0.2x+0.7y \end{pmatrix} &= \begin{pmatrix} x \\ y \end{pmatrix}\\ \end{aligned}$$ This gives \(0.8x+0.3y = x\) and \(0.2x+0.7y=y\).
Simplifying, we get \(-0.2x+0.3y = 0\) and \(0.2x-0.3y=0\).
Thus \(0.2x = 0.3y\), which implies \(2x = 3y\).
Letting \(y = 2t\), we have \(x = 3t\), so: $$ \mathbf{s} = \begin{pmatrix} 3t \\ 2t \end{pmatrix}$$ Since \(\mathbf{s}\) is a state vector, the sum of its components must be 1: $$ 3t + 2t = 1 \implies 5t = 1 \implies t = \frac{1}{5} $$ $$ \mathbf{s} = \begin{pmatrix} 3 \cdot \frac{1}{5} \\ 2 \cdot \frac{1}{5} \end{pmatrix} = \begin{pmatrix} 0.6 \\ 0.4 \end{pmatrix} $$ - In the long run, \(60\pourcent\) of the bikes will be at the City Center and \(40\pourcent\) at the Train Station.
- City Center: \(1000 \times 0.6 = 600\) bikes.
- Train Station: \(1000 \times 0.4 = 400\) bikes.