Results 1 to 8 of 8

Math Help - markov chain

  1. #1
    Junior Member
    Joined
    Oct 2009
    Posts
    39

    markov chain

    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??
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Mar 2010
    From
    Florida
    Posts
    3,093
    Thanks
    5
    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}<br />
(\lambda)_{1}^k &  &  & \\ <br />
 & (\lambda)_{2}^k &  & \\ <br />
 &  & \ddots & \\ <br />
 &  &  & (\lambda)_{n}^k<br />
\end{bmatrix}X^{-1}

    A converges to a steady state vector and x is a probability vector.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Junior Member
    Joined
    Oct 2009
    Posts
    39
    Quote Originally Posted by dwsmith View Post
    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}<br />
(\lambda)_{1}^k & & & \\ <br />
& (\lambda)_{2}^k & & \\ <br />
& & \ddots & \\ <br />
& & & (\lambda)_{n}^k<br />
\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.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor
    Joined
    Mar 2010
    From
    Florida
    Posts
    3,093
    Thanks
    5
    Have you found the eigenvectors of A yet?
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Junior Member
    Joined
    Oct 2009
    Posts
    39
    Quote Originally Posted by dwsmith View Post
    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?
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor
    Joined
    Mar 2010
    From
    Florida
    Posts
    3,093
    Thanks
    5
    Quote Originally Posted by 234578 View Post
    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?
    Last edited by dwsmith; April 17th 2010 at 09:45 PM.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Junior Member
    Joined
    Oct 2009
    Posts
    39
    Quote Originally Posted by dwsmith View Post
    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
    Last edited by 234578; April 18th 2010 at 10:04 AM.
    Follow Math Help Forum on Facebook and Google+

  8. #8
    MHF Contributor
    Joined
    Mar 2010
    From
    Florida
    Posts
    3,093
    Thanks
    5
    Your eigenspace for lambda equals zero is:
    x_1\begin{bmatrix}<br />
1\\ <br />
0\\ <br />
0\\ <br />
0<br />
\end{bmatrix}+x_4\begin{bmatrix}<br />
0\\ <br />
0\\ <br />
0\\ <br />
1<br />
\end{bmatrix} Therefore, you have four eigenvectors now. Sorry for the slow reply was busy.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Markov Chain of random variables from a primitive markov chain
    Posted in the Advanced Statistics Forum
    Replies: 0
    Last Post: October 19th 2011, 08:12 AM
  2. Markov Chain Help
    Posted in the Advanced Statistics Forum
    Replies: 0
    Last Post: June 28th 2010, 07:37 AM
  3. Markov Chain
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: December 12th 2009, 04:52 PM
  4. Markov Chain HELP!!!!
    Posted in the Advanced Statistics Forum
    Replies: 1
    Last Post: April 9th 2009, 09:28 PM
  5. Replies: 2
    Last Post: October 28th 2008, 06:32 PM

Search Tags


/mathhelpforum @mathhelpforum