Learning Notes

# Markov Property

To recap, Markov property suggest that previous events has no influence to future events. Formulated by [Eq.1]

$\displaystyle P(\{X_n=i_n\}|\{X_{n-1}=i_{n-1}, X_{n-2}=i_{n-2}, \dots, X_0=i_0 \} )$

$\displaystyle \indent = P(\{X_n=i_n\}|\{X_{n-1}=i_{n-1}\})$

# Transition Probability Matrix

## Transition Property of Markov Chain

Denoting $X_n = \{X_n = i_n\}$,

$\displaystyle P(X_{n+1}, X_n, \dots, X_1)$

$\displaystyle = P(X_{n+1}|X_n, \dots, X_1) \cdot P(X_n, \dots, X_1)$

$\displaystyle = P(X_{n+1}|X_n) \cdot P(X_n, \dots, X_1)$
(by Markov Properties [Eq.1])

$\displaystyle = P(X_{n+1}|X_n) \cdot P(X_n|X_{n-1}) \cdots P(X_1)$

$\displaystyle = P_{n, n + 1} \cdot P_{n - 1, n}\cdots P_{1, 2}\cdot P_1$
(Denote $P(j|i)$ as $P_{i,j}$ )

## Transition Probability written as Matrix

The upper describes the transitional property of a Markov chain. If we write the probabilities of going to j-th state from i-th state into the components of a matrix, we call this a Transition Probability Matrix (TPM) or more commonly the Stochastic Matrix.  In general, it can be written as follow [Eq.2]:

$\displaystyle P =\begin{pmatrix} P_{1,1}&P_{1,2}&\dots &P_{1,j}&\dots &P_{1,n+1}\\P_{2,1}&P_{2,2}&\dots &P_{2,j}&\dots &P_{2,n+1}\\\vdots &\vdots &\ddots &\vdots &\ddots &\vdots \\P_{i,1}&P_{i,2}&\dots &P_{i,j}&\dots &P_{i,n+1}\\\vdots &\vdots &\ddots &\vdots &\ddots &\vdots \\P_{n+1,1}&P_{n+1,2}&\dots &P_{n+1,j}&\dots &P_{n+1,n+1}\\\end{pmatrix}$

Which also carries the transitional property, for instance, the probabilities of going into j-th state from i-th state in exactly n steps would be $P^n$.

### Example:

Suppose we want to know the probabilities of the system ending in each states which initially started from i-th state and went through n steps. First, construct a unit state vector where only the i-th element is 1:

$\displaystyle \pi_i^{(0)} = \{0, 0, \dots, 1, \dots, 0\}$

Then, probabilities we want can be calculate by the multiplication:

$\displaystyle \pi^{(n)} = \pi_i^{(0)} \cdot P^n$

(To be continue)