Rapid Mixing of the Flip Chain over Non-Crossing Spanning Trees

Our main strategy is to compare the flip chain with another chain that is easier to analyse. Naturally we would choose a chain over structures that have a bijection with NCSTs. There are a few candidates (see e.g. [45]), and we choose $2$-Dyck paths. The bijection is defined through the same recursive structure, such as (1), for both $2$-Dyck paths and NCSTs. Note that while these structures share the same count and have bijections among them, a local move in one structure may cause drastic changes in another through the bijection. Thus we need to pick a starting point chain so that the distortion caused by the bijection is manageable and the overhead of the comparison can be bounded by a polynomial.

We represent a $2$-Dyck path by a string consisting of $2n$ ups ($\nearrow$) and $n$ downs ($\searrow$) such that any prefix of the string contains no fewer ups than twice the number of downs. The formal definition is given in Section 3.1. One can verify that the positions of the down arrows form a basis of a matroid. This generalises the so-called Catalan matroid introduced by Ardila [7]. Since the bases-exchange walk for these matroids has an $O(n\log n)$ mixing time [19], a natural choice would be to compare this chain with the flip chain over NCSTs. This chain randomly chooses a down arrow and moves it to a random valid location. However, as mentioned before, one move in the bases-exchange walk may change NCSTs drastically. See Example 2.

Since the bases-exchange chain appears to be difficult to compare with, we choose a different chain to control the changes in the corresponding NCSTs, and that is the adjacent move chain. Instead of moving a down arrow to a random location, we restrict the movement to be either left or right one position. More formally, each transition of this chain chooses two adjacent coordinates uniformly at random. If swapping them results in a valid path, we do so with probability $1/2$, and otherwise make no change. For example, suppose the current state is $\nearrow \nearrow \searrow \nearrow \nearrow \searrow$. If, with probability $1/5$, we choose the second and third positions, then the path will not change as swapping them leads to an invalid $2$-Dyck path. On the other hand, if (with probability $1/5$) we choose the third and fourth positions, then the chain will move to $\nearrow \nearrow \nearrow \searrow \nearrow \searrow$ with probability $1/2$ and remain unchanged otherwise.

While this chain is not directly studied before, we verify that the coupling method of Wilson [48] still applies here. Wilson’s original argument is applied to Lattice paths or the Bernoulli-Laplacian model (the uniform distribution over all strings with a fixed number of ups and downs). Without too much change, the same argument implies that the adjacent move chain over $2$-Dyck paths mixes in $O(n^3\log n)$ steps.

Our main technical contribution is then to compare the adjacent move chain over $2$-Dyck paths with the flip chain over NCSTs. We need to characterise how one adjacent move changes the NCSTs. Consider again $W_2$ in Example 2, and another $2$-Dyck path $W_3$ that can be reached from $W_2$ by a single adjacent move:

The adjacent move swaps the position $20$ and $21$. The corresponding NCST of $W_3$ is shown in Figure 2. Note that there are still a lot of altered edges, and in fact, one can also construct examples where $\mathrm{\Omega }(n)$ edges get changed after an adjacent move. This time, however, the reader may have observed a pattern of the changes: the blue part in the NCST of $W_3$ is the same as the red part in that of $W_2$, but shifted clockwise once. As formally proved in Section 5.1, each adjacent move corresponds to at most two edge flips, plus one shifting in a particular form (see (9)).

To apply the path method for Markov chain comparison [23], we need to simulate an adjacent move with a sequence of flip moves, and to be able to recover the initial and final states of the adjacent move, given the two states of the flip move and at most polynomial amount of additional information. The main task is to simulate the shift. We do so by identifying a hierarchical structure of the shift, and only flip edges following a particular pattern. This design allows us to uniquely recover the initial and final states of the shift, as long as we know the current transition, the recursion depth, and constant amount of extra information. This is the crux of our whole argument and is given in Section 5.

