Faster Triangulation Mixing via Transport Flows

A random walk matrix $P\in {ℝ}^{\mathrm{\Omega }\times \mathrm{\Omega }}$ is a matrix with non-negative entries, all of whose rows sum to 1. Formally,

A distribution $\pi :\mathrm{\Omega }\to [0,1]$ is called stationary for $P$ if, $\pi P=\pi$. The walk described by $P$ is reversible, if the following detailed balance conditions hold:

We will also write $\alpha (P)={\min }_{x\in \mathrm{\Omega }}P(x,x)$ for the holding probability of the random walk $P$ and ${\pi }^{\ast }={\min }_{x\in \mathrm{\Omega }}\pi (x)$ for the minimum measure of $\pi$.

The $ϵ$-mixing time of a random walk is defined to be the least time point such that after $t$ steps of random walk according to $P$, the distribution of the random walk is $ϵ$-close to the stationary distribution regardless of the initial distribution, i.e.

where ${\Vert \mu -\nu \Vert }_{\mathrm{𝚃𝚅}}=1/2\cdot {\sum }_{x\in \mathrm{\Omega }}|\mu (x)-\nu (x)|$.

Let $(\mathrm{\Omega },P,\pi )$ be an ergodic Markov chain and $\mathrm{\Omega }={\bigcup }_{t\in T}{\mathrm{\Omega }}_t$ a decomposition of its state space. When the stationary distribution $\pi$ is clear from context, we will simply write $(\mathrm{\Omega },P)$ in place of $(\mathrm{\Omega },P,\pi )$. We write $\overline{\pi }(t)=\pi ({\mathrm{\Omega }}_t)$ for all $t\in T$ and define the projection chain by the triple $(\overline{\mathrm{\Omega }},\overline{P},\overline{\pi })$ where

when $t\ne t^{\prime }$ and with self loops for the remaining probabilities. That is, the probability of transitioning from class $t$ to $t^{\prime }$ in the projection chain is the probability we transition from any element of ${\mathrm{\Omega }}_t$ to any element of ${\mathrm{\Omega }}_{t^{\prime }}$ in the original chain conditioned on being in ${\mathrm{\Omega }}_t$. Naturally, by defining ${\pi }_t(x)=\frac{\pi (x)}{\pi ({\mathrm{\Omega }}_t)}$ we can also define the restriction chain as the triple $({\mathrm{\Omega }}_t,P_t,{\pi }_t)$ where

for all $x,y\in {\mathrm{\Omega }}_t$.

Let $k$ be a positive integer, $({\mathrm{\Omega }}_{,}{P}_i,{\pi }_i),1\le i\le k$ be Markov chains and $w$ a distribution on $k$. Consider the product chain $(\mathrm{\Omega },P,\pi )$ with $\mathrm{\Omega }={\prod }_{i=1}^n{\mathrm{\Omega }}_i$ and

Equivalently, the transition from every state consists of picking a coordinate in $[k]$ according to $w$ and then change this coordinate according to $({\mathrm{\Omega }}_i,P_i)$. It is straightforward to verify that the stationary distribution of the product chain is $\pi ={⨂}_{i=1}^n{\pi }_i$. We note that the graph which underlies the product chain corresponds to a weighted Cartesian product of the graphs which underlie the individual chains $(\mathrm{\Omega },P_i,{\pi }_i)$.

Let $f:\mathrm{\Omega }\to ℝ$ be any function. Given a probability measure $\pi :\mathrm{\Omega }\to [0,1]$ the variance functional ${\mathrm{Var}}_{\pi }(f)$ is:

If ${\bigcup }_{t\in T}{\mathrm{\Omega }}_t$ is a decomposition of $\mathrm{\Omega }$, then the following equation is known as the law of total variance

where $F:T\to ℝ$ is defined as $F(t)={𝔼}_{{\pi }_t}f$ and $\overline{\pi }$ is the stationary distribution of the projection chain.

We will make use of the following consequence of Jensen’s inequality,

The second functional we will need is that of entropy. If $f:\mathrm{\Omega }\to {ℝ}_{\ge 0}$ is a non-negative function, the entropy ${\mathrm{Ent}}_{\pi }(f)$ of $f$ is

Similarly to variance, we have the analogous law of total entropy for a decomposition ${\cup }_{t\in T}{\mathrm{\Omega }}_t$ of the state space:

The following comparison between variance and entropy is well-known:

