Home » Markov chain mixing » Catalan mixing

Catalan mixing

Let $V$ denote the subset of the hypercube $\{-1,1\}^n$ consisting of strings $(x_1,\dots,x_n)$ that satisfy $\sum_{i=1}^k x_i \ge 0$ for $k=1,\dots, n$ .

Consider the random transposition walk on $V$ . That is, at each step choose $i,j \in \{1,\dots,n\}$ uniformly at random ( $i=j$ is allowed), and if swapping $x_i$ and $x_j$ yields a sequence in $V$ , then perform this swap, otherwise do nothing. What is the order of magnitude of mixing time of this chain? A natural conjecture is that it is $\Theta(n \log n)$ . A lower bound of that order should not be hard to prove, although the best published bound we are aware of is of order $n$ , see [1], section 4. The best available upper bound, proved in [1], see also [2], is $O(n^2 \log n)$ . The proof is quite ingenious.

REFERENCES

[1] Cohen, Emma, Prasad Tetali, and Damir Yeliussizov. "Lattice path matroids: negative correlation and fast mixing." Link >>

[2] Cohen, Emma. "Problems in catalan mixing and matchings in regular hypergraphs." PhD diss., Georgia Institute of Technology, 2016. Link >>

Catalan mixing

Send me questions about this open problem

Contact Me