Theorem 1 is shown by combining the comparison argument with the $O(n^3\log n)$ mixing time of the adjacent move chain. The comparison has an overhead of $O(n^4)$, which, roughly speaking, consists of $O(n)$ for the encoding, $O(n)$ for the path length, and $O(n^2)$ to account for the transition probability difference. Finally, together with the $O(n)$ overhead resulting from spectral gaps, we obtain our mixing time bound of $O(n^8\log n)$.

McShine and Tetali’s mixing time argument for convex triangulations [38] is similar to our result in spirit, which is also built on a comparison argument with Wilson’s lattice path chain [48]. However, in their case the starting point is $1$-Dyck path and the argument is more straightforward. The idiosyncrasies of non-crossing spanning trees warrant a more complicated path construction.

We have mentioned that the down arrows of $2$-Dyck paths form bases of a matroid. However it appears difficult to directly relate that matroid and related dynamics with the flip chain. Another very similar structure is the graphic matroid, whose bases are spanning trees of a graph. The bases-exchange walk for matroids is known to mix very rapidly [6, 19]. However, with the non-crossing restriction, even when the points are in convex position, NCSTs do not form the bases of a matroid if we take all possible edges as the ground set. To see this, we give an example where the basis exchange property of matroids fails. Consider $4$ points $\{0,1,2,3\}$ on a circle, a tree $T_1$ consisting of edges $(0,1)$, $(1,3)$ and $(2,3)$, and another tree $T_2=\{(0,2),(1,2),(2,3)\}$. Remove the edge $(0,1)$ from $T_1$. The possible choices of the new edge to add are $T_2\setminus T_1=\{(0,2),(1,2)\}$, but neither of them results in a valid non-crossing spanning tree, contradicting to the basis exchange property. Nonetheless, it is an interesting open problem to utilise techniques for the rapid mixing of graphic spanning trees to obtain better bounds in the non-crossing spanning trees context.

There has been a flurry of new tools building upon [6, 19] for analysing Markov chains, most notable among which is the spectral independence technique [5]. However, the results utilising spectral independence or its variants mostly focus on spin systems, and non-crossing trees are not spin systems. The trees all have the same size, which is a constraint usually not present in spin systems. There are some exceptions, such as the optimal mixing time of the down-up walk of independent sets of the same size [29]. These analyses rely heavily on the relationship between the fixed size distribution with the one without size restrictions. There is no similar connection to be utilised for non-crossing trees.

The most straightforward open problem is to establish the correct order of the mixing time for the NCST flip chain. The $O(n^8\log n)$ bound in Theorem 1 is unlikely to be tight. Our starting point, the adjacent move chain for $2$-Dyck paths, has diameter $\mathrm{\Omega }(n^2)$ by a simple potential argument,¹¹1One can also consider how the area below the path evolves and show that the mixing time is at least $\mathrm{\Omega }(n^3/\log n)$, so Wilson’s bound is almost tight. and thus does not mix very fast. On the other hand, reconfiguration results [8, 10] imply that the flip chain has diameter $O(n)$. Therefore, we expect the flip chain to mix at least no slower than the adjacent move chain, instead of the polynomial slow-down in our current bound. On the other hand, there is no known lower bound on the mixing time other than the trivial $\mathrm{\Omega }(n)$ obtained via the diameter bound. It would be interesting to close or shrink this gap.

Another interesting problem is to study the flip chain when points are not necessarily in convex position. Recall that the complexity of counting NCSTs with input points in general position, either exactly or approximately, is not known. Studying the flip chain would be helpful in resolving the approximate counting complexity. Constructing a set of points such that the flip chain mixes torpidly (i.e., not mixing in polynomial time) would rule out direct MCMC approaches, and often torpid-mixing instances help people construct gadgets for hardness reductions. On the other hand, if this chain always mixes in polynomial time, then efficient approximate counting would be possible.

The path method [23] is a way to compare two Markov chains $P$ and $\tilde{P}$, with stationary distributions $\pi$ and $\tilde{\pi }$, by simulating any transition in $\tilde{P}$ using a series of transitions in $P$. This is a generalisation of the canonical path method by Jerrum and Sinclair [30].

