# STRONG STATIONARY TIMES FOR FINITE HEISENBERG WALKS

LAURENT MICLO<fnref n="1" />,<fnref n="2" />,*,†

**Abstract.** The random mapping construction of strong stationary times is applied here to finite Heisenberg random walks over $Z_M$, for odd $M \ge 3$. When they correspond to $3 \times 3$ matrices, the strong stationary times are of order $M^6$, estimate which can be improved to $M^4$ if we are only interested in the convergence to equilibrium of the last column. Simulations by Chhaibi suggest that the proposed strong stationary time is of the right $M^2$ order. These results are extended to $N \times N$ matrices, with $N \ge 3$. All the obtained bounds are thought to be non-optimal, nevertheless this original approach is promising, as it relates the investigation of the previously elusive strong stationary times of such random walks to new absorbing Markov chains with a statistical physics flavor and whose quantitative study is to be pushed further. In addition, for $N = 3$, a strong equilibrium time is proposed in the same spirit for the non-Markovian coordinate in the upper right corner. This result would extend to separation discrepancy the corresponding fast convergence for this coordinate in total variation and open a new method for the investigation of this phenomenon in higher dimension.

**Mathematics Subject Classification.** MSC2010, 60J10, 60B15, 82C41, 37A25, 60K35.

Received July 4, 2021. Accepted March 27, 2023.

## 1. INTRODUCTION

The investigation of the quantitative convergence to equilibrium of random walks on finite groups has lead to a prodigious literature devoted to various techniques, see for instance the overview of Saloff-Coste [22] or the book of Levin, Peres and Wilmer [14]. One of the most probabilistic approaches is based on the strong stationary times introduced by Aldous and Diaconis [1]. Diaconis and Fill [7] presented a general construction of strong stationary times via intertwining dual processes, in particular set-valued dual processes. It was proposed in [17] to obtain the latter processes through the resort of random mappings, in the spirit of Propp and Wilson [21]. Here we apply this method to deduce strong stationary times for finite Heisenberg random walks. It will illustrate that the random mapping technique can be effective in constructing strong stationary times in situations where they are difficult to find and have lead to numerous mistakes in the past. While there is room for improvement in our estimates, we hope this new approach will help the understanding of the convergence to equilibrium of related random walks, see for instance Hermon and Thomas [11], Breuillard and Varjú [2], Eberhard and Varjú [9] or Chatterjee and Diaconis [5] for very recent progress in this direction.

<footnote>*Keywords and phrases:* Random mappings, strong stationary times, finite Heisenberg random walks, absorbing Markov chains.</footnote>

<footnote n="1">¹ Toulouse School of Economics 1, Esplanade de l'Université 31080 Toulouse Cedex 06, France.</footnote>

<footnote n="2">² Institut de Mathématiques de Toulouse Université Paul Sabatier, 118, route de Narbonne 31062 Toulouse cedex 9, France.</footnote>

<footnote>* Corresponding author: miclo@math.cnrs.fr</footnote>

<footnote>† Funding from the grant ANR-17-EURE-0010 is acknowledged.</footnote>
To avoid notational difficulties, we begin by presenting the case of 3 × 3 matrices. For $M \ge 3$ and $M$ odd, let $\mathbb{H}_M$ be the **Heisenberg group** of matrices of the form

$$ \begin{pmatrix} 1 & x & z \\ 0 & 1 & y \\ 0 & 0 & 1 \end{pmatrix} $$

where $x, y, z \in \mathbb{Z}_M$. Such matrices will be identified with $[x, y, z] \in \mathbb{Z}_M^3$, the multiplication corresponding to

