7
$\begingroup$

Define $$ A = \left( \begin{matrix} .5 & .5 \\ .5 & .5 \end{matrix} \right),\; \; B = \left( \begin{matrix} .99 & .01 \\ .01 & .99 \end{matrix} \right), \; \; C = \left( \begin{matrix} .01 & .99 \\ .99 & .01 \end{matrix} \right)$$

Taken as Markov chains, clearly $A$ permits movement between its states better than $B$, and $C$ permits movement between its states better than $A$.

Is there some sort of measure on the space of Markov chains that measures how well they permit movement between their states? Some kind of congestion or accessibility statistic?

Edit: I know about mixing rates, but I'm wondering about a statistic that works for absorbing Markov chains too.

Improve this question
$\endgroup$
5
  • 1
    $\begingroup$ One measure would be the tendency to remain in the same state, which could be measured in a crude way by some function of the trace $\endgroup$
    – Glen_b
    Nov 4, 2015 at 21:06
  • $\begingroup$ Agreed. For non-absorbing I was thinking something like $\sum_{i} \pi_i (1-p_{ii})$ where the sum is over all states, which is the probability of moving away from the current state weighted by the probability of being in that state (so basically, the probability of moving). I don't know how to extend this to absorbing though (no stationary dist), and "a function of the trace" seems imperfect in that it doesn't consider the probability of being in each state and weights them all equally. $\endgroup$
    – Bianca
    Nov 4, 2015 at 21:11
  • 3
    $\begingroup$ It seems clear that any useful measure will and indeed must be calculatable directly from the transition probabilities as these are what define a particular class of chains. Also, there will be some loss of information in that in general no scalar measure will be reversible to give a matrix uniquely. But the variance of the probabilities is a first candidate as the variance for $A$ is zero and the variance for the other two is much larger. It is naturally an inverse measure. But what do you want this measure for? $\endgroup$
    – Nick Cox
    Nov 4, 2015 at 23:54
  • 1
    $\begingroup$ Variance is a candidate, yes, but will give the same number for $B$ and $C$, which doesn't reflect the answer I want. I suppose we could combo ideas... there could be a way to do signed variance, where the sign comes from the trace? My supervisor is uncomfortable with me posting details of unpublished research, but vaguely: We've come up with a new way of constructing a very large matrix important in biology, and we'd like to show that it allows for flow between states better than the last construction, which sometimes got stuck in certain states for long periods of time. $\endgroup$
    – Bianca
    Nov 5, 2015 at 17:34
  • 1
    $\begingroup$ We're having to speculate about what you're really looking for, so further explanation of the motivation of this question would be welcome. One thought is to compute expected residence time of non-absorbing states, where "residence time" means the number of steps that occur before the system transitions out of its current state. There are direct relationships between expected residence times, mean flow speeds, and "retardation factors" in chains that represent advective and diffusive transport of substances carried along in flows. $\endgroup$
    – whuber ♦
    Mar 31, 2016 at 15:39

2 Answers 2

Reset to default
1
$\begingroup$

Maybe the conductance of the Markov chain is the right notion to look at. Let $P\in[0,1]^{n\times n}$ be a transition matrix with stationary distribution $\pi$ (in your cases, $\pi$ is always the uniform distribution). The conductance of $P$ is

$$\Phi(P):=\min_{S\subset [n], \pi(S)\le\frac{1}{2}}\frac{\sum_{i\in S,j\in S^c} \pi(i)\cdot P_{i,j}}{\pi(S)}.$$ See for example "Conductance and Rapidly Mixing Markov Chains" by James King.

Your examples yield $\Phi(A)=0.5$, $\Phi(B)=0.1$, and $\Phi(C)=0.99$.

Improve this answer
$\endgroup$
3
  • 1
    $\begingroup$ As per comment of @Bianca above, conductance "give<s> the same number for B and C, which doesn't reflect the answer I want." $\endgroup$
    – Mark L. Stone
    Mar 31, 2016 at 15:30
  • $\begingroup$ @MarkL.Stone: There was a typo in $\Phi(C)$ in the previous version of my answer, this is now corrected. $\endgroup$
    – Tobias Windisch
    Mar 31, 2016 at 17:07
  • 1
    $\begingroup$ Based on that, I hereby "withdraw" my above comment, but have not deleted it so as not to leave your comment hanging "in left field". $\endgroup$
    – Mark L. Stone
    Mar 31, 2016 at 17:12
0
$\begingroup$

If the transition graph is strongly connected (i.e. given an initial state, any other state is reachable with p>0, possibly via intermediate states) , then as time goes to infinity the probability to find the system in a given state does not depend on the initial state. That is to say, there is a chance $$p_i(X)$$ to find the system in state X after i steps, which converges to some constant $$p(X)$$ which is a function only of the transition matrix (The stationary distribution $\pi$ in Tobias's answer).

For all 3 your examples, this $\pi$ is simply (.5, .5) as both states are equally likely. This makes sense: $$\left( \begin{matrix} .5 \\ .5 \end{matrix} \right) \left( \begin{matrix} .5 & .5 \\ .5 & .5 \end{matrix} \right) = \left( \begin{matrix} .5 \\ .5 \end{matrix} \right)$$ but also $$\left( \begin{matrix} .5 \\ .5 \end{matrix} \right) \left( \begin{matrix} .9 & .1 \\ .1 & .9 \end{matrix} \right) = \left( \begin{matrix} .5 \\ .5 \end{matrix} \right)$$ but in general this need not hold. Not all states have to be equally likely. Simple example: $$\left( \begin{matrix} .5 & .5 & 0 \\ .25 & .5 & .25 \\ 0 & .5 & .5 \end{matrix} \right) $$ with probabilities (.25, .5, .25). You can think of this as a Left<->Middle<->Right triplet of states, with a 50% chance of moving but not directly from left to right. Since you always have to go through the middle, it's most likely.

Now, as the comments on the question already indicated, you can use this probability to weigh the chances of staying in each different state.

In your simple examples, the respective results would be 0.5, 0.99 and 0.1, simply because the chances to stay in the same state (values of the diagonal) are the same on the diagonal. For non-trivial matrices, it would be a weighted average of the diagonal.

This means that the exact off-diagonal values do not matter. I believe this reflects the intent of the question, which does not differentiate between different kind of state transitions either.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.