For every pair of $x,y\in \mathrm{\Omega }$, let ${\mathrm{\Gamma }}_{xy}=(x=x_0,x_1,\mathrm{\dots },x_{\mathrm{\ell }-1},x_{\mathrm{\ell }}=y)$ be a path of length $\mathrm{\ell }=|{\mathrm{\Gamma }}_{xy}|$ in the state space where $P(x_{i-1},x_i)>0$ for all $i\in [\mathrm{\ell }]$. The congestion ratio $B$ for a collection of paths $\mathrm{\Gamma }={\{{\mathrm{\Gamma }}_{xy}\}}_{x,y\in \mathrm{\Omega }}$ is defined as

Roughly speaking, the congestion bounds how much of a slowdown the path method can cause. It gives an upper bound on how much of a bottleneck can result from our simulated transitions.

Imagine that there is a hiking frog starting from the sea level. Each time it takes a step forward, it either lifts itself up by $1$ meter, or drops by $k$ meters. The two conditions are interpreted as (1) at any point it cannot go below the sea level, and (2) after $(k+1)n$ steps it must land on the sea level. This view leads to the following terminology for $k$-Dyck paths. We replace $+1$ with an up-step $\nearrow$, and $-k$ with a down-step $\searrow$. The partial sum

indicates the height of the frog after $j$ steps. Below is an example of a valid $2$-Dyck path of length $21$.

The following simple fact is useful later.

The decomposition can be obtained as follows. The $B$ part begins at the position where the height first reaches $0$ (except the starting point), namely $\mathrm{𝖲𝗍𝖺𝗋𝗍}(B)=\min \{j:{\mathrm{ht}}_W(j)=0,j\ge 1\}$. Each $A_i$ part begins at the position one step after where the height reaches $i-1$ for the last time before the $B$ part, namely . See Figure 3 for an example of such a decomposition for a $2$-Dyck path.

Fact 7 immediately implies the recurrence on the number of $k$-Dyck paths of length $(k+1)n$, denoted by $C_{k,n}$:

This is called the $k$-Fuss-Catalan number [46, Chapter 4, A14], a generalisation of the Catalan number. It is well-known that the number of $1$-Dyck paths equals the Catalan number.

Non-crossing spanning trees for points in convex position have a one-to-one correspondence with $2$-Dyck paths. It will be more convenient to consider the following alternative way to draw the trees (see [45, Exercise 5.46]). Instead of putting points in convex position, we arrange them on a line. Each edge is represented by a curve, drawn above the line segment. A tree is non-crossing if and only if it can be drawn this way without any two edges intersecting (except at the endpoints). See Figure 4(a)(b) for the two drawings of the same tree. In other words, each edge is represented by a pair of integers $(a,b)$ where , and there does not exist any two edges $(a,b)$ and $(c,d)$ that . As a result, any subtree must consist of points labeled by consecutive numbers. For this reason, if a subtree is spanned by $s,s+1,\mathrm{\cdots },t$, we use a shorthand $[s,t]$ for it. A subtree is empty (consists of no edges) if $s=t$.

Resembling Fact 7 for $2$-Dyck paths, the above decomposition not only suggests exactly the same recurrence (1) for the number of $n$-edge non-crossing spanning trees, but also a one-to-one correspondence between $2$-Dyck paths and non-crossing spanning trees. Compare Figure 4(c) and Figure 3 for instance.

The decomposition has the following useful property.

The proof of Proposition 10 can be found in the full version [4]. Inspired by the decomposition, we introduce the following terminology that will be useful later.

A single adjacent move on non-crossing spanning trees still requires altering an $\mathrm{\Omega }(n)$ number of edges. Yet, we will show that it consists of a constant number of flip moves, plus one subtree shifting, taking the form of

where the bubble does not change. Note that the overarching edge of the subtree remains unchanged. This is formally defined as follows, using the non-crossing tree decomposition.