For a reversible $P\in {ℝ}^{\mathrm{\Omega }\times \mathrm{\Omega }}$ with stationary measure of $\pi$, we define the Dirichlet form ${ℰ}_P(f)$ of $f$ as follows:

The Poincaré constant or the spectral gap of $P$ and is denoted by $\mathrm{𝚐𝚊𝚙}(P)$ and is the solution to the following variational formula,

The log-Sobolev constant $\mathrm{𝚕𝚜}(P)$ of $P$ is defined as the solution to the following variational formula,

The following result is well-known, see e.g. [19]:

The following result shows that the log-Sobolev constant controls the mixing time in a very precise manner,

In our argument, it will be important to write the Poincaré and LSI constants of a product chain in terms of the corresponding constants of its components. The relation between them is well-known and given by the following lemma:

A triangulation of a point set (in, say, the Euclidean plane) is a maximal collection of pairwise non-crossing edges connecting pairs of points. In the special case that the point set is convex, every triangulation of the point set includes the convex hull, and thus we will assume the point set is a convex polygon. Since the edges belonging to the convex hull are in every triangulation, we will identify a triangulation $x$ by its set of non-hull edges, and we will call these edges diagonals.

Given a diagonal $d$, it will be convenient for us to define the length of $d$ to be the number of edges in a shortest path consisting of polygon edges that connects the two endpoints of $d$.

One can view a triangulation naturally as a planar graph. The dual graph of a convex polygon triangulation is a binary tree. One can orient the polygon so that the dual tree is rooted, and therefore the number of triangulations of an $n+2$-gon is equal to the number of binary plane trees with $n$ nodes. This is known to be equal to the Catalan number [29] $C_n=\frac{1}{n+1}\left(\genfrac{}{}{0pt}{}{2n}{n}\right).$ Notice that the Catalan numbers satisfy the recurrence relation,

where $C_0=1$ (see for example, [25, Chapters 5 and 7]). With this, it is easy to observe that $C_n$ counts the number of rooted subtrees of the infinite binary tree on $n$ vertices, or equivalently, unlabelled rooted plane trees on $n$-vertices. Henceforth, we will refer to such trees as Catalan trees.

Using Stirling’s formula, $C_n$ is seen to grow asymptotically as $\mathrm{\Theta }\left(\frac{1}{n^{3/2}}\cdot 4^n\right)$.

The triangulation flip walk (which we will also call the triangulation walk) is the following random walk, defined with respect to the regular $n+2$-gon: start with an arbitrary triangulation $x$. Then repeatedly flip a uniformly random diagonal $d$ of the current triangulation: that is, remove $d$ and replace it with the unique diagonal $d^{\prime }\ne d$ that can be added to the triangulation $x$ without introducing a crossing. (The removal of $d$ induces a quadrilateral formed by the two triangles incident to $d$. The existence and uniqueness of $d^{\prime }$ can be seen to follow from the convexity of the $n+2$-gon.) We impose a holding probability of 1/2 (see Section 2.1).

The flip walk is invariant to perturbations of the $n+2$-gon, so long as it remains convex.

The flip walk is known to be isomorphic to the rotation walk (see e.g. [41]) on binary trees. A rotation in a binary tree is an operation of one of two forms. The first form is as follows: take a parent node $z$ and a left child $w$ of $z$. Replace $z$ by $w$: that is, make $w$ a child of the parent of $z$ (a left child if $z$ is a left child, a right child if $z$ is a right child) – or, if $z$ is the root, make $w$ the root. Let $w$ retain its left child; let $z$ retain its right child. Then, let $u$ be the right child of $w$; and make $u$ the new left child of $z$.

The second form is the mirror image of the first: let $w$ be a right child of $z$, and proceed as in the first case but with left and right reversed.

The rotation walk is as follows: start with an arbitrary binary tree on $n$ nodes. Then repeatedly choose a uniformly random edge in the current tree, and perform a rotation at the parent node of that edge. (Impose a $1/2$ holding probability as in the triangulation walk.)

The isomorphism between the two walks follows from observing the correspondence between a triangulation flip and a tree rotation.

A standard technique in bounding the mixing times of Markov chains uses canonical paths. The idea is to show that the state space of the chain is in some sense free of “bottlenecks”, by finding a path between each pair of states such that no edge belongs to too many paths. A generalization of canonical paths is to construct a multicommodity flow: a collection of flow functions in which for every pair of states $s,t\in \mathrm{\Omega }$, $s$ sends a unit of flow to $t$ through paths in the state space $\mathrm{\Omega }$. The congestion of a multicommodity flow is the maximum, over all edges, of the amount of flow sent across the edge, summed over all $s,t$ pairs that use the edge.

