0
$\begingroup$

This is a re-edit of the previous question titled "How to start the Markov chain State Vector" which was closed because it was not clear enough. Here are some details and rearrange it, and hopefully it will make the question clearer. Suppose we have a Left Hand Markov stochastic transition matrix A. A is a real $n\times n$ square matrix with all its entries $P_{ij}$ known and satisfying stochastic Matrix Conditions, ie. $0 \leq P_{ij} \leq 1$ for all $i,j$ and, sum of row entries = 1 for all rows. The solution by iteration goes with Markov chains as $x^{(1)} = Ax^{(0)}$ and $x^{(2)} = Ax^{(1)}$ ... $Ax^{(k + 1)} = Ax^{(k)}$. Our goal is to find the solution or vertical steady state eigenvector $x$ of this matrix defined by the Limit of $x^{(k)}$ as $k$ tends to infinity which does not seem to be an easy task.

Indeed, matrix A distinguishes the Markov chain from some initial states $x^{(0)}$ to the final destination of the stable state which we call the solution. Yet how to ensure that this chain path is stable and converges to the solution? At least one eigenvalue for the Markov Matrix is ​​1 ensuring stable convergent solution exist, while the other eigenvalues ​​may be negative or even complex that are incompatible with material physical reality and can lead to instability and non-convergence of the solution. I assume the eigenvalue of 1 corresponds to the best condition number and hence the best behaviour or maximal stable and fastest transport chain but all of that depends on the proper choice of the initial vector $x^{(0)}$ elements. To my knowledge $x^{(0)}$ should be as close as possible from the solution which we actually don't know? The question is, how obtain or guess the 40 initial vector elements for n=40 for example, for a specific amount of vector C " C=Sum of all vector elements which is conserved by transition"? " one answer was setting C/40 for all elements of $x^{(0)}$". The question remains :is there any guide how can we correctly choose or start the initial state vector $x^{(0)}$ to ensure following the series of unity eigenvalue ​​for best stability and convergence results?

$\endgroup$
1
  • $\begingroup$ . Guessing or choosing the initial vector x (0) with all of its entries equal C / n is our simple, ready answer. To investigate whether this leads to a stable convergence of the solution or not, further evaluation is required and is the crux of the question. $\endgroup$
    – user737980
    Jan 10, 2020 at 21:20

2 Answers 2

1
$\begingroup$

As long as you have a good enough matrix (an indivisible chain in this case), the initial choice doesn't matter, by definition, the chain converges to its stationary state (the number of iterations depends on the initial state of course, but one can only guess that). I suggest you try to implement your question in Python to get a hands on experience. Below is a sample code for a $3\times 3$ matrix, tweak it as you fancy, for starters, I suggest you alter the s_ini vector.

import numpy as np

# probability matrices P
P1 = [
     [ 0.2, 0.6, 0.2 ],
     [ 0.3, 0.1, 0.6 ],
     [ 0.5, 0.0, 0.5 ] 
    ]

P_absorb = [
     [ 1/3, 1/3, 1/3 ],
     [ 0.0, 1/2, 1/2 ],
     [ 0.0, 0.0, 1.0 ]
    ]

# initial state vector
s_ini = [ 1,0,0 ]

# try to reach a stationary state
aux = s_ini
for i in range(10000):
    s = np.dot(aux, P1)
    if np.array_equal(s, aux):
        print('Stationary distribution', s, 'reached in iteration', i)
        break
    aux = s
$\endgroup$
0
$\begingroup$

What we do know is all the entries of the probability matrix (40 x 40 in this example) and the total population number C (let C = 1000) which is a time-invariant or transition invariant in a stochastic Markov matrix. If we don't have any other criteria for defining the 40 elements of the initial vector x(0), then guessing or choosing the initial vector x (0) with all of its 40 inputs equal to C / n (25 in this example ) is our first simple ready-made answer. In order to ascertain whether or not this leads to a stable convergence of the solution, further investigation is necessary and actually is the crux of the question.

$\endgroup$

You must log in to answer this question.