Do random triangulation edge-flips maintain randomness?

Question

Let $S$ be a fixed set of $n$ points in the plane in general position. Let $T$ be a triangulation of $S$, (somehow) selected uniformly at random from all triangulations of $S$. (There are an exponential number of triangulations,¹ somewhere between $2.6^n$ and $43^n$.)

An edge-flip is the operation illustrated below; it requires $e$ to be a diagonal of a convex quadrilateral $Q$.

---

         
          ^{(Image from Hanke, Sabine, Thomas Ottmann, and Sven Schuierer.
          "The edge-flipping distance of triangulations." J. UCS 2.8 (1996): 570-579. (PDF).)}

---

My question is:

Q. Starting from $T$, select a random $e$, and edge-flip if $Q$ is convex. Repeat $k$ times, resulting in triangulation $T_k$. As $k \to \infty$, does it remain true that $T_k$ is random, i.e., as if selected uniformly at random from all triangulations of $S$?

This seems almost obviously true, but because the flip operation depends on the geometric structure of the triangulation, it seems conceivable to me that repeated flips bias the triangulations in some way, privileging some over others. Note that there is no edge-flip circumcircle condition here that leads to the Delaunay triangulation. But still the convexity of $Q$ is a geometric constraint.

This is likely well-known, in which case a pointer to the appropriate literature would be appreciated. Thanks!

---

¹Sharir, Micha, and Emo Welzl. "Random triangulations of planar point sets." Proc. the 22nd Annual Symposium on Computational Geometry. ACM, 2006. (PDF.)

Answer 1

It disturbs uniformity. What you have is a Markov chain and it converges to a distribution given by the Perron eigenvector of the transition matrix. To preserve uniformity you need that eigenvector to have equal entries, which will only be the case if the same number of flips are available for each triangulation.

However, there is a simple way to make it preserve uniformity. Each "move" consists of: choose an internal edge at random and flip it if that is legal. Do this $k$ times where $k$ is chosen in advance. The difference is that moves which don't result in flips are counted as well as those that do. Counting flips rather than moves introduces a bias.