Welcome to our community

Be a part of something great, join today!

Markov process - Limit

mathmari

Well-known member
MHB Site Helper
Apr 14, 2013
4,004
Hey!! :eek:

We consider the equation \begin{equation*}u_{k+1}=\begin{pmatrix}a & b \\ 1-a & 1-b\end{pmatrix}u_k \ \text{ with } \ u_0=\begin{pmatrix}1 \\1 \end{pmatrix}\end{equation*}

For which values of $a$ and $b$ is the above equation a Markov process?
Calculate $u_k$ as a function of $a,b$.
Which conditions do $a,b$ have to satisfy so that $u_k$ approximates a finite limit as $k\rightarrow \infty$ and which is that limit?


I have done the following:

So that the equation is a Markov process the element of the matrix must be non-negativ and the sum of the colums must be $1$.
So, we get $0\leq a,b\leq 1$.

\begin{align*}&u_0=\begin{pmatrix}1 \\ 1\end{pmatrix} \\ &u_1=\begin{pmatrix}a+b \\ 2-(a+b)\end{pmatrix} \\ &u_2=\begin{pmatrix}a^2+2b-b^2 \\ 2-(a^2+2b-b^2)\end{pmatrix}\\ &u_3=\begin{pmatrix}a^3+2ab-b^2a+2b-a^2b-2b^2+b^3 \\ 2-(a^3+2ab-b^2a+2b-a^2b-2b^2+b^3)\end{pmatrix} \\ & \ldots\end{align*}

Let $u_k=(x_k,y_k)^T$ then it holds that \begin{align*}&x_k+y_k=2 \\ & x_{k+1}=(a−b)x_k+2b \\ & x0=y0=1\end{align*}

We have that \begin{align*} x_{k+1}&=(a−b)x_k+2b \\ & =(a-b)^2x_{k-1}+2b(1-b)+2b \\ & = (a-b)^3x_{k-2}+2b(a-b)^2+2b(a-b)+2b \\ & =\ldots \\ & = (a-b)^{k+1}x_0+2b\left (\sum_{i=0}^k(a-b)^i\right )\end{align*}

Therefore, we get \begin{equation*}u_k=\begin{pmatrix}x_k \\ y_k\end{pmatrix}=\begin{pmatrix}(a-b)^{k+1}x_0+2b\left (\sum_{i=0}^k(a-b)^i\right )\\ 2-(a-b)^{k+1}x_0+2b\left (\sum_{i=0}^k(a-b)^i\right )\end{pmatrix} \end{equation*}

So that $u_k$ approximates a finite limit as $k\rightarrow \infty$ it must be $0<a-b<1$.

Is everything correct? (Wondering)
 

steep

Member
Dec 17, 2018
51
Hey!! :eek:

We consider the equation \begin{equation*}u_{k+1}=\begin{pmatrix}a & b \\ 1-a & 1-b\end{pmatrix}u_k \ \text{ with } \ u_0=\begin{pmatrix}1 \\1 \end{pmatrix}\end{equation*}

For which values of $a$ and $b$ is the above equation a Markov process?
Calculate $u_k$ as a function of $a,b$.
Which conditions do $a,b$ have to satisfy so that $u_k$ approximates a finite limit as $k\rightarrow \infty$ and which is that limit?
let's call your transition matrix

$P := \begin{pmatrix}a & b \\ 1-a & 1-b\end{pmatrix}$

it's customary in probability theory to make $P$ row stochastics (rows sum to one, nonnegative entries) not column stochastic, but in principle there's no issue with being column stochastic. You've stated the conditions for being column stochastic just fine. Note with $\mathbf 1$ the ones vector (which $\mathbf u_0$ is for some reason), being column stochastic means

$\mathbf 1^T P = \mathbf 1^T$
or
$P^T \mathbf 1 = \mathbf 1$

so the ones vector is a (left) eigenvector with eigenvalue of 1.

We'll call the eigenvalue $\lambda_1 = 1$, which is of course an eigenvalue of $P$ and $P^T$


... Therefore, we get \begin{equation*}u_k=\begin{pmatrix}x_k \\ y_k\end{pmatrix}=\begin{pmatrix}(a-b)^{k+1}x_0+2b\left (\sum_{i=0}^k(a-b)^i\right )\\ 2-(a-b)^{k+1}x_0+2b\left (\sum_{i=0}^k(a-b)^i\right )\end{pmatrix} \end{equation*}

So that $u_k$ approximates a finite limit as $k\rightarrow \infty$ it must be $0<a-b<1$.

Is everything correct? (Wondering)
I appreciate all the work, but the conclusion doesn't follow. I see no problem with e.g. $b= 0.7$ and $a = 0.2$, you'll still get a valid limit.

A much simpler approach is to make use of trace, so

$\text{tr} \big(P\big) = a + 1-b = \lambda_1 + \lambda_2 = 1 +\lambda_2$

so
$a -b = \lambda_2$

if $\big \vert \lambda_2 \big \vert \lt 1$, then you must get a finite limit (why?). You should be able to find the single (right) eigenvector in the nullspace of $\big(P-I\big)$ and from here figure out the limiting value of $\mathbf u_k$.

If $\lambda_2 = -1$ you have periodic behavior (period of 2) and no limit can exist; in this case the matrix is a pairwise swap permutation matrix. The special case of $\lambda_2 = 1$ remains to be considered and you can check that this implies $P$ is the identity matrix, which is no problem for limits...