\documentclass[finalversion]{FPSAC2024}
\articlenumber{8}

\usepackage{tabu}
\usepackage{makecell}
\usepackage{float}

\usepackage{mathrsfs}

\newtheorem{theorem}{Theorem}
\newtheorem{lemma}{Lemma}
\newtheorem{corollary}{Corollary}
\newtheorem{conjecture}{Conjecture}
\newtheorem{proposition}{Proposition}
\newtheorem{question}{Question}
\newtheorem{problem}{Problem}

\theoremstyle{definition}
\newtheorem{definition}{Definition}
\newtheorem{example}{Example}
\newtheorem{remark}{Remark}


\newcommand{\dfn}[1]{\textcolor{blue}{\emph{#1}}}

\newcommand{\CD}[1]{\textcolor{red}{\textsf{#1}}}
\newcommand{\RL}[1]{\textcolor{olive}{\textsf{#1}}}
\newcommand{\EN}[1]{\textcolor{violet}{\textsf{#1}}}

\newcommand{\ddeg}{\mathrm{ddeg}}
\newcommand{\dTV}{d_{\mathrm{TV}}}
\newcommand{\tmix}{t^{\mathrm{mix}}}
\newcommand{\width}{\mathrm{width}}
\newcommand{\PP}{\mathbb{P}}
\newcommand{\mc}{\mathcal}
\newcommand{\row}{\mathrm{Row}}
\newcommand{\TT}{\mathbf{T}}
\newcommand{\JJ}{\mathcal{J}}
\newcommand{\LL}{\mathfrak{L}}
\newcommand{\MM}{\mathcal{M}}
\newcommand{\HH}{\mathcal{H}}
\newcommand{\KK}{\mathcal{K}}
\newcommand{\bM}{{\bf M}}
\newcommand{\ZZ}{\mathbb{Z}}
\newcommand{\Ind}{\mathrm{Ind}}
\newcommand{\DD}{\mathcal{D}}
\newcommand{\UU}{\mathcal{U}}

\definecolor{NormalGreen}{RGB}{0,220,0}
\definecolor{MyPurple}{RGB}{200,0,255}

\usepackage{etoolbox}

\newcommand{\includeSymbol}[1]{\ensuremath{%
	\mathchoice
		{\raisebox{-.7mm}{\includegraphics[height=2.2ex]{#1}}}	
		{\raisebox{-.7mm}{\includegraphics[height=2.2ex]{#1}}}
		{\raisebox{-.6mm}{\includegraphics[height=1.6ex]{#1}}}
		{\raisebox{-.5mm}{\includegraphics[height=1ex]{#1}}}
}}

\robustify{\includeSymbol}
\newcommand{\hexx}{\includeSymbol{hexx}}

\def\E{\mathbb{E}}
\def\F{\mathbb{F}}
\def\P{\mathbb{P}}
\def\N{\mathbb{N}}


\title[Rowmotion Markov Chains]{Rowmotion Markov Chains}

\author[Colin Defant, Rupert Li, and Evita Nestoridi]{
Colin Defant\thanks{\href{mailto:colindefant@gmail.com}{colindefant@gmail.com}. Supported by the National Science Foundation under Award No.\ 2201907 and by a Benjamin Peirce Fellowship at Harvard University.}\addressmark{1},
Rupert Li\thanks{\href{mailto:rupertli@mit.edu}{rupertli@mit.edu}.}\addressmark{2}, \and
Evita Nestoridi\thanks{\href{mailto:evrydiki.nestoridi@stonybrook.edu}{evrydiki.nestoridi@stonybrook.edu}. Supported by the National Science Foundation  grant DMS-2052659.}\addressmark{3}}


\address{{1}Department of Mathematics, Harvard University, Cambridge, MA 02139, USA\\ 
\addressmark{2}Massachusetts Institute of Technology, Cambridge, MA 02139, USA\\ 
\addressmark{3}Mathematics Department, Stony Brook University, Stony Brook NY, 11794-3651, USA
}

\received{}


%\revised{}

\abstract{\emph{Rowmotion} is a certain well-studied bijective operator on the distributive lattice $J(P)$ of order ideals of a finite poset $P$. We introduce the \emph{rowmotion Markov chain} ${\bf M}_{J(P)}$ by assigning a probability $p_x$ to each $x\in P$ and using these probabilities to insert randomness into the original definition of rowmotion. More generally, we introduce a very broad family of \emph{toggle Markov chains} inspired by Striker's notion of generalized toggling. We characterize when toggle Markov chains are irreducible, and we show that each toggle Markov chain has a remarkably simple stationary distribution. 

We also provide a second generalization of rowmotion Markov chains to the context of semidistrim lattices. Given a semidistrim lattice $L$, we assign a probability $p_j$ to each join-irreducible element $j$ of $L$ and use these probabilities to construct a rowmotion Markov chain ${\bf M}_L$. Under the assumption that each probability $p_j$ is strictly between $0$ and $1$, we prove that ${\bf M}_{L}$ is irreducible. We also compute the stationary distribution of the rowmotion Markov chain of a lattice obtained by adding a minimal element and a maximal element to a disjoint union of two chains.

We bound the mixing time of ${\bf M}_{L}$ for an arbitrary semidistrim lattice $L$. In the special case when $L$ is a Boolean lattice, we use spectral methods to obtain much stronger estimates on the mixing time, showing that rowmotion Markov chains of Boolean lattices exhibit the cutoff phenomenon.   
}


\keywords{Toggle, rowmotion, Markov chain, stationary distribution, mixing time, lattice}

\usepackage[backend=bibtex]{biblatex}
\addbibresource{Toggle.bib}

\renewbibmacro{in:}{}


\begin{document}

\maketitle




\section{Introduction}\label{SecIntro}
Let $P$ be a finite poset, and let $J(P)$ denote the set of order ideals of $P$. For $S\subseteq P$, let \[\Delta(S)=\{x\in P:x\leq s\text{ for some }s\in S\}\quad\text{and}\quad\nabla(S)=\{x\in P:x\geq s\text{ for some }s\in S\},\] and let $\min(S)$ and $\max(S)$ denote the set of minimal elements and the set of maximal elements of $S$, respectively. \dfn{Rowmotion}, a well-studied operator in the growing field of dynamical algebraic combinatorics, is the bijection $\row\colon J(P)\to J(P)$ defined by\footnote{Many authors define rowmotion to be the inverse of the operator that we have defined. Our definition agrees with the conventions used in \cite{Barnard, Semidistrim, ThomasWilliams}.} 
\begin{equation}\label{eq:row_def}
\row(I)=P\setminus \nabla(\max(I)).
\end{equation} 
We refer the reader to \cite{StrikerWilliams,ThomasWilliams} for the history of rowmotion. The purpose of this extended abstract of the article \cite{RMC} is to introduce randomness into the ongoing saga of rowmotion by defining certain Markov chains. We were inspired by the articles \cite{Ayyer, Poznanovic, Rhodes}; these articles define Markov chains based on the \emph{promotion} operator, which is closely related to rowmotion in special cases \cite{StrikerWilliams} (though our Markov chains are fundamentally different from these promotion-based Markov chains). 

For each $x\in P$, fix a probability $p_x\in[0,1]$. We define the \dfn{rowmotion Markov chain} $\bM_{J(P)}$ with state space $J(P)$ as follows. Starting from a state $I\in J(P)$, select a random subset $S$ of $\max(I)$ by adding each element $x\in\max(I)$ into $S$ with probability $p_x$; then transition to the new state $P\setminus\nabla(S)=\row(\Delta(S))$. Thus, for any $I,I'\in J(P)$, the transition probability from $I$ to $I'$ is \[\mathbb P(I\to I')=\begin{cases} \left(\prod\limits_{x\in \min(P\setminus I')}p_x\right)\left(\prod\limits_{x'\in \max(I)\setminus\min(P\setminus I')}(1-p_{x'})\right) & \mbox{if }\min(P\setminus I')\subseteq\max(I); \\ 0 & \mbox{otherwise.}\end{cases}\]
Observe that if $p_x=1$ for all $x\in P$, then $\bM_{J(P)}$ is deterministic and agrees with the rowmotion operator. On the other hand, if $p_x=0$ for all $x\in P$, then $\bM_{J(P)}$ is deterministic and sends every order ideal of $P$ to the order ideal $P$. 

\begin{example}\label{Exam1}
Suppose $P$ is the poset \[\begin{array}{l}\includegraphics[height=1cm]{RowmotionMarkovPIC2}\end{array},\] whose elements $x,y,z$ are as indicated. Then $J(P)$ forms a distributive lattice with $5$ elements. The transition diagram of ${\bf M}_{J(P)}$ is drawn over the Hasse diagram of $J(P)$ in \Cref{Fig1}. 
\end{example}

\begin{figure}
  \begin{center}{\includegraphics[height=14.87cm]{RowmotionMarkovPIC1}}
  \end{center}
  \caption{The transition diagram of ${\bf M}_{J(P)}$, where $P$ is the $3$-element poset from \Cref{Exam1}. The elements of each order ideal in $J(P)$ are circled and colored blue. }\label{Fig1}
\end{figure}

Suppose each probability $p_x$ is strictly between 0 and 1. One of our main results will imply that ${\bf M}_{J(P)}$ is irreducible and that the probability of the state $I$ in the stationary distribution of $\bM_{J(P)}$ is \begin{equation}\label{eq:stationary}
\frac{1}{Z(J(P))}\prod_{x\in I}p_x^{-1},
\end{equation} 
where $\displaystyle Z(J(P))=\sum_{I'\in J(P)}\prod_{x'\in I'}p_{x'}^{-1}$. 


It is surprising that there is such a clean formula for the stationary distribution in this level of generality. We will deduce this result from a more general result about a vastly broader family of Markov chains. 

\section{Toggle Markov Chains}\label{subsec:toggle}

Let $P$ be a finite set of size $n$, and let $\KK$ be a collection of subsets of $P$. For each $x\in P$, define the \dfn{toggle operator} $\tau_x\colon \KK\to \KK$ by \[\tau_x(A)=\begin{cases}
A\triangle\{x\} & \text{ if } A\triangle\{x\}\in \KK \\
A & \text{ otherwise},
\end{cases}\]
where $\triangle$ denotes symmetric difference. Note that $\tau_x$ is an involution. 
Fix a tuple ${\bf x}=(x_1,\ldots,x_n)$ that contains each element of $P$ exactly once. In other words, ${\bf x}$ is an ordering of the elements of $P$. Given a set $Y\subseteq P$, let $\tau_Y=\tau_{y_r}\circ\cdots\circ\tau_{y_1}$, where $y_1,\ldots,y_r$ is the list of elements of $Y$ in the order that they appear within the list $x_1,\ldots,x_n$.


Striker \cite{Striker} viewed the map $\tau_P\colon\KK\to\KK$ as a generalization of rowmotion. Indeed, if $P$ is a poset, ${\bf x}=(x_1,\ldots,x_n)$ is a linear extension of $P$ (meaning $i<j$ whenever $x_i<x_j$ in $P$), and $\KK=J(P)$, then $\tau_P$ is equal to rowmotion. The recent article \cite{Elder} studies the dynamical aspects of $\tau_P$ when $P$ is a poset, ${\bf x}$ is a linear extension of $P$, and $\KK$ is the collection of \emph{interval-closed} (also called \emph{convex}) subsets of $P$. The articles \cite{DJMM, Joseph, JosephRoby} consider $\tau_P$ when $P$ is the vertex set of a particular graph, ${\bf x}$ is a special ordering of the vertices, and $\KK$ is the collection of independent sets of the graph. 

For each $x\in P$, fix a probability $p_x$. Define the \dfn{toggle Markov chain} $\TT=\TT(\KK,{\bf x})$ as follows. The state space of $\TT$ is $\KK$. Suppose the Markov chain is in a state $A\in \KK$. Choose a subset $T\subseteq A$ randomly so that each element $x\in A$ is included in $T$ with probability $p_x$, and then transition from $A$ to the new state $\tau_{T}(A)$. 

To phrase this differently, define the \dfn{random toggle} $\widetilde\tau_x$ to be the stochastic operator that acts as follows on a set $A\in\KK$. Let $X$ be a Bernoulli random variable that takes the value $1$ with probability $p_x$, and let \[\widetilde\tau_x(A)=\begin{cases} \tau_x(A) & \mbox{if }x\not\in A\text{ or }X=1; \\ A & \mbox{if }x\in A\text{ and }X=0.\end{cases}\] Then the Markov chain transitions to the state obtained from $A$ by applying the random toggles $\widetilde\tau_{x_1},\ldots,\widetilde\tau_{x_n}$ in this order. (Each time we apply a random toggle, we use a new Bernoulli random variable that is independent of those used before.) 

\begin{example}\label{Exam2}
Suppose $G$ is the graph $\begin{array}{l}\includegraphics[height=0.612cm]{RowmotionMarkovPIC8}\end{array}$, whose vertices $x,y,z$ are as indicated. Let $\KK$ be the collection of independent sets of $G$. \Cref{Fig4} depicts the random toggles $\widetilde\tau_x,\widetilde\tau_y,\widetilde\tau_z$. If we let ${\bf x}=(x,y,z)$, then a transition of ${\bf T}(\KK,{\bf x})$ consists of applying these random toggles in the order $\widetilde\tau_x,\widetilde\tau_y,\widetilde\tau_z$. 
\end{example}

\begin{figure}
  \begin{center}{\includegraphics[height=5.35cm]{RowmotionMarkovPIC7}}
  \end{center}
  \caption{As in \cref{Exam2}, we consider random toggles, where $\KK$ is the collection of independent sets of a path graph with vertices $x,y,z$ (from left to right). The elements of each independent set are circled and colored blue. To apply the random toggle $\widetilde\tau_x$ to an independent set $A$, we follow one of the {\color{red}red} arrows starting at $A$; the probability that a particular arrow is used is written next to the arrow. Similarly, we follow a {\color{NormalGreen}green} arrow when we apply $\widetilde\tau_y$, and we follow a {\color{MyPurple}purple} arrow when we apply $\widetilde\tau_z$. }\label{Fig4}
\end{figure}

Given a set $P$, let $\HH^P$ be the hypercube graph with vertex set $2^P$ (the power set of $P$) such that two sets $A,A'\subseteq P$ are adjacent if and only if $|A\triangle A'|=1$. For $S\subseteq 2^P$, let $\HH^P\vert_S$ be the induced subgraph of $\HH^P$ with vertex set $S$.


Let us now state our main results about irreducibility and stationary distributions of toggle Markov chains. As before, we fix a finite set $P$, a collection $\KK$ of subsets of $P$, an ordering ${\bf x}$ of the elements of $P$, and a probability $p_x$ for each $x\in P$. 


\begin{theorem}[\cite{RMC}]\label{thm:toggle_irreducible}
Suppose $0<p_x<1$ for each $x\in P$. The toggle Markov chain $\TT(\KK,{\bf x})$ is irreducible if and only if the graph $\HH^P\vert_{\KK}$ is connected. 
\end{theorem}

If $P$ is a finite poset and ${\bf x}$ is a linear extension of $P$, then one can show that $\TT(\mathcal J(P),{\bf x})$ coincides with the rowmotion Markov chain ${\bf M}_{J(P)}$. In this case, every connected component of $\HH^P\vert_{J(P)}$ contains the empty set as a vertex. Thus, it is immediate from \Cref{thm:toggle_irreducible} that the rowmotion Markov chain ${\bf M}_{J(P)}$ is irreducible whenever $0<p_x<1$ for every $x\in P$. 

\begin{theorem}[\cite{RMC}]\label{thm:toggle_stationary}
Suppose the toggle Markov chain $\TT(\KK,{\bf x})$ is irreducible and $p_x>0$ for every $x\in P$. For $A\in \KK$, the probability of the state $A$ in the stationary distribution of $\TT(\KK,{\bf x})$ is \[\frac{1}{Z(\KK)}\prod_{x\in A}p_x^{-1},\] where $\displaystyle Z(\KK)=\sum_{A'\in \KK}\prod_{x'\in A'}p_{x'}^{-1}$.
\end{theorem}

Note that the stationary distribution in \Cref{thm:toggle_stationary} is independent of the ordering ${\bf x}$ (though the Markov chain itself can certainly depend on ${\bf x}$).

\section{Mixing Times}

Suppose ${\bf M}$ is an irreducible finite Markov chain with state space $\Omega$, transition matrix $Q$, and stationary distribution $\pi$. For $x\in\Omega$, let $Q^i(x,\cdot)$ denote the distribution on $\Omega$ in which the probability of a state $x'$ is the probability of reaching $x'$ by starting at $x$ and applying $i$ transitions (this probability is the entry in $Q^i$ in the row indexed by $x$ and the column indexed by $x'$).
The \dfn{total variation distance} $\dTV=\dTV^{\Omega}$ is the metric on the space of distributions on $\Omega$ defined by
\[ \dTV(\mu,\nu)=\max_{A\subseteq \Omega} |\mu(A)-\nu(A)| = \frac{1}{2}\sum_{x\in\Omega} |\mu(x)-\nu(x)|. \]
For $\varepsilon>0$, the \dfn{mixing time} of $\bM$, denoted $\tmix_{\bM}(\varepsilon)$, is
the smallest nonnegative integer $i$ such that $\dTV(Q^i(x,\cdot),\pi)<\varepsilon$ for all $x\in\Omega$. 

The \dfn{width} of a finite poset $P$, denoted $\width(P)$, is the maximum size of an antichain in $P$. In \cite{RMC}, we use the method of coupling to prove the following bound on the mixing time of an arbitrary rowmotion Markov chain. 

\begin{theorem}[\cite{RMC}]\label{thm:general_mixing}
Let $P$ be a finite poset, and fix a probability $p_x\in(0,1)$ for each $x\in P$. Let $\overline p=\max\limits_{x\in P}p_x$. For each $\varepsilon>0$, the mixing time of $\bM_{J(P)}$ satisfies \[\tmix_{\bM_{J(P)}}(\varepsilon)\leq\left\lceil\frac{\log\varepsilon}{\log\left(1-\left(1-\overline{p}\right)^{\width(P)}\right)}\right\rceil.\]
\end{theorem}

We can drastically improve the bound in \Cref{thm:general_mixing} when $P$ is an antichain (so $J(P)$ is a Boolean lattice). For simplicity, we assume that all probabilities $p_x$ are equal to a single value $p$. In this setting, the Markov chain is reversible with respect to $\pi$; this allows us to give a spectral proof of the following result, which is an instance of the well-studied \emph{cutoff phenomenon}.  

\begin{theorem}[\cite{RMC}]\label{cutoff}
Let $P$ be an $n$-element antichain, and fix a probability $p\in(0,1)$. Let $p_x=p$ for all $x\in P$. Let $Q$ and $\pi$ be the transition matrix and stationary distribution, respectively, of the Markov chain ${\bf M}_{J(P)}$.  
\begin{enumerate}
    \item 
For $c>\frac{1}{2}$ and $t=\frac{1}{2} \log_{1/p}n + c$, we have
\[\max_{x\in J(P)}\dTV(Q^t(x,\cdot),\pi)\leq \frac{1}{2} \left( e^{p^{2c-1}} -1 \right)^{1/2}.\]
\item For $0<c<\frac{1}{2}\log_{1/p}n$ and $t=\frac{1}{2} \log_{1/p}n -c$, we have
\[\max_{x\in J(P)}\dTV(Q^t(x,\cdot),\pi) \geq 1- 4 p^{2c+1}-4 p^{2c}.\]
\end{enumerate}
\end{theorem}

It would be interesting to prove that other natural families of toggle Markov chains exhibit cutoff. 



\section{Semidistrim Lattices}
If $P$ is a finite poset, then we can order $J(P)$ by inclusion to obtain a distributive lattice. In fact, Birkhoff's Fundamental Theorem of Finite Distributive Lattices states that every finite distributive lattice is isomorphic to the lattice of order ideals of some finite poset. Thus, instead of viewing rowmotion as a bijective operator on the set of order ideals of a finite poset, one can equivalently view it as a bijective operator on the set of \emph{elements} of a distributive lattice. This perspective has led to more general definitions of rowmotion in recent years. Barnard \cite{Barnard} showed how to extend the definition of rowmotion to the broader family of \emph{semidistributive} lattices, while Thomas and Williams \cite{ThomasWilliams} discussed how to extend the definition to the family of \emph{trim} lattices. (Every distributive lattice is semidistributive and trim, but there are semidistributive lattices that are not trim and trim lattices that are not semidistributive.) 

One notable example motivating these extended definitions comes from Reading's \emph{Cambrian lattices} \cite{ReadingCambrian}. Suppose $c$ is a Coxeter element of a finite Coxeter group $W$. Reading \cite{ReadingClusters} found a bijection from the $c$-Cambrian lattice to the $c$-noncrossing partition lattice of $W$; under this bijection, rowmotion on the $c$-Cambrian lattice corresponds to the well-studied \emph{Kreweras complementation} operator on the $c$-noncrossing partition lattice of $W$ \cite{Barnard, ThomasWilliams}. See \cite{DefantLin, HopkinsCDE, ThomasWilliams} for other non-distributive lattices where rowmotion has been studied. 

Recently, the first author and Williams \cite{Semidistrim} introduced the even broader family of \emph{semidistrim} lattices and showed how to define a natural rowmotion operator on them; this is now the broadest family of lattices where rowmotion has been defined. It turns out that we can extend our definition of rowmotion Markov chains to semidistrim lattices; this provides a generalization of rowmotion Markov chains that is different from the toggle Markov chains discussed in \Cref{subsec:toggle}. We sketch the details here, referring to \cite{RMC} for the full definition of a semidistrim lattice and an explanation of why this definition specializes to the one given above when the lattice is distributive. 

Let $L$ be a semidistrim lattice, and let $\JJ_L$ and $\MM_L$ be the set of join-irreducible elements of $L$ and the set of meet-irreducible elements of $L$, respectively. There is a specific bijection $\kappa_L\colon\JJ_L\to\MM_L$ satisfying certain properties. The \emph{Galois graph} of $L$ is the loopless directed graph $G_L$ with vertex set $\JJ_L$ such that for all distinct $j,j'\in\JJ_L$, there is an arrow $j\to j'$ if and only if $j\not\leq\kappa_L(j')$. Let $\Ind(G_L)$ be the set of independent sets of $G_L$. There is a particular way to label the edges of the Hasse diagram of $L$ with elements of $\JJ_L$; we write $j_{uv}$ for the label of the edge $u\lessdot v$. For $w\in L$, let $\DD_L(w)$ be the set of labels of the edges of the form $u\lessdot w$, and let $\UU_L(w)$ be the set of labels of the edges of the form $w\lessdot v$. Then $\DD_L(w)$ and $\UU_L(w)$ are actually independent sets of $G_L$. Moreover, the maps $\DD_L,\UU_L\colon L\to \Ind(G_L)$ are bijections. The \emph{rowmotion} operator $\row\colon L\to L$ is defined by $\row=\UU_L^{-1}\circ\DD_L$. 

The \emph{rowmotion Markov chain} ${\bf M}_L$ has $L$ as its set of states. For each $j\in\JJ_L$, we fix a probability $p_j\in[0,1]$. Starting at a state $u\in L$, we choose a random subset $S$ of $\DD_L(u)$ by adding each element $j\in\DD_L(u)$ into $S$ with probability $p_j$ and then transition to the new state $u'=\row_L(\bigvee S)$. 

When $p_j=1$ for all $j\in\JJ_L$, the Markov chain $\bM_L$ is deterministic and agrees with rowmotion; indeed, this follows from \cite[Theorem~5.6]{Semidistrim}, which tells us that $\bigvee\DD_L(u)=u$ for all $u\in L$.  

Our main result about rowmotion Markov chains of semidistrim lattices is as follows. 

\begin{theorem}[\cite{RMC}]\label{thm:semidistrim_irreducible}
Let $L$ be a semidistrim lattice, and fix a probability $p_j\in(0,1)$ for each join-irreducible element $j\in\JJ_L$. The rowmotion Markov chain $\bM_L$ is irreducible. 
\end{theorem}

Let us remark that this theorem is not at all obvious. Our proof uses a delicate induction that relies on some difficult results about semidistrim lattices proven in \cite{Semidistrim}. For example, we use the fact that intervals in semidistrim lattices are semidistrim. 


We can also generalize \Cref{thm:general_mixing} to the realm of semidistrim lattices in the following theorem. Given a semidistrim lattice $L$ and an element $u\in L$, we write $\ddeg(u)$ for the \dfn{down-degree} of $u$, which is the number of elements of $L$ covered by $u$. Let $\alpha(G_L)$ denote the independence number of the Galois graph $G_L$; that is, $\alpha(G_L)=\max\limits_{\mathcal I\in\Ind(G_L)}|\mathcal I|$. Equivalently, $\alpha(G_L)=\max\limits_{u\in L}\ddeg(u)$. If $P$ is a finite poset, then $\alpha(G_{J(P)})=\width(P)$.   

\begin{theorem}[\cite{RMC}]\label{thm:semidistrim_mixing}
Let $L$ be a semidistrim lattice, and fix a probability $p_j\in(0,1)$ for each $j\in \JJ_L$. Let $\overline p=\max\limits_{j\in\JJ_L}p_j$. For each $\varepsilon>0$, the mixing time of $\bM_{L}$ satisfies \[\tmix_{\bM_{L}}(\varepsilon)\leq\left\lceil\frac{\log\varepsilon}{\log\left(1-\left(1-\overline{p}\right)^{\alpha(G_L)}\right)}\right\rceil.\]
\end{theorem}

We were not able to find a formula for the stationary distribution of the rowmotion Markov chain of an arbitrary semidistrim (or even semidistributive or trim) lattice; this serves to underscore the anomalistic nature of the formula for distributive lattices in \eqref{eq:stationary}. However, there is one family of semidistrim (in fact, semidistributive) lattices where we were able to find such a formula. Given positive integers $a$ and $b$, let $\hexx_{a,b}$ be the lattice obtained by taking two disjoint chains $x_1<\cdots <x_a$ and $y_1<\cdots< y_b$ and adding a bottom element $\hat 0$ and a top element $\hat 1$. Let us remark that $\hexx_{m-1,m-1}$ is isomorphic to the weak order of the dihedral group of order $2m$, whereas $\hexx_{m-1,1}$ is isomorphic to the $c$-Cambrian lattice of that same dihedral group (for any Coxeter element $c$). We have $\mathcal J_{\hexx_{a,b}}=\mathcal M_{\hexx_{a,b}}=\{x_1,\ldots,x_a,y_1,\ldots,y_b\}$. For $2\leq i\leq a$ and $2\leq i'\leq b$, we have $\kappa_{\hexx_{a,b}}(x_i)=x_{i-1}$ and $\kappa_{\hexx_{a,b}}(y_{i'})=y_{i'-1}$; moreover, $\kappa_{\hexx_{a,b}}(x_1)=y_b$ and $\kappa_{\hexx_{a,b}}(y_1)=x_a$.  This is illustrated in \Cref{Fig3} when $a=3$ and $b=2$. \Cref{Fig2} shows the transition diagram of ${\bf M}_{\text{\hexx}_{2,1}}$. 

\begin{theorem}[\cite{RMC}]\label{thm:hexx}
Fix positive integers $a$ and $b$, and let $\kappa=\kappa_{\hexx_{a,b}}$. For each $j\in\JJ_{\text{\hexx}_{a,b}}$, fix a probability $p_j\in(0,1)$. There is a constant $Z(\hexx_{a,b})$ (depending only on $a$ and $b$) such that in the stationary distribution of $\bM_{\text{\hexx}_{a,b}}$, we have 
\begin{align*}
\mathbb P(\hat 0)&=\frac{1}{Z(\hexx_{a,b})}p_{x_1}p_{y_1}\left(1-\prod_{j\in\JJ_{\text{\hexx}_{a,b}}}p_j\right); \\
\mathbb P(\hat 1)&=\frac{1}{Z(\hexx_{a,b})}\left(1-\prod_{j\in\JJ_{\text{\hexx}_{a,b}}}p_j\right); \\ 
\mathbb P(x_i)&=\frac{1}{Z(\text{\hexx}_{a,b})}\left((1-p_{x_1})\prod_{\substack{j\in\JJ_{\text{\hexx}_{a,b}} \\ \kappa(j)\geq x_i}}p_j+(1-p_{y_1})\prod_{\substack{j\in\JJ_{\text{\hexx}_{a,b}} \\ \kappa(j)\not<x_i}}p_j\right)\quad\text{for}\quad 1\leq i \leq a; \\ 
\mathbb P(y_i)&=\frac{1}{Z(\text{\hexx}_{a,b})}\left((1-p_{y_1})\prod_{\substack{j\in\JJ_{\text{\hexx}_{a,b}} \\ \kappa(j)\geq y_i}}p_j+(1-p_{x_1})\prod_{\substack{j\in\JJ_{\text{\hexx}_{a,b}} \\ \kappa(j)\not<y_i}}p_j\right)\quad\text{for}\quad 1\leq i \leq b.  
\end{align*}
\end{theorem}

\begin{figure}[H]
  \begin{center}{\includegraphics[height=10cm]{RowmotionMarkovPIC6}}
  \end{center}
  \caption{The lattice $\hexx_{3,2}$. Next to each edge $u\lessdot v$ is a box containing the edge label $j_{uv}$. The red arrows represent the action of $\kappa_{\hexx_{3,2}}$.}\label{Fig3}
\end{figure}




\section{Future Directions}\label{sec:conclusion}

In \cref{cutoff}, we saw that the rowmotion Markov chains of Boolean lattices exhibit the cutoff phenomenon. It would be very interesting to obtain similar results for other toggle Markov chains. Some particularly interesting toggle Markov chains ${\bf T}(\KK,{\bf x})$ are as follows: 
\begin{itemize}
\item Let $P$ be the set of vertices of a graph $G$, let $\KK$ be the collection of independent sets of $G$, and let ${\bf x}$ be some special ordering of $P$. For example, if $G$ is a cycle graph, then ${\bf x}$ could be the ordering obtained by reading the vertices of $G$ clockwise. 
\item Let $P$ be an $n$-element set, and let ${\bf x}$ be an arbitrary ordering of the elements of $P$. For $0\leq k\leq n$, let $\KK=\{I\subseteq P:|I|\leq k\}$.  
\item Let $P$ be an $n$-element set, and let ${\bf x}$ be an arbitrary ordering of the elements of $P$. For $0\leq k\leq n$, let $\KK=\{I\subseteq P:|I|\geq k\}$.  
\end{itemize}
It would also be interesting to improve our estimates for the mixing times of rowmotion Markov chains for other families of semidistrim (or just distributive) lattices. 


\begin{figure}[H]
  \begin{center}{\includegraphics[height=13cm]{RowmotionMarkovPIC4}}
  \end{center}
  \caption{The transition diagram of $\bM_{\text{\hexx}_{2,1}}$ drawn over the Hasse diagram of $\hexx_{2,1}$. Next to each edge $u\lessdot v$ is a box containing the edge label $j_{uv}$.}\label{Fig2}
\end{figure}

In \Cref{thm:toggle_stationary,thm:hexx}, we computed the stationary distributions of rowmotion Markov chains of distributive lattices and the lattices $\hexx_{a,b}$. It would be quite interesting to find other special families of semidistrim lattices for which one can compute these stationary distributions. 




\printbibliography

\end{document}