Finding the rate of convergence for a markov chain

[bonfire09]

Homework Statement

For the following Markov chain, find the rate of convergence to the stationary distribution:
\begin{bmatrix} 0.4 & 0.6 \\ 1 & 0 \end{bmatrix}

Homework Equations

none

The Attempt at a Solution

I found the eigenvalues which were \lambda_1=-.6 or \lambda_2=1. The corresponding eigenvectors I found were \vec{v_1}=\begin{bmatrix} -0.6 & 1 \end{bmatrix} and \vec{v_2}=\begin{bmatrix} -1 & 1 \end{bmatrix}. The stationary distribution which I found that satisfies p=pA(A is the transition matrix) and p_1+p_2=1 is \vec{p}=\begin{bmatrix} .625 & .375 \end{bmatrix}. From here I do not know how to get the rate of convergence. I think it has something to do with the eigenvalues or eigenvectors. Any help would be great thanks.[/B]

 

[andrewkirk]

The wikipedia page on Markov Chain convergence contains all you should need.

BTW I'm not sure your first eigenvector is correct. Multiply it out and check.

 

[bonfire09]

I checked the eigenvectors. I had them switched. So do I use the formula right below where it "since the eigenvectors are orthonormal..."?

 

[andrewkirk]

That depends on what you think it does. It's best to only use formulas that one understands. Without going through every step of the maths, do you understand broadly why that formula has that form?

 

[bonfire09]

Actually I don't. We talked about limiting distributions and stationary distributions in class but did not cover rate of convergence. In essence I only understand the very basics. So somehow I have to show the rate of convergence with what I have so far.

 

[andrewkirk]

Well, the matrix eigenvectors will be orthogonal and hence form a basis for the vector space. So any vector $\mathbf{x}$ can be expressed as a linear sum $\sum_{i=1}^na_i\mathbf{u}_i$ of eigenvectors, as shown in the wiki article. If only one of the eigenvalues, say $\lambda_1$, corresponding to eigenvector $\mathbf{u}_1$, has absolute value equal to 1, and all others have absolute values less than 1, what will happen to $\mathbf{x}=\sum_{i=1}^na_i\mathbf{u}_i$ as you repeatedly right-multiply it by the matrix? Think about the impact of each term in the sum separately.

 

[Ray Vickson]

Homework Statement

For the following Markov chain, find the rate of convergence to the stationary distribution:
\begin{bmatrix} 0.4 & 0.6 \\ 1 & 0 \end{bmatrix}

Homework Equations

none

The Attempt at a Solution

I found the eigenvalues which were \lambda_1=-.6 or \lambda_2=1. The corresponding eigenvectors I found were \vec{v_1}=\begin{bmatrix} -0.6 & 1 \end{bmatrix} and \vec{v_2}=\begin{bmatrix} -1 & 1 \end{bmatrix}. The stationary distribution which I found that satisfies p=pA(A is the transition matrix) and p_1+p_2=1 is \vec{p}=\begin{bmatrix} .625 & .375 \end{bmatrix}. From here I do not know how to get the rate of convergence. I think it has something to do with the eigenvalues or eigenvectors. Any help would be great thanks.[/B]

Please tun off the bold font, reserving it for emphasis on individual words, etc, like what I do below.

Anyway, do you know the definition of rate of convergence? Is this discussed in your textbook or course notes? Even if it is in a section of your text that you have not reached yet, I would bet you would be allowed to read it ahead of time and use the material as needed. If such material is not in your text or course notes, please tell us so we can point you in the appropriate direction.