1
$\begingroup$

Given that all edges in a markov chain are bi-directional (though not necessarily equally weighted), and each edge for a given node has equal probability, does the steady state always converge to a vector of proportions of the form $|d^{out}|/|E|$? (where $d^{out}$ is the outdegree of a given node)

For example, in sample network I've been playing with: $$P_a=\left[\begin{array}{cccc} .25&.25&.25&.25\\ .5&.5&0&0\\ .333 & 0 & .333 & .333 \\ .333 & 0 & .333 & .333 \\ \end{array}\right]$$

$$S^* = \left[\begin{array}{c}4/12\\ 2/12\\ 3/12\\ 3/12\\ \end{array}\right] = \left[\begin{array}{c} 0.3333\\ 0.1667\\ 0.25\\ 0.25 \end{array}\right]$$

I know this won't hold if I were to change the network to remove one direction of an edge, say:

$$P_b=\left[\begin{array}{cccc} .25&.25&.25&.25\\ .5&.5&0&0\\ .333 & 0 & .333 & .333 \\ 0 & 0 & 0.5 & 0.5 \\ \end{array}\right]$$

Or if the edges per node were not equally weighted: $$P_c=\left[\begin{array}{cccc} .5&.125&.125&.25\\ .5&.5&0&0\\ .333 & 0 & .333 & .333 \\ .333 & 0 & .333 & .333 \\ \end{array}\right]$$

I get intuitively that there is an equal weighting so the number of edges controls the uniform distribution, but what property causes it to happen in $P_a$ but not $P_b$ or $P_c$?

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.