Two classical theorems relate canonical paths (more generally, multicommodity flows) to mixing. The first uses the Cheeger inequalities to obtain an upper bound on the relaxation time from an upper bound on the congestion in a multicommodity flow. However, one suffers a quadratic cost in this process, as well as an additional cost in passing from the relaxation time to the mixing time, [42, Theorem 2.1]. The latter problem can be solved in some cases using a result in [34]. [20] used this theorem to obtain an $\tilde{O}(n^3)$ mixing time for the triangulation walk.

Another theorem [19] allows one to pass from flows to relaxation time without the quadratic cost; however, one trades this cost for a cost incurred in analyzing the worst-case length of a path in the construction. The worst-case path length is sufficiently long in the construction in [20] that it is not clear how to apply the theorem in this case.

In this paper, rather than using multicommodity flows, it will be useful to consider a flow function from one set of states $S\subseteq \mathrm{\Omega }$ to a set $T\subseteq \mathrm{\Omega }$, where we only use a single commodity. [20] gave a notion of multi-way single commodity flows. We adapt the formulation as follows.

Given $S,T\subseteq \mathrm{\Omega }$ where $S\cap T=\mathrm{\varnothing }$, let an $S$-$T$ flow be a function

such that $\varphi (x,y)=-\varphi (y,x)$ for all $x,y$, and such that, defining the net flow out of a state $x\in \mathrm{\Omega }$ to be ${\sum }_{y\in \mathrm{\Omega }:P(x,y)>0}\varphi (x,y)$:

1. (i)

   the net flow out of each $x\in S$ is equal to $\pi (T)$ ,

2. (ii)

   the net flow into each $y\in T$ is equal to $\pi (S)$ , and

3. (iii)

   the net flow into (and the net flow out of) each $x\in \mathrm{\Omega }\setminus \left(S\cup T\right)$ is zero.

(Here, if the net flow out of $x$ is $\varphi$ then we let the net flow into $x$ be $-\varphi$.)

We begin by presenting the two key partitions of the triangulation state space given by [36] and [20] and outlining some of their main properties. The central triangle of a triangulation is the triangle which contains the center of the polygon; in the case where the center lies on one of the diagonals, we slightly perturb the center so that it lies in a unique triangle.

Let $T$ be the set of central triangles. Define the central triangle partition as the projection chain $\left(\overline{\mathrm{\Omega }}=T,\overline{P},\overline{\pi }\right)$ corresponding to the decomposition

Recall that the transitions are given by

when $t\ne t^{\prime }$ and with self loops for the remaining probabilities, while the stationary distribution $\overline{\pi }$ satisfies $\overline{\pi }(t)=\pi ({\mathrm{\Omega }}_t)={\sum }_{x\in {\mathrm{\Omega }}_t}\pi (x)$. According to the law of total variance, we may decompose

Since our goal is to obtain a Poincaré inequality, we want to bound both the terms by the Dirichlet form of the overall chain. Note that the second term is the average restricted variance in ${\mathrm{\Omega }}_t$, i.e. over triangulations with a given central triangle $t$. As the average of the Dirichlet forms of the restrictions is bounded by Dirichlet form of the overall chain (this is straightforward to check, but we will prove it explicitly when we use it), we need a meaningful Poincaré inequality for each restriction chain. A crucial observation is that every restriction chain is in fact a product chain over smaller triangulation walks (see Figure 1). This, combined with Lemma 7, will enable us to obtain a recursive bound on the Poincaré constant.

It remains to bound ${\mathrm{Var}}_{\overline{\pi }}F$, the variance on the projection chain, by the Dirichlet form on the overall chain. This will be done using the transport flow machinery from Section 3. The flow construction naturally points to studying boundaries between ${\mathrm{\Omega }}_t,{\mathrm{\Omega }}_{t^{\prime }}$ for different central triangles, in which a new projection chain will arise.

Define the oriented partition chain as the projection chain $\left(\widehat{\mathrm{\Omega }}=[n],\widehat{P},\widehat{\pi }\right)$ corresponding to the decomposition ${\mathrm{\Omega }}_i=\{x\in \mathrm{\Omega }\mid x\text{ includes the triangle }(0,i,n+1)\}$, with $\widehat{P},\widehat{\pi }$ defined in an analogous fashion to $\overline{P},\overline{\pi }$. Given $S\subseteq \widehat{\mathrm{\Omega }}$, we will write $\mathrm{\Omega }[S]:={\bigcup }_{i\in S}{\mathrm{\Omega }}_i$.

