# Linking and Cutting Spanning Trees
## 4 The Details
### Coupling
#### 4.2.2. \(d(x,y)=1\)
In this case the chains coalesce, i.e., \(x^{\prime}=y^{\prime}\) (see Figure 6). When the chains coalesce, the edges \(e_{x^{\prime}}\) and \(e_{y^{\prime}}\) no longer exist and the set \(U_{y^{\prime}}\) is no longer relevant. Figure 5: Case 2. Figure 7: Case 4.a.i, case 4.b.i, and case 4.c.i. Figure 10: Case 4.a.iii, case 4.b.iv, and case 4.c.iv, when \(B^{\prime}\) is true. If \(|C_{x}|<|C_{y}|\) then \(X_{t}\) will choose \(o_{x}\in I\) with a higher probability then what \(Y_{t}\) should. Therefore, we use a Bernoulli random variable \(B\) with a success probability \(p\) defined as follows: \[p=\frac{C_{x}-1}{C_{y}-1}\] In Lemma 2 we prove that \(p\) properly balances the necessary probabilities. For now note that when \(|C_{x}|=|C_{y}|\) the expression for \(p\) yields \(p=1\). This is coherent with the following cases, because when \(B\) yields true we use the choices defined for \(|C_{x}|=|C_{y}|\). The following situations are possible: 1. If \(o_{x}=e_{x}\) then we reduce to the case 4.\(a\).i, both when \(B\) yields true or when \(B\) fails and \(s_{y}\in U_{y}\). Set \(o_{y}=e_{y}\) (see Figure 7). The new case occurs when \(B\) fails and \(s_{y}\
otin U_{y}\), in this situation set \(o_{y}=s_{y}\) and \(U_{y^{\prime}}=(U_{y}\cap C_{y})\setminus\{o_{y}\}\) (see Figure 12). 2. If \(o_{x}\in I\setminus\{i_{x}\}\) then we reduce to the case 4.\(a\).ii when \(B\) yields true. Set \(o_{y}=o_{x}\) (see Figures 8 and 9). When \(B\) fails and \(s_{y}\in U_{y}\) we have a new situation. Set \(o_{y}=e_{y}\) and \(U_{y^{\prime}}=I\setminus\{i_{x}\}\). The chains preserve their distance, i.e., \(d(x^{\prime},y^{\prime})=1\) (see Figure 13). The alternative, when \(s_{y}\
otin U_{y}\), is considered in the next case (4.\(b\).iii). If \(o_{x}\in I\setminus\{i_{x}\}\) and \(B\) fails and \(s_{y}\
otin U_{y}\). We have a new situation,set \(o_{y}=s_{y}\). The distance increases, \(d(x^{\prime},y^{\prime})=2\) (see Figure 14). Set \(U_{z^{\prime}}=I\setminus\{i_{x}\}\) and \(U_{y^{\prime}}=(U_{y}\cap E_{y})\setminus\{o_{y}\}\). 4. If \(o_{x}\in E_{x}\setminus\{e_{x}\}\) then if \(s_{y}\in U_{y}\) use case 4.\(a\).iii (Figure 10), otherwise, when \(s_{y}\
otin U_{y}\), use case 4.\(a\).iv (Figure 11). Figure 11: Case 4.\(a\).iv, case 4.\(b\).iv, and case 4.\(c\).iv. * If \(|C_{x}|>|C_{y}|\) we have the following situations: 1. If \(o_{x}=e_{x}\) then use case 4.a.i and set \(o_{y}=e_{y}\) (see Figure 7). The chains coalesce. 2. If \(o_{x}\in I\setminus\{i_{x}\}\) then use case 4.a.ii and set \(o_{y}=o_{x}\) (see Figures 8 and 9). 3. If \(o_{x}\in E_{x}\setminus\{e_{x}\}\) then we use a new Bernoulli random variable \(B^{*}\) with a success probability \(p^{*}\) defined as follows: \[p^{*}=\left(\frac{1}{C_{y}-1}-\frac{1}{C_{x}-1}\right)\times\frac{(C_{x}-1)(I -1)}{E_{x}-1}\] In Lemma 2 we prove that \(B^{*}\) properly balances the necessary probabilities. For now, note that when \(|C_{x}|=|C_{y}|\) the expression for \(p^{*}\) yields \(p^{*}=0\), because \(1/(C_{y}-1)-1/(C_{x}-1)\) becomes \(0\). This is coherent because when \(B^{*}\) returns false we will use the choices defined for \(|C_{x}|=|C_{y}|\). The case when \(B^{*}\) fails is considered in the next case (4.c.iv). Figure 12: Case 4.b.i when \(B\) fails and \(s_{y}\
otin U_{y}\). Figure 13: Case 4.b.ii. Notice that the case 4._a._ii applies when \(C_{x}=C_{y}\), thus solving this situation as a particular case. This case is shown in Figure 4:0 It may even be the case that \(C_{x}=C_{y}\) and \(C_{x}\) and \(C_{\epsilon}\) are disjointed, i.e., \(C_{x}\cap C_{\epsilon}=\emptyset\). This case is not drawn. Formally, a coupling is Markovian when Equations (1a) and (1b) hold, where \(Z_{t}\) is the coupling, which is defined as a pair of chains \((X_{t},Y_{t})\). The chain \(M_{t}\) represents the original chain. Figure 4:1 Figure 4:2  
To establish vital insight into the coupling structure we will start by studying it when it is Markovian.