Markov Chains

Say, $A$ and $B$ are libraries with $1000$ books.

In the beginning, $x_0=\left[\begin{array}{c}0.5\\ 0.5\end{array}\right]$ Now, after $1$ month, $x_1=\left[\begin{array}{c}0.8\cdot 0.5+0.3\cdot 0.5\\ 0.2\cdot 0.5+0.7\cdot 0.5\end{array}\right]=\left[\begin{array}{cc}0.8& 0.3\\ 0.2& 0.7\end{array}\right]\left[\begin{array}{c}0.5\\ 0.5\end{array}\right]=P{x}_1$

$$\boxed{P=\left[\begin{array}{cc}0.8& 0.3\\ 0.2& 0.7\end{array}\right]}$$

Now, after $2$ months, $x_2=P{x}_1=P^2{x}_0$ $⋮$ Now, after $k$ months, $x_k=P^k{x}_0$

Steady State

Find the steady state of $P=\left[\begin{array}{cc}0.8& 0.3\\ 0.2& 0.7\end{array}\right]$.

$$\begin{array}{rl}P\vec{q}& =\vec{q}\\ P\vec{q}-\vec{q}& =0\\ P\vec{q}-I_n\vec{q}& =0\\ (P-I_n)\vec{q}& =0\\ \left(\left[\begin{array}{cc}0.8& 0.3\\ 0.2& 0.7\end{array}\right]-\left[\begin{array}{cc}1& 0\\ 0& 1\end{array}\right]\right)\vec{q}& =0\\ \left[\begin{array}{cc}-0.2& 0.3\\ 0.2& -0.3\end{array}\right]\vec{q}& =0\\ \{\begin{array}{llc}-2x_1& +3x_2& =0\\ 2x_1& -3x_2& =0\end{array}& \\ \{x_1=3,x_2& =2\}\\ \frac{1}{3+2}\left[\begin{array}{c}3\\ 2\end{array}\right]& =\vec{q}\\ \vec{q}& =\boxed{\left[\begin{array}{c}\frac{3}{5}\\ \frac{2}{5}\end{array}\right]}\end{array}$$

If a matrix is regular stochastic, it implies the existence of a steady state. (The converse is not necessarily true)

Convergence

We have $x_1,x_2,x_3,\dots x_k$. We want to know if while $k\to \infty$ $x_k$ will converge to a steady state.

If $P$ is a regular stochastic matrix (vocabulary), then $P$ has a unique steady-state vector $\vec{q}$, and ${\vec{x}}_{k+1}=P{\vec{x}}_k$ converges to $\vec{q}$ as $k\to \infty$.

Using Eigenvalues to find Convergence

Say $P$ has 2 eigenvalues (${\lambda }_1\text{ and }{\lambda }_2$) and eigenvectors ($v_1\text{ and }{v}_2$).

$$\begin{array}{rlr}{x}_{k+1}& =P{x}_k& \\ x_0& =c_1{v}_1+c_2{v}_2& \\ x_1& =P{x}_0& \\ x_1& =P(c_1{v}_1+c_2{v}_2)& =c_{1}P{v}_1+c_{2}P{v}_2\\ x_1& =c_1{\lambda }_1{v}_1+c_2{\lambda }_2{v}_2& \\ x_2& =P{x}_1& \\ x_1& =P(c_1{\lambda }_1{v}_1+c_2{\lambda }_2{v}_2)& =c_1({\lambda }_1{)}^2{v}_1+c_2({\lambda }_2{)}^2{v}_2\\ x_k& =c_1({\lambda }_1{)}^k{v}_1+c_2({\lambda }_2{)}^k{v}_2& \end{array}$$ $$\begin{array}{rlrl}{x}_0& =c_1{v}_1+c_2{v}_2& & \\ \left[\begin{array}{c}1\\ 0\end{array}\right]& =c_1\left[\begin{array}{c}1\\ 0\end{array}\right]+c_2\left[\begin{array}{c}1\\ -1\end{array}\right]& & \\ c_1& =1& c_1& =0\end{array}$$

$\boxed{x_k=v_1}$