Given $t,t^{\prime }\in \overline{\mathrm{\Omega }}$ with $\overline{P}(t,t^{\prime })>0$, define

The set ${\mathrm{\Omega }}_{t{t}^{\prime }}$ is the set of states in ${\mathrm{\Omega }}_t$ having a neighboring state in ${\mathrm{\Omega }}_{t^{\prime }}$.

Similarly given $i,j\in \widehat{\mathrm{\Omega }}$ (recall that for all $i,j$, $\widehat{P}(i,j)>0$), define

See Figure 2.

The central triangle $t$ partitions the polygon into three smaller polygons (one of which may be the empty polgyon). Label the sub-polygon containing the triangle $u$ as polygon (1); label the other two sub-polgyons as (2) and (3). Consider any partial triangulation in which sub-polygons (2) and (3) are fully triangulated, but sub-polygon (1) is not triangulated. Denote such a sub-triangulation as $\eta \in {\mathrm{\Omega }}_t^{(2)}\times {\mathrm{\Omega }}_t^{(3)}$. Given $\eta$, let ${\mathrm{\Omega }}^{(t,\eta )}$ denote the set of states in ${\mathrm{\Omega }}_t$ having sub-polygons (2) and (3) triangulated according to $\eta$.

We extend this notation and use $({\mathrm{\Omega }}^{(t,\eta )},P^{(t,\eta )},{\pi }^{(t,\eta )})$ to refer respectively to the copy of the chain $({\mathrm{\Omega }}_t^{(1)},P_t^{(1)},{\pi }_t^{(1)})$ induced by fixing $\eta$. Given a function $f:\mathrm{\Omega }\to ℝ$ and given $t\in \overline{\mathrm{\Omega }}$ and given $\eta \in {\mathrm{\Omega }}_t^{(2)}\times {\mathrm{\Omega }}_t^{(3)}$, define the function $f^{(t,\eta )}:{\mathrm{\Omega }}^{(t,\eta )}\to ℝ$ so that, if $z\in {\mathrm{\Omega }}^{(t,\eta )}$ we let $f^{(t,\eta )}(z)=f(z\cup \eta )$.

We will also denote by $\mathrm{\Delta }$ the degree of the (regular) graph induced by the chain $(\mathrm{\Omega },P,\pi )$, and note that for all $x,y\in \mathrm{\Omega }$ such that $P(x,y)>0$ we have $P(x,y)=\frac{1}{\mathrm{\Delta }}$. (We have $\mathrm{\Delta }=\mathrm{\Theta }(n)$, but it will be useful for clarity to distinguish it as a variable.) We will denote by ${\mathrm{\Delta }}_t^{(1)}$ the degree of the graph induced by $({\mathrm{\Omega }}_t^{(1)},P_t^{(1)},{\pi }_t^{(1)})$ and define ${\mathrm{\Delta }}_t^{(2)},{\mathrm{\Delta }}_t^{(3)}$ similarly.

[20] observed that given $t,t^{\prime }\in \overline{\mathrm{\Omega }}$, the boundary set ${\mathrm{\Omega }}_{t{t}^{\prime }}$ is precisely the set of triangulations that contain both the triangle $t$, and a particular triangle $u$ formed by two vertices of $t$ and an additional vertex of $t^{\prime }$. Letting $i$ be that additional vertex of $t^{\prime }$, $u$ is the unique triangle having vertex $i$ and sharing its other two vertices with $t$. See Figure 3.

We will denote by ${\widehat{\mathrm{\Omega }}}^{(t,\eta )}$ the set of all vertices $i$ induced by some triangle $u$ as described above, and denote by $({\widehat{\mathrm{\Omega }}}^{(t,\eta )},{\widehat{P}}^{(t,\eta )},{\widehat{\pi }}^{(t,\eta )})$ the oriented projection chain induced by fixing the “special edge” to be the edge of $u$ that bounds polygon (1) (i.e., the edge $(j,b)$ in Figure 3). We then define $F^{(t,\eta )}:{\widehat{\mathrm{\Omega }}}^{(t,\eta )}\to ℝ$ so that

We have:

where by ${\mathrm{\Omega }}_i^{(t,\eta )}\subseteq {\mathrm{\Omega }}^{(t,\eta )}$ we denote the set of states in ${\mathrm{\Omega }}^{(t,\eta )}$ that contain the triangle $u$ (having vertex $i$) described above.

