"MC with states that are connected in a line is reversible."

95 Views Asked by At

There are two examples from my university's past final solution backs up the statement in the title.

Example1 Time reversible MC

Example2

example2-1 example2-2


My question is (1) what kind of line-form diagram is time reversible. What about, for example, the diagram of $P_{i,i+1} = p, P_{i,0}=1-p$? What if the diagram is not aperiodic? (2) How to prove the statement?

1

There are 1 best solutions below

2
On BEST ANSWER

Another way of saying that a chain is reversible is that it is in detailed balance, or more precisely that it is in detailed balance with respect to some distribution $\pi$. This means that $\pi_i p_{ij} = \pi_j p_{ji}$ for all pairs of states $i,j$, and $\pi$ also must be a distribution i.e. with nonnegative entries summing to $1$. This essentially means that at equilibrium, it isn't just that probability current into and out of each state balance out, but in fact each pair of states that are connected balance each other's probability currents.

A line in this context is just a chain diagram where the only edges except for self-loops are between directly adjacent nodes. The reason for this is that now the detailed balance equations are solvable by recursion: $\pi_i=\frac{\pi_{i+1} p_{i+1,i}}{p_{i,i+1}}$, then the final $\pi_N$ can be chosen for normalization, and then everything propagates back down through these formulas. This is one of the advantages of the concept of detailed balance: it gives more restrictive equations which might not even have any solution, but if they do have a solution then they will furnish a stationary distribution (the only one, if the chain is irreducible).

Something like your $p_{i,i+1}=p,p_{i,0}=1-p$ is "topologically irreversible" since there is no probability to get back to some $i \geq 2$ after a transition to zero in one step. A transition diagram is "topologically reversible" if whenever $p_{ij}>0$, either $i$ is transient or $p_{ji}>0$. This isn't enough to put the chain in detailed balance, but it is a necessary condition.

A chain in detailed balance can only have period at most 2, but a deterministic cycle with period 2 is in detailed balance.