This particular form of shifting may look strange at first sight. A more intuitive version would be just moving a subtree left or right, without caring about the overarching edge or the other side of the gap. However, as it will become clear later when we bound the congestion of the paths, it is this form of shifting that allows an efficient encoding.

Next is the characterisation of an adjacent move via flip moves and shifting.

The proof of Lemma 16 can be found in the full version [4]. There are two cases in this lemma, depending on whether one or two steps the first time the $2$-Dyck path goes below the end of the adjacent move, which we call Type-1 and Type-2 moves. See Figure 5 (1a) and (2a) for illustrations of the two types of transitions. The flip moves to simulate the adjacent move are also intuitive. See the illustrations in Figure 5 (1b) and (2b).

The next step is to resolve the shifting, by designing a sequence of flippings that simulates it. We call this sequence of flip moves a shift sequence. The design of the shift sequence is the trickiest part of the whole comparison argument, because we have to be able to recover the initial and final states by just looking at a transition with some succinct extra encoding. We only need to deal with right shifting, as for left shifting we just reverse the sequence.

The proof of Lemma 17 can be found in the full version [4]. Essentially, we design a recursive way of simulating shifts. We decompose the subtree to shift into minimal segments, and then move them one at a time. To move a minimal segment, we perform edge flips so that subtrees of the minimal segment are in the form of a shift, and finish moving it using recursion. See Figure 6 for an illustration of an example.

We are going to apply the path method, namely Theorem 3, to compare $P_{\mathrm{AM}}$ and $P_{\mathrm{FM}}$. Because of the bijection between $2$-Dyck paths and NCSTs, we simply treat $P_{\mathrm{AM}}$ and $P_{\mathrm{FM}}$ as having the same stationary distribution. To compare the two chains, we will need to construct a path (namely, a sequence of transitions) for any two $2$-Dyck paths $I$ and $F$ where $P_{\mathrm{AM}}(I,F)>0$ using only transitions in $P_{\mathrm{FM}}$. We summarise the construction in Algorithm 1, with half of the procedure omitted due to redundancy. This construction follows closely the simulation of an adjacent move via two flip moves and one shifting in Lemma 16, and then simulating the shifting via flip moves in Lemma 17. The edges $a=(a_1,a_2)$, $e=(p,g_e+1)$ and $g_a$ in Transition1($I,F$) are defined in the proof of Lemma 16. Intuitively, $a$ and $e$ are the distinguished edges marked in Figure 5, and $g_a,g_a+1$ is the unique gap beneath $a$. The markers (#0) to (#5) are used in the proof of Lemma 19. We expand out the Type-1 move and omit the details of the Type-2 move to avoid redundancy. (The flip moves for Type-2 moves are described in the proof of Lemma 16 and Figure 5(2$\ast$), and the ShiftLeft sequence is the reverse of ShiftRight.)

Let $T_I$ and $T_F$ be the non-crossing spanning trees corresponding to $I$ and $F$. The construction yields a path $T_I=Z_0\to Z_1\to \mathrm{\cdots }\to Z_{\mathrm{\ell }}=T_F$ where $P_{\mathrm{FM}}(Z_i,Z_{i+1})>0$ for any $i\le \mathrm{\ell }-1$. Its validity, namely that each transition is valid, is implied by Lemma 16 and Lemma 17. These two lemmas also imply an upper bound on the length of the path $\mathrm{\ell }\le 3n+2$ ($3n$ for the shift sequence and $2$ for the two simple flips).

The goal of the Markov chain comparison argument is to show the following lemma:

Lemma 18 is a straightforward application of Theorem 3 where we bound the congestion using Equation 8 and Corollary 20. The proof can be found in the full version [4].

The next lemma shows that our canonical path construction ensures that each transition in the flip move $P_{\mathrm{FM}}$ is used by a limited number of $(I,F)$ pairs in the adjacent move $P_{\mathrm{AM}}$. This is proved by designing an encoding such that we can uniquely recover the $(I,F)$ pair from the current transition and the encoding. The number of $(I,F)$ pairs is then bounded by the number of possible encodings, which we ensure to be linear in $n$.