In other words, Lemma 14 states that a triangulation $x\in {\mathrm{\Omega }}_t$ is in ${\mathrm{\Omega }}_{t{t}^{\prime }}$ if and only if $x$ contains the triangle $u$ (which has vertex $i$). These triangulations can then grouped according to how they triangulate ${\mathrm{\Omega }}_t^{(2)}$ and ${\mathrm{\Omega }}_t^{(3)}$, and by definition this union is disjoint. See Figure 3.

Lemma 14 is a key observation that relates the central-triangle projection chain and the oriented projection chain. It allowed [20] to reduce the problem of sending flow between central-triangle projection states $t$ and $t^{\prime }$ to two problems: (i) sending flow from the boundary set ${\mathrm{\Omega }}_{t^{\prime }t}$ to ${\mathrm{\Omega }}_{t{t}^{\prime }}$, and (ii) sending flow from the boundary set ${\mathrm{\Omega }}_{t{t}^{\prime }}$ to the rest of ${\mathrm{\Omega }}_t$. Problem (i) is easy to solve as there is a perfect matching (see Lemma 17) between ${\mathrm{\Omega }}_{t{t}^{\prime }}$ and ${\mathrm{\Omega }}_{t^{\prime }t}$. Problem (ii) was solved by reducing to the problem of sending flow from ${\mathrm{\Omega }}_i^{(t,\eta )}$ to the rest of ${\mathrm{\Omega }}^{(t,\eta )}$ – that is, the problem of sending flow from a state in the oriented projection chain ${\widehat{\mathrm{\Omega }}}^{(t,\eta )}$ to the other states in that projection chain. This problem in turn, [20] showed (we will retrace the proof rigorously), can be recursively decomposed with no blowup in congestion.

The aim of this section is to show the following lemma:

Lemma 15, combined with a hierarchical decomposition of the (variance of the) overall chain using the projection chain $(\overline{\mathrm{\Omega }},\overline{P},\overline{\pi })$, will allow us to establish the desired lower bound on the spectral gap.

[20] constructed a multicommodity flow in the projection chain $(\overline{\mathrm{\Omega }},\overline{P},\overline{\pi })$ and analyzed its congestion. Their analysis can be used to show the following,

The term in the RHS of (4) describes the problem of sending flow between the boundary sets ${\mathrm{\Omega }}_{t{t}^{\prime }}$ and ${\mathrm{\Omega }}_{t^{\prime }t}$; similarly the RHS of the final display line describes the problem of sending flow from a set $S_k^{(t,\eta )}\subseteq {\mathrm{\Omega }}^{(t,\eta )}$, i.e. a union of subsets of the chain ${\mathrm{\Omega }}^{(t,\eta )}$, to the rest of ${\mathrm{\Omega }}^{(t,\eta )}$. The expectation runs over all partial triangulations in ${\mathrm{\Omega }}_t$ in which two of the three sub-polgyons are triangulated.

We derive Lemma 16 from [21, Lemma 32], which is the congestion analysis of a flow construction. In the construction, each ${\mathrm{\Omega }}_t$ begins with uniformly concentrated flow that ${\mathrm{\Omega }}_t$ needs to route to the rest of $\mathrm{\Omega }$ (through edges in $\mathrm{\Omega }$). (This flow problem corresponds to the terms of the form $\overline{\pi }(t){(F(t)-{𝔼}_{\pi }f)}^2$ in the variance of the projection function $F$.) The authors then reduce the problem to a collection of flow subproblems in which (i) a pair of adjacent projection chain states send flow across the boundary between them, and (ii) a state $t$ receives flow from other states that it must distribute from its boundary throughout ${\mathrm{\Omega }}_t$.

Subproblems of the form (i) correspond to (4), and subproblems of the form (ii) correspond to (5). For reasons specific to the flow construction, each subproblem of form (ii) involves distributing flow from multiple boundary sets (i.e. multiple states in the oriented projection chain ${\widehat{\mathrm{\Omega }}}^{(t,\eta )}$), of the form ${\widehat{S}}_k^{(t,\eta )}\subseteq {\widehat{\mathrm{\Omega }}}^{(t,\eta )}$.

The following insight from [20] will allow us to bound (4):

Using Lemma 17 and the fact that $\pi$ is uniform, we can get the following, which we prove in the full version of the paper [4] (see e.g. [23, 31] for a similar technique):

The more challenging task is to bound (5):

We defer the proof of Lemma 19 to [4]. We will combine these bounds with the following straightforward corollary of Corollary 10.

We are now ready to prove Lemma 15.