Markov Chains

A general model of a system which moves from one state to state is described and applied to concrete problem. It is shown that such systems tend to a steady-state eventually.

Definition

The transition probability $p_{ij}$ is the probability that if the system is in state $j$ at any one observation, it will be in state $i$ at the next observation.

Definition

A transition matrix $P=[p_{ij}]$ is any square matrix with nonnegative entries, all of whose column sums are one.

Definition

The probability vectors (column vectors of a transition matrix) $x^{(n)}$ for $n=0,1,...$ are said to be the state vectors of a Markov process if the $i-th$ component $x_i^{(n)}$ of $x^{(n)}$ is the probability that the system is in the $i-th$ state at the $n-th$ observation.

Theorem

If $P$ is the transition matrix of a Markov process and $x^{(n)}$ is the state vector at the $n-th$ observation, then


MATH

Example

A car rental agency has three rental locations, 1, 2, and 3. A customer may rent a car from any of the three locations and return the car to any of the three locations. The manager finds that the customers return the cars to the various locations according to the following probabilities:


MATH
where $p_{ij}$ stands for the probability of renting a car from location $j$ and return it to location $i.$ Suppose a car is initially rented from location number 2.

(1) Find the state vector $x^{(12)}.$

(2) Predict $x^{(n)},n\geq 12$.

We define MATH, and


MATH

which is designed to compute


MATH
Then

MATH MATH $P(14)=$ MATH So all state vectors are equal to $x^{(12)}$ to three decimal places.

What if we set MATH ? We obtain that

MATH MATH and MATH

Limiting Behavior

Definition

A transition matrix is regular if some integer power of it has all positive entries.

Theorem

If $P$ is a regular transition matrix, then as MATH


MATH
where the $q_i$ are positive numbers such that $\sum_{i=1}^kq_i=1.$

Theorem

If $P$ is a regular transition matrix and $x$ is any probability vector, then as MATH


MATH
where $q$ is a fixed probability vector independent of $n$.

Remark

Note that if $P$ is regular, then as MATH then $P^n\rightarrow Q$ for some $Q.$ Thus MATH which is a fixed vector and we set it to be $q.$

Definition

Let $P$ be an transition matrix of a Markov process. State vector $x$ is called a stable state or steady state of the Markov process if
MATH

Remark


MATH

Example

The transition matrix MATH. Find the steady-state vector $q$.

Method 1: We compute MATH as we did in the previous example.

Method 2: If $Pq=q$, then $(I-P)q=0$, which is equivalent to solve a homogeneous linear system. (We build Identity matrix with Scientific Workplace by using ''Matrices + Fill Matrix + Identity''.) We set $A=I-P$ as follows:

MATH MATH. We solve


MATH
and the "Solution is : MATH

This document created by Scientific WorkPlace 4.0.