# Cycle representations of Markv paths

Cycles are my personal obsession, so I try to intercept any paper containing the words “cycle” and “Markov” (with the aim of, one day, condense all this stuff into a report on cycles in Stochastic Thermodynamics). In this post and a future one I will try to explain what I understand about this remarkable paper:

Chen Jia, Daquan Jiang, Minping Qian, Cycle symmetries and circulation fluctuations for discrete-time and continuous-time Markov chains, arXiv:1407.1263

The Qian dinasty and their students and coworkers are major experts on the particular techniques in Markov processes that are at the interface with NonEquilibrium Statistical Mechanics. I suggest taking a look at the very impressive book Mathematical Theory of Nonequilibrium Steady States. In particular, at some point in one of their early papers I found one of the “early manifestations” of the Fluctuation Theorem for Markov processes that was re-discovered years later by many people. I also have my own version of the FT, on which we will briefly touch later on.

So let’s consider the trajectory performed by a Markovian walker on some state space (not displayed: if you really want it, draw dots at line intersections and elsewhere):

It obviously forms many cycles. How do we characterize this trajectory in terms of the cycles it forms?

There are several ways. The first, which subtends Schnakenberg’s theory and the corresponding Fluctaution Theorems by Andrieux and Gaspard [J. Stat. Phys. 2007] (then generalized by myself [J. Stat. Mech. 2014] to transient times) is as follows. Consider the support of the trajectory (the figure it draws), and then remove as many pieces (correspoding to some Markovian transition between inner states) as it takes in such a way that the support is still connected, but contains no cycles. One then obtains a so-called spanning tree, which is sort of the cycle-less scheleton of the trajectory, for example:

Now, notice that the trajectory is fully described by the initial and final states and by the ordered sequence of missing segments crossed by the Markovian walker, for example $x = a,b,c,d,e$ on the left-hand side of this figure:

Moreover, by definition, notice that when one adds one of the missing lines (e.g. $c$ on the l.h.s.) one encloses a unique cycle, so that the trajectory can be fully described by the sequence of cycles on the right-hand side of the above figure. Physically speaking, one can associate to each such cycle a value $\Sigma(x)$ sometimes called affinity and measuring the entropy delivered to the environment when performing a thermodynamic cycle, and such that the total entropy produced by the trajectory is $\Sigma(a) + \ldots \Sigma(e)$.

However, what the Qians have in mind by cycle representation is different. The idea is very simple: whenever the Markov walker encloses a cycle, record that cycle and cut it off, util you’re left with a final trajectory without cycles:

Again, one obtains a sequence of cycles that represents the trajectory (i.e. one could reconstruct the trajectory by knowing initial and final states, and the sequence of cycles), but different from the Schnakenberg one. The difference is quite substantial. In fact, suppose that the Markovian walker kept moving along these lines and performing more and more cycles. Then, in the Schnakenberg representation this would keep adding cycles of type $a,b,c,d,e$, and nothing different. Instead, in the latter representation any self-avoiding cycle that can be drawn without lifting the pencil could be generated, which is a larger set comprising $a,b,c,d,e,ab,bc,abc,ec,ea,eca$. As regards the entropy production, one obtains the same result provided the cycle affinity of compound cycles is additive, $\Sigma(ab) = \Sigma(a)+\Sigma(b)$ etc.

Another interesting aspect of the inequality of these two representations has to do with time reversal, which is believed to be a crucial operation in the formulation of Fluctuation Theorems. A simple look at the Schnakenberg cycle representation of a trajectory conveys that by swapping initial and final points and by inverting the sequence of visited missing edges to $-e,-d,-c,-b,-a$ (the minus meaning that now the cycles have to be toured in the other direction) one obtains the exact time-reversed trajectory.  This is not the case in the Qians/Kalpazidou representation. In fact if we were to invert the trajectory we would obtain a different set of (backward) cycles:

This means that time-inversion leads to a nontrivial symmetry of the cycle currents. In fact, numbering from 1 to 11 the sequence of segments of the forward trajectory (on the left of next figure), the trajectory that does invert the sequence of cycles is the following (on the right):

Notice that it is not obtained by setting $i \to 11 - i$ (which would correspond to time inversion). Still, the second trajectory is a cut-and-paste of fragments of the time-reversed trajectory, and therefore by the Markov property they have the same probability. Moreover, it can be proven (I think) that the trajectory that does invert all of the cycle fluxes is unique, hence there is a one-to-one correspondence. And therefore, one should expect the Fluctuation Theorem for cycle currents to be satisfied, despite it not being a direct consequence of time-reversal arguments.