$$ [x, y, z] \cdot [x', y', z'] = [x + x', y + y', z + z' + xy'] $$

for any $[x, y, z], [x', y', z'] \in \mathbb{Z}_M^3$.

Consider the usual system of generators of $\mathbb{H}_M$, $\{[1, 0, 0], [-1, 0, 0], [0, 1, 0], [0, -1, 0]\}$, as well as the random walk $[X, Y, Z] := ([X_n, Y_n, Z_n])_{n \in \mathbb{Z}_+}$, starting from the identity $[0, 0, 0]$ and whose transitions are obtained by multiplying on the left by one of these elements, each chosen with probability $1/6$. With the remaining probability $1/3$, the random walk does not move. The **uniform distribution** $\mathcal{U}$ on $\mathbb{H}_M$ is invariant and reversible for the random walk $[X, Y, Z]$. A finite stopping time $\tau$ with respect to the filtration generated by $[X, Y, Z]$, possibly enriched with some independent randomness, is said to be a **strong stationary time** if

* $\tau$ and $[X_\tau, Y_\tau, Z_\tau]$ are independent,

* $[X_\tau, Y_\tau, Z_\tau]$ is distributed as $\mathcal{U}$.

The tail probabilities of a strong stationary time enable to estimate the speed of convergence of the law $\mathcal{L}[X_n, Y_n, Z_n]$ of $[X_n, Y_n, Z_n]$ toward $\mathcal{U}$, in the separation sense, as shown by Diaconis and Fill [7]. More precisely, recall that the separation discrepancy $\mathfrak{s}(m, \mu)$ between two probability measures $m$ and $\mu$ defined on the same measurable space is defined by

$$ \mathfrak{s}(m, \mu) := \ess \sup_{\mu} 1 - \frac{dm}{d\mu} $$

where $dm/d\mu$ is the Radon-Nikodym density of $m$ with respect to $\mu$.

For any strong stationary time $\tau$ associated to $[X, Y, Z]$, we have

$$ \forall n \in \mathbb{Z}_+, \quad \mathfrak{s}(\mathcal{L}[X_n, Y_n, Z_n], \mathcal{U}) \le \mathbb{P}[\tau > n] $$

It justifies the interest the following bound:

**Theorem 1.1.** There exists a strong stationary time $\tau$ for $[X, Y, Z]$ such that for $M$ large enough,

$$ \forall r \ge 0, \quad \mathbb{P}[\tau \ge r] \le 3 \exp \left( - \frac{r}{17M^6} \right) $$

Taking into account the invariance of the transition matrix of $[X, Y, Z]$ with respect to the right (or left) group multiplication, the above result can be extended to any initial distribution of $[X_0, Y_0, Z_0]$. Note that $(X, Y)$ is a lazy random walk on the finite torus $\mathbb{Z}_M^2$, so it needs a time of order $M^2$ to reach equilibrium in the strong stationary time sense. This estimate will be made more precise in Lemma 3.1.

Nevertheless, the puzzling feature of the 3 × 3 Heisenberg model over $\mathbb{Z}_M$ is the fast convergence of $Z$, mixing more rapidly than $(X, Y)$, at a time that should be of order $M$, up to possible logarithmic corrections. In the total variation sense, this is known to be true, see e.g. [3, 4] and the references given there. We believe this also holds in the separation sense and that the new approach presented here can be refined to go in this direction. More precisely, a **strong equilibrium time** for the (non-Markovian) $Z$ is a finite stopping time $\hat{\tau}$ for
$[X, Y, Z]$ (and with respect to possible independent randomness) such that $\hat{\tau}$ and $Z_{\hat{\tau}}$ are independent and $Z_{\hat{\tau}}$ is distributed according to the uniform law on $Z_M$. In Remark 4.8 (c), such a time $\hat{\tau}$ is proposed and believed to be of order $M$. Simulations programmed by Chhaibi [6] suggest it is at most of order $M^{1.5}$.

Up to our knowledge, no strong stationary time can be found in the literature for finite Heisenberg models. So the main point of this paper is to show that such a strong stationary time can be constructed via the random mapping method of [17], even if it is sub-optimal. Indeed in Theorem 1.1 the right order should be $M^2$, the same as for the usual random walk $(X, Y)$ on $Z_M^2$, the extra time for $Z$ being expected to be negligible as said above. Nevertheless, we will be led to new interesting models of absorbing Markov chains with a statistical physics flavor whose investigation should be pushed further to get the desired estimate, see Remark 4.8 in Section 4.

If one is only interested in the convergence to equilibrium of the Markovian last column $(Y, Z)$, the same approach gives a better result, even if it remains sub-optimal according to the above observations. Nevertheless simulations by Chhaibi [6] hint the strong stationary time below is of the optimal order $M^2$.

**Theorem 1.2.** There exists a strong stationary time $\tilde{\tau}$ for $(Y, Z)$ such that for $M$ large enough,

$$ \forall r \ge 0, \quad \mathbb{P}[\tilde{\tau} \ge r] \le 3 \exp \left( -\frac{r}{17M^4} \right) $$

One could think that once the equilibrium has been reached for $(Y, Z)$, it is sufficient to wait for a supplementary time for $X$ of order $M^2$ to equilibrate to get a strong stationary time for the whole chain $[X, Y, Z]$. But one has to be more careful with this kind of assertions, see Remark 5.1 in Section 5 for more details.

These considerations can be extended to the $N \times N$ Heisenberg $\mathbb{H}_{N,M}$ group model over $Z_M$. It consists in the matrices of the form

$$ \begin{pmatrix} 1 & x_{1,2} & x_{1,3} & \cdots & x_{1,N-1} & x_{1,N} \\ 0 & 1 & x_{2,3} & \cdots & x_{2,N-1} & x_{2,N} \\ 0 & 0 & 1 & \cdots & x_{3,N-1} & x_{3,N} \\ \vdots & \vdots & \vdots & \ddots & \vdots & \vdots \\ 0 & 0 & 0 & \cdots & 1 & x_{N-1,N} \\ 0 & 0 & 0 & \cdots & 0 & 1 \end{pmatrix} $$

where $x_{k,l} \in Z_M$ for $1 \le k < l \le N$, the group operation corresponds to the matrix multiplication. Such matrices will be identified with $[x_{k,l}]_{1 \le k < l \le N} \in Z_M^{\Delta_N}$, where $\Delta_N := \{(k, l) : 1 \le k < l \le N\}$. Consider the usual system of generators of $\mathbb{H}_{N,M}$, $\{\varepsilon\delta_{(I,I+1)} : I \in [N-1] \text{ and } \varepsilon \in \{\pm 1\}\}$, where $\delta_{(I,I+1)}$ is the element of $Z_M^{\Delta_N}$ whose entries all vanish, except the one indexed by $(I, I+1)$ which is equal to 1. We used the notation $[[k]] := \{1, 2, \dots, k\}$ for any $k \in Z_+$, and more generally for any $k, l \in Z$, we will denote $[[k, l]] := \{k, k+1, \dots, l\}$ (which is empty by convention if $k > l$). Let $[X] := ([X](n))_{n \in Z_+} := ([X_{k,l}(n)])_{1 \le k < l \le N, n \in Z_+}$ be the random walk starting from the identity $[0]_{1 \le k < l \le N}$ and whose transitions are obtained by multiplying on the left by one of the generators, each chosen with probability $1/(3(N-1))$. With the remaining probability $1/3$, the random walk does not move. The invariant measure is the uniform distribution on $\mathbb{H}_{N,M}$. We have a result similar to Theorem 1.1:

**Theorem 1.3.** There exists a strong stationary time $\tau$ for $[X]$ such that for $M$ large enough,

$$ \forall r \ge 0, \quad \mathbb{P}[\tau \ge r] \le 3 \exp \left( -\frac{2r}{17(N-1)M^{N(N-1)}} \right) $$

More generally it is possible to exploit the upper diagonal structure of the model. Introduce for $[x] \in \mathbb{H}_{N,M}$ and $b \in [N-1]$, the $b$th upper diagonal $d_b[x] := (x_{k,k+b})_{k \in [N-b]}$, as well as $d_{[b]}[x] := (d_k[x])_{k \in [b]}$. Note that $[x] = d_{[N-1]}[x]$. Similarly, for $b \in [N-1]$, we can associate the stochastic chains $D_b := (d_b[X(n)])_{n \in Z_+}$ as well as $D_{[b]} := (d_{[b]}[X(n)])_{n \in Z_+}$ to the Markov chain $[X]$. It is not difficult to see that $D_{[b]}$ is a Markov chain itself
(but $D_b$ is not). We will see that for any $b \in [2, N - 2]$, there exists a strong stationary time $\tau_b$ for $D_{[b]}$ of order at most $NM^{b(2N-b-1)}$, see Theorem 6.3 in Section 6. The estimate of Theorem 1.3 does match exactly that of Theorem 1.1 when $N = 3$, because we looked for a faithful generalization to facilitate reading. Again, all these bounds are very rough and we hope they are a preliminary step toward the conjecture that the order of convergence for the (non-Markovian) up-diagonal $D_b$ should be $M^{2/b}$ for fixed $N$ and $b \in [N - 1]$ (see for instance [3]).

Theorem 1.2 has equally an extension. Denote $C_N[X]$ the last column of $[X]$ and remark this is a Markov chain.

**Theorem 1.4.** There exists a strong stationary time $\tilde{\tau}$ for $C_N[X]$ such that for $M$ large enough,

$$ \forall r \ge 0, \quad \mathbb{P}[\tilde{\tau} \ge r] \le 3 \exp \left( - \frac{2r}{17(N-1)M^{2(N-1)}} \right) $$

The plan of the paper is as follows. In the next section, as a warming-up computation and to recall the approach of [17], we construct strong stationary times for quite lazy random walks on the finite circle $\mathbb{Z}_M$ (no longer assuming that $M \ge 3$ is odd). This construction is extended in Section 3, through a kind of tensorization, to produce a strong stationary times for the Markov chain $(X, Y)$ on the finite torus $\mathbb{Z}_M^2$, extracted from $[X, Y, Z]$. This procedure is itself distorted in Section 4 to prove Theorem 1.1. The underlying idea is an optimization over the choice of some sign functions, to get random mappings spreading and retracting as much as possible the subset-valued dual chains. Section 5 presents the modification needed for Theorem 1.2, it corresponds in fact to the simplest illustration of the method we are proposing. A general roadmap of the latter is presented at the beginning of Section 6, before working out the extensions to random walks on higher dimensional Heisenberg groups. Finally, Appendix A ends the investigation of random walks on the finite circle $\mathbb{Z}_M$ by treating the remaining cases, when the level of laziness is weak, and Appendix B provides an index of the main notations.

## 2. STRONG STATIONARY TIMES FOR FINITE CIRCLES

Here we construct strong stationary times for certain random walks on discrete circles (the remaining cases will be treated in Appendix A). It will enable us to recall the random mapping approach, as developed in [17].

We start by presenting the general situation of random walks on discrete circles with at least 3 points. Let $M \in \mathbb{N} \setminus \{1, 2\}$ and $a \in (0, 1/2]$ be fixed. We consider the Markov kernel $P$ on $\mathbb{Z}_M$ given by

$$ \forall x, y \in \mathbb{Z}_M, \quad P(x, y) := \begin{cases} a & , \text{ if } y = x + 1 \text{ or } y = x - 1 \\ 1 - 2a & , \text{ if } y = x \\ 0 & , \text{ otherwise} \end{cases} $$

We are looking for strong stationary times for the corresponding random walk starting from 0 (or from any other initial point by symmetry). From Diaconis and Fill [7], it is always possible to construct such strong stationary times, except when $a = 1/2$ and $M$ is odd, then the random walk has period 2 and does not converge to its equilibrium (instead, we will recover in this case a dual process related to the discrete Pitman's Thm. [20]).

More precisely, since $a > 0$, the unique invariant probability associated to $P$ is $\pi$ the uniform distribution on $\mathbb{Z}_M$. It is even reversible, so that the adjoint matrix $P^*$ of $P$ in $\mathbb{L}^2(\pi)$ is just $P^* = P$. In the sequel and in Appendix A, we will consider certain sets $\mathfrak{M}$ consisting of non-empty subsets of $\mathbb{Z}_M$ and containing the whole state space $\mathbb{Z}_M$. There will be three instances for $\mathfrak{M}$, depending on the values of $a$ and $M$ (a fourth one will be considered in Sect. A.3). Here we will deal with the simplest case, when $a \in (0, 1/3]$. We will then take $\mathfrak{M} = \mathfrak{I}$,
the set of intervals in $\mathbb{Z}_M$ which are symmetric with respect to 0, namely

$$ \mathfrak{J} := \{B(0, r) : r \in [0, \lfloor M/2 \rfloor]\} $$

where $\lfloor \cdot \rfloor$ is the usual integer part and $B(0, r) := \lfloor -r, -r \rfloor$ is the (closed) ball centered at 0 and of radius $r$, for the usual graph distance on $\mathbb{Z}_M$. Here we extended the notation for discrete segments introduced before Theorem 1.3 to their “projections” on $\mathbb{Z}_M$. For the other definitions of $\mathfrak{J}$, when $a \in (1/3, 1/2]$, we refer to Appendix A. These cases, while instructive, will not be helpful for the next sections. For the sake of the general arguments below, just assume that we have chosen a $\mathfrak{J}$ consisting of “nice” subsets of $\mathbb{Z}_M$.

For any $S \in \mathfrak{J}$, we are looking for a **random mapping** $\psi_S : \mathbb{Z}_M \to \mathbb{Z}_M$ satisfying two conditions:

* the **weak association** with $P^* = P$, namely

$$ \forall x \in \mathbb{Z}_M, \forall y \in S, \quad \mathbb{P}[\psi_S(x) = y] = \frac{1}{\xi(S)} P(x, y) \qquad (2.1) $$

where $\xi(S) > 0$ is a positive number.

* the **stability** of $\mathfrak{J}$: the set

$$ \Psi(S) := \psi_S^{-1}(S) \qquad (2.2) $$

belongs to $\mathfrak{J} \sqcup \{\emptyset\}$.

The interest of such random mappings is that they enable to construct a $\mathfrak{J}$-valued intertwining dual process, and a strong stationary time if the latter ends up being absorbed in the whole set $\mathbb{Z}_M$. Indeed, introduce the Markov kernel $\Lambda$ from $\mathfrak{J}$ to $\mathbb{Z}_M$ given by

$$ \forall S \in \mathfrak{J}, \forall x \in \mathbb{Z}_M, \quad \Lambda(S, x) := \frac{\pi(x)}{\pi(S)} \mathbb{1}_S(x) $$

where $\mathbb{1}_S$ is the indicator function of $S$. Consider next the $\mathfrak{J} \times \mathfrak{J}$-matrix $\mathfrak{P}$ given by

$$ \forall S, S' \in \mathfrak{J}, \quad \mathfrak{P}(S, S') = \frac{\xi(S)\pi(S')}{\pi(S)} \mathbb{P}[\Psi(S) = S'] \qquad (2.3) $$

We have shown in [17] that $\mathfrak{P}$ is a Markov kernel and that it is intertwined with $P$ through $\Lambda$:

$$ \mathfrak{P}\Lambda = \Lambda P $$

Note that $\mathbb{Z}_M$ is absorbing for $\mathfrak{P}$, since we always have $\Psi(\mathbb{Z}_M) = \mathbb{Z}_M$ and $\xi(\mathbb{Z}_M) = 1$ (by summing with respect to $y \in \mathbb{Z}_M$ in (2.1)). Let $\mathcal{X} := (\mathcal{X}_n)_{n \in \mathbb{Z}_+}$ be a Markov chain on $\mathfrak{J}$ starting from $\{0\}$ and whose transition kernel is $\mathfrak{P}$. Consider its absorbing time:

$$ t := \inf\{n \in \mathbb{Z}_+ : \mathcal{X}_n = \mathbb{Z}_M\} \in \mathbb{N} \cup \{\infty\} $$

Let $X := (X_n)_{n \in \mathbb{Z}_+}$ be a Markov chain on $\mathbb{Z}_M$ starting from 0 and whose transition kernel is $P$. As in the introduction, a finite stopping time $\tau$ for the filtration generated by $X$ (and maybe some additional independent randomness) is said to be a **strong stationary time** for $X$ if $\tau$ and $X_\tau$ are independent and $X_\tau$ is distributed according to $\pi$. According to Diaconis and Fill [7], if $t$ is almost surely finite, then it has the same law as a strong stationary time for $X$, since it is possible to construct a coupling between $X$ and $\mathcal{X}$ such that $t$ is a
strong stationary time for $X$ (see also [17], where this coupling is explicitly constructed in terms of the random mappings).

Except when $a = 1/2$ and $M$ is even, the $t$ we are to construct here and in Appendix A will be a.s. finite. Furthermore, when $a \in (0, 1/3]$, $t$ will be a **sharp** strong stationary time, in the sense that its law will be stochastically dominated by the law of any other strong stationary time. As a consequence, we get that

$$ \forall n \in \mathbb{Z}_+, \quad \mathfrak{s}(\mathcal{L}(X_n), \pi) = \mathbb{P}[t > n] \qquad (2.4) $$

Indeed, this sharpness is a consequence of Remark 2.39 of Diaconis and Fill [7] and the fact that

$$ \forall S \in \mathcal{J} \setminus \{\mathbb{Z}_M\}, \quad \Lambda(S, \lfloor M/2 \rfloor) = 0 \qquad (2.5) $$

This relation, with $S \in \mathfrak{M} \setminus \{\mathbb{Z}_M\}$, will not be satisfied by the constructions of Appendix A, so we will not be able to conclude to sharpness when $a \in (1/3, 1/2)$ or $a = 1/2$ and $M$ odd.

For the remaining part of this section we assume $M \ge 3$ and $a \in (0, 1/3]$. Let us construct the desired random mappings $(\psi_S)_{S \in \mathcal{J}}$. We distinguish $S = \{0\}$ from the other cases.

## 2.1. The random mapping $\psi_{\{0\}}$

The construction of $\psi_{\{0\}}$ is different from that of the other $\psi_S$, for $S \in \mathcal{J} \setminus \{\{0\}\}$. Choose two mappings $\tilde{\psi}, \hat{\psi} : \mathbb{Z}_M \to \mathbb{Z}_M$ satisfying respectively $\tilde{\psi}(0) = 0 = \tilde{\psi}(-1) = \tilde{\psi}(1)$ and $\tilde{\psi}(x) \ne 0$ for $x \in \mathbb{Z}_M \setminus [-1, 1]$, and $\tilde{\psi}(0) = 0$ and $\hat{\psi}(x) \ne 0$ for $x \in \mathbb{Z}_M \setminus \{0\}$. Take $\psi_{\{0\}}$ to be equal to $\tilde{\psi}$ with some probability $p \in [0, 1]$ and to $\hat{\psi}$ with probability $1-p$. Let us compute $p$ so that Condition (2.1) is satisfied, which here amounts to the validity of

$$ \mathbb{P}[\psi_{\{0\}}(x) = 0] = \frac{1}{\xi(\{0\})} P(x, 0) \qquad (2.6) $$

for all $x \in \mathbb{Z}_M$ and for some $\xi(\{0\}) > 0$.

* When $x \notin [-1, 1]$, both sides of (2.6) vanish.

* When $x = 0$, the l.h.s. of (2.6) is 1, while the r.h.s. is $(1-2a)/\xi(\{0\})$. This implies that $\xi(\{0\}) = 1-2a$.

* When $x \in \{-1, 1\}$, (2.6) is equivalent to

$$ p = \frac{a}{1-2a} $$

and this number $p$ does belongs to $(0, 1]$ for $a \in (0, 1/3]$.

Next we must check that for this random mapping $\psi_{\{0\}}$, (2.2) is satisfied, namely $\Psi(\{0\}) \in \mathcal{J} \cup \{\emptyset\}$. This is true, because $\tilde{\psi}^{-1}(\{0\}) = [-1, 1] \in \mathcal{J}$ and $\hat{\psi}^{-1}(\{0\}) = \{0\} \in \mathcal{J}$.

## 2.2. The other random mappings

We now come to the construction of the random mappings $\psi_S$, for $S \in \mathcal{J} \setminus \{\{0\}\}$, which is valid for all $a \in (0, 1/2]$ and does not depend on the particular value of $S \in \mathcal{J} \setminus \{\{0\}\}$. So let us call this random mapping $\phi$. It will takes five values $\{\phi_1, \phi_2, \phi_3, \phi_4, \phi_5\}$, and to describe them it is better to discriminate according the parity of $M$.

**When $M$ is odd.** Here is the definition of the mappings $\phi_l$, for $l \in \lfloor 5 \rfloor$.
• $\phi_1$ is defined by

$$ \forall x \in \mathbb{Z}_M, \quad \phi_1(x) := \begin{cases} x+1, & \text{if } x \in \lfloor -(M-1)/2, -1 \rfloor \\ 1, & \text{if } x=0 \\ x-1, & \text{if } x \in \lfloor 1, (M-1)/2 \rfloor \end{cases} $$

• $\phi_2$ is defined by

$$ \forall x \in \mathbb{Z}_M, \quad \phi_2(x) := \begin{cases} x+1, & \text{if } x \in \lfloor -(M-1)/2, -1 \rfloor \\ -1, & \text{if } x=0 \\ x-1, & \text{if } x \in \lfloor 1, (M-1)/2 \rfloor \end{cases} $$

• $\phi_3$ is defined by

$$ \forall x \in \mathbb{Z}_M, \quad \phi_3(x) := \begin{cases} x-1, & \text{if } x \in \lfloor -(M-1)/2, -1 \rfloor \\ 1, & \text{if } x=0 \\ x+1, & \text{if } x \in \lfloor 1, (M-1)/2 \rfloor \end{cases} $$

• $\phi_4$ is defined by

$$ \forall x \in \mathbb{Z}_M, \quad \phi_4(x) := \begin{cases} x-1, & \text{if } x \in \lfloor -(M-1)/2, -1 \rfloor \\ -1, & \text{if } x=0 \\ x+1, & \text{if } x \in \lfloor 1, (M-1)/2 \rfloor \end{cases} $$

• $\phi_5$ is just the identity mapping

The random mapping $\phi$ is taking each of the values $\phi_1, \phi_2, \phi_3$ and $\phi_4$ with the probability $a/2$ and the value $\phi_5$ with the remaining probability $1-2a$. It is immediate to check (2.1) can be reinforced into

$$ \forall x, y \in \mathbb{Z}_+, \quad \mathbb{P}[\psi_S(x) = y] = P(x, y) \qquad (2.7) $$

(called the strong association condition with $P^* = P$ in [17]). Furthermore, we have for any $r \in [(M-1)/2 - 1]$,

$$ \left\{ \begin{aligned} \phi_1^{-1}(B(0, r)) &= B(0, r+1) \\ \phi_2^{-1}(B(0, r)) &= B(0, r+1) \\ \phi_3^{-1}(B(0, r)) &= B(0, r-1) \\ \phi_4^{-1}(B(0, r)) &= B(0, r-1) \\ \phi_5^{-1}(B(0, r)) &= B(0, r) \end{aligned} \right. \qquad (2.8) $$

It follows that $\mathfrak{J}$ is left stable by the random mapping $\Psi$ defined in (2.2) (since the remaining set $\mathbb{Z}_M = B(0, (M-1)/2)$ is left stable by any mapping from $\mathbb{Z}_M$ to $\mathbb{Z}_M$).

**When M is even.** The previous mappings have to be slightly modified, due to the special role of the point $M/2$. More precisely, $\phi_1, \phi_2, \phi_3, \phi_4$ and $\phi_5$ are defined in exactly the same way on $\mathbb{Z}_M \setminus \{M/2\}$ and in addition:

$$ \phi_1(M/2) = M/2 + 1 $$

$$ \phi_2(M/2) = M/2 - 1 $$

$$ \phi_3(M/2) = M/2 + 1 $$
$$ \phi_4(M/2) = M/2 - 1 $$

$$ \phi_5(M/2) = M/2 $$

The random mapping $\phi$ is taking each of the values $\phi_1, \phi_2, \phi_3, \phi_4$ and $\phi_5$ with the same probabilities as in the case $M$ odd. The strong association condition (2.7) as well as the stability of $\mathfrak{J}$ by $\Psi$ are similarly verified ((2.8) is now true for $r \in [M/2 - 1]$).

## 2.3. The Markov transition kernel $\mathfrak{P}$

To simplify the description of $\mathfrak{P}$ given in (2.3), let us identify $[−r, r]$ with $r$, for $r \in [0, [M/2]]$. Then it appears that $\mathfrak{P}$ is the transition matrix of a birth and death chain:

$$ \forall k, l \in [0, \lfloor M/2 \rfloor], \quad \mathfrak{P}(k, l) = \begin{cases} 1 - 3a, & \text{if } k = 0 = l \\ 3a, & \text{if } k = 0 \text{ and } l = 1 \\ a \frac{2l+1}{2k+1}, & \text{if } k \in [1, \lfloor M/2 \rfloor - 1] \text{ and } |k-l| = 1 \\ 1 - 2a, & \text{if } k \in [1, \lfloor M/2 \rfloor - 1] \text{ and } k = l \\ 1, & \text{if } k = \lfloor M/2 \rfloor = l \\ 0, & \text{otherwise} \end{cases} $$

Since $\mathfrak{P}$ enables to reach the absorbing point $\lfloor M/2 \rfloor$ from all the other points, the absorbing time $t$ is a.s. finite and due to (2.5), its law is the distribution of a sharp strong stationary time for $X$, namely the tail probabilities of $t$ correspond exactly to the evolution of the separation distance between the time marginal distribution and $\pi$, see (2.4). Since the starting point $\mathcal{X}_0 = \{0\}$, identified with 0, is the opposite boundary point of the absorbing point $\lfloor M/2 \rfloor$, Karlin and McGregor [13] described explicitly the law of $t$ in terms of the spectrum of $\mathfrak{P}$ (see also Fill [10] or [8] for probabilistic proofs via intertwining relations). In particular when this spectrum is non-negative, $t$ is a sum of independent geometric variables whose parameters are the eigenvalues (except 1) of $\mathfrak{P}$.

**Remark 2.1.** When $a = 1/3$, Diaconis and Fill [7] gives another illustrative example of a sharp strong stationary time for $P$, see also Section 4.1 of Pak [19].

**Remark 2.2.** We could have first projected $\mathbb{Z}_M$ on $[0, \lfloor M/2 \rfloor]$ (sending 0 to 0, -1 and 1 to 1, etc.) and lump $X$ to obtain a birth-and-death process $\tilde{X}$. Its transition matrix $\tilde{P}$ satisfies $\tilde{P}(0, 1) = 2a$, $\tilde{P}(1, 0) = a$, $\tilde{P}(1, 2) = a$, etc. (note that $P([M/2], [M/2] - 1)$ is equal to $a$ or $2a$, depending on the parity of $M$). Constructing a corresponding set-valued intertwining dual, we would have ended with the same strong stationary time. According to Proposition 4.6 of Diaconis and Fill [7] (where we take into account that $\tilde{P}$ is reversible and that $\tilde{X}_0 = 0$), there exists a dual process to $\tilde{X}$ taking values in $\{[0, x] : x \in [0, \lfloor M/2 \rfloor]\}$ if and only if $\tilde{X}$ is monotone. It is easy to check that $\tilde{X}$ is monotone if and only if $a \in (0, 1/3]$ (compare $\tilde{P}(0, [1, \lfloor M/2 \rfloor]) = 2a$ with $\tilde{P}(1, [1, \lfloor M/2 \rfloor]) = 1 - a$, this special role of 0 is related to the difference between Sections 2.1 and 2.2). This explains the critical position of $a = 1/3$ and justifies the different treatment of the case $a \in (1/3, 1/2]$ in Appendix A.

**Remark 2.3.** If we had chosen for $\psi_{\{0\}}$ a random mapping satisfying the strong association condition (2.7) instead of the weak association (2.1), then we could not have achieved the stability condition $\Psi(\mathfrak{J}) \subset \mathfrak{J}$. Indeed, the condition $\mathbb{P}[\psi_{\{0\}}(0) = 0] = 1 - 2a$ would have implied that $\mathbb{P}[\Psi(\{0\} \ni 0)] = \mathbb{P}[\psi_{\{0\}}(0) = 0] = 1 - 2a < 1$ and thus with positive probability $\Psi(\{0\})$ must take values in the subsets not containing 0. Nevertheless, it is possible to choose a random mapping verifying (2.7) and such that the only additional value of $\Psi(\{0\})$ is the empty set, so that $\Psi(\{0\}) \in \{\emptyset, \{0\}, \{-1, 0, 1\}\}$. Due to the fact that necessarily $\mathfrak{P}(\{0\}, \cdot)\Lambda = \Lambda P(0, \cdot) = P(0, \cdot) = (1 - 2a)\delta_0 + a(\delta_{-1} + \delta_1)$ (where $\delta$ stands for the Dirac mass), we then end up with the same $\mathfrak{P}(\{0\}, \cdot)$ and thus the same kernel $\mathfrak{P}$.
If with positive probability $\Psi(\{0\})$ takes other values than $\emptyset$, $\{0\}$ and $\{-1, 0, 1\}$, and if we keep the same $\phi$ for the other random mappings, then $t$ will not be sharp (if is a.s. finite at all, cf. Rem. A.1), as it can be deduced from Appendix A.

## 2.4. Illustration for $a = 1/3$ and $M$ odd

When $a = 1/3$, the transition matrix $\mathfrak{P}$ is given on $\llbracket 0, (M-1)/2 \rrbracket$ by

$$ \forall k, l \in \llbracket 0, \lfloor M/2 \rfloor \rrbracket, \quad \mathfrak{P}(k, l) = \begin{cases} 0 & , \text{ if } k = 0 = l \\ 1 & , \text{ if } k = 0 \text{ and } l = 1 \\ \frac{1}{3} \frac{2l+1}{2k+1} & , \text{ if } k \in \llbracket 1, (M-3)/2 \rrbracket \text{ and } |k-l| = 1 \\ \frac{1}{3} & , \text{ if } k \in \llbracket 1, (M-3)/2 \rrbracket \text{ and } k = l \\ 1 & , \text{ if } k = (M-1)/2 = l \\ 0 & , \text{ otherwise} \end{cases} $$

Let $t$ be the time a Markov chain $\mathcal{X}$ associated to $\mathfrak{P}$ and starting from 0 hits $(M-1)/2$. Consider $W$ a random walk on $\mathbb{Z}$, starting from 0, whose transition probabilities of going one step upward, one step downward or to stay at the same position are all equal to $1/3$. Let $\zeta$ be the hitting time by $W$ of the set $\{-(M-1)/2, (M-1)/2\}$. Since for $k \in \llbracket 1, (M-3)/2 \rrbracket$, we have $\mathfrak{P}(k, k+1) \ge 1/3$ and $\mathfrak{P}(k, k-1) \le 1/3$, a simple comparison with the random walk $W$ enables us to see that $t$ is stochastically dominated by $\zeta$. This elementary observation leads to:

**Corollary 2.4.** *The strong stationary time $t$ for the random walk on the circle $\mathbb{Z}_M$ corresponding to $a = 1/3$, constructed as the absorption of the above Markov chain $\mathcal{X}$, has tail distributions satisfying for $M$ large enough,*

$$ \forall r \ge 0, \quad \mathbb{P}[t \ge rM^2] \le 2 \exp(-r/4) $$

*Proof.* It is sufficient to prove the same bound for $\zeta$: for $M$ large enough,

$$ \forall r \ge 0, \quad \mathbb{P}[\zeta \ge rM^2] \le 2 \exp(-r/4) \qquad (2.9) $$

For any $\alpha \in \mathbb{R}$, define

$$ \rho_{\alpha} := \frac{1 + e^{-\alpha} + e^{\alpha}}{3} $$

We have for any $n \in \mathbb{Z}_+$,

$$ \mathbb{E}[e^{\alpha W_{n+1}} | \sigma(W_n, W_{n-1}, \dots, W_1, W_0 = 0)] = \rho_{\alpha} e^{\alpha W_n} $$

and as a consequence, the process $(M_n)_{n \in \mathbb{Z}_+}$ defined by

$$ \forall n \in \mathbb{Z}_+, \quad M_n := e^{\alpha W_n - \ln(\rho_\alpha)n} $$

is a martingale. Note that by symmetry and since $\zeta$ is independent from $\operatorname{sgn}(W_\zeta)$, we have

$$ \begin{aligned} \mathbb{E}[M_\zeta] &= \mathbb{E}[e^{\alpha(M-1)/2 - \ln(\rho_\alpha)\zeta} \mathbb{1}_{W_\zeta = (M-1)/2}] + \mathbb{E}[e^{-\alpha(M-1)/2 - \ln(\rho_\alpha)\zeta} \mathbb{1}_{W_\zeta = -(M-1)/2}] \\ &= \cosh(\alpha(M-1)/2) \mathbb{E}[e^{-\ln(\rho_\alpha)\zeta}] \end{aligned} $$
Furthermore, $(M_{n \wedge \zeta})_{n \in \mathbb{Z}_+}$ is a bounded martingale (since $\rho_\alpha \ge 1$), so the stopping theorem gives us $\mathbb{E}[M_\zeta] = \mathbb{E}[M_0] = 1$, and we get

$$ \mathbb{E}[\rho_{\alpha}^{-\zeta}] = \frac{1}{\cosh(\alpha(M-1)/2)} $$

By analytic extension, this equality is still valid if $\alpha$ is replaced by $\alpha i$ (where $i \in \mathbb{C}$, $i^2 = -1$), as long as $|\alpha|(M-1)/2 < \pi/2$, and we get

$$ \mathbb{E}\left[\left(\frac{3}{1 + 2 \cos(\alpha)}\right)^{\zeta}\right] = \frac{1}{\cos(\alpha(M-1)/2)} $$

Apply this equality with $\alpha = 1/M$, to deduce that for large $M$,

$$ \mathbb{E}\left[\left(\frac{3}{1 + 2 \cos(1/M)}\right)^{\zeta}\right] \sim \frac{1}{\cos(1/2)} $$

For $r > 0$, remarking that $\cos(1/M) < 1$, we get

$$ \begin{aligned} \mathbb{P}[\zeta \ge rM^2] & \le \left(\frac{1 + 2 \cos(1/M)}{3}\right)^{rM^2} \mathbb{E}\left[\left(\frac{3}{1 + 2 \cos(1/M)}\right)^{\zeta}\right] \\ & \sim \frac{1}{\cos(1/2)} \left(1 - \frac{1}{3M^2}\right)^{rM^2} \\ & = \frac{1}{\cos(1/2)} \exp(-r(1 + o(1))/3) \end{aligned} $$

Taking into account that $1/\cos(1/2) \approx 1.139$, we see that (2.9) is satisfied for $M$ large enough. $\square$

<figure><img src="image_1.png" /></figure>

### 3. A STRONG STATIONARY TIME FOR THE FINITE TORUS

Here we construct a set-valued dual process associated to the random walk $[X, Y, Z]$ on the Heisenberg group $\mathbb{H}_M$ described in the introduction, where the odd number $M \ge 3$ is fixed. In some sense it is just a tensorization of the construction of the previous section. It will provide a strong stationary time for the random walk $(X, Y)$ on the torus, but not for $[X, Y, Z]$ as we are to see. The main interest of this section is to serve as a link between the considerations of Sections 2 and 4, justifying the construction that will be done there. Except for this pedagogical purpose, this section is not needed in the sequel.

Denote by $P$ the transition kernel of $[X, Y, Z]$. The uniform probability measure $\mathcal{U}$ on $\mathbb{H}_M$ is reversible with respect to $P$, so that $P^* = P$, where $P^*$ is the adjoint operator of $P$ in $\mathbb{L}^2(\mathcal{U})$. As in the previous section, we are looking for a dual process $\mathcal{X} := (\mathcal{X}_n)_{n \in \mathbb{Z}_+}$ taking values in a set $\mathfrak{V}$ of non-empty subsets of $\mathbb{H}_M$, whose transition kernel $\mathfrak{P}$ is intertwined with $P$ through:

$$ \mathfrak{P}\Lambda = \Lambda P \qquad (3.1) $$

where the Markov kernel $\Lambda$ from $\mathfrak{V}$ to $\mathbb{H}_M$ is given by

$$ \forall \Omega \in \mathfrak{V}, \forall u \in \mathbb{H}_M, \quad \Lambda(\Omega, u) := \frac{\mathcal{U}(u)}{\mathcal{U}(\Omega)} \mathbb{1}_{\Omega}(u) $$
Since $[X, Y, Z]$ is starting from $[0, 0, 0]$, we will require furthermore that $\mathcal{X}_0 = \{[0, 0, 0]\}$. The construction of $\mathfrak{P}$ will follow the general random mapping method described in [17] and already alluded to in the previous section. More precisely, for any $\Omega \in \mathfrak{V}$, we are looking for a **random mapping** $\psi_{\Omega} : \mathbb{H}_M \to \mathbb{H}_M$ satisfying two conditions:

* the **weak association** with $P^* = P$, namely

$$ \forall u \in \mathbb{H}_M, \forall v \in \Omega, \quad \mathbb{P}[\psi_{\Omega}(u) = v] = \frac{1}{\xi(\Omega)} P(u, v) \qquad (3.2) $$

where $\xi(\Omega) > 0$ is a positive number.

* the **stability** of $\mathfrak{V}$: the set

$$ \Psi(\Omega) := \psi_{\Omega}^{-1}(\Omega) \qquad (3.3) $$

belongs to $\mathfrak{V} \sqcup \{\emptyset\}$.

It is shown in [17] that the Markov kernel defined on $\mathfrak{V}$ by

$$ \forall \Omega, \Omega' \in \mathfrak{V}, \quad \mathfrak{P}(\Omega, \Omega') = \frac{\xi(\Omega)\mathcal{U}(\Omega')}{\mathcal{U}(\Omega)} \mathbb{P}[\Psi(\Omega) = \Omega'] $$

satisfies (3.1). Note that the whole state space $\mathbb{H}_M$ is absorbing for $\mathfrak{P}$, so if

$$ t := \inf\{n \in \mathbb{Z}_+ : \mathcal{X}_n = \mathbb{H}_M\} \in \mathbb{N} \sqcup \{\infty\} $$

is a.s. finite, then it has the same law as a strong stationary time for $[X, Y, Z]$, as a consequence of Diaconis and Fill [7].

Let us now describe $\mathfrak{V}$ and the corresponding random mappings $(\psi_{\Omega})_{\Omega \in \mathfrak{V}}$. The set $\mathfrak{V}$ consists of subsets $\Omega \subset \mathbb{H}_M$ of the form

$$ \Omega_{r,s,A} := \{[x, y, z] \in \mathbb{H}_M : x \in B(r), y \in B(s), z \in A(x, y)\} \qquad (3.4) $$

where $r \in [0, (M-1)/2]$, $s \in [0, (M-1)/2]$, $B(r) := [-r, r]$ seen as the closed ball of $\mathbb{Z}_M$ centered at 0 and of radius $r$, and $A$ is a mapping from $B(r) \times B(s)$ to the non-empty subsets of $\mathbb{Z}_M$. We call $A$ a **special field** going from the **base space** $B(r) \times B(s)$ to the **fiber space** consisting of the non-empty subsets of $\mathbb{Z}_M$. In the next section, this notion will be relaxed into that of a **field**, which is a mapping $F$ from a finite set $S$ to the set of subsets (the empty set included) of another finite set $S'$ and serves to describe subsets of $S \times S'$ via the representation

$$ \{(x, y) \in S \times S' : y \in F(x)\} $$

In order to construct our random mappings $(\psi_{\Omega})_{\Omega \in \mathfrak{V}}$, we need to introduce the following 7 mappings, inspired by the considerations of the previous section. Denote $\mathbb{Z}_M^- := [-((M-1)/2), -1]$ and $\mathbb{Z}_M^+ := [0, (M-1)/2]$, seen as subsets of $\mathbb{Z}_M$. We define the mapping **sgn** on $\mathbb{Z}_M$ via

$$ \forall x \in \mathbb{Z}_M, \quad \operatorname{sgn}(x) := \begin{cases} -1, & \text{if } x \in \mathbb{Z}_M^- \\ 1, & \text{if } x \in \mathbb{Z}_M^+ \end{cases} $$

Here are the mappings that will be the values of the random mappings $(\psi_{\Omega})_{\Omega \in \mathfrak{V}}$:
• The mapping $\tilde{\phi}^{(0)}$:

$$ \forall [x, y, z] \in \mathbb{H}_M, \quad \tilde{\phi}^{(0)}([x, y, z]) := \begin{cases} [0, y, z - xy], & \text{if } x \in \{-1, 0, 1\} \\ [x, y, z], & \text{if } x \notin \{-1, 0, 1\} \end{cases} $$

• The mapping $\hat{\phi}^{(0)}$:

$$ \forall [x, y, z] \in \mathbb{H}_M, \quad \hat{\phi}^{(0)}([x, y, z]) := \begin{cases} [x, 0, z], & \text{if } y \in \{-1, 0, 1\} \\ [x, y, z], & \text{if } y \notin \{-1, 0, 1\} \end{cases} $$

• The mapping $\tilde{\phi}^{(1)}$:

$$ \forall [x, y, z] \in \mathbb{H}_M, \quad \tilde{\phi}^{(1)}([x, y, z]) := [x - \operatorname{sgn}(x), y, z - \operatorname{sgn}(x)y] $$

• The mapping $\hat{\phi}^{(1)}$:

$$ \forall [x, y, z] \in \mathbb{H}_M, \quad \hat{\phi}^{(1)}([x, y, z]) := [x, y - \operatorname{sgn}(y), z] $$

• The mapping $\tilde{\phi}^{(2)}$:

$$ \forall [x, y, z] \in \mathbb{H}_M, \quad \tilde{\phi}^{(2)}([x, y, z]) := [x + \operatorname{sgn}(x), y, z + \operatorname{sgn}(x)y] $$

• The mapping $\hat{\phi}^{(2)}$:

$$ \forall [x, y, z] \in \mathbb{H}_M, \quad \hat{\phi}^{(2)}([x, y, z]) := [x, y + \operatorname{sgn}(y), z] $$

• $\hat{\phi}^{(3)}$ is just the identity mapping on $\mathbb{H}_M$.

We can now define the family $(\psi_{\Omega})_{\Omega \in \mathcal{N}}$. Again we fix a set $\Omega := \Omega_{r,s,A}$ as in (3.4). The underlying probability depends on $\Omega$ through the following cases.

• If $r = s = 0$. The random mapping $\psi_{\Omega}$ takes with the values $\tilde{\phi}^{(0)}$ and $\hat{\phi}^{(0)}$ with probability $1/2$ each. The weak association with $P$ is satisfied with $\xi(\Omega) = 1/3$: for any $[x, y, z] \in \mathbb{H}_M$ and $[x', y', z'] \in \Omega$,

$$ \mathbb{P}[\psi_{\Omega}([x, y, z]) = [x', y', z')] = 3P([x, y, z], [x', y', z']) \quad (3.5) $$

Indeed, first note that $[x', y', z'] \in \Omega_{0,0,A}$ implies that $x' = y' = 0$. Next, both sides vanish if we do not have $(x, y) \in \{(-1, 0), (1, 0), (0, 1), (0, -1), (0, 0)\}$, and $z' = z$. Consider the case $(x, y) = (0, 0)$, we have for any $z \in \mathbb{Z}_M$,

$$ \begin{aligned} \mathbb{P}[\psi_{\Omega}([0, 0, z]) = [0, 0, z]] &= 1 \\ \mathbb{P}([0, 0, z], [0, 0, z]) &= 1/3 \end{aligned} $$

so (3.5) is satisfied.

When $(x, y) = (-1, 0)$, we have for any $z \in \mathbb{Z}_M$,

$$ \begin{aligned} \mathbb{P}[\psi_{\Omega}([-1, 0, z]) = [0, 0, z]] &= \mathbb{P}[\psi_{\Omega} = \tilde{\phi}^{(0)}] = 1/2 \\ \mathbb{P}([-1, 0, z], [0, 0, z]) &= 1/6 \end{aligned} $$
so (3.5) is satisfied again. The other cases are treated in the same way.

* If $r=0$ and $s \neq 0$. The random mapping $\psi_{\Omega}$ takes with the value $\tilde{\phi}^{(0)}$ with probability $p$, $\hat{\phi}^{(1)}$ and $\hat{\phi}^{(2)}$ each with probability $q$, and $\hat{\phi}^{(3)}$ with probability $1-p-2q$, where $p, q \in [0, 1]$ are such that $1-p-2q \in [0, 1]$. Let us find $p, q$ such that furthermore the weak association with $P$ is satisfied with some $\xi(\Omega) > 0$: for any $[x, y, z] \in \mathbb{H}_M$ and $[x', y', z'] \in \Omega$,

$$ \mathbb{P}[\psi_{\Omega}([x, y, z]) = [x', y', z')] = \frac{1}{\xi(\Omega)} P([x, y, z], [x', y', z']) \quad (3.6) $$

First note that $[x', y', z'] \in \Omega_{0,s,A}$ implies that $x' = 0$. Next we have

$$ \mathbb{P}[\psi_{\Omega}([x, y, z]) = [0, y', z')] = p1_{\{\tilde{\phi}^{(0)}([x,y,z])=[0,y',z']\}} + q1_{\{\hat{\phi}^{(1)}([x,y,z])=[0,y',z']\}} \\ +q1_{\{\hat{\phi}^{(2)}([x,y,z])=[0,y',z']\}} + (1-p-2q)1_{\{\hat{\phi}^{(3)}([x,y,z])=[0,y',z']\}} $$

Let us first investigate the possibility $\tilde{\phi}^{(0)}([x, y, z]) = [0, y', z']$. Necessarily, $x \in \{-1, 0, 1\}$, $y = y'$, $z' = z - xy$. Whatever $x \in \{-1, 0, 1\}$, since $\hat{\phi}^{(1)}([x, y, z]) \neq [0, y, z']$ and $\hat{\phi}^{(2)}([x, y, z]) \neq [0, y, z']$ (due to $\text{sign}(y) \neq 0$), we have

$$ \mathbb{P}[\psi_{\Omega}([x, y, z]) = [0, y, z')] = p1_{\{\tilde{\phi}^{(0)}([x,y,z])=[0,y,z-xy]\}} + (1-p-2q)1_{\{\hat{\phi}^{(3)}([x,y,z])=[0,y,z-xy]\}} \\ = \begin{cases} p & , \text{ if } x \in \{-1, 1\} \\ 1-2q & , \text{ if } x = 0 \end{cases} $$

On the other hand, we have

$$ P([x, y, z], [0, y, z]) = \begin{cases} 1/6 & , \text{ if } x \in \{-1, 1\} \\ 1/3 & , \text{ if } x = 0 \end{cases} $$

thus we end up with the conditions $1-2q=2p$ and $\xi(\Omega)=1/(6p)$.

Next we consider the possibility $\hat{\phi}^{(1)}([x, y, z]) = [0, y', z']$ (the symmetric case $\hat{\phi}^{(2)}([x, y, z]) = [0, y', z']$ is similarly treated). Necessarily $x=0$, $z'=z$ and $y=y' \pm 1$, depending on $y \in \mathbb{Z}_M^+$ or $y \in \mathbb{Z}_M^-$. With these values, it follows that the l.h.s. of (3.6) is $q$ and the r.h.s. is $1/(6\xi(\Omega))$, leading us to the equation $q=1/(6\xi(\Omega))$. Putting together all the equations between $p, q$ and $\xi(\Omega)$, we get that $p=q=1/4$ and $\xi(\Omega)=2/3$. It is then immediate to check that (3.6) is true.

* If $r \neq 0$ and $s=0$. The random mapping $\psi_{\Omega}$ takes with the values $\hat{\phi}^{(0)}, \tilde{\phi}^{(1)}, \tilde{\phi}^{(2)}$ and $\hat{\phi}^{(3)}$, each with probability $1/4$. The treatment of this case is similar to the previous one.

* If $r \neq 0$ and $s \neq 0$. The random mapping $\psi_{\Omega}$ takes the value $\hat{\phi}^{(3)}$ with probability $1/3$ and each of the values $\tilde{\phi}^{(1)}, \hat{\phi}^{(1)}, \tilde{\phi}^{(2)}$ and $\hat{\phi}^{(2)}$ with probability $1/6$. This situation is the simplest one, we clearly have for any $[x, y, z] \in \mathbb{H}_M$ and $[x', y', z'] \in \Omega$,

$$ \mathbb{P}[\psi_{\Omega}([x, y, z]) = [x', y', z')] = P([x, y, z], [x', y', z']) $$

Our next task is to check that the random mapping $\Psi$ associated to the family $(\psi_{\Omega})_{\Omega \in \mathcal{M}}$ lets $\mathfrak{M}$ stable and moreover to describe its action. Fix some $\Omega := \Omega_{r,s,A} \in \mathfrak{M}$, we are wondering in which set it will be transformed by $\Psi$. Again we consider the previous situations.

* If $r=s=0$. Then $\Psi(\Omega)$ is equal either to $(\tilde{\phi}^{(0)})^{-1}(\Omega)$ or to $(\hat{\phi}^{(0)})^{-1}(\Omega)$. Let us consider the first case. By definition, we have

$$ (\tilde{\phi}^{(0)})^{-1}(\Omega) = \{[x', y', z'] \in \mathbb{H}_M : \tilde{\phi}^{(0)}([x', y', z']) \in \Omega\} $$
$$
\begin{align*}
&= \{[x', y', z'] \in \mathbb{H}_M : \exists [x, y, z] \in \Omega, \text{ with } \tilde{\phi}^{(0)}([x', y', z']) = [x, y, z]\} \\
&= \{[x', y', z'] \in \mathbb{H}_M : \exists z \in A(0, 0), \text{ with } \tilde{\phi}^{(0)}([x', y', z']) = [0, 0, z]\} \\
&= \{[x', y', z'] \in \mathbb{H}_M : \exists z \in A(0, 0), \text{ with } x' \in \{-1, 0, 1\} \text{ and } [0, y', z' - x'y'] = [0, 0, z]\} \\
&= \{[x', 0, z'] \in \mathbb{H}_M : x' \in \{-1, 0, 1\} \text{ and } z' \in A(0, 0)\} \\
&= \Omega_{1,0,A'}
\end{align*}
$$

where $A'$ is defined by:

$$
\forall (x', y') \in B(1) \times \{0\}, \quad A'(x', y') := A(0, 0)
$$

Similarly, we get $(\hat{\phi}^{(0)})^{-1}(\Omega) = \Omega_{0,1,A'}$.

* If $r = 0$ and $s \neq 0$. There are four possibilities for $\Psi(\Omega): (\tilde{\phi}^{(0)})^{-1}(\Omega)$, $(\hat{\phi}^{(1)})^{-1}(\Omega)$, $(\hat{\phi}^{(2)})^{-1}(\Omega)$ or $(\hat{\phi}^{(3)})^{-1}(\Omega)$. The same computation as above shows that

$$
\begin{align*}
(\tilde{\phi}^{(0)})^{-1}(\Omega) \\
&= \{[x', y', z'] \in \mathbb{H}_M : \exists y \in B(s), \exists z \in A(0, y), \text{ with } x' \in \{-1, 0, 1\} \text{ and } [0, y', z' - x'y'] = [0, y, z]\} \\
&= \{[x', y', z'] \in \mathbb{H}_M : x' \in \{-1, 0, 1\}, y' \in B(s) \text{ and } z' \in A(0, y') + x'y'\} \\
&= \Omega_{1,s,A'}
\end{align*}
$$

where $A'$ is defined by:

$$
\forall (x', y') \in B(1) \times B(s), \quad A'(x', y') := A(0, y') + x'y'
$$

Next consider $(\hat{\phi}^{(1)})^{-1}(\Omega)$:

$$
\begin{align*}
(\hat{\phi}^{(1)})^{-1}(\Omega) &= \{[x', y', z'] \in \mathbb{H}_M : \exists y \in B(s), \exists z \in A(0, y) \text{ with } x' = 0, y' - \operatorname{sgn}(y') = y, z' = z\} \\
&= \Omega_{0,s+1,A'}
\end{align*}
$$

where $A'$ is defined by:

$$
\forall (x', y') \in \{0\} \times B(s+1), \quad A'(x', y') := A(0, y' - \operatorname{sgn}(y'))
$$

Similarly, $(\hat{\phi}^{(2)})^{-1}(\Omega) = \Omega_{0,s-1,A'}$, with another set-valued mapping $A'$:

$$
\forall (x', y') \in \{0\} \times B(s-1), \quad A'(x', y') := A(0, y' + \operatorname{sgn}(y'))
$$

Of course, we have $(\hat{\phi}^{(3)})^{-1}(\Omega) = \Omega$.

* The other cases where $r \neq 0$ are treated in a similar way. For instance for $r \neq 0$, $(M-1)/2$ and $s \neq 0$, we have $(\hat{\phi}^{(1)})^{-1}(\Omega) = \Omega_{r+1,s,A'}$ with

$$
\forall (x', y') \in B((r+1) \wedge ((M-1)/2)) \times B(s), \quad A'(x', y') := A(x' - \operatorname{sgn}(x'), y') + \operatorname{sgn}(x')y'
$$

Let $\mathfrak{P}$ the transition kernel induced by the above family of random mappings $(\psi_{\Omega})_{\Omega \in \mathcal{O}}$ and consider $\mathcal{X} := (\mathcal{X}_n)_{n \in \mathbb{Z}_+}$ an associated Markov chain starting from $\{[0,0,0]\}$. For any $n \in \mathbb{Z}_+$, let us write $\mathcal{X}_n = \Omega_{R_n, S_n, A_n}$ with the previous notation. Define

$$
\sigma := \inf\{n \in \mathbb{Z}_+ : R_n = (M-1)/2 = S_n\}
$$
Taking into account the considerations of Section 2, $\sigma$ is a.s. finite and we have

$$ \forall n \ge \sigma, \quad R_n = (M-1)/2 = S_n $$

Nevertheless, this Markov chain has a serious drawback:

$$ \forall n \in \mathbb{Z}_+, \forall x \in B(R_n), \forall y \in B(S_n), \quad |A_n(x, y)| = 1 \qquad (3.7) $$

Indeed, from the above construction, we deduce that

$$ \forall n \in \mathbb{Z}_+, \forall x' \in B(R_{n+1}), \forall y' \in B(S_{n+1}), \exists x \in B(R_n), \exists y \in B(S_n) : |A_{n+1}(x', y')| = |A_n(x, y)| $$

This observation is true for any initial condition $\mathcal{X}_0$. When $\mathcal{X}_0 = \{[0,0,0]\}$, the fiber-valued component of $\mathcal{X}_0$ is only $\{0\}$ and has size 1. The latter property is inherited by all the following values of $\mathcal{X}_n$ for $n \in \mathbb{Z}_+$, justifying (3.7). For the fiber-valued components of $\mathcal{X}$ to reach the whole state space $\mathbb{Z}_M$, we need to change our strategy. Before doing so in the next section, let us estimate the tail probabilities of $\sigma$, taking into account Corollary 2.4:

**Lemma 3.1.** For $M$ large enough, we have

$$ \forall r \ge 0, \quad \mathbb{P}[\sigma \ge rM^2] \le 5 \exp(-r/10) $$

*Proof.* Let $\tilde{X} := (\tilde{X}_n)_{n \in \mathbb{Z}_+}$ and $\tilde{Y} := (\tilde{Y}_n)_{n \in \mathbb{Z}_+}$ be two independent random walks on $\mathbb{Z}_M$ as in Section 2.4. Let $(B_n)_{n \in \mathbb{Z}_+}$ be a family of independent Bernoulli variables of parameter $1/2$ (independent from $(\tilde{X}, \tilde{Y})$) and define

$$ \forall n \in \mathbb{Z}_+, \quad \theta_n := \sum_{m \in [n]} B_m $$

The chain $(X, Y)$ has the same law as $(\tilde{X}_{\theta_n}, \tilde{Y}_{n-\theta_n})_{n \in \mathbb{Z}_+}$ and from the above construction, it appears that

$$ \sigma = \inf\{n \in \mathbb{Z}_+ : \theta_n \ge t_1 \text{ and } n - \theta_n \ge t_2\} $$

where $t_1$ (respectively $t_2$) is the strong stationary time constructed as in Section 2.4 for $\tilde{X}$ (resp. $\tilde{Y}$). It follows that for any $n \in \mathbb{Z}_+$,

$$ \begin{aligned} \mathbb{P}[\sigma \ge n] &\le \mathbb{P}[\theta_n \le t_1] + \mathbb{P}[n - \theta_n \le t_2] \\ &= 2\mathbb{P}[\theta_n \le t_1] \end{aligned} $$

since $(\theta_n, t_1)$ and $(n - \theta_n, t_2)$ have the same law. According to Corollary 2.4, we have for the conditional expectation knowing $\theta_n$ and for large $M$:

$$ \mathbb{P}[\theta_n \le t_1 | \theta_n] \le 2 \exp(-\theta_n/(4M^2)) $$

so that

$$ \begin{aligned} \mathbb{P}[\theta_n \le t_1] &\le 2\mathbb{E}[\exp(-\theta_n/(4M^2))] \\ &= 2\mathbb{E}[\exp(-B_1/M^2)]^n \\ &= 2 \left( \frac{1 + \exp(-1/(4M^2))}{2} \right)^n \end{aligned} $$
It follows that if $n$ is of the form $[rM^2]$ for some $r \ge 0$, then

$$ \mathbb{P}[\sigma \ge rM^2] \le 4 \left( \frac{1 + \exp(-1/(4M^2))}{2} \right)^{rM^2} \\ \le 5 \exp(-r/10) $$

for $M$ large enough (uniformly in $r \ge 0$). $\square$

Note that $\sigma$ is a strong stationary time for the random walk $(X, Y)$ on the torus $\mathbb{Z}_M^2$. Thus Lemma 3.1 enables to recover the order $M^2$ for the speed of convergence to equilibrium of $(X, Y)$ in separation.

### 4. A STRONG STATIONARY TIME FOR THE FINITE HEISENBERG WALK

Here we modify the family of random mappings considered in the previous section, in order to construct another set-valued dual process associated to the random walk $[X, Y, Z]$, with better spreading properties. The basic idea is to play with the signs which appeared in the definitions of $\tilde{\phi}^{(1)}$, $\hat{\phi}^{(1)}$, $\tilde{\phi}^{(2)}$, $\hat{\phi}^{(2)}$ (in fact they were already present in the construction of Section 2.2, even if they were not written explicitly). In Section 3, these signs simply depended on either the coordinate $x$ or $y$. Below they will be allowed to depend on the whole element $[x, y, z]$. We will first consider general sign functions, denoted $\tilde{\varphi}_A$ and $\hat{\varphi}_A$ in (4.1) and (4.2), and compute their action on fields. Then we will optimize over the choice of these sign functions to insure the creation of fields as large as possible (and consequently also of fields as small as possible).

We begin by presenting a representation of the subsets of $\mathbb{H}_M$ in terms of fields. A field is mapping $A$ from $\mathbb{Z}_M^2$ to the set of subsets of $\mathbb{Z}_M$. The set of fields is denoted $\mathbb{A}$. To any field $A := (A(x, y))_{(x,y)\in\mathbb{Z}_M^2} \in \mathbb{A}$, we associate the subset $\Omega_A \subset \mathbb{H}_M$ via

$$ \Omega_A := \{[x, y, z] \in \mathbb{H}_M : z \in A(x, y)\} $$

This relation is in fact a bijection between $\mathbb{A}$ and the set of subsets of $\mathbb{H}_M$. The subsets $A(x, y)$, for $(x, y) \in \mathbb{Z}_M^2$, will still be called the fibers. The special fields considered in the previous section are the fields such that the non-empty fibers are exactly indexed by sets of the form $B(r) \times B(s)$, for some $r, s \in [0, (M-1)/2]$. Here it will be more convenient to work with fields than with the subsets of $\mathbb{H}_M$. The main difference between our new family of random mappings $(\psi_A)_{A \in \mathbb{A}}$ and that $(\psi_\Omega)_{\Omega \in \mathcal{O}}$ of Section 3 consists in replacing the function sign that was acting on the first coordinates of $\mathbb{H}_M$ by a much more general mapping. More precisely, let us fix a field $A \in \mathbb{A}$. Assume that for any $x, y \in \mathbb{Z}_M$, we are given two partitions of $\mathbb{Z}_M$ into two disjoint subsets respectively $\tilde{B}_{A,x,y}^{-} \sqcup \tilde{B}_{A,x,y}^{+}$ and $\tilde{B}_{A,x,y}^{-} \sqcup \tilde{B}_{A,x,y}^{+}$, that depend on $A$, $x$ and $y$. We define corresponding functions $\tilde{\varphi}_A$ and $\hat{\varphi}_A$ on $\mathbb{H}_M$ via

$$ \forall [x, y, z] \in \mathbb{H}_M, \quad \tilde{\varphi}_A(x, y, z) := \begin{cases} -1, & \text{if } z \in \tilde{B}_{A,x,y}^{-} \\ 1, & \text{if } z \in \tilde{B}_{A,x,y}^{+} \end{cases} \quad (4.1) $$

$$ \forall [x, y, z] \in \mathbb{H}_M, \quad \hat{\varphi}_A(x, y, z) := \begin{cases} -1, & \text{if } z \in \hat{B}_{A,x,y}^{-} \\ 1, & \text{if } z \in \hat{B}_{A,x,y}^{+} \end{cases} \quad (4.2) $$

Next we replace $\tilde{\phi}^{(1)}, \tilde{\phi}^{(2)}, \hat{\phi}^{(1)}$ and $\hat{\phi}^{(2)}$ respectively by

$$ \forall [x, y, z] \in \mathbb{H}_M, \quad \tilde{\phi}_A^{(1)}([x, y, z]) := [x - \tilde{\varphi}_A(x, y, z), y, z - \tilde{\varphi}_A(x, y, z)y] $$

$$ \forall [x, y, z] \in \mathbb{H}_M, \quad \tilde{\phi}_A^{(2)}([x, y, z]) := [x + \tilde{\varphi}_A(x, y, z), y, z + \tilde{\varphi}_A(x, y, z)y] $$

$$ \forall [x, y, z] \in \mathbb{H}_M, \quad \hat{\phi}_A^{(1)}([x, y, z]) := [x, y - \hat{\varphi}_A(x, y, z), z] $$
$$ \forall [x, y, z] \in \mathbb{H}_M, \quad \hat{\phi}_A^{(2)}([x, y, z]) := [x, y + \hat{\varphi}_A(x, y, z), z] $$

The random mapping $\psi_A$ is constructed as the corresponding $\psi_\Omega$ in the case $r \neq 0$ and $s \neq 0$. Namely, the random mapping $\psi_A$ takes the value $\hat{\phi}^{(3)}$ with probability $1/3$ and each of the values $\tilde{\phi}_A^{(1)}, \hat{\phi}_A^{(1)}, \tilde{\phi}_A^{(2)}$ and $\hat{\phi}_A^{(2)}$ with probability $1/6$. There is no difficulty in checking that $\psi_A$ is associated to $P$:

$$ \forall [x, y, z] \in \mathbb{H}_M, \forall [x', y', z'] \in \Omega_A, \quad \mathbb{P}[\psi_A([x, y, z]) = [x', y', z')] = P([x, y, z], [x', y', z']) $$

(note that $\tilde{\phi}^{(0)}$ and $\hat{\phi}^{(0)}$ are no longer required, they were only useful to initiate the spread of the evolving sets associated to $(\psi_\Omega)_{\Omega \in \mathcal{Y}}$ on the base space $\mathbb{Z}_M \times \mathbb{Z}_M$ corresponding to the two first coordinates of $\mathbb{H}_M$).

Consider the random mapping $\Psi$ associated to the family $(\psi_A)_{A \in \mathcal{A}}$ and let us describe its action. Fix some $A \in \mathcal{A}$, we are wondering what is $\Psi(\Omega_A)$, namely we have to compute $(\tilde{\phi}_A^{(1)})^{-1}(\Omega_A)$, $(\hat{\phi}^{(1)})^{-1}(\Omega_A)$, $(\tilde{\phi}_A^{(2)})^{-1}(\Omega_A)$ and $(\hat{\phi}^{(2)})^{-1}(\Omega_A)$. Let us start with

$$ (\tilde{\phi}_A^{(1)})^{-1}(\Omega_A) = \{[x', y', z'] \in \mathbb{H}_M : \exists [x, y, z] \in \Omega_A, \text{ with } \tilde{\phi}_A^{(1)}([x', y', z']) = [x, y, z]\} $$

The belonging of $[x, y, z]$ to $\Omega_A$ means that $z \in A(x, y)$, and the equality $\tilde{\phi}_A^{(1)}([x', y', z']) = [x, y, z]$ is equivalent to

$$ \begin{cases} x' - \tilde{\varphi}_A(x', y', z') = x \\ y' = y \\ z' - \tilde{\varphi}_A(x', y', z')y' = z \end{cases} $$

Thus $[x', y', z']$ belongs to $(\tilde{\phi}_A^{(1)})^{-1}(\Omega_A)$ if and only if

$$ z' \in A(x' - \tilde{\varphi}_A(x', y', z'), y') + \tilde{\varphi}_A(x', y', z')y' $$

namely, either

$$ \tilde{\varphi}_A(x', y', z') = -1 \text{ and } z' \in A(x' + 1, y') - y' \quad (4.3) $$

or

$$ \tilde{\varphi}_A(x', y', z') = 1 \text{ and } z' \in A(x' - 1, y') + y' \quad (4.4) $$

Thus defining the new field $\tilde{A}^{(1)}$ via

$$ \forall (x', y') \in \mathbb{Z}_M^2, \quad \tilde{A}^{(1)}(x', y') := ((A(x' + 1, y') - y') \cap \tilde{B}_{A,x',y'}^{-}) \cup ((A(x' - 1, y') + y') \cap \tilde{B}_{A,x',y'}^{+}) $$

we get that

$$ (\tilde{\phi}_A^{(1)})^{-1}(\Omega_A) = \Omega_{\tilde{A}^{(1)}} $$

The other cases are treated in a similar way and we get

$$ (\hat{\phi}_A^{(1)})^{-1}(\Omega_A) = \Omega_{\hat{A}^{(1)}} $$

$$ (\tilde{\phi}_A^{(2)})^{-1}(\Omega_A) = \Omega_{\tilde{A}^{(2)}} $$
$$(\hat{\phi}_A^{(2)})^{-1}(\Omega_A) = \Omega_{\hat{A}^{(2)}}$$

where for any $(x', y') \in \mathbb{Z}_M^2$,

$$\hat{A}^{(1)}(x', y') := (A(x', y' + 1) \cap \hat{B}_{A,x',y'}^{-}) \cup ((A(x', y' - 1) \cap \hat{B}_{A,x',y'}^{+})$$

$$\tilde{A}^{(2)}(x', y') := ((A(x' + 1, y') - y') \cap \tilde{B}_{A,x',y'}^{+}) \cup ((A(x' - 1, y') + y') \cap \tilde{B}_{A,x',y'}^{-})$$

$$\hat{A}^{(2)}(x', y') := (A(x', y' + 1) \cap \hat{B}_{A,x',y'}^{+}) \cup ((A(x', y' - 1) \cap \hat{B}_{A,x',y'}^{-})$$

Let $\mathcal{Q}$ be the transition kernel induced by the above family of random mappings $(\psi_A)_{A \in \mathcal{A}}$ as in (2.3). More precisely, it is given by

$$\mathcal{Q}(A, A') := \frac{|A'|}{|A|} \left( \frac{1}{6} \mathbb{1}_{\hat{A}^{(1)}}(A') + \frac{1}{6} \mathbb{1}_{\hat{A}^{(1)}}(A') + \frac{1}{6} \mathbb{1}_{\hat{A}^{(2)}}(A') + \frac{1}{6} \mathbb{1}_{\hat{A}^{(2)}}(A') + \frac{1}{3} \mathbb{1}_{A}(A') \right)$$

for any fields $A, A'$, where $A \in \mathcal{A}\{\emptyset\}$ (where $\emptyset$ is the field whose fibers are all empty) and where for any field $A$, the **thickness** of $A$ is defined by

$$|A| := \sum_{x,y \in \mathbb{Z}_M} |A(x,y)|$$

It corresponds to the cardinal of the subset of $\mathbb{H}_M$ associated to the field $A$. Note in particular that transitions to $\emptyset$ have the probability 0. Markov chains whose transitions are dictated by $\mathcal{Q}$ will be denoted $(A_n)_{n \in \mathbb{Z}_+}$, they start from an initial field $A_0 \in \mathcal{A}\{\emptyset\}$ and stay afterward in $\mathcal{A}\{\emptyset\}$.

Our next task is to make an appropriate choice of the partitions $\mathbb{Z}_M = \tilde{B}_{A,x,y}^{-} \cup \tilde{B}_{A,x,y}^{+}$ and $\mathbb{Z}_M = \hat{B}_{A,x,y}^{-} \cup \hat{B}_{A,x,y}^{+}$ so that the Markov chain $(A_n)_{n \in \mathbb{Z}_+}$ ends up at the **full field** $A_\infty$, defined by

$$\forall x, y \in \mathbb{Z}_M, \quad A_\infty(x, y) = \mathbb{Z}_M$$

(note that this field is absorbing). A guiding principle behind such a choice should be that there is a chance to get a “big” field (measured through its thickness). It leads us to following choice:

$$\forall A \in \mathcal{A}, \forall x, y \in \mathbb{Z}_M, \quad \left\{ \begin{array}{l} \tilde{B}_{A,x,y}^{-} := A(x + 1, y) - y \\ \tilde{B}_{A,x,y}^{+} := \mathbb{Z}_M \setminus \tilde{B}_{A,x,y}^{-} \\ \hat{B}_{A,x,y}^{-} := A(x, y + 1) \\ \hat{B}_{A,x,y}^{+} := \mathbb{Z}_M \setminus \hat{B}_{A,x,y}^{-} \end{array} \right.$$

We get that for any $A \in \mathcal{A}$ and any $(x, y) \in \mathbb{Z}_M^2$,

$$\left\{ \begin{array}{l} \tilde{A}^{(1)}(x, y) := (A(x + 1, y) - y) \cup (A(x - 1, y) + y) \\ \tilde{A}^{(2)}(x, y) := (A(x + 1, y) - y) \cap (A(x - 1, y) + y) \\ \hat{A}^{(1)}(x, y) := A(x, y + 1) \cup A(x, y - 1) \\ \hat{A}^{(2)}(x, y) := A(x, y + 1) \cap A(x, y - 1) \end{array} \right. \qquad (4.5)$$
**Remark 4.1.** The fact that $\tilde{A}^{(1)}(x, y)$ (respectively $\hat{A}^{(1)}(x, y)$) is the biggest possible has to be compensated by the fact $\tilde{A}^{(2)}(x, y)$ (resp. $\hat{A}^{(2)}(x, y)$) is the smallest possible. But we should not worry so much about this feature, as $\mathfrak{Q}$ promotes bigger fields.

Let us check that this choice of dual process goes in the direction of our purposes.

**Proposition 4.2.** The Markov kernel $\mathfrak{Q}$ associated to (4.5) admits only one recurrence class which is $\{A_\infty\}$, i.e. the Markov chain $(A_n)_{n\in\mathbb{Z}_+}$ ends up being absorbed in finite time at the full field.

*Proof.* Let be given any $A_0 \in A\setminus\{\emptyset, A_\infty\}$. It is sufficient to find a finite sequence $(A_l)_{l\in\mathbb{L}}$ with $L \in \mathbb{N}$, $A_L = A_\infty$ and

$$ \forall l \in [0, L-1], \quad \mathfrak{Q}(A_l, A_{l+1}) > 0 $$

Here is a construction of such a sequence, in two times. First we get a field whose fibers are all non-empty and next we obtain the full field. Denote $\tilde{T}$ (respectively $\hat{T}$) the mapping on fields corresponding to the transition $A \mapsto \tilde{A}^{(1)}$ (resp. $A \mapsto \hat{A}^{(1)}$).

*First step.* Since $A_0$ is not empty, there exists $x_0, y_0 \in \mathbb{Z}_M^2$ such that $A_0(x_0, y_0) \neq \emptyset$. For any $n \in [0, [M/2]]$, denote

$$ \mathcal{V}_n := \{y \in \mathbb{Z}_M : \hat{T}^n[A](x_0, y) \neq \emptyset\} $$

Note that $y_0 \in \mathcal{V}_0$ and that next

$$ \begin{aligned} \{y_0 - 1, y_0 + 1\} &\subset \mathcal{V}_1 \\ \{y_0 - 2, y_0 - 1, y_0, y_0 + 1, y_0 + 2\} &\subset \mathcal{V}_2 \\ \{y_0 - 3, y_0 - 2, y_0 - 1, y_0, y_0 + 1, y_0 + 2, y_0 + 3\} &\subset \mathcal{V}_3 \\ &\vdots \\ \mathbb{Z}_M &= \mathcal{V}_{[M/2]} \end{aligned} $$

Next, for any $n \in [[M/2] + 1, 2[M/2]]$, denote

$$ \mathcal{V}_n := \{x \in \mathbb{Z}_M : \forall x \in \mathbb{Z}_M, \tilde{T}^n[\hat{T}^{[M/2]}](x, y) \neq \emptyset\} $$

From the above argument, we have $x_0 \in \mathcal{V}_{[M/2]}$ and we deduce

$$ \begin{aligned} \{x_0 - 1, x_0 + 1\} &\subset \mathcal{V}_{[M/2]+1} \\ \{x_0 - 2, x_0 - 1, x_0, x_0 + 1, x_0 + 2\} &\subset \mathcal{V}_{[M/2]+2} \\ \{x_0 - 3, x_0 - 2, x_0 - 1, x_0, x_0 + 1, x_0 + 2, x_0 + 3\} &\subset \mathcal{V}_{[M/2]+3} \\ &\vdots \\ \mathbb{Z}_M &= \mathcal{V}_{2[M/2]} \end{aligned} $$

thus showing that all the fibers of $\tilde{T}^{[M/2]}[\hat{T}^{[M/2]}]$ are non empty.

*Second step.* In view of the previous step, we assume now that all the fibers of $A_0$ are non-empty. We begin by constructing $A_1, A_2, A_3$ and $A_4$ by successively applying $\tilde{T}, \hat{T}, \tilde{T}$ and $\hat{T}$. Fix $(x, y) \in \mathbb{Z}_M^2$ as well as $z \in A_0(x, y)$. Applying $\tilde{T}$, we get that $z + y \in A_1(x + 1, y)$ and $z - y \in A_1(x - 1, y)$. Applying $\hat{T}$, we have that $z + y \in A_2(x + 1, y + 1)$ and $z - y \in A_2(x - 1, y + 1)$. Next $\tilde{T}$ insures that $z - 1 = z + y - (y + 1) \in A_3(x, y + 1)$
and $z + 1 = z - y + (y + 1) \in A_3(x, y + 1)$. Finally, under $\hat{T}$, we get that $z - 1 \in A_4(x, y)$ and $z + 1 \in A_4(x, y)$. Successively applying again $\hat{T}$, $\hat{T}$, $\hat{T}$ and $\hat{T}$, we construct $A_5$, $A_6$, $A_7$ and $A_8$. By the above considerations, we deduce that $z - 2$, $z$ and $z + 2$ belong to $A_8(x, y)$. Let us successively apply $M - 3$ more times $\hat{T}$, $\hat{T}$, $\hat{T}$ and $\hat{T}$, to get $A_9$, ..., $A_{4(M-1)}$. It appears that $A_{4(M-1)}(x, y)$ contains $z - M + 1$, $z - M + 3$, ..., $z + M - 3$, $z + M - 1$. Due to the fact that $M$ is odd, the latter set is just $\mathbb{Z}_M$. Thus we get that for any $(x, y) \in \mathbb{Z}_M^2$, $A_{4(M-1)}(x, y) = \mathbb{Z}_M$, namely $A_{4(M-1)} = A_\infty$. It provides the desired finite sequence with $L = 4(M - 1)$. $\square$

**Remark 4.3.** The successive applications of $\tilde{T}$, $\hat{T}$, $\tilde{T}$ and $\hat{T}$ is not without recalling the construction of the bracket of two vector fields in differential geometry. The latter is used to investigate hypo-ellipticity, see for instance the book of Hörmander [12], the continuous Heisenberg group being a famous instance. Our objective of showing that the full space is covered by the dual process is a discrete analogue of the property of hypoelliptic diffusions to admit a positive density at any positive time (see also [16] for another link between hypoellipticity and intertwining dual processes).

From the above results, we can construct a strong stationary time for the random walk on $\mathbb{H}_M$. Consider $\tau$ the hitting time of the full field. From [17], we get that $\tau$ has the law of a strong stationary time for the random walk on $\mathbb{H}_M$. This ends the qualitative construction of a strong stationary time. To go quantitative, the hitting time $\tau$ has to be investigated more thoroughly. More precisely, our goal is to prove Theorem 1.1.

Fix $A \in A\setminus\emptyset$ for the two following results.

**Lemma 4.4.** We have

$$ (|\tilde{A}^{(1)}| = |A| = |\hat{A}^{(1)}|) \Rightarrow A = A_{\infty} $$

*Proof.* So let us assume that

$$ |\tilde{A}^{(1)}| = |A| = |\hat{A}^{(1)}| \quad (4.6) $$

For any $(x, y) \in \mathbb{Z}_M^2$, we have

$$ \begin{aligned} |\tilde{A}^{(1)}(x, y)| &= \left| (A(x + 1, y) - y) \cup (A(x - 1, y) + y) \right| \\ &\geq |A(x + 1, y) - y| \\ &= |A(x + 1, y)| \end{aligned} $$

and we get

$$ \begin{aligned} |\tilde{A}^{(1)}| &\geq \sum_{(x,y) \in \mathbb{Z}_M^2} |A(x+1,y)| \\ &= \sum_{(x,y) \in \mathbb{Z}_M^2} |A(x,y)| \\ &= |A| \end{aligned} $$

Due to (4.6), the previous inequality must be an equality, and we deduce that

$$ \forall (x, y) \in \mathbb{Z}_M^2, \quad \left| (A(x + 1, y) - y) \cup (A(x - 1, y) + y) \right| = |A(x + 1, y) - y| $$
namely

$$ \forall (x, y) \in \mathbb{Z}_M^2, \quad (A(x+1, y) - y) \cup (A(x-1, y) + y) = A(x+1, y) - y $$

Similarly, we get

$$ \forall (x, y) \in \mathbb{Z}_M^2, \quad (A(x+1, y) - y) \cup (A(x-1, y) + y) = A(x-1, y) + y $$

so that

$$ \forall (x, y) \in \mathbb{Z}_M^2, \quad A(x+1, y) - y = A(x-1, y) + y \qquad (4.7) $$

The same reasoning with $\hat{A}^{(1)}$ instead of $\tilde{A}^{(1)}$, leads us to

$$ \forall (x, y) \in \mathbb{Z}_M^2, \quad A(x, y+1) = A(x, y-1) $$

or equivalently

$$ \forall (x, y) \in \mathbb{Z}_M^2, \quad A(x, y+2) = A(x, y) $$

Since $M$ is odd, the mapping $\mathbb{Z}_M \ni y \mapsto y+2$ has only one orbit, which by consequence covers $\mathbb{Z}_M$. It follows that for any fixed $x \in \mathbb{Z}_M$, the set $A(x, y)$ does not depend on $y$, let us call it $A(x)$. Coming back to (4.7), we get

$$ \forall (x, y) \in \mathbb{Z}_M^2, \quad A(x+2) = A(x) + 2y $$

Since any element $z \in \mathbb{Z}_M$ can be written under the form $2y$ for some $y \in \mathbb{Z}_M$, we deduce

$$ \forall (x, z) \in \mathbb{Z}_M^2, \quad A(x+2) = A(x) + z $$

Iterating $M$ times this relation in $x$, we obtain

$$ \forall (x, z) \in \mathbb{Z}_M^2, \quad A(x) = A(x) + z $$

and this relations implies that $A(x) = \mathbb{Z}_M$. This amounts to say that for any $(x, y) \in \mathbb{Z}_M$, $A(x, y) = \mathbb{Z}_M$, namely $A = A_\infty$. $\square$

Here is a quantitative version of the previous lemma:

**Corollary 4.5.** When $A \neq A_\infty$, then either

$$ |\tilde{A}^{(1)}| \geq |A| + 1 \quad \text{or} \quad |\hat{A}^{(1)}| \geq |A| + 1 $$

*Proof.* When $A \neq A_\infty$, then either $|\tilde{A}^{(1)}| > |A|$ or $|\hat{A}^{(1)}| > |A|$, since the proof of Lemma 4.4 shows that we always have $|\tilde{A}^{(1)}| \geq |A|$ and $|\hat{A}^{(1)}| \geq |A|$, and that $|\tilde{A}^{(1)}| = |A| = |\hat{A}^{(1)}|$ implies that $A = A_\infty$. It remains to take into account that thicknesses are integer numbers. $\square$

Define the stochastic chain $R := (R_n)_{n \in \mathbb{Z}_+}$ via

$$ \forall n \in \mathbb{Z}_+, \quad R_n := |A_n| $$
The following result is the crucial element in the proof of Theorem 1.1:

**Lemma 4.6.** We have

$$ \forall n \in \mathbb{Z}_+, \quad \mathbb{E}[R_{n+1}|\mathcal{A}_n] \ge R_n + \frac{1}{6R_n} \quad \text{on } \{\tau > n\} $$

(where the filtration $(\mathcal{A}_n)_{n \in \mathbb{Z}_+}$ is generated by $(A_n)_{n \in \mathbb{Z}_+}$).

*Proof.* By the Markov property, for any $n \in \mathbb{Z}_+$, we have $\mathbb{E}[R_{n+1}|\mathcal{A}_n] = \mathbb{E}[R_{n+1}|A_n]$. Furthermore, for any $A \in \mathbb{A}\setminus\{\emptyset\}$, we have

$$ \begin{aligned} \mathbb{E}[R_{n+1}|A_n = A] &= \sum_{A' \in \mathbb{A} \setminus \{\emptyset\}} \mathfrak{Q}(A, A')|A'| \\ &= \frac{1}{|A|} \sum_{A' \in \mathbb{A}} \mathfrak{R}(A, A')|A'|^2 \end{aligned} \quad (4.8) $$

where $\mathfrak{R}$ is the kernel on $\mathbb{A}$ defined by

$$ \mathfrak{R}(A, A') := \frac{1}{6} \mathbb{1}_{\tilde{A}^{(1)}}(A') + \frac{1}{6} \mathbb{1}_{\tilde{A}^{(1)}}(A') + \frac{1}{6} \mathbb{1}_{\tilde{A}^{(2)}}(A') + \frac{1}{6} \mathbb{1}_{\tilde{A}^{(2)}}(A') + \frac{1}{3} \mathbb{1}_{A}(A') $$

Recall that

$$ \forall A \in \mathbb{A} \setminus \{\emptyset\}, \quad \sum_{A' \in \mathbb{A}} \mathfrak{R}(A, A') |A'| = |A| \quad (4.9) $$

as a consequence of the Markovianity of $\mathfrak{Q}$. We deduce that

$$ \begin{aligned} \mathbb{E}[R_{n+1}|A_n = A] - |A| &= \frac{1}{|A|} \left( \sum_{A' \in \mathbb{A}} \mathfrak{R}(A, A') |A'|^2 - |A|^2 \right) \\ &= \frac{1}{|A|} \left( \sum_{A' \in \mathbb{A}} \mathfrak{R}(A, A') |A'|^2 - \left( \sum_{A'' \in \mathbb{A}} \mathfrak{R}(A, A'') |A''| \right)^2 \right) \\ &= \frac{1}{|A|} \sum_{A' \in \mathbb{A}} \mathfrak{R}(A, A') (|A'| - |A|)^2 \end{aligned} $$

Assume now that $A \neq A_\infty$. With the above notation, it means that $A_n \neq A_\infty$, i.e. $\tau > n$. According to Corollary 4.5, either $|\tilde{A}^{(1)}| \ge |A| + 1$ or $|\tilde{A}^{(1)}| \ge |A| + 1$. Whatever the case, we deduce that

$$ \sum_{A' \in \mathbb{A}} \mathfrak{R}(A, A') (|A'| - |A|)^2 \ge \frac{1}{6} $$

and the desired bound follows.

<figure><img src="image_2.png" /></figure>

The next result goes in the direction of Theorem 1.1, by proving in a weak sense that $\tau$ is of order $M^6$.

**Proposition 4.7.** We have

$$ \mathbb{E}[\tau] \le 6M^6 $$
*Proof.* According to Lemma 4.6, the stochastic chain $(R_{\tau \wedge n} - \frac{1}{6M^3}(\tau \wedge n))_{n \in \mathbb{Z}_+}$ is a submartingale. It follows that

$$ \forall n \in \mathbb{Z}_+, \quad \mathbb{E}[R_{\tau \wedge n}] \geq \frac{1}{6M^3} \mathbb{E}[\tau \wedge n] $$

Letting $n$ go to infinity, we get, by dominated convergence in the l.h.s. and by monotone convergence in the r.h.s.,

$$ \mathbb{E}[R_{\tau}] \geq \frac{1}{6M^3} \mathbb{E}[\tau] $$

To conclude to the desired bound, note that

$$ \begin{aligned} \mathbb{E}[R_{\tau}] &= |A_{\infty}| \\ &= M^3 \end{aligned} $$

□

We can now come to the

*Proof of Theorem 1.1.* Traditional Markov arguments enable to strengthen the weak estimate of Proposition 4.7 into a stronger one about the tail probabilities of $\tau$. More precisely the previous computations did not take into account that the Markov chain $(A_n)_{n \in \mathbb{Z}_+}$ starts from a particular non-empty field $A_0$. In fact they are valid for any initial field $A_0 \neq \emptyset$. So whatever $A_0 \neq \emptyset$, we have

$$ \begin{aligned} \mathbb{P}[\tau \geq 6eM^6] &\leq \frac{\mathbb{E}[\tau]}{6eM^6} \\ &\leq \frac{1}{e} \end{aligned} $$

By the Markov property we deduce

$$ \forall n \in \mathbb{Z}_+, \quad \mathbb{P}[\tau \geq 6eM^6] \leq e^{-n} $$

For any $r \geq 0$, writing

$$ r \geq \left\lfloor \frac{r}{6eM^6} \right\rfloor 6eM^6 $$

(where $\lfloor \cdot \rfloor$ stands for the integer part), we get

$$ \begin{aligned} \mathbb{P}[\tau \geq r] &\leq \mathbb{P}\left[\tau > \left\lfloor \frac{r}{6eM^6} \right\rfloor 6eM^6\right] \\ &\leq \exp\left(-\left\lfloor \frac{r}{6eM^6} \right\rfloor\right) \\ &\leq e \exp\left(-\frac{r}{6eM^6}\right) \\ &\leq 3 \exp\left(-\frac{r}{17M^6}\right) \end{aligned} $$

□
**Remark 4.8.** (a) Lemma 4.6 cannot be essentially improved under its present form, because it is almost an equality when $A_n$ is very close to $A_x$. Away from the latter end, there is a lot of room for improvements. Nevertheless, it will not be really helpful, since we think that much of the time needed by $R$ to go from 1 to $M^3$ is the time required to go from, say $M^3/2$, to $M^3$. For a field $A$ such that $M^3/2 \le |A| \le M^3$, it is likely that the conditional variance

$$ \mathbb{E}[(R_{n+1} - R_n)^2 | A_n = A] = \frac{1}{|A|} \sum_{A' \in A} \mathfrak{Q}(A, A')(|A'| - |A|)^2 $$

is of order 1. Thus the evolution of $R$ could be compared to that of a diffusion $\rho := (\rho_t)_{t \ge 0}$ solution of the stochastic differential equation

$$ d\rho_t = cd\beta_t + \frac{c'}{\rho_t}dt $$

where $c, c'$ are two positive constants and $\beta := (\beta_t)_{t \ge 0}$ is a Brownian motion. It appears that $\rho$ is a Bessel process (up to a linear time change). Taking into account its scaling property, it takes a time of order $M^6$ for $\rho$ to go from $M^3/2$ to $M^3$.

(b) In view of the above observation, it seems hopeless to get a bound on $\tau$ of order $M^2$ up to logarithmic corrections, which is the kind of results we are looking for. We believe that only working with the thickness is not sufficient for this purpose, as there is more structure than just the size in this problem. This is illustrated by the proof of Lemma 4.4, where the translations of the fibers of the field $A$ induced by $\tilde{A}^{(1)}$ played an important role for the “diversification” of the fibers. But this feature is lost in Corollary 4.5 and Lemma 4.6, where only the size is taken into account. Better estimates in Theorem 1.1 (and by consequence in Theorem 1.2 and Theorem 1.3, whose proofs will follow the same pattern) would require to investigate more carefully this point.

(c) If we are only interested in the speed of convergence to equilibrium of the component $Z$, we should introduce another hitting time $\hat{\tau}$. More precisely, to any field $A \in A \setminus \{\emptyset\}$, associate the probability distribution $\eta_A$ of $z$ when $[x, y, z]$ is sampled uniformly on $\Omega_A$. It is given by

$$ \forall z \in \mathbb{Z}_M, \quad \eta_A(z) := \frac{1}{|A|} \sum_{x,y \in \mathbb{Z}_M} \mathbb{1}_{A(x,y)}(z) $$

Let $\mathfrak{B}$ be the set of $A \in A \setminus \{\emptyset\}$ such that $\eta_A$ is equal to the uniform distribution on $\mathbb{Z}_M$. Note that the full field belongs to $\mathfrak{B}$. Define $\hat{\tau}$ as the hitting time of $\mathfrak{B}$. The interest of $\hat{\tau}$ is that $Z_{\hat{\tau}}$ is uniformly distributed (and independent from $\hat{\tau}$, as seen via the classical arguments of Diaconis and Fill [7]). We conjecture that $\hat{\tau}$ is of order $M$, the simulations of Chhaibi [6] suggesting it is at most of order $M^{1.5}$. In particular, it would justify that $Z$ goes to equilibrium much faster than $(X, Y)$ in the separation sense.

## 5. A REDUCED STRONG STATIONARY TIME

In this section, we indicate the changes in the above arguments needed to prove Theorem 1.2. It will give us the opportunity to give a broad view of the whole approach by revisiting it.

First note that $(Y, Z)$ is indeed a Markov chain, whose state space is $\mathbb{Z}_M^2$ and whose generic elements will be denoted $[y, z]$. The associated transition matrix $P$ is given by

$$ \forall [y, z], [y', z'] \in \mathbb{Z}_M^2, \quad P([y, z], [y', z']) = \begin{cases} 1/6, & \text{if } [y', z'] \in \{[y \pm 1, z], [y, z \pm y]\} \\ 1/3, & \text{if } [y', z'] = [y, z] \\ 0, & \text{otherwise} \end{cases} $$
and the corresponding reversible probability is the uniform distribution on $Z_M^2$. To construct a corresponding set-valued intertwining dual $\mathcal{X}$ as in [17], we are to specify a set $\mathfrak{V}$ of non-empty subsets of $Z_M^2$ and a family of random mappings $(\psi_\Omega)_{\Omega \in \mathfrak{V}}$ compatible with $P$, namely satisfying the weak association and stability conditions recalled in Section 2. Every subset $\Omega \subset Z_M^2$ is uniquely determined by a field $A := (A(y))_{y \in \mathbb{Z}_M}$ of subsets of $Z_M$ such that

$$[y, z] \in \Omega \Leftrightarrow z \in A(y)$$

Denote $\mathbb{A}$ the set of such fields. Given $A := (A(y))_{y \in \mathbb{Z}_M} \in \mathbb{A}$, the corresponding subset of $Z_M^2$ is

$$\Omega_A = \{[y, z] \in \mathbb{Z}_M^2 : z \in A(y)\}$$

In the sequel, we identify $\Omega = \Omega_A$ with $A$ and $\mathfrak{V}$ with $A\setminus\{\emptyset\}$, where $\emptyset$ is the field corresponding to the empty subset of $Z_M^2$. For any given $A \in \mathbb{A}$, the description of the random mapping $\psi_A$ follows the pattern given in Section 4. More precisely, it corresponds to forgetting the $x$-component there. Thus we consider the following sign functions

$$\forall [y, z] \in \mathbb{Z}_M^2, \quad \tilde{\varphi}_A(y, z) := \begin{cases} -1, & \text{if } z \in A(y) - y \\ 1, & \text{if } z \notin A(y) - y \end{cases}$$

$$\forall [y, z] \in \mathbb{Z}_M^2, \quad \hat{\varphi}_A(y, z) := \begin{cases} -1, & \text{if } z \in A(y+1) \\ 1, & \text{if } z \notin A(y+1) \end{cases}$$

as well as the corresponding mappings acting on $Z_M^2$

$$\forall [y, z] \in \mathbb{Z}_M^2, \quad \tilde{\phi}_A^-([y, z]) := [y, z - \tilde{\varphi}_A(y, z)y]$$

$$\forall [y, z] \in \mathbb{Z}_M^2, \quad \tilde{\phi}_A^+([y, z]) := [y, z + \tilde{\varphi}_A(y, z)y]$$

$$\forall [y, z] \in \mathbb{Z}_M^2, \quad \hat{\phi}_A^-([y, z]) := [y - \hat{\varphi}_A(y, z), z]$$

$$\forall [y, z] \in \mathbb{Z}_M^2, \quad \hat{\phi}_A^+([y, z]) := [y + \hat{\varphi}_A(y, z), z]$$

The random mapping $\psi_A$ takes each of the $\tilde{\phi}_A^-, \tilde{\phi}_A^+, \hat{\phi}_A^-, \hat{\phi}_A^+$ with probability 1/6 and the identity mapping $\tilde{\phi}^{(0)}$ with the remaining probability 1/3. As in Section 4, we check that $\psi_A$ is weakly associated to $P$, with $\xi(A) = 1$. It is also stable, since $\mathbb{A}$ corresponds to the whole set from subsets of $Z_M^2$. Furthermore, we have $(\tilde{\phi}_A^-)^{-1}(A) = \tilde{A}^-, (\tilde{\phi}_A^+)^{-1}(A) = \tilde{A}^+, (\hat{\phi}_A^-)^{-1}(A) = \hat{A}^-$ and $(\hat{\phi}_A^+)^{-1}(A) = \hat{A}^+$, where by definition

$$\forall y \in \mathbb{Z}_M, \quad \left\{ \begin{array}{l} \tilde{A}^-(y) := (A(y) - y) \cup (A(y) + y) \\ \tilde{A}^+(y) := (A(y) - y) \cap (A(y) + y) \\ \hat{A}^-(y) := A(y+1) \cup A(y-1) \\ \hat{A}^+(y) := A(y+1) \cap A(y-1) \end{array} \right.$$

From the family of random mappings $(\psi_A)_{A \in \mathbb{A}}$, construct the field-valued dual $A := (A(n))_{n \in \mathbb{Z}_+}$, as in [17]. Its transition kernel $\mathfrak{Q}$ is given, for any fields $A, A'$ by

$$\mathfrak{Q}(A, A') := \frac{|A'|}{|A|} \left( \frac{1}{6} \mathbb{1}_{\tilde{A}^{-}}(A') + \frac{1}{6} \mathbb{1}_{\tilde{A}^{+}}(A') + \frac{1}{6} \mathbb{1}_{\hat{A}^{-}}(A') + \frac{1}{6} \mathbb{1}_{\hat{A}^{+}}(A') + \frac{1}{3} \mathbb{1}_{A}(A') \right)$$
where for any field $A$, the **thickness** of $A$ is defined by

$$|A| := \sum_{y \in \mathbb{Z}_M} |A(y)|$$

Consider the **full field** $A_\infty := (\mathbb{Z}_M)_{y \in \mathbb{Z}_M}$ and the associated hitting time

$$\tilde{\tau} := \inf\{n \in \mathbb{Z}_+ : A(n) = A_\infty\}$$

According to the general intertwining theory of Diaconis and Fill [7], the absorption time $\tilde{\tau}$ has the same law as a strong stationary time for $(Y, Z)$. It remains to investigate the tail probabilities of $\tilde{\tau}$ to prove Theorem 1.2. Our first task is to check that $\mathcal{Q}$ leads to the a.s. absorption at $A_\infty$ from any starting field. In this direction the proof of Lemma 4.4 is still valid and even simpler: it is sufficient to remove the first component $x$ in the fields. It follows that for any field $A$,

$$(|\tilde{A}^-| = |A| = |\hat{A}^-|) \Rightarrow A = A_\infty$$

As a consequence, Corollary 4.5 and Lemma 4.6 provide exactly the same estimates: When $A \neq A_\infty$, then either

$$|\tilde{A}^-| \geq |A| + 1 \text{ or } |\hat{A}^-| \geq |A| + 1$$

and

$$\forall n < \tilde{\tau}, \quad \begin{aligned} \mathbb{E}[R_{n+1}|A_n] &\geq R_n + \frac{1}{6R_n} \\ &\geq R_n + \frac{1}{6M^2} \end{aligned}$$

where

$$\forall n \in \mathbb{Z}_+, \quad R_n := |A_n|$$

and where the filtration $(A_n)_{n \in \mathbb{Z}_+}$ is generated by $(A_n)_{n \in \mathbb{Z}_+}$. Since $|A_\infty| = M^2$ instead of $M^3$, we get as in Proposition 4.7,

$$\mathbb{E}[\tilde{\tau}] \leq 6M^4$$

The proof of Theorem 1.1 can then be transposed to show Theorem 1.2.

**Remark 5.1.** Coming back to the whole finite Heisenberg Markov chain $[X, Y, Z]$, we could think that after the strong stationary time $\tau$ defined above, $[X, Y, Z]$ will reach equilibrium after a new strong stationary time of order $M^2$. This is not clear from our approach, since at time $\tau$ we don't know how $X$ and $(Y, Z)$ are linked.

# 6. EXTENSION TO HIGHER DIMENSIONAL HEISENBERG WALKS

Here we explain how the constructions of the two previous sections can be extended to deal with higher dimensional Heisenberg random walks. The goal is to prove Theorem 1.3 (in fact directly the extension mentioned after its statement, see Theorem 6.3 below) and Theorem 1.4.

The roadmap is the same as in the previous section. But now the state space of the (primal) Markov chains of interest consists of the set of the $b$th first above diagonals, for a fixed $b \in [2, N]$ (or their restrictions to the last column, i.e. its last $b$ entries, for Thm. 1.4). Since our goal is to construct a set-valued dual Markov chain,
we first need a convenient description of the subsets $\Omega$ of the state space of the primal Markov chain. Again we will resort to fields, which give the set (called fibers) of $(b+1)\text{th}$ above diagonals that can be concatenated to any prescribed $b$th first above diagonals (whose set is called the base space), to get an element of $\Omega$. Thus, the starting subset being a singleton, it corresponds to a field whose all fibers are empty, except one which is a singleton. The absorbing set is the whole state space of the primal Markov chain and corresponds to the field whose all fibers are the set of all possible $b$th diagonals. Next we consider mappings associated to the primal Markov chain which act in a clean way on the fields, by taking shifts, unions and intersections of neighboring fibers (two elements of the base are neighbors if they are transformed one into another by elementary moves of the primal Markov chain, namely the $F_{I,\epsilon}$ defined below for $I \in \llbracket N-1 \rrbracket$ and $\epsilon \in \{-1, 1\}$). These nice random mappings are obtained by optimally (respectively to the enlargement of fields) choosing joint signs for adding or subtracting rows (Lems. 6.1 and 6.2). This description allows to investigate the evolution of the size of the evolving subsets via a submartingale property (Lemma 6.6). A classical argument leads to the desired estimate on the time of absorption of the dual chain. The case of Theorem 1.3 corresponds to $b = N$. The investigations for the different $b$ are independent as no iteration is required, so the reader only interested in Theorem 1.3 can replace $b$ by $N$ in the following arguments.

More precisely, recall that in the introduction we associated to any $[x] := [x_{k,l}]_{1 \le k < l \le N} \in \mathbb{H}_{N,M}$ and to any $b \in \llbracket N-1 \rrbracket$, the $b$th upper diagonal $d_b[x] := (x_{k,k+b})_{k \in \llbracket N-b \rrbracket}$. Denote $\mathbb{D}_b$ the set of such elements, i.e.

$$ \mathbb{D}_b := \mathbb{Z}_M^{\{(k,k+b) : k \in \llbracket N-b \rrbracket\}} $$

We also write

$$ d_{\llbracket b \rrbracket}[x] := (d_k[x])_{k \in \llbracket b \rrbracket} \in \mathbb{D}_{\llbracket b \rrbracket} := \prod_{k \in \llbracket b \rrbracket} \mathbb{D}_k $$

Let $d_0$ be the usual diagonal consisting only of 1, when necessary, we will also see elements of $\mathbb{D}_{\llbracket b \rrbracket}$ as elements of $\prod_{k \in \llbracket 0, b \rrbracket} \mathbb{D}_k$, where $\mathbb{D}_0 = \{d_0\}$. Note that $\mathbb{D}_{\llbracket N-1 \rrbracket}$ identifies with $\mathbb{H}_{N,M}$. Similarly, for $b \in \llbracket N-1 \rrbracket$, we introduced after Theorem 1.3 the Markov chains $D_b := (D_b(n))_{n \in \mathbb{Z}_+} := (d_b[X_n])_{n \in \mathbb{Z}_+}$ and $D_{\llbracket b \rrbracket} := (D_{\llbracket b \rrbracket}(n))_{n \in \mathbb{Z}_+} := (d_{\llbracket b \rrbracket}[X_n])_{n \in \mathbb{Z}_+}$, respectively taking values in $\mathbb{D}_b$ and $\mathbb{D}_{\llbracket b \rrbracket}$. In particular, $D_{\llbracket N-1 \rrbracket}$ is the Markov chain $[X]$ on $\mathbb{H}_{N,M}$. Our goal here is to construct strong stationary times for these Markov chains, via set-valued dual processes. The case $b=1$ is simpler and will only be quickly treated in Lemma 6.8 below. Until then, we fix $b \in \llbracket 2, N-1 \rrbracket$. Again we apply the random mapping method described in [17] and recalled in the previous sections. So our main ingredients will be a set $\mathfrak{Y}_b$ of non-empty subsets of $\mathbb{D}_{\llbracket b \rrbracket}$, and for any $\Omega \in \mathfrak{Y}_b$, a random mapping $\psi_{\Omega} : \mathbb{D}_{\llbracket b \rrbracket} \to \mathbb{D}_{\llbracket b \rrbracket}$. The set $\mathfrak{Y}_b$ is very simple: it is the collection of all non-empty subsets of $\mathbb{D}_{\llbracket b \rrbracket}$. As in the last two sections, a subset $\Omega \subset \mathbb{D}_{\llbracket b \rrbracket}$ is described by a **field**, which is the family $A := (A(d_{\llbracket b-1 \rrbracket}))_{d_{\llbracket b-1 \rrbracket} \in \mathbb{D}_{\llbracket b-1 \rrbracket}}$ of subsets of $\mathbb{D}_b$, where

$$ d_{\llbracket b-1 \rrbracket}[x] \in \Omega \Leftrightarrow \forall d_{\llbracket b-1 \rrbracket} \in \mathbb{D}_{\llbracket b-1 \rrbracket}, d_b[x] \in A(d_{\llbracket b-1 \rrbracket}) \quad (6.1) $$

As before, the sets $A(d_{\llbracket b-1 \rrbracket})$, for $d_{\llbracket b-1 \rrbracket} \in \mathbb{D}_{\llbracket b-1 \rrbracket}$, are called the **fibers** of the field $A$. To simplify the already heavy notations, we will also write $[x] := [x_{k,l}]_{1 \le k < l \le k+b}$ for the elements of $\mathbb{D}_{\llbracket b \rrbracket}$, instead of $d_{\llbracket b \rrbracket}[x]$. To describe the random mappings $\psi_{\Omega}$, for $\Omega \in \mathfrak{Y}_b$, another notation is required. For $I \in \llbracket N-1 \rrbracket$ and $\epsilon \in \{\pm 1\}$, let $F_{I,\epsilon}$ be the mapping acting on $\mathbb{H}_{N,M}$ by adding (respectively subtracting) the $(I+1)^{\text{th}}$ row to the $I^{\text{th}}$ row, if $\epsilon = 1$ (resp. $\epsilon = -1$). We will also see $F_{I,\epsilon}$ as a mapping acting on the $\mathbb{D}_{\llbracket b \rrbracket}$, for $l \in \llbracket N-1 \rrbracket$ (and this is the only reason for the addition of the diagonal $d_0$ to $\mathbb{D}_{\llbracket b \rrbracket}$).

For fixed $\Omega \in \mathfrak{Y}_b$, $\psi_{\Omega}$ is defined as follows. The field corresponding to $\Omega$ is denoted $A := (A(d_{\llbracket b-1 \rrbracket}))_{d_{\llbracket b-1 \rrbracket} \in \mathbb{D}_{\llbracket b-1 \rrbracket}}$. Aside from the identity, the values of $\psi_{\Omega}$ are the $\phi_{\Omega,I,\epsilon}$, for $I \in \llbracket N-1 \rrbracket$ and $\epsilon \in \{\pm 1\}$, where

$$ \forall [x] \in \mathbb{D}_{\llbracket b \rrbracket}, \quad \phi_{\Omega,I,\epsilon}([x]) := F_{I,\epsilon\phi_A(I,[x])}([x]) $$
where $\varphi_A(I, [x]) \in \{-1, 1\}$ will be defined below. Each $\phi_{\Omega, I, \epsilon}$ will be chosen with probability $1/(3(N-1))$ and the identity with the remaining probability $1/3$. It remains to define the quantity $\varphi_A(I, [x])$. The index $I \in \llbracket N-1 \rrbracket$ is assumed to be fixed now. Let be given a family $(B_A(I, d_{\llbracket b-1 \rrbracket}))_{d_{\llbracket b-1 \rrbracket} \in \mathbb{D}_{\llbracket d-1 \rrbracket}}$ of subsets from $\mathbb{D}_b$, whose dependence on the field $A$ will be specified later on. Consider an element $[x] \in \mathbb{D}_{\llbracket b-1 \rrbracket}$, it can be naturally decomposed into $d_{\llbracket b-1 \rrbracket}[x] \in \mathbb{D}_{\llbracket d-1 \rrbracket}$ and $d_b[x] \in \mathbb{D}_b$. The quantity $\varphi_A(I, [x])$ has the form:

$$ \varphi_A(I, [x]) := \begin{cases} 1, & \text{if } d_b[x] \in B_A(I, d_{\llbracket b-1 \rrbracket}[x]) \\ -1, & \text{otherwise} \end{cases} $$

Since $\mathfrak{W}_b$ is the whole set of subsets of $\mathbb{D}_{\llbracket b \rrbracket}$, the stability property is automatically fulfilled. Let us investigate the action of the mappings $\phi_{\Omega, I, \epsilon}$, with $\Omega \in \mathfrak{W}_b$, $I \in \llbracket N-1 \rrbracket$ and $\epsilon \in \{-1, 1\}$. Here is a first case:

**Lemma 6.1.** For any $\Omega \in \mathfrak{W}_b$ and any $I \in \llbracket N-1 \rrbracket$, $\Omega' := \phi_{\Omega, I, 1}^{-1}(\Omega)$ is described by the field $A' := (A'(d_{\llbracket b-1 \rrbracket}))_{d_{\llbracket b-1 \rrbracket} \in \mathbb{D}_{\llbracket b-1 \rrbracket}}$ whose fibers are given by

$$ \forall d_{\llbracket b-1 \rrbracket} \in \mathbb{D}_{\llbracket b-1 \rrbracket}, \quad A'(d_{\llbracket b-1 \rrbracket}) = ([A(F_{I,1}(d_{\llbracket b-1 \rrbracket})) - \theta_I[d_{b-1}]] \cap B_A(I, d_{\llbracket b-1 \rrbracket})) \cup ([A(F_{I,-1}(d_{\llbracket b-1 \rrbracket})) + \theta_I[d_{b-1}]] \cap B_A(I, d_{\llbracket b-1 \rrbracket})^c) $$

where $\theta_I[d_{b-1}]$ is the element of $\mathbb{D}_b$ whose coordinates vanish, except the $I^{\text{th}}$ one, which is equal to the $(I+1)^{\text{th}}$ coordinate of $d_{b-1}$ (with the convention that $\theta_I[d_{b-1}] = 0$ if this coordinate does not exist, i.e. $I+1 > N-b+1$).

*Proof.* An element $[x'] \in \mathbb{D}_{\llbracket b \rrbracket}$ belongs to $\Omega'$ if and only if there exists $[x] \in \Omega$ such that $\phi_{\Omega, I, 1}([x']) = [x]$. Namely, $[x]$ being defined by

$$ \forall 1 \le k < l \le k+b, \quad x_{k,l} = \begin{cases} x'_{k,l} + \varphi_A(I, [x']) x'_{k+1,l}, & \text{if } k = I \\ x'_{k,l}, & \text{otherwise} \end{cases} \qquad (6.2) $$

must satisfy (6.1). Note that (6.2) can be written in terms of the upper diagonals:

$$ \forall l \in \llbracket b \rrbracket, \quad d_l[x] = d_l[x'] + \varphi_A(I, [x']) \theta_I[d_{l-1}[x')] \qquad (6.3) $$

We distinguish two cases.

* If $d_b[x'] \in B_A(I, d_{\llbracket b-1 \rrbracket}[x'])$, then (6.3) implies

$$ d_b[x] = d_b[x'] + \theta_I[d_{b-1}[x')] $$

Taking into account that

$$ d_{\llbracket b-1 \rrbracket}[x] = F_{I, \varphi_A(I, [x'])}(d_{\llbracket b-1 \rrbracket}[x']) = F_{I, 1}(d_{\llbracket b-1 \rrbracket}[x']) $$

the condition $d_b[x] \in A(d_{\llbracket b-1 \rrbracket}[x])$ translates into

$$ d_b[x'] \in A(F_{I,1}(d_{\llbracket b-1 \rrbracket}[x])) - \theta_I[d_{b-1}[x')] $$

and we get

$$ d_b[x'] \in (A(F_{I,1}(d_{\llbracket b-1 \rrbracket}[x']) - \theta_I[d_{b-1}[x']]) \cap B_A(I, d_{\llbracket b-1 \rrbracket}[x']) $$
Conversely, this inclusion implies $d_b[x] \in A(d_{\llbracket b-1 \rrbracket}[x])$, since the above arguments can be reversed. • If $d_b[x'] \notin B_A(I, d_{\llbracket b-1 \rrbracket}[x'])$, then similar considerations lead to the equivalence of $d_b[x] \in A(d_{\llbracket b-1 \rrbracket}[x])$ with

$$d_b[x'] \in (A(F_{I,-1}(d_{\llbracket b-1 \rrbracket}[x'])) + \theta_I[d_{b-1}[x']]) \cap B_A(I, d_{\llbracket b-1 \rrbracket}[x'])^c$$

It follows that we can take $A'(d_{\llbracket b-1 \rrbracket})$ equal to

$$([A(F_{I,1}(d_{\llbracket b-1 \rrbracket})) - \theta_I[d_{b-1}]] \cap B_A(I, d_{\llbracket b-1 \rrbracket})) \cup ([A(F_{I,-1}(d_{\llbracket b-1 \rrbracket})) + \theta_I[d_{b-1}]] \cap B_A(I, d_{\llbracket b-1 \rrbracket})^c)$$

□

Similar arguments, or replacing the sets $B_A(I, d_{\llbracket b-1 \rrbracket})$ by their complementary sets, leads to

**Lemma 6.2.** For any $\Omega \in \mathfrak{M}_b$ and any $I \in [N-1]$, $\Omega' := \phi_{\Omega,I,-1}^{-1}(\Omega)$ is described by the field $A' := (A'(d_{\llbracket b-1 \rrbracket}))_{d_{\llbracket b-1 \rrbracket} \in \mathbb{D}_{\llbracket b-1 \rrbracket}}$ whose fibers are given by

$$\forall d_{\llbracket b-1 \rrbracket} \in \mathbb{D}_{\llbracket b-1 \rrbracket}, \quad A'(d_{\llbracket b-1 \rrbracket}) = ([A(F_{I,-1}(d_{\llbracket b-1 \rrbracket})) + \theta_I[d_{b-1}]] \cap B_A(I, d_{\llbracket b-1 \rrbracket})) \cup ([A(F_{I,1}(d_{\llbracket b-1 \rrbracket})) - \theta_I[d_{b-1}]] \cap B_A(I, d_{\llbracket b-1 \rrbracket})^c)$$

Due to the guideline recalled in Remark 4.1, we are lead to choose

$$\forall I \in [N-1], \forall d_{\llbracket b-1 \rrbracket} \in \mathbb{D}_{\llbracket b-1 \rrbracket}, \quad B_A(I, d_{\llbracket b-1 \rrbracket}) := A(F_{I,1}(d_{\llbracket b-1 \rrbracket})) - \theta_I[d_{b-1}] \quad (6.4)$$

It follows from Lemma 6.1, that the fibers of $\Omega' := \phi_{\Omega,I,1}^{-1}(\Omega)$ are given by

$$\forall d_{\llbracket b-1 \rrbracket} \in \mathbb{D}_{\llbracket b-1 \rrbracket}, \quad A'(d_{\llbracket b-1 \rrbracket}) = (A(F_{I,1}(d_{\llbracket b-1 \rrbracket})) - \theta_I[d_{b-1}]) \cup (A(F_{I,-1}(d_{\llbracket b-1 \rrbracket})) + \theta_I[d_{b-1}])$$

From Lemma 6.2, we deduce that the fibers of $\Omega' := \phi_{\Omega,I,-1}^{-1}(\Omega)$ are given by

$$\forall d_{\llbracket b-1 \rrbracket} \in \mathbb{D}_{\llbracket b-1 \rrbracket}, \quad A'(d_{\llbracket b-1 \rrbracket}) = (A(F_{I,1}(d_{\llbracket b-1 \rrbracket})) - \theta_I[d_{b-1}]) \cap (A(F_{I,-1}(d_{\llbracket b-1 \rrbracket})) + \theta_I[d_{b-1}])$$

As in the two previous sections, we identify a subset with its field. Denote $A_{b,\infty}$ the field whose fibers are all equal to $\mathbb{D}_b$, equivalently, it corresponds to $\Omega = \mathbb{D}_{\llbracket b \rrbracket}$. Denote $\mathcal{X}_b$ the subset valued Markov chain associated to the random mappings $(\psi_{\Omega})_{\Omega \in \mathfrak{M}_b}$. It is clear from Lemmas 6.1 and 6.2 that $\mathcal{X}_b$ is absorbed at $A_{b,\infty}$. Define

$$t_b = \inf\{n \in \mathbb{Z}_+ : \mathcal{X}_b(n) = A_{b,\infty}\}$$

In particular, $t_b$ has the same law as a strong stationary time for $D_{\llbracket b \rrbracket}$ according to [17]. It is the $\tau$ of Theorem 1.3 when $b = N-1$. Here is the extension of Theorem 1.3 mentioned in the introduction.

**Theorem 6.3.** For $b \in [2, N-1]$ and $M$ odd and large enough (uniformly in $b$ and $N$), we have

$$\forall r \ge 0, \quad \mathbb{P}[t_b \ge r] \le 3 \exp \left( - \frac{2r}{17(N-1)M^{b(2N-b-1)}} \right)$$

As in Section 4, this result is to be proven by getting an estimate on the tendency of $\mathcal{X}_b(n)$ to grow. With this respect, introduce for any field $A$, the quantity

$$|A| := \sum_{d_{\llbracket b-1 \rrbracket} \in \mathbb{D}_{\llbracket b-1 \rrbracket}} |A(d_{\llbracket b-1 \rrbracket})| \quad (6.5)$$
where in the r.h.s. $|\cdot|$ corresponds to the cardinality. We have again $|A| = |\Omega|$, when A corresponds to $\Omega$. To any field $A := (A(d_{\llbracket b-1 \rrbracket}))_{d_{\llbracket b-1 \rrbracket} \in \mathbb{D}_{\llbracket b-1 \rrbracket}}$ of subsets of $\mathbb{D}_b$ and to any $I \in [N-1]$, associate the new fields $A^{\cup,I} := (A^{\cup,I}(d_{\llbracket b-1 \rrbracket}))_{d_{\llbracket b-1 \rrbracket} \in \mathbb{D}_{\llbracket b-1 \rrbracket}}$ and $A^{\cap,I} := (A^{\cap,I}(d_{\llbracket b-1 \rrbracket}))_{d_{\llbracket b-1 \rrbracket} \in \mathbb{D}_{\llbracket b-1 \rrbracket}}$ defined by taking for any $d_{\llbracket b-1 \rrbracket} \in \mathbb{D}_{\llbracket b-1 \rrbracket}$,

$$A^{\cup,I}(d_{\llbracket b-1 \rrbracket}) := (A(F_{I,1}(d_{\llbracket b-1 \rrbracket})) - \theta_I[d_{b-1}]) \cup (A(F_{I,-1}(d_{\llbracket b-1 \rrbracket})) + \theta_I[d_{b-1}])$$

$$A^{\cap,I}(d_{\llbracket b-1 \rrbracket}) := (A(F_{I,1}(d_{\llbracket b-1 \rrbracket})) - \theta_I[d_{b-1}]) \cap (A(F_{I,-1}(d_{\llbracket b-1 \rrbracket})) + \theta_I[d_{b-1}])$$

The following result is the generalization of Lemma 4.4,

**Lemma 6.4.** We have

$$\forall I \in [N-1], \quad |A^{\cup,I}| \ge |A|$$

and if for all $I \in [N-1]$, $|A^{\cup,I}| = |A|$, then $A = A_{b,\infty}$.

*Proof.* Concerning the first point, for any $d_{\llbracket b-1 \rrbracket} \in \mathbb{D}_{\llbracket b-1 \rrbracket}$ and $I \in [N-1]$, we have

$$\begin{align}
|A^{\cup,I}(d_{\llbracket b-1 \rrbracket})| &= |(A(F_{I,1}(d_{\llbracket b-1 \rrbracket})) - \theta_I[d_{b-1}]) \cup (A(F_{I,-1}(d_{\llbracket b-1 \rrbracket})) + \theta_I[d_{b-1}])| \nonumber \\
&\ge |A(F_{I,1}(d_{\llbracket b-1 \rrbracket})) - \theta_I[d_{b-1}]| \tag{6.6} \\
&= |A(F_{I,1}(d_{\llbracket b-1 \rrbracket}))| \nonumber
\end{align}$$

so that

$$\begin{align*}
|A^{\cup,I}| &= \sum_{d_{\llbracket b-1 \rrbracket} \in \mathbb{D}_{\llbracket b-1 \rrbracket}} |A^{\cup,I}(d_{\llbracket b-1 \rrbracket})| \\
&\ge \sum_{d_{\llbracket b-1 \rrbracket} \in \mathbb{D}_{\llbracket b-1 \rrbracket}} |A(F_{I,1}(d_{\llbracket b-1 \rrbracket}))| \\
&= \sum_{d_{\llbracket b-1 \rrbracket} \in \mathbb{D}_{\llbracket b-1 \rrbracket}} |A(d_{\llbracket b-1 \rrbracket})| \\
&= |A|
\end{align*}$$

where we used that the mapping $F_{I,1}$ is a bijection on $\mathbb{D}_{\llbracket b-1 \rrbracket}$, with inverse mapping given by $F_{I,-1}$. Assume next that the field $A$ is such that $|A^{\cup,I}| = |A|$, for any $I \in [N-1]$. According to the above computation, we must have for any $d_{\llbracket b-1 \rrbracket} \in \mathbb{D}_{\llbracket b-1 \rrbracket}$,

$$| (A(F_{I,1}(d_{\llbracket b-1 \rrbracket})) - \theta_I[d_{b-1}]) \cup (A(F_{I,-1}(d_{\llbracket b-1 \rrbracket})) + \theta_I[d_{b-1}]) | = |A(F_{I,1}(d_{\llbracket b-1 \rrbracket})) - \theta_I[d_{b-1}] |$$

namely

$$(A(F_{I,1}(d_{\llbracket b-1 \rrbracket})) - \theta_I[d_{b-1}]) \cup (A(F_{I,-1}(d_{\llbracket b-1 \rrbracket})) + \theta_I[d_{b-1}]) = A(F_{I,1}(d_{\llbracket b-1 \rrbracket})) - \theta_I[d_{b-1}]$$

Similarly, replacing (6.6) by

$$| (A(F_{I,1}(d_{\llbracket b-1 \rrbracket})) - \theta_I[d_{b-1}]) \cup (A(F_{I,-1}(d_{\llbracket b-1 \rrbracket})) + \theta_I[d_{b-1}]) | \ge |A(F_{I,-1}(d_{\llbracket b-1 \rrbracket})) + \theta_I[d_{b-1}]|$$

we get for any $d_{\llbracket b-1 \rrbracket} \in \mathbb{D}_{\llbracket b-1 \rrbracket}$,

$$(A(F_{I,1}(d_{\llbracket b-1 \rrbracket})) - \theta_I[d_{b-1}]) \cup (A(F_{I,-1}(d_{\llbracket b-1 \rrbracket})) + \theta_I[d_{b-1}]) = A(F_{I,-1}(d_{\llbracket b-1 \rrbracket})) + \theta_I[d_{b-1}]$$
and we deduce

$$A(F_{I,1}(d_{\llbracket b-1 \rrbracket})) - \theta_I[d_{b-1}] = A(F_{I,-1}(d_{\llbracket b-1 \rrbracket})) + \theta_I[d_{b-1}]$$

i.e.

$$A(d_{\llbracket b-1 \rrbracket}) = A(F_{I,-1} \circ F_{I,1}^{-1}(d_{\llbracket b-1 \rrbracket})) + 2\theta_I[(F_{I,1}^{-1}(d_{\llbracket b-1 \rrbracket}))_{b-1}] \\ = A(F_{I,-1}^2(d_{\llbracket b-1 \rrbracket})) + 2\theta_I[(F_{I,-1}(d_{\llbracket b-1 \rrbracket}))_{b-1}]$$

where $F_{I,-1}^2$ is the composition of $F_{I,-1}$ with itself. Recall from its definition in Lemma 6.1 that if $I \ge N - b + 1$, then the $\theta_I[(F_{I,-1}(d_{\llbracket b-1 \rrbracket}))_{b-1}]$ vanishes. First consider the case $I = N - 1$, where this condition is satisfied, so that

$$A(d_{\llbracket b-1 \rrbracket}) = A(F_{N-1,-1}^2(d_{\llbracket b-1 \rrbracket})) \quad (6.7)$$

Let us write $[x_{k,l}]_{1 \le k < l \le k+b-1} := d_{\llbracket b-1 \rrbracket}$ and $[x'_{k,l}]_{1 \le k < l \le k+b-1} := F_{N-1,-1}^2(d_{\llbracket b-1 \rrbracket}) \in \mathbb{D}_{\llbracket b-1 \rrbracket}$. We have $x'_{k,l} = x_{k,l}$, except for $(k, l) = (N-1, N)$, where $x'_{N-1,N} = x_{N-1,N} - 2$. Since the mapping $\mathbb{Z}_M \ni z \mapsto z - 2 \in \mathbb{Z}_M$ is a bijection, it follows from (6.7) that $A(d_{\llbracket b-1 \rrbracket})$ does not depend on the coordinate $x_{N-1,N}$ of $d_{\llbracket b-1 \rrbracket}$. Next assume that $b \ge 3$ and take $I = N - 2$. We have

$$A(d_{\llbracket b-1 \rrbracket}) = A(F_{N-2,-1}^2(d_{\llbracket b-1 \rrbracket})) \quad (6.8)$$

Writing $[x_{k,l}]_{1 \le k < l \le k+b-1} := d_{\llbracket b-1 \rrbracket}$ and $[x'_{k,l}]_{1 \le k < l \le k+b-1} := F_{N-2,-1}^2(d_{\llbracket b-1 \rrbracket})$, these coordinates coincide, except that $x'_{N-2,N-1} = x_{N-2,N-1} - 2$ and $x'_{N-2,N} = x_{N-2,N} - 2x_{N-1,N}$. Since both side of (6.8) do not depend on $x_{N-1,N}$, it follows that they also do not depend on the coordinate $x_{N-2,N}$. Resorting again to the bijectivity of the mapping $\mathbb{Z}_M \ni z \mapsto z - 2 \in \mathbb{Z}_M$, we see they equally do not depend on $x_{N-2,N-1}$. By iteration, considering successively $I = N - 3, ..., I = N - b + 1$, it appears that $A(d_{\llbracket b-1 \rrbracket})$ does not depend on the coordinates $x_{k,l}$, where $k > N - b$ (and $k < l \le k + b - 1$). For $I = N - b$, we have

$$A(d_{\llbracket b-1 \rrbracket}) = A(F_{N-b,-1}^2(d_{\llbracket b-1 \rrbracket})) + 2\theta_{N-b}[(F_{N-b,-1}(d_{\llbracket b-1 \rrbracket}))_{b-1}] \quad (6.9)$$

Note that the diagonal $F_{N-b,-1}(d_{\llbracket b-1 \rrbracket})_{b-1} \in \mathbb{D}_{b-1}$ is different from $d_{b-1}$ only in the last-but-one coordinate. It follows that $\theta_{N-b}[(F_{N-b,-1}(d_{\llbracket b-1 \rrbracket}))_{b-1}] = \theta_{N-b}(d_{b-1}) = (0, 0, ..., 0, x_{N-b+1,N}) \in \mathbb{D}_b$, with the above notation. Denote $y := (x_{N-b+1,N-b+2}, x_{N-b+1,N-b+3}, ..., x_{N-b+1,N-1})$. We have that

* the set $A(d_{\llbracket b-1 \rrbracket})$ does not depend on $y$ nor on $x_{N-b+1,N}$, since as mentioned above (6.9), it does not depend on the coordinates $x_{k,l}$, where $k \ge N - b + 1$,

* the set $A(F_{N-b,-1}^2(d_{\llbracket b-1 \rrbracket}))$ a priori depends on $y$, but not on $x_{N-b+1,N}$,

* the vector $2\theta_{N-b}[(F_{N-b,-1}(d_{\llbracket b-1 \rrbracket}))_{b-1}]$ only depends on $x_{N-b+1,N}$.

It follows that $A(d_{\llbracket b-1 \rrbracket})$ is preserved by the translations by vectors of the form $(0, 0, ..., 0, z) \in \mathbb{D}_b$ with $z \in \mathbb{Z}_M$. Namely, we can write $A(d_{\llbracket b-1 \rrbracket}) = A^{(1)}(d_{\llbracket b-1 \rrbracket}) \times \mathbb{Z}_M$, where $A^{(1)}(d_{\llbracket b-1 \rrbracket})$ is a subset of $\mathbb{Z}_M^{\{(k,b+k) : k \in \llbracket N-b-1 \rrbracket\}}$. Coming back to (6.9), we deduce that $A^{(1)}(d_{\llbracket b-1 \rrbracket})$ does not depend on $y$ (nor on the rows indexed by $\llbracket N - b + 1, N \rrbracket$ of $d_{\llbracket b-1 \rrbracket}$). The previous arguments can be iterated with $I = N - b - 1, ..., I = 1$. At the end we get that $A(d_{\llbracket b-1 \rrbracket}) = \mathbb{D}_b$, as desired. $\square$

The next result is the generalization of Corollary 4.5.

**Corollary 6.5.** When $A := (A(d_{\llbracket b-1 \rrbracket}))_{d_{\llbracket b-1 \rrbracket} \in \mathbb{D}_{\llbracket b-1 \rrbracket}} \neq A_{b,\infty}$, there exist $I \in \llbracket N - 1 \rrbracket$ such that

$$|A^{\cup,I}| \ge |A| + 1$$
Proof. Lemma 6.4 shows that when $A \neq A_{b, \infty}$, there exists $I \in [N-1]$ such that $|A^{\cup, I}| > |A|$. It remains to take into account that the cardinals are integer-valued. $\square$

Let us keep following the path of Section 4 by presenting the generalization of Lemma 4.6. We need the following notations:

$$ \forall n \in \mathbb{Z}_+, \quad \begin{cases} \mathcal{A}_n := \sigma(\mathcal{X}_b(0), \mathcal{X}_b(1), \dots, \mathcal{X}_b(n)) \\ R_n := |\mathcal{X}_b(n)| \end{cases} $$

**Lemma 6.6.** We have for any $n \in \mathbb{Z}_+$ such that $\mathcal{X}_b(n) \neq A_{b, \infty}$,

$$ \mathbb{E}[R_{n+1}|\mathcal{A}_n] \geq R_n + \frac{1}{6(N-1)M^{b(2N-b-1)/2}} $$

Proof. From the general theory developed in [17], from Lemmas 6.1 and 6.2 and from the choice (6.4), the conditional law of the field $A'$ representing $\mathcal{X}_b(n+1)$ knowing $\mathcal{A}_n$, in particular knowing the field $A$ standing for $\mathcal{X}_b(n)$, is given by

$$ \mathfrak{Q}(A, A') := \frac{1}{3}\delta_A(A') + \frac{1}{3(N-1)}\sum_{I \in [N-1]} \frac{|A'|}{|A|}(\delta_{A^{\cup, I}}(A') + \delta_{A^{\cap, I}}(A')) $$

This is a Markov kernel on $\mathbb{A}_b$, the set of fields $A$ with $|A| \ge 1$. As in the proof of Lemma 4.6, the kernel $\mathfrak{Q}$ is the modification through the cardinal weights of the kernel $\mathfrak{R}$ defined by

$$ \mathfrak{R}(A, A') := \frac{1}{3}\delta_A(A') + \frac{1}{3(N-1)}\sum_{I \in [N-1]} (\delta_{A^{\cup, I}}(A') + \delta_{A^{\cap, I}}(A')) $$

Note that since $\mathfrak{Q}$ is a Markov kernel, we have for any $A \in \mathbb{A}_b$,

$$ \begin{aligned} \sum_{A' \in \mathbb{A}_b} \mathfrak{R}(A, A') |A'| &= |A| \sum_{A' \in \mathbb{A}_b} \mathfrak{R}(A, A') \frac{|A'|}{|A|} \\ &= |A| \sum_{A' \in \mathbb{A}_b} \mathfrak{Q}(A, A') \\ &= |A| \end{aligned} \qquad (6.10) $$

With the above notations, it follows that

$$ \mathbb{E}[R_{n+1}|\mathcal{A}_n] - R_n = \frac{1}{|A|} \sum_{A' \in \mathbb{A}_b} \mathfrak{R}(A, A')(|A'| - |A|)^2 $$

From Corollary 6.5, when $A \neq A_{b, \infty}$, there exists $I \in [N-1]$ such that $\mathfrak{R}(A, A^{\cup, I}) \ge 1/(3(N-1))$ and $|A^{\cup, I}| - |A| \ge 1$, so that

$$ \mathbb{E}[R_{n+1}|\mathcal{A}_n] - R_n \ge \frac{1}{3(N-1)|A|} $$

Note that

$$ |A| \le |A_{b, \infty}| $$
$$
\begin{align*}
&= |\mathbb{D}_{[b-1]}| |\mathbb{D}_b| \\
&= M^{(N-1)+(N-2)+\cdots+(N-b+1)} M^{(N-b)} \\
&= M^{b(2N-b-1)/2}
\end{align*}
$$

it follows that

$$
\mathbb{E}[R_{n+1}|\mathcal{A}_n] - R_n \ge \frac{1}{3(N-1)M^{b(2N-b-1)/2}}
$$

□

We deduce a weak estimate on t_b, as in Proposition 4.7:

**Proposition 6.7.** We have, for $b \in [2, N-1]$,

$$
\mathbb{E}[t_b] \le 3(N-1)M^{b(2N-b-1)}
$$

*Proof.* According to Lemma 6.6, the stochastic chain

$$
\left( R_{t_b \wedge n} - \frac{1}{3(N-1)M^{b(2N-b-1)/2}} (t_b \wedge n) \right)_{n \in \mathbb{Z}_+}
$$

is a submartingale. It follows that

$$
\forall n \in \mathbb{Z}_+, \quad \mathbb{E}[R_{t_b \wedge n}] \ge \frac{1}{3(N-1)M^{b(2N-b-1)/2}} \mathbb{E}[t_b \wedge n]
$$

Letting $n$ go to infinity, we get, by dominated convergence in the l.h.s. and by monotone convergence in the r.h.s.,

$$
\mathbb{E}[R_{t_b}] \ge \frac{1}{3(N-1)M^{b(2N-b-1)/2}} \mathbb{E}[t_b]
$$

To get the first announced bound, note that

$$
\mathbb{E}[R_{t_b}] = |A_{b,\infty}| = M^{b(2N-b-1)/2}
$$

so that

$$
\begin{align*}
\mathbb{E}[\mathbf{t}_b] &\le 3(N-1)M^{b(2N-b-1)/2} M^{b(2N-b-1)/2} \\
&= 3(N-1)M^{b(2N-b-1)}
\end{align*}
$$

□

Note that the quadratic mapping $\mathbb{R} \ni b \mapsto b(2N - b - 1)$ attains its maximum value at $b = N - 1/2$. So on $[[N-1]]$ its maximum value is attained at $b = N - 1$. It follows that the bound of Proposition 6.7 is increasing in $b \in [2, N-1]$ (as it should be) and its largest value is $3(N-1)M^{N(N-1)}$. Theorem 6.3 is now obtained via the Markovian arguments recalled in the proof of Theorem 1.1.

In turn, Theorem 6.3 implies Theorem 1.3 and provides the justification of the assertions made after its statement. Theorem 6.3 is only valid for $b \ge 2$, but for $b = 1$ a direct argument is available, close to the proof of Lemma 3.1. We get:
**Lemma 6.8.** For $M$ large enough, we have

$$ \forall N \ge 3, \forall r \ge 0, \quad \mathbb{P}[t_1 \ge r] \le 5 \frac{N-1}{2} \exp \left( - \frac{r}{5(N-1)M^2} \right) $$

(the factor $5/2$ is here just to recover Lem. 3.1 when $N = 3$).

*Proof.* Consider $(\tilde{X}_k)_{k \in [N-1]} := (\tilde{X}_k(n))_{n \in \mathbb{Z}_+, k \in [N-1]}$, $N-1$ independent random walks on $\mathbb{Z}_M$ as in Section 2.4. Let $(B_n)_{n \in \mathbb{Z}_+}$ be a family of independent variables uniformly distributed on $[N-1]$ (and independent from the $\tilde{X}_k$, for $k \in [N-1]$) and define

$$ \forall k \in [N-1], \forall n \in \mathbb{Z}_+, \quad \theta_k(n) := \sum_{m \in [n]} 1_{\{B_m=k\}} $$

The chain $[X_{k,k+1}(n)]_{k \in [N-1], n \in \mathbb{Z}_+} = (d_1[X](n))_{n \in \mathbb{Z}_+}$ has the same law as $(\tilde{X}_k(\theta_k(n)))_{k \in [N-1], n \in \mathbb{Z}_+}$ and from the above construction, it appears that

$$ t_1 = \inf\{n \in \mathbb{Z}_+ : \forall k \in [N-1], \theta_k(n) \ge \tilde{t}_k\} $$

where for any $k \in [N-1]$, $\tilde{t}_k$ is the strong stationary time constructed as in Section 2.4 for $\tilde{X}_k$. It follows that for any $n \in \mathbb{Z}_+$,

$$ \begin{aligned} \mathbb{P}[t_1 \ge n] &\le \sum_{k \in [N-1]} \mathbb{P}[\theta_k(n) \le \tilde{t}_k] \\ &= (N-1)\mathbb{P}[\theta_1(n) \le \tilde{t}_1] \end{aligned} $$

since the $(\theta_k(n), \tilde{t}_k)$ have the same law for all $k \in [N-1]$. According to Corollary 2.4, we have for the conditional expectation knowing $\theta_k(n)$ and for large $M$:

$$ \mathbb{P}[\theta_1(n) \le \tilde{t}_1 | \theta_1(n)] \le 2 \exp(-\theta_1(n)/(4M^2)) $$

so that

$$ \begin{aligned} \mathbb{P}[\theta_1(n) \le \tilde{t}_1] &\le 2\mathbb{E}[\exp(-\theta_1(n)/(4M^2))] \\ &= 2\mathbb{E}[\exp(-1_{\{B_1=1\}}/M^2)]^n \\ &= 2 \left( \frac{N-2 + \exp(-1/(4M^2))}{N-1} \right)^n \\ &= 2 \left( 1 + \frac{\exp(-1/(4M^2)) - 1}{N-1} \right)^n \\ &\le 2 \exp \left( - \frac{n}{5(N-1)M^2} \right) \end{aligned} $$

for $M$ large enough, uniformly in $n \in \mathbb{Z}_+$ and in $N \in \mathbb{N}$, $N \ge 3$. As a consequence, for any $r \ge 0$, we have

$$ \begin{aligned} \mathbb{P}[t_1 \ge r] &\le \mathbb{P}[t_1 \ge [r]] \\ &\le 2(N-1) \exp \left( - \frac{|r|}{5(N-1)M^2} \right) \end{aligned} $$
$$
\begin{align*}
&\le 2(N-1) \exp \left( - \frac{r-1}{5(N-1)M^2} \right) \\
&\le 2(N-1) \exp \left( \frac{1}{5(N-1)M^2} \right) \exp \left( - \frac{r}{5(N-1)M^2} \right) \\
&\le 5 \frac{N-1}{2} \exp \left( - \frac{r}{5(N-1)M^2} \right)
\end{align*}
$$

since we have $2 \exp(1/(5 \times 2 \times 3^2)) \approx 2.02234613753 < 5/2$. $\square$

The above estimate implies the more telling bound, for $M$ large enough and uniformly in $N \in \mathbb{N}$, $N \ge 3$,

$$
\forall r \ge 0, \quad \mathbb{P}[t_1 \ge 5N \ln(N)M^2 + rNM^2] \le 5 \exp(-r/5)
$$

To end this section, let us mention the modifications required by the proof of Theorem 1.4. They extend to higher dimensions the arguments of Section 5. It is possible to consider an extension in the spirit of Theorem 6.3, namely to construct a strong stationary times for $[X_{k,N}]_{k \in \llbracket N-b,N-1 \rrbracket}$, for $b \in \llbracket 2, N-1 \rrbracket$. But up to removing the $N-b-1$ first rows of matrices from $\mathbb{H}_{N,M}$, this is the same Markov chain, except for the time spent to changing the removed rows.

First note that the last column $C_N[X] := [X_{k,N}]_{k \in \llbracket N-1 \rrbracket}$ is indeed a Markov chain, whose state space is $\mathbb{Z}_M^{N-1}$ and whose generic elements will be denoted $[x] := [x_k]_{k \in \llbracket N-1 \rrbracket}$. The associated transition matrix $P$ is given by its entries for any $[x], [x'] \in \mathbb{Z}_M^{N-1}$,

$$
P([x], [x']) = \begin{cases} 1/(6(N-1)), & \text{if } [x'] = F_{I,\epsilon}[x] \text{ for some } I \in \llbracket N-1 \rrbracket \text{ and } \epsilon \in \{\pm 1\} \\ \frac{1}{3}, & \text{if } [x'] = [x] \\ 0, & \text{otherwise} \end{cases}
$$

where for any $[x] := [x_k]_{k \in \llbracket N-1 \rrbracket} \in \mathbb{Z}_M^{N-1}$, $l \in \llbracket N-1 \rrbracket$, $I \in \llbracket N-1 \rrbracket$ and $\epsilon \in \{\pm 1\}$, the $l$th coordinate of $F_{I,\epsilon}[x]$ is given by

$$
(F_{I,\epsilon}[x])_l := \begin{cases} x_l & , \text{ if } l \neq I \\ x_l + \epsilon x_{l+1} & , \text{ if } l = I \end{cases}
$$

with the convention $x_N = 1$. The transition kernel $P$ admits the uniform distribution on $\mathbb{Z}_M^{N-1}$ as reversible probability. The method of [17] is applied with $\mathfrak{Y}$ being the whole collection of non-empty subsets of $\mathbb{Z}_M^{N-1}$. Let us describe the family of random mappings $(\psi_\Omega)_{\Omega \in \mathfrak{Y}}$. As usual, note that any subset $\Omega$ of $\mathbb{Z}_M^{N-1}$ is uniquely determined by a **field** $A := (A(x_{\llbracket 2,N-1 \rrbracket}))_{x_{\llbracket 2,N-1 \rrbracket} \in \mathbb{Z}_M^{\llbracket 2,N-1 \rrbracket}}$ of subsets of $\mathbb{Z}_M$ (still called **fibers**) such that

$$
[x] \in \Omega \Leftrightarrow x_1 \in A(x_{\llbracket 2,N-1 \rrbracket})
$$

(with the traditional notation $x_{\llbracket 2,N-1 \rrbracket} := (x_k)_{k \in \llbracket 2,N-1 \rrbracket}$). The construction of the random mappings is similar to the one presented earlier in this section, just keeping the effects on the last column. As before, the subsets $\Omega$ are identified with their representative field $A$. Given such a field

$$
A := (A(x_{\llbracket 2,N-1 \rrbracket}))_{x_{\llbracket 2,N-1 \rrbracket} \in \mathbb{Z}_M^{\llbracket 2,N-1 \rrbracket}} \quad (6.11)
$$

and $I \in \llbracket N-1 \rrbracket$, associate two other fields $A^{\cup,I}$ and $A^{\cap,I}$ defined by taking for any $x_{\llbracket 2,N-1 \rrbracket} \in \mathbb{Z}_M^{\llbracket 2,N-1 \rrbracket}$,

$$
A^{\cup,I}(x_{\llbracket 2,N-1 \rrbracket}) := (A(F_{I,1}(x_{\llbracket 2,N-1 \rrbracket})) - \delta_1(I)x_2) \cup (A(F_{I,-1}(x_{\llbracket 2,N-1 \rrbracket}))) + \delta_1(I)x_2
$$
$$A^{\wedge, I}(x_{[2,N-1]}) := (A(F_{I,1}(x_{[2,N-1]})) - \delta_1(I)x_2) \cap (A(F_{I,-1}(x_{[2,N-1]})) + \delta_1(I)x_2)$$

where $\delta_1(I)$ is the Kronecker symbol whose value is 1 if $I = 1$ and 0 otherwise.

Let $\mathfrak{A}$ be the set of fields of the form (6.11) corresponding to non-empty subsets of $\mathbb{Z}_M^{N-1}$, i.e. elements of $\mathfrak{A}$. They are the fields whose fibers are not all empty. Following meticulously the method described in the first part of this section, we are led to investigate Markov chains $(A(n))_{n \in \mathbb{Z}_+}$ on $\mathfrak{A}$ whose transition kernel $\mathfrak{Q}$ is given by

$$\forall A, A' \in \mathfrak{A}, \quad \mathfrak{Q}(A, A') := \frac{1}{3}\delta_A(A') + \frac{1}{3(N-1)} \sum_{I \in [N-1]} \frac{|A'|}{|A|} (\delta_{A \wedge I}(A') + \delta_{A \vee I}(A'))$$

where

$$\forall A \in \mathfrak{A}, \quad |A| := \sum_{x_{[2,N-1]} \in \mathbb{Z}_M^{[2,N-1]}} |A(x_{[2,N-1]})|$$

Specifying Lemma 6.4 to the last column of the objects considered there, it appears that $(A(n))_{n \in \mathbb{Z}_+}$ ends up being absorbed into $A_\mathfrak{A}$, the element of $\mathfrak{A}$ whose fibers are all equal to $\mathbb{Z}_M$. Denote $\mathfrak{t}$ the corresponding absorbing time. Our approach relies on the possibility to estimate the tail probabilities of $\mathfrak{t}$. Here is the equivalent of Theorem 6.3:

**Proposition 6.9.** For any initial distribution of $A_0$, we have for $M$ large enough (uniformly in $N$),

$$\forall r \ge 0, \quad \mathbb{P}[t \ge r] \le 3 \exp \left( - \frac{2r}{17(N-1)M^{2(N-1)}} \right)$$

The proof of these bounds is similar to that of Theorem 6.3. The difference is that the index set is $\mathbb{Z}_M^{[2,N-1]}$ (instead of $\mathbb{D}_{[b-1]}$) and that the fibers are included into $\mathbb{Z}_M$ (instead of $\mathbb{D}_b$) so we replace $|\mathbb{D}_b||\mathbb{D}_{[b-1]}|$ by $|\mathbb{Z}_M^{[2,N-1]}||\mathbb{Z}_M| = M^{N-1}$, i.e. $1/M^{b(2N-b-1)/2}$ by $1/M^{N-1}$, in Lemmas 6.5 and 6.6, and $M^{b(2N-b-1)}$ by $M^{2(N-1)}$ in Proposition 6.7. This ends the proof of Theorem 1.4, since $\mathfrak{t}$ has the same law as a strong stationary time for $C_N[X]$, according to [17].

**Remark 6.10.** An estimate for a strong stationary time for the coordinate $X_{N-1,N}$ is provided by the analogue of Lemma 6.8, where the factor $N-1$ in the r.h.s. can be removed, since we don't have to wait for the whole first upper diagonal to reach equilibrium.

**Remark 6.11.** Remark 4.8 (c) admits a natural extension to the present higher dimension situation, to get a strong equilibrium time for the right-up component $X_{1,N}$, believed to be of order $M^{1/(N-1)}$.

# APPENDIX A. THE FINITE CIRCLE: REMAINING CASES

In the context of the beginning of Section 2, we deal here with the remaining cases where $a \in (1/3, 1/2]$. To construct the sets $\mathfrak{A}$ and the corresponding random mappings $(\psi_S)_{S \in \mathfrak{A}}$ satisfying the conditions of weak association with $P$ and of stability of $\mathfrak{A}$, we distinguish two situations, depending on the parity of $M \in \mathbb{N}\{1, 2\}$.

## A.1 When $M$ is even

For $a \in (1/3, 1/2]$, we need to add new kinds of sets in $\mathfrak{A}$, in addition to the segments from $\mathfrak{J}$. More precisely, for $r \in [0, M/2]$, let $B_-(0, r)$ be the set of $x \in B(0, r)$ which have the same parity as $r$ (there is no ambiguity in the definition of the parity in $\mathbb{Z}_M$, since $M$ is even). Consider

$$\mathfrak{J}_- := \{B_-(0, r) : r \in [1, M/2]\}$$
$$ \mathfrak{J} := \mathfrak{J} \sqcup \mathfrak{J}_{-} $$

Note that the only subset of the form $B_-(0, r)$ that belongs to $\mathfrak{J}$ is $B_-(0, 0) = \{0\}$, which does not belong to $\mathfrak{J}_{-}$.

### A.1.1 The random mapping $\psi_{\{0\}}$

When $a \in (1/3, 1/2]$, the construction of $\psi_{\{0\}}$ given in Section 2.1 is no longer valid. So here is another construction (an alternative one will be provided in Sect. A.3.1). Choose two mappings $\tilde{\psi}, \hat{\psi} : \mathbb{Z}_M \to \mathbb{Z}_M$ satisfying respectively $\tilde{\psi}(0) = 0 = \tilde{\psi}(-1) = \tilde{\psi}(1)$ and $\tilde{\psi}(x) \neq 0$ for $x \in \mathbb{Z}_M \setminus [-1, 1]$, and $\hat{\psi}(-1) = 0 = \hat{\psi}(1)$ and $\hat{\psi}(x) \neq 0$ for $x \in \mathbb{Z}_M \setminus \{-1, 1\}$. Take $\psi_{\{0\}}$ to equal to $\tilde{\psi}$ with some probability $p \in [0, 1]$ and to $\hat{\psi}$ with probability $1-p$. Let us compute $p$ so that Condition (2.1) is satisfied, which here still amounts to (2.6).

* When $x \notin [-1, 1]$, both sides of (2.6) vanish.

* When $x \in \{-1, 1\}$, the l.h.s. of (2.6) is 1, while the r.h.s. is $a/\xi(\{0\})$. This implies that $\xi(\{0\}) = a$.

* When $x = 0$, (2.6) is equivalent to

$$ p = \frac{1 - 2a}{a} $$

and this number $p$ does belong to $[0, 1]$ for $a \in (1/3, 1/2]$.

Next we must check that for this random mapping $\psi_{\{0\}}$, (2.2) is satisfied, namely $\Psi(\{0\}) \in \mathfrak{J} = \mathfrak{J} \sqcup \mathfrak{J}_{-}$. This is true, because $\tilde{\psi}^{-1}(\{0\}) = [-1, 1] \in \mathfrak{J}$ and $\hat{\psi}^{-1}(\{0\}) = \{-1, 1\} = B_-(0, 1) \in \mathfrak{J}_{-}$.

### A.1.2 The other random mappings and the Markov transition kernel $\mathfrak{P}$

For $S \in \mathfrak{J} \sqcup \mathfrak{J}_{-} \setminus \{0\}$, take the same random mapping $\psi_S = \phi$ defined in Section 2.2. It is clear that (2.7) is still satisfied, since the proof is valid for any $a \in (0, 1/2]$ (and any $M \ge 3$). Concerning the stability of $\mathfrak{J} \sqcup \mathfrak{J}_{-}$ by $\phi$, note that in addition to (2.8), we also have for any $r \in [1, M/2]$,

$$ \left\{ \begin{array}{l} \phi_1^{-1}(B_-(0, r)) = B_-(0, r + 1) \\ \phi_2^{-1}(B_-(0, r)) = B_-(0, r + 1) \\ \phi_3^{-1}(B_-(0, r)) = B_-(0, r - 1) \\ \phi_4^{-1}(B_-(0, r)) = B_-(0, r - 1) \\ \phi_5^{-1}(B_-(0, r)) = B_-(0, r) \end{array} \right. \qquad (A.1) $$

(where $M/2 + 1$ has to be understood as $M/2 - 1$).

As in Section 2.3, we identify $B(0, r)$ with $r$, for $r \in [0, M/2]$, and furthermore, for $r \in [1, M/2]$, we identify $B_-(0, r)$ with $-r$. It appears that $\mathfrak{P}$ is also the transition matrix of a birth and death chain, but this time on $[-M/2, M/2]$:

$$ \forall k, l \in [-M/2, M/2], \qquad \mathfrak{P}(k, l) = \begin{cases} 1 - 2a, & \text{if } k = 0 \text{ and } l = 1 \\ 3a - 1, & \text{if } k = 0 \text{ and } l = -1 \\ a \frac{2l+1}{2k+1}, & \text{if } k \ge 1, k \ne M/2 \text{ and } |k-l| = 1 \\ a \frac{|l+1|}{|k+1|}, & \text{if } k \le -1, \text{ and } |k-l| = 1 \\ 1 - 2a, & \text{if } |k| \ge 1, k \ne M/2 \text{ and } k = l \\ 1, & \text{if } k = M/2 = l \\ 0, & \text{otherwise} \end{cases} $$
(we used that $|B_-(0, r)| = r + 1$, for $r \in [0, M/2]$).

When $p \in (1/3, 1/2)$, $\mathfrak{P}$ enables to reach the absorbing point $M/2$ from all the other points, thus the absorbing time $t$ is a.s. finite and its law is the distribution of a strong stationary time for $X$. A different feature is that the starting point $\mathcal{X}_0 = \{0\}$, identified with 0, is at the middle of the discrete segment $[-M/2, M/2]$ and the left boundary is not absorbing.

When $p = 1/2$, the transition from 0 to 1 is forbidden: $\mathfrak{P}(0, 1) = 0$. Starting from 0, the Markov chain $\mathcal{X}$ stays on the irreducible state space $[-M/2, 0]$ and never reaches $M/2$, i.e. $t = \infty$ a.s. This result could have been guessed, as due to the periodicity of order 2, $X$ does not converge to $\pi$ in large times. The Markov chain $-\mathcal{X}$ is a finite equivalent of the process on $\mathbb{Z}_+$ introduced by Pitman in [20] (see also [17] for an approach via random mappings).

**Remark A.1.** It is important that $\psi_{\{0\}}$ is different from the random mapping $\phi$ considered in Sections 2.2 and A.1.2. Indeed, whatever $a \in (0, 1/2]$, if we had taken $\psi_{\{0\}} = \phi$, we would have ended up with $\mathcal{X}_1 \in \{\{-1, 1\}, \{0\}\}$ and from (A.1), we can deduce that for any $n \in \mathbb{Z}_+$, we would have $\mathcal{X}_n \in \{\{0\}\} \cup \mathcal{J}_-$. In particular $t = +\infty$ when $M$ is even.

## A.2 When $M$ is odd

In this situation, we enrich the set $\mathcal{I}_-$. For $r \in [0, (M-1)/2]$, $B_-(0, r)$ is defined as at the beginning of Section A.1. Now the parity of an element $x \in \mathbb{Z}_M$ is the parity of its representative in $[-(M-1)/2, (M-1)/2]$. Furthermore, for $r \in [(M+1)/2, M-1]$, we consider

$$B_-(0, r) = B_-(0, (M-1)/2) \cup B(-(M-1)/2, r - (M-1)/2) \cup B((M-1)/2, r - (M-1)/2)$$

namely this subset contains all the points encountered when going clock-wise from $r - (M-1)$ to $M-1-r$, and all the other points which have the parity of $r - (M-1)$. In particular when $r = M-1$, we get $B_-(0, M-1) = \mathbb{Z}_M$. We take

$$\begin{align*} \mathcal{I}_- &:= \{B_-(0, r) : r \in [1, M-1]\} \\ \mathfrak{V} &:= \mathcal{J} \cup \mathcal{J}_- \end{align*}$$

Note that the only element in the intersection of $\mathcal{I}$ and $\mathcal{I}_-$ is the whole state space $\mathbb{Z}_M = B(0, (M-1)/2) = B_-(0, M-1)$, nevertheless, it will be convenient to see $B(0, (M-1)/2)$ and $B_-(0, M-1)$ as different (i.e. to interpret $\mathfrak{V}$ as a multiset, with $\mathbb{Z}_M$ of multiplicity 2), namely to write $\mathfrak{V} = \mathcal{J} \cup \mathcal{J}_-$.

We consider the same random mappings as those constructed in Section A.1: The random mapping $\psi_{\{0\}}$ is the one of Section A.1.1 and for $S \in \mathfrak{V}\{\{0\}\}$, $\psi_S = \phi$, defined in Sections 2.2 and A.1.2. It follows that (2.1) holds (with $\xi(\{0\}) = a$ and $\xi(S) = 1$, for $S \in \mathfrak{V}\{\{0\}\}$). Furthermore, due to the fact that $M$ is odd, we get that (A.1) is still true for $r \in [1, M-1]$, with the convention that $B_-(0, M) = \mathbb{Z}_M$. Now we identify $B(0, r)$ with $r$, for $r \in [0, (M-1)/2]$, and $B_-(0, r)$ with $-r$, for $r \in [1, M-1]$. In accordance with the multiplicity 2 of $\mathbb{Z}_M$ mentioned above, the whole state space $\mathbb{Z}_M$ is seen as the two points $(M-1)/2$ and $-(M-1)$. This identification enables us to see $\mathfrak{P}$ as the transition matrix of a birth and death chain on $[-(M-1), (M-1)/2]$:

$$\forall k, l \in [-(M-1), (M-1)/2], \quad \mathfrak{P}(k, l) = \begin{cases} 1 - 2a, & \text{if } k = 0 \text{ and } l = 1 \\ 3a - 1, & \text{if } k = 0 \text{ and } l = -1 \\ a \frac{2l+1}{2k+1}, & \text{if } k \ge 1, k \ne M/2 \text{ and } |k-l| = 1 \\ a \frac{|l+1|}{|k|+1}, & \text{if } k \le -1, k \ne -(M-1) \text{ and } |k-l| = 1 \\ 1, & \text{if } k = l \in \{-(M-1), (M-1)/2\} \\ 0, & \text{otherwise} \end{cases}$$
(we used that $|B_-(0, r)| = r + 1$, for $r \in [0, M - 1]$).

When $p \in (1/3, 1/2)$, $\mathfrak{P}$ enables to reach the two absorbing points $(M-1)/2$ and $-(M-1)$ from all the other points, thus the absorbing time $t$ is a.s. finite and its law is the distribution of a strong stationary time for $X$. The Markov chain $\mathcal{X}$ still starts from 0 and ends up being absorbed in one of boundary points $(M-1)/2$ or $-(M-1)$.

When $p = 1/2$, the transition from 0 to 1 is still forbidden: $\mathfrak{P}(0, 1) = 0$. Starting from 0, the Markov chain $\mathcal{X}$ stays on the irreducible state space $[-(M-1), 0]$ and ends up being absorbed at $-(M-1)$. Thus $t$ is a.s. finite and $X$ admits a strong stationary time, it was expected as there is no problem of periodicity when $M$ is odd.

### A.3 Alternative random mappings, still for $a \in [1/3, 1/2)$

The constructions of the previous subsections could also have been obtained by first lumping $X$ (see Rem. 2.2, whose “projection” is valid for all $a \in (0, 1/2]$). Here we propose another construction which is no longer compatible with this procedure. We take for $\mathfrak{V}$ the set of all balls $B(x, r)$, for $x \in \mathbb{Z}_M$ and $r \in [0, \lfloor M/2 \rfloor]$. All these balls are different, except that $B(x, \lfloor M/2 \rfloor) = \mathbb{Z}_M$ for any $x \in \mathbb{Z}_M$. The space $\mathfrak{V}$ can be seen as a wheel: the tyre is the discrete circle consisting of the $B(x, 0) = \{x\}$ for $x \in \mathbb{Z}_M$. For any fixed $x \in \mathbb{Z}_M$, the set $\{B(x, r) : r \in [0, \lfloor M/2 \rfloor]\}$ is a ray going from the tyre to the center of the wheel, represented by $\mathbb{Z}_M$. The Markov kernel $\mathfrak{P}$ that we are to construct will respect this wheel graph.

#### A.3.1 The alternative random mappings $\psi_{\{x\}}$, for $x \in \mathbb{Z}_M$

Fix some $x \in \mathbb{Z}_M$. We slightly modify the random mapping considered in Section A.1.1 (after rotating $\mathbb{Z}_M$ by $-x$). Choose three mappings $\tilde{\psi}_x, \tilde{\psi}_{\tilde{x}}, \tilde{\psi}_{\tilde{x}} : \mathbb{Z}_M \to \mathbb{Z}_M$ satisfying respectively

* $\tilde{\psi}_x(x) = x = \tilde{\psi}_x(x-1) = \tilde{\psi}_x(x+1)$ and $\tilde{\psi}_x(y) \neq x$ for $y \in \mathbb{Z}_M \setminus [x-1, x+1]$

* $\tilde{\psi}_x(x-1) = x$ and $\tilde{\psi}_x(y) \neq x$ for $y \in \mathbb{Z}_M \setminus \{x-1\}$

* $\tilde{\psi}_x(x+1) = x$ and $\tilde{\psi}_x(y) \neq x$ for $y \in \mathbb{Z}_M \setminus \{x+1\}$

Take $\psi_{\{x\}}$ to equal to $\tilde{\psi}_x$ with some probability $p \in [0, 1]$ and to each of $\tilde{\psi}_x$ and $\tilde{\psi}_{\tilde{x}}$ with probability $(1-p)/2$. Let us compute $p$ so that Condition (2.1) is satisfied, which here amounts to

$$ \forall y \in \mathbb{Z}_M, \quad \mathbb{P}[\psi_{\{x\}}(y) = x] = \frac{1}{\xi(\{x\})} P(y, x) \qquad (A.2) $$

* When $y \notin [x-1, x+1]$, both sides of (A.2) vanish.

* When $y \in \{x-1, x+1\}$, the l.h.s. of (A.2) is $1 - (1-p)/2$, while the r.h.s. is $a/\xi(\{x\})$. This implies that $\xi(\{x\}) = 2a/(1+p)$.

* When $y = x$, (A.2) is equivalent to

$$ p = \frac{(1 - 2a)(1 + p)}{2a} $$

namely $p = (1 - 2a)/(4a - 1)$, which belongs to $[0, 1)$ for $a \in (1/3, 1/2]$.

For the computations of the next section, note that according to (2.3),

$$ \begin{aligned} \mathfrak{P}(\{x\}, \{x-1, x, x+1\}) &= 3\xi(\{x\})p \\ &= 3\frac{2a}{1+p} \frac{(1-2a)(1+p)}{2a} \\ &= 3(1-2a) \end{aligned} $$
and

$$
\begin{align*}
\mathfrak{P}(\{x\}, \{x-1\}) &= \mathfrak{P}(\{x\}, \{x+1\}) \\
&= \frac{1 - \mathfrak{P}(\{x\}, \{x-1, x, x+1\})}{2} \\
&= 3a - 1
\end{align*}
$$

Next we must check that for this random mapping $\psi_{\{x\}}$, (2.2) is satisfied, namely $\psi_x(\{x\}) \in \mathfrak{V}$. This is true, because $\tilde{\psi}_x^{-1}(\{x\}) = B(x, 1)$, $\hat{\psi}_x^{-1}(\{x\}) = B(x-1, 0)$ and $\tilde{\psi}_x^{-1}(\{x\}) = B(x+1, 0)$.

### A.3.2 The other random mappings and the Markov transition kernel $\mathfrak{P}$

For any $x \in \mathbb{Z}_M$, the mappings $\phi_{1,x}, \phi_{2,x}, \phi_{3,x}, \phi_{4,x}$ and $\phi_{5,x}$, as well as the random mapping $\phi_x$, are constructed as $\phi_1, \phi_2, \phi_3, \phi_4, \phi_5$ and $\phi$ in Sections 2.2 and A.1.2, but are centered at $x$ instead of 0. Then we take $\psi_S = \phi_x$, for any $S = B(x,r)$, with $r \in [1, \lfloor M/2 \rfloor]$. By the same proofs as before ("rotated" by $-x$), we get that these random mappings are strongly associated to $P$ and that (2.2) is satisfied, since we have for any $r \in [1, \lfloor M/2 \rfloor]$,

$$
\left\{
\begin{aligned}
\phi_{1,x}^{-1}(B(x,r)) &= B(x, r+1) \\
\phi_{2,x}^{-1}(B(x,r)) &= B(x, r+1) \\
\phi_{3,x}^{-1}(B(x,r)) &= B(x, r-1) \\
\phi_{4,x}^{-1}(B(x,r)) &= B(x, r-1) \\
\phi_{5,x}^{-1}(B(x,r)) &= B(x, r)
\end{aligned}
\right.
$$

(where $B(x, \lfloor M/2 \rfloor) = B(x, \lfloor M/2 \rfloor + 1) = \mathbb{Z}_M$). The corresponding Markov kernel $\mathfrak{P}$ is compatible with the wheel structure of $\mathfrak{V}$ and we have for any $S, S' \in \mathfrak{V}$ which are neighbors in this graph, and where $x$ is the center of $S$,

$$
\mathfrak{P}(S, S') =
\begin{cases}
3a - 1, & \text{if } S = \{x\} \text{ and } S' = \{x + 1\} \text{ or } S' = \{x - 1\} \\
3 - 6a, & \text{if } S = \{x\} \text{ and } S' = \{x - 1, x, x + 1\} \\
a \frac{2l+1}{2k+1}, & \text{if } S = B(x, k) \text{ and } S = B(x, l) \text{ with } k \in [1, \lfloor M/2 \rfloor - 1] \text{ and } |k - l| = 1 \\
1 - 2a, & \text{if } S = B(x, k) = S' \text{ with } x \in \mathbb{Z}_M \text{ and } k \in [1, \lfloor M/2 \rfloor - 1] \\
1, & \text{if } S = S' = \mathbb{Z}_M
\end{cases}
$$

For a corresponding Markov chain, $\mathcal{X}$ starting from $\{0\}$, we are interested in the absorption time $t$ in $\mathbb{Z}_M$, since its distribution is the law of a strong stationary time for $X$. Note that we can again come back to a birth and death chain: for any ball $S \in \mathfrak{V}$, denote $\rho(S)$ its radius (with $\rho(\mathbb{Z}_M) = \lfloor M/2 \rfloor$). Remark that $\rho(\mathcal{X})$ is a birth and death chain, starting from 0, absorbed at $\lfloor M/2 \rfloor$ and whose transition matrix is:

$$
\forall k, l \in [0, \lfloor M/2 \rfloor], \quad \Omega(k, l) =
\begin{cases}
3a - 1, & \text{if } k = 0 = l \\
3 - 6a, & \text{if } k = 0 \text{ and } l = 1 \\
a \frac{2l+1}{2k+1}, & \text{if } k \in [1, \lfloor M/2 \rfloor - 1] \text{ and } |k - l| = 1 \\
1 - 2a, & \text{if } k \in [1, \lfloor M/2 \rfloor - 1] \text{ and } k = l \\
1, & \text{if } k = \lfloor M/2 \rfloor = l \\
0, & \text{otherwise}
\end{cases}
$$
The absorption time of $\rho(\mathcal{X})$ at $[M/2]$ has the same law as $t$ and Karlin and McGregor [13] enable to compute it in terms of the spectrum of $\mathcal{Q}$.

## APPENDIX B. INDEX OF NOTATIONS

The notations being sometimes quite heavy, a listing of the main ones is provided here.

* **State spaces**

* the $3 \times 3$ Heisenberg group $\mathbb{H}_M$: 516

* the $N \times N$ Heisenberg group $\mathbb{H}_{N,M}$: 517

* the set $\mathbb{D}_b$ of $(b+1)$th diagonals and the set $\mathbb{D}_{[b]}$ of the first $(b+1)$th diagonals: 541

* **Subsets**

* generic family $\mathfrak{V}$ of subsets: 518

* centered intervals $\mathfrak{J}$: 519

* the sets $\Omega_{r,s,A}$: 525

* the sets $\Omega_A$: 530, 539

* even/odd centered intervals $\mathfrak{J}_-$: 551

* **Fields**

* special fields: 525

* (general) fields $A \in \mathbb{A}$: 530, 539

* $\tilde{A}^{(1)}, \hat{A}^{(1)}, \tilde{A}^{(2)}, \hat{A}^{(2)}$: 531, 532

* full field $A_\infty$: 532, 540

* $\tilde{A}^-, \hat{A}^+, \tilde{A}^-, \hat{A}^+$: 539

* $(A(d_{[[b-1]]}))_{d_{[[b-1]]} \in \mathbb{D}_{[[b-1]]}}$: 541

* $A'(d_{[[b-1]]})$: 542, 543

* $A^{\cup,I}$ and $A^{\cap,I}$: 544

* $(A(x_{[[2,N-1]]}))_{x_{[[2,N-1]]}}$: 549

* **Markov kernels**

* $P$ for the primal chain: 518, 524, 539, 549

* link $\Lambda$ from the dual state space to the primal state space: 519

* $\mathfrak{P}$ for the dual chain: 519, 522, 523, 552, 553, 554

* $\mathfrak{Q}$ for fields: 532, 540, 546, 550

* unweighted $\mathfrak{R}$ for fields: 536, 546

* the last column $C_N[X]$ : 549

* **Markov chains**

* $[X, Y, Z]$ on $\mathbb{H}_M$: 516

* $[X] := [X_{k,l}]_{1 \le k<l \le N, n \in \mathbb{Z}_+}$ on $\mathbb{H}_{N,M}$: 517

* the dual chain $\mathcal{X}$: 519, 524

* the primal chain $X$: 519

* the primal chains $D_b$ and $D_{[b]}$ respectively on $\mathbb{D}_b$ and $\mathbb{D}_{[b]}$: 541

* the dual chain $\mathcal{X}_b$ to $D_{[b]}$: 543

* **Strong stationary/equilibrium times**

* $\tau$ for $[X, Y, Z]$ or $[X]$ : 516, 517

* $\hat{\tau}$ for $Z$ : 516

* $\tilde{\tau}$ for $(Y, Z)$ or for the last column of $[X]$ : 517, 518

* $t$ for the random walk on $\mathbb{Z}_M$ or $\mathbb{H}_M$: 523, 525

* $t_b$ for $D_{[b]}$ : 543

* **Random mappings**

* generic $\psi_S$ or $\psi_\Omega$ for particular subsets $\Omega$: 519, 526

* $\psi_{\{0\}}$: 520, 551
o $\tilde{\phi}_1, \phi_2, \phi_3, \phi_4$: 521

o $\tilde{\phi}^{(0)}, \tilde{\phi}^{(0)}, \tilde{\phi}^{(1)}, \tilde{\phi}^{(1)}, \tilde{\phi}^{(2)}, \tilde{\phi}^{(2)}, \tilde{\phi}^{(3)}$: 526, 526

o $\tilde{\phi}_A^{(1)}, \tilde{\phi}_A^{(1)}, \tilde{\phi}_A^{(2)}, \tilde{\phi}_A^{(2)}, \tilde{\phi}^{(3)}$: 531

o sign functions $\tilde{\phi}_A, \tilde{\phi}_A$: 530, 539

o $\tilde{\phi}_A^{-}, \tilde{\phi}_A^{+}, \tilde{\phi}_A^{-}, \tilde{\phi}_A^{+}$: 539

o base set transformations $F_{I,\epsilon}$: 541

o $\phi_{\Omega,I,\epsilon}$: 542

o sign functions $\varphi_A(I, \cdot)$: 542

*Acknowledgements.* This paper was motivated by a talk of Evita Nestoridi dealing with the convergence to equilibrium of discrete Heisenberg walks (based on a forthcoming work with Allan Sly [18]), during the conference for the 75th birthday of Persi Diaconis. In the ensuing discussion, it appeared no strong stationary time was known for these models. I’m also very endebted to Reda Chhaibi, whose simulations based on a first version of this paper have shown it was quite erroneous! It led to this revised version and to his new simulations [6]. Finally I’m grateful to the referee for his help in improving the paper.

## REFERENCES

[1] D. Aldous and P. Diaconis, Shuffling cards and stopping times. *Am. Math. Monthly* **93** (1986) 333–348.

[2] E. Breuillard and P.P. Varjú, Cut-off phenomenon for the $ax + b$ Markov chain over a finite field, 2019.

[3] D. Bump, P. Diaconis, A. Hicks, L. Miclo and H. Widom, An exercise(?) in Fourier analysis on the Heisenberg group. *Ann. Fac. Sci. Toulouse Math.* **26** (2017) 263–288.

[4] D. Bump, P. Diaconis, A. Hicks, L. Miclo and H. Widom, Useful bounds on the extreme eigenvalues and vectors of matrices for Harper’s operators. in Large Truncated Toeplitz Matrices, Toeplitz Operators, and Related Topics. Vol. 259 of *Oper. Theory Adv. Appl.* Birkhäuser/Springer, Cham (2017), 235–265.

[5] S. Chatterjee and P. Diaconis, Speeding up Markov chains with deterministic jumps, arXiv preprint 2004.11491. April 2020.

[6] R. Chhaibi, https://github.com/redachhaibi/StrongStationaryTimes. July 2021.

[7] P. Diaconis and J.A. Fill, Strong stationary times via a new form of duality. *Ann. Probab.* **18** (1990) 1483–1522.

[8] P. Diaconis and L. Miclo, On times to quasi-stationarity for birth and death processes. *J. Theoret. Probab.* **22** (2009) 558–586.

[9] S. Eberhard and P.P. Varjú, Mixing time of the Chung–Diaconis–Graham random process, 2020.

[10] J.A. Fill, The passage time distribution for a birth-and-death chain: strong stationary duality gives a first stochastic proof. *J. Theoret. Probab.* **22** (2009) 543–557.

[11] J. Hermon and S. Thomas, Random Cayley graphs I: cutoff and geometry for Heisenberg groups, 2019.

[12] L. Hörmander, Hypoelliptic second order differential equations. *Acta Math.* **119** (1967) 147–171.

[13] S. Karlin and J. McGregor, Coincidence properties of birth and death processes. *Pacific J. Math.* **9** (1959) 1109–1140.

[14] D.A. Levin, Y. Peres and E.L. Wilmer, Markov Chains and Mixing Times. American Mathematical Society, Providence, RI (2009).

[15] L. Miclo, Remarques sur l'hypercontractivité et l'évolution de l'entropie pour des chaînes de Markov finies. in Séminaire de Probabilités, XXXI. Vol, 1655 of *Lecture Notes in Math.* Springer, Berlin (1997), 136–167.

[16] L. Miclo, Duality and hypoellipticity: one-dimensional case studies. *Electron. J. Probab.* **22** (2017) 32.

[17] L. Miclo, On the construction of measure-valued dual processes. *Electron. J. Probab.* **25** (2020) 1–64.

[18] E. Nestoridi and A. Sly, arXiv preprint 2012.08731. December 2020.

[19] I. Pak, *Random Walks on Groups: Strong Uniform Time Approach*. PhD Thesis, Harvard University. ProQuest LLC, Ann Arbor, MI (1997).

[20] J.W. Pitman, One-dimensional Brownian motion and the three-dimensional Bessel process. *Adv. Appl. Probab.* **7** (1975) 511–526.

[21] J.G. Propp and D.B. Wilson, Exact sampling with coupled Markov chains and applications to statistical mechanics. in *Proceedings of the Seventh International Conference on Random Structures and Algorithms (Atlanta, GA, 1995)*, Vol. 9, (1996) 223–252.
[22] L. Saloff-Coste, Random walks on finite groups, in Probability on Discrete Structures. Vol. 110 of *Encyclopaedia Math. Sci.*. Springer, Berlin (2004) 263–346.

<figure><img src="image_3.png" /></figure>

Please help to maintain this journal in open access!

This journal is currently published in open access under the **Subscribe to Open model** (S2O). We are thankful to our subscribers and supporters for making it possible to publish this journal in open access in the current year, free of charge for authors and readers.

Check with your library that it subscribes to the journal, or consider making a personal donation to the S2O programme by contacting [subscribers@edpsciences.org](mailto:subscribers@edpsciences.org).

More information, including a list of supporters and financial transparency reports, is available at [https://edpsciences.org/en/subscribe-to-open-s2o](https://edpsciences.org/en/subscribe-to-open-s2o).