markov chain

**234578** · April 17th 2010, 07:04 PM

There are four adjacent squares and a marker. A player begins a game by placing a marker in square#2. A die is rolled and the marker is moved one square to the left if a 1 or 2 is rolled and one square to the right if a 3, 4, 5, or 6 is rolled. The process is continued until the marker lands in square#1 (win) or square#4 (lose). What is the probability of winning?

Hint: instead of diagonalizing the appropriate transition matrix, A, it is easier to represent e2 as a linear combination of the eigenvectors of A and then apply $A^n$ to the result.

I know how to answer this the "harder" way by diagonalizing A but I don't understand what the hint is saying. I assume e2 is the second vector in the standard ordered basis for 4x1 matrices but how do I "apply $A^n$ to the result" and why would I want to??

**dwsmith** · April 17th 2010, 07:20 PM

1. If A is diagonalizable, then the column vectors of the diagonalizing matrix X are eigen vectors of A and the diagonal elements D are corresponding eigenvalues of A
2. The diagonalizing matrix X is not unique.
3. If A is nxn and A has n distinct eigenvalues, then A is diagonalizable. If not distinct, then A may or may not be diagonalizable, depending on whether A has n lin. ind. eigenvectors.
4. If A is diagonalizable, then A can be factored into a product $XDX^-1$ .

To obtain eigenvectors, you need to first get the eigenvalues.

$det(A-\lambda I)=0$

If the eigenvalues are used to form a diagonalizing matrix X, then $A^k=XD^kX^{-1}$

$A^k=X\begin{bmatrix} (\lambda)_{1}^k & & & \\ & (\lambda)_{2}^k & & \\ & & \ddots & \\ & & & (\lambda)_{n}^k \end{bmatrix}X^{-1}$

A converges to a steady state vector and x is a probability vector.

**234578** · April 17th 2010, 08:09 PM

Originally Posted by dwsmith

1. If A is diagonalizable, then the column vectors of the diagonalizing matrix X are eigen vectors of A and the diagonal elements D are corresponding eigenvalues of A
2. The diagonalizing matrix X is not unique.
3. If A is nxn and A has n distinct eigenvalues, then A is diagonalizable. If not distinct, then A may or may not be diagonalizable, depending on whether A has n lin. ind. eigenvectors.
4. If A is diagonalizable, then A can be factored into a product $XDX^-1$ .

To obtain eigenvectors, you need to first get the eigenvalues.

$det(A-\lambda I)=0$

If the eigenvalues are used to form a diagonalizing matrix X, then $A^k=XD^kX^{-1}$

$A^k=X\begin{bmatrix} (\lambda)_{1}^k & & & \\ & (\lambda)_{2}^k & & \\ & & \ddots & \\ & & & (\lambda)_{n}^k \end{bmatrix}X^{-1}$

A converges to a steady state vector and x is a probability vector.

Thanks for the reply. I agree, this is the way I would normally solve the problem--by diagonalizing A. But the hint says "rather than diagonalizing the appropriate transition matrix, A, it is easier to represent e2 as a linear combination of the eigenvectors of A and then apply $A^n$ to the result" so I would be representing e2 as a linear combination of the columns of the diagonalizing matrix (X, in your notation)....I'm still not sure how the hint applies.

**dwsmith** · April 17th 2010, 08:11 PM

Have you found the eigenvectors of A yet?

**234578** · April 17th 2010, 09:19 PM

Originally Posted by dwsmith

Have you found the eigenvectors of A yet?

I got characteristic polynomial $f(t)=(t^2)(t-\frac{\sqrt2}3)(t+\frac{\sqrt2}3)$

( $\frac12$ , $\frac1{\sqrt2}$ , $1, \sqrt2$ ) is an eigenvector that is a basis for the eigenspace of $\lambda$ = $\frac{\sqrt2}3$

( $\frac12$ , $\frac{-1}{\sqrt2}$ , $1, -\sqrt2$ ) is an eigenvector that is a basis for the eigenspace of $\lambda$ = $\frac{-\sqrt2}3$

but when I tried to find an eigenvector, $v$ , to form a basis for the eigenspace corresponding to $\lambda =0$ I only got v=(0, 0, 0, 0) which cannot be an eigenvector and furthermore cannot be in a basis.... did I do something wrong or am I missing something?

**dwsmith** · April 17th 2010, 09:20 PM

Originally Posted by 234578

I got characteristic polynomial $f(t)=(t^2)(t-\frac{\sqrt2}3)(t+\frac{\sqrt2}3)$

( $\frac12$ , $\frac1{\sqrt2}$ , $1, \sqrt2$ ) is an eigenvector that is a basis for the eigenspace of $\lambda$ = $\frac{\sqrt2}3$

( $\frac12$ , $\frac{-1}{\sqrt2}$ , $1, -\sqrt2$ ) is an eigenvector that is a basis for the eigenspace of $\lambda$ = $\frac{-\sqrt2}3$

but when I tried to find an eigenvector, $v$ , to form a basis for the eigenspace corresponding to $\lambda =0$ I only got v=(0, 0, 0, 0) which cannot be an eigenvector and furthermore cannot be in a basis.... did I do something wrong or am I missing something?

Can you post your determinant matrix you used?

**234578** · April 18th 2010, 09:24 AM

Originally Posted by dwsmith

Can you post your determinant matrix you used?

1st row of A: 0, 1/3, 0, 0
2nd row of A: 0, 0, 1/3, 0
3rd row of A: 0, 2/3, 0, 0
4th row of A: 0, 0, 2/3, 0

I found det(A-tI) to find characteristic polynomial.
Once I determined $\lambda=0$ , $\lambda=\frac{\sqrt2}3$ and $\lambda=\frac{-\sqrt2}3$
I solved (A- $\lambda$ )v=0 for v to find bases for the eigenspaces

**dwsmith** · April 23rd 2010, 04:05 PM

Your eigenspace for lambda equals zero is:
$x_1\begin{bmatrix} 1\\ 0\\ 0\\ 0 \end{bmatrix}+x_4\begin{bmatrix} 0\\ 0\\ 0\\ 1 \end{bmatrix}$ Therefore, you have four eigenvectors now. Sorry for the slow reply was busy.

Thread: markov chain

LinkBack

Thread Tools

Display

markov chain

Similar Math Help Forum Discussions

Markov Chain of random variables from a primitive markov chain

Markov Chain Help

Markov Chain

Markov Chain HELP!!!!

how to show that the X_kn is a markov chain if X_n is a markov chain

Search Tags