# Linking and Cutting Spanning Trees
## 4 The Details
### Coupling  
In this section, we focus on bounding the mixing time. We did not obtain general analytical bounds from existing analysis techniques, such as couplings [6; 7], strong stopping times [7] and canonical paths [8]. The coupling technique yielded a bound only for cycle graphs and moreover a simulation of the resulting coupling converges for ladder graphs. Before diving into the reasoning in this section, we first need a finer understanding of the cycles generated in our process. We consider a closed walk to be a sequence of vertices \(v_{0},\ldots,v_{n}=v_{0}\), starting and ending at the same vertex, such that any two consecutive vertices \(v_{i}\) and \(v_{i+1}\) are adjacent; in our case \((v_{i},v_{i+1})\in A\cup\{(u,v)\}\). The cycles we consider are simple in the sense that they consist of a set of edges for which a closed walk can be formed that traverses all the edges in the cycle, and moreover no vertex repetitions are allowed, except for the vertex \(v_{0}\), which is only repeated at the end. Formally this can be stated as: if \(0\leq i,j<n\) and \(i\
eq j\), then \(v_{i}\
eq v_{j}\). The cycles that occur in our randomizing process are even more regular. A cordless cycle in a graph is a cycle such that no two vertexes of the cycle are connected by an edge that does not itself belong to the cycle. The cycles we produce also have this property, otherwise if such a chord existed then it would form a cycle on our tree \(A\), which is a contradiction. In fact, a spanning tree over a graph can alternatively be defined as a set of edges such that for any pair of vertices \(v\) and \(v^{\prime}\) there is exactly one path linking \(v\) to \(v^{\prime}\). A coupling is an association between two copies of the same Markov chain \(X_{t}\) and \(Y_{t}\), in our case the edge-swapping chain. The goal of a coupling is to make the two chains meet as fast as possible, i.e., to obtain \(X_{\tau}=Y_{\tau}\), for a small value of \(\tau\). At this point we say that the chains have coalesced. The two chains may share information and cooperate towards this goal. However, when analyzed in isolation, each chain must be indistinguishable from the original chain \(M_{t}\). Obtaining \(X_{\tau}=Y_{\tau}\) with a high probability implies that at time \(\tau\) the chain is well mixed. Precise statements of these claims are given in Section 5. We use the random variable \(X_{t}\) to represent the state of the first chain, at time \(t\). The variable \(Y_{t}\) represents the state of the second chain. We consider the chain \(X_{t}\) in state \(x\) and the chain \(Y_{t}\) in state \(y\). In one step, the chain \(X_{t}\) will transition to the state \(x^{\prime}=X_{t+1}\) and the chain \(Y_{t}\) will transition to state \(y^{\prime}=Y_{t+1}\). The set \(A_{x}\setminus A_{y}\) contains the edges that are exclusive to \(A_{x}\) and likewise the set \(A_{y}\setminus A_{x}\) contains the edges that are exclusive to \(A_{y}\). The number of such edges provides a distance \(d(x,y)=|A_{x}\setminus A_{y}|=|A_{y}\setminus A_{x}|\) that measures how far apart the two states are. We refer to this distance as the edge distance. We define a coupling when \(d(x,y)\leq 1\), which can be extended for states \(x\) and \(y\) that are farther apart by using the path-coupling technique [9]. To use the path-coupling technique we cannot alter the behavior of the chain \(X_{t}\) as, in general, it is determined by the previous element in the path. We denote by \(i_{x}\) the edge that gets added to \(A_{x}\), and by \(o_{x}\) the edge that gets removed from the corresponding cycle \(C_{x}\subseteq A_{x}\cup\{i_{x}\}\), in the case such a cycle exists. Likewise, \(i_{y}\) represents the edge that is inserted into \(A_{y}\) and \(o_{y}\) the edge that gets removed from the corresponding cycle \(C_{y}\subseteq A_{y}\cup\{i_{y}\}\), in the case such a cycle exists. The edge \(i_{x}\) is chosen uniformly at random from \(E\) and \(o_{x}\) is chosen uniformly at random from \(C_{x}\setminus\{i_{x}\}\).