Stochastic dynamics and Edmonds' algorithm

Figure 1.  Cycles. For given least cost correspondence, the set of cycles, closed cycles and simple cycles

Figure 2.  Aggregation of states in a CLE decomposition/Edmonds' algorithm. This diagram illustrates cyclic decomposition, moving step by step from $ \mathscr{P}_0 $ to $ \mathscr{P}_4 $. The cost function $ C(\cdot, \cdot) $ is given by edge weights, with missing edges denoting transitions with infinite cost. The values of $ C(\cdot, \cdot) $ on the initial partition $ \mathscr{P}_0 $ are assumed. Costs for partitions $ \mathscr{P}_{\ell} $, $ \ell>0 $, are calculated as described in the text. Least cost transitions are denoted by an underlined cost and a red arrow, so that a subset of elements in a partition is a cycle if is the vertex set for a (graphical) simple cycle of such edges in the diagram. At each step, one simple cycle is consolidated. For example, in moving from $ \mathscr{P}_0 $ to $ \mathscr{P}_1 $, cycle $ \{\{u\}, \{v\} , \{w\} \} \subset \mathscr{P}_0 $ is consolidated to form $ \{u, v, w\} \in \mathscr{P}_1 $, with the costs of transitions to and from $ \{u, v, w\} $ given by expressions (6) and (7) in the text. For example, $ C(\{u, v, w\}, \{y\}) = \min\{4-4+\infty, 4-2+ \infty, 4-2+5 \} = 7 $

Figure 3.  Disaggregation of states under Edmonds' algorithm. This diagram illustrates disaggregation and the construction of a spanning tree under Edmonds' algorithm, moving step by step from $ \mathscr{P}_4 $ to $ \mathscr{P}_0 $. At each step a composite is expanded into the cycle that formed it during the aggregation phase. For example, $ \{x, y, z\} \in \mathscr{P}_3 $ is expanded to $ \{\{x, y\}, \{z\} \} \subset \mathscr{P}_2 $ and edges from $ \{x, y\} $ to $ \{z\} $ and from $ \{z\} $ to $ \{x, y\} $ are added. Next, edges to or from the composite that is expanded are assigned to the elements of the cycle that solved (6) or (7) when the cycle was consolidated during the aggregation phase. For example, the edge from $ \{x, y, z\} $ to $ \{u, v, w\} $ is replaced by an edge from $ \{x, y\} $ to $ \{u, v, w\} $. Finally, an edge in the expanded cycle is deleted (denoted by a dotted line in the diagram). If the expanded composite was not the root of the tree at the previous step (e.g. $ \{x, y, z\} $ in $ \mathscr{P}_3 $), then the element of the cycle with an outgoing edge to outside of the cycle (e.g. $ \{x, y\} $ in $ \{\{x, y\}, \{z\}\} $) has its outgoing edge within the cycle deleted (e.g. the edge from $ \{x, y\} $ to $ \{z\} $). If the expanded composite was the root of the tree at the previous step (e.g. $ \{u, v, w\} $ in $ \mathscr{P}_1 $), then the element of the cycle with the highest least cost transition (e.g. $ \{u\} $ in $ \{\{u\}, \{v\}, \{w\}\} $) has its outgoing edge deleted (e.g. the edge from $ \{u\} $ to $ \{v\} $)

Figure 4.  The tree structure of decompositions. The tree structure of the decomposition considered in Figure 2. Edges connect composites to their pieces below them in the diagram. Edge weights give $ \underline{C}(\cdot) $ for the composite at the lower end of the edge in question. For each composite $ \alpha $, we give $ r_{\alpha} $ which measures the order of magnitude of the probability placed on $ \alpha $ by the invariant measure. These are calculated using the values of $ \underline{C}(\cdot) $. For example, $ \{x, y\} $ has $ r_{\{x, y\}} = 2 $, therefore by Lemma 3.1, one of its pieces has $ r = 2 $ and none have $ r<2 $. As $ \underline{C}(\{x\}) = 1< 2 = \underline{C}(\{y\}) $ and Lemma 2.1 states that $ \underline{C}(\{x\}) + r_{\{x\}} = \underline{C}(\{y\}) + r_{\{y\}} $, it must be that $ r_{\{x\}} = 3 $ and $ r_{\{y\}} = 2 $