Imelda Elohor Agbedo, Ophokpokpo Matthew Salami, Ojiyovwi Rhoda Osanakpa, Oluranran Clinton Kayoh, Ifeanyi Jeff Ugbene
Department of Mathematics, Federal University of Petroleum Resources, Effurun, Nigeria.
DOI: 10.4236/ojdm.2026.163003   PDF    HTML   XML   9 Downloads   78 Views   Citations

Abstract

Let $X_n=\left\{1,2,\cdots ,n\right\}$ and let $T_n$ denote the full transformation semigroup of all $n^n$ maps $\alpha :X_n\to X_n$ . Each $\alpha \in T_n$ induces a functional digraph ${\Gamma }_{\alpha }$ whose vertex set is $X_n$ and whose arc set is $\left\{\left(x,\alpha \left(x\right)\right):x\in X_n\right\}$ . Because every vertex has out-degree exactly one, ${\Gamma }_{\alpha }$ belongs to the class of functional (mapping) digraphs. The Eulerian members of this class are precisely the functional digraphs induced by permutations $\alpha \in S_n\subset T_n$ : there are $n!$ Eulerian functional digraphs on $X_n$ , and their isomorphism classes are in bijection with the integer partitions of $n$ . A functional digraph is connected (strongly connected) if and only if $\alpha$ is a single $n$ -cycle; there are $\left(n-1\right)!$ such digraphs, forming a single isomorphism class. This paper studies lazy simple random walks on connected Eulerian functional digraphs of $T_n$ from the perspective of quantitative mixing theory. Our main results are as follows: 1) ${\Gamma }_{\alpha }$ is Eulerian if and only if $\alpha \in S_n$ . The number of Eulerian functional digraphs on $X_n$ is $n!$ , with $p\left(n\right)$ isomorphism classes (one per integer partition of $n$ ), of which exactly one class (the directed $n$ -cycle) is connected. 2) For the connected case ($\alpha$ an $n$ -cycle), the uniform mixing time satisfies $c{n}^2\le t_{unif}\le C{n}^2$ for absolute constants $c,C>0$ . 3) For the Eulerian directed graph $F_n$ on $n+1$ vertices formed by gluing two directed $n/2$ -cycles at a common vertex (a natural object associated with permutations of cycle type $\left(n/2,n/2\right)$ in $S_n$ , though not itself a functional digraph), modifying the laziness parameter on a fraction of vertices from 1/2 to $p^{*}=2/\left(\sqrt{5}+1\right)$ reduces $t_{mix}$ from $\Theta \left(n^2\right)$ to $\Theta \left(n^{3/2}\right)$ . 4) For the $k$ -exploration time $T_k$ (first time $k$ distinct vertices are visited) on a connected Eulerian functional digraph, ${\mathbb{E}}_v\left[T_k\right]=O\left(k^2\right)$ . The proofs combine the spectral-profile technique, local central limit theorems, Diophantine approximation via the three-distance theorem, and the cycle structure of $S_n$ .

Keywords

Full Transformation Semigroup, Functional Digraph, Eulerian Digraph, Lazy Random Walk, Mixing Time, Sensitivity, Spectral Profile, Exploration Time, Three-Distance Theorem

Share and Cite:

1. Introduction

The full transformation semigroup $T_n$ consists of all $n^n$ functions $\alpha :X_n\to X_n$ on the set $X_n=\left\{1,\cdots ,n\right\}$ , composed by $\left(\alpha \beta \right)\left(x\right)=\beta \left(\alpha \left(x\right)\right)$ . It is one of the most studied objects in finite semigroup theory, and its combinatorial properties have been investigated through its associated functional digraph ${\Gamma }_{\alpha }=\left(X_n,A_{\alpha }\right)$ , where $A_{\alpha }=\left\{\left(x,\alpha \left(x\right)\right):x\in X_n\right\}$ [1]-[7]. Since $d^{+}\left(x\right)=1$ for all $x$ , the digraph ${\Gamma }_{\alpha }$ is precisely a functional (mapping) digraph in the sense of Harris [8] and Harary [9]. By the structure theorem for functional digraphs, each weakly connected component of ${\Gamma }_{\alpha }$ contains a unique directed cycle, with directed trees (rho-shaped components) attached to the cycle vertices.

The algebraic and combinatorial study of $T_n$ through ${\Gamma }_{\alpha }$ has a rich history. Howie [10] [11], characterized the subsemigroup generated by the idempotents of $T_n$ . The connectivity of ${\Gamma }_{\alpha }$ in terms of $\text{rank}\left(\alpha \right)$ was systematically developed in [12], which counted strongly connected, strictly unilaterally connected, strictly weakly connected, Hamiltonian, Eulerian and self-converse digraphs. Further structural results appear in East, Gadouleau and Mitchell [13], Yang and Yang [14] [15], and Wright [16].

Random walks on directed graphs have recently attracted substantial attention following the realisation that the classical theory for undirected graphs which exploits spectral methods and electrical-network analogies does not directly apply in the directed setting [17]-[22]. Boczkowski, Peres and Sousi [23] proved that for Eulerian digraphs on $n$ vertices and $m$ edges (a natural directed analogue of the undirected case), the uniform mixing time [24] of the lazy random walk satisfies $t_{unif}=O\left(mn\right)$ , and established exploration-time bounds $O\left(k^3\right)$ and $O\left(k^2\right)$ (regular case) extending those of Barnes-Feige [25] to the directed setting. Crucially, they showed that in sharp contrast to the undirected case the mixing time can be sensitive to the laziness parameter: changing the laziness at some vertices by a constant factor can change $t_{mix}$ by a polynomial factor changing the [26]. Mixing times have also been used in other contexts, for instance as a tool to obtain lower bounds on the Estrada index, a spectral measure of network robustness [27]. On the algebraic side, the skew eigenvalues of oriented bipartite graphs have been studied via their characteristic polynomials [28]. However, neither of these lines of work touches the combinatorial structure of functional digraphs arising from transformation semigroups, nor do they address the mixing or exploration behaviour of random walks on such digraphs.

The present paper investigates precisely which elements of $T_n$ produce connected Eulerian digraphs, and analyses the mixing and exploration times of lazy random walks on these digraphs within the algebraically structured family $\left\{{\Gamma }_{\alpha }:\alpha \in S_n\right\}$ . This links two fields, finite transformation semigroups and quantitative mixing theory, that have not previously been connected in the literature.

1.1. Statement of Main Results

Throughout the paper, $n\ge 2$ is an integer, $T_n$ is the full transformation semigroup on $X_n=\left\{1,\cdots ,n\right\}$ , $S_n\subset T_n$ is the symmetric group (group of units of $T_n$ ), and $X$ denotes the lazy simple random walk on ${\Gamma }_{\alpha }$ (defined precisely in Section 2.4).

Theorem 1.1 (Characterisation of Eulerian functional digraphs). Let $\alpha \in T_n$ . The functional digraph ${\Gamma }_{\alpha }$ is Eulerian (i.e. $d^{+}\left(v\right)=d^{-}\left(v\right)$ for every $v\in X_n$ ) if and only if $\alpha \in S_n$ . Consequently:

(1) The number of $\alpha \in T_n$ for which ${\Gamma }_{\alpha }$ is Eulerian is $n!$ .

(2) The number of $\alpha \in T_n$ for which ${\Gamma }_{\alpha }$ is connected and Eulerian is $\left(n-1\right)!$ .

Every Eulerian functional digraph ${\Gamma }_{\alpha }$ is self-converse (isomorphic to its arc-reversal). The number of isomorphism classes of connected Eulerian functional digraphs on $X_n$ equals the number of integer partitions of $n$ .

Theorem 1.2 (Mixing-time bounds). There exist absolute constants $c,C>0$ such that for all $n\ge 2$ and any $\alpha \in S_n$ which is a single $n$ -cycle (so that ${\Gamma }_{\alpha }$ is a directed $n$ -cycle),

$c{n}^2\le t_{unif}\le C{n}^2.$

Theorem 1.3 (Exploration times). Let $\alpha \in S_n$ and suppose ${\Gamma }_{\alpha }$ is connected. There exist absolute constants $c_1,c_2>0$ such that for all $k\le n$ and all starting vertices $v\in X_n$ :

(1) (Equidistributed cycle type.) If every cycle of $\alpha$ has the same length, then ${\mathbb{E}}_v\left[T_k\right]\le c_1{k}^2$ .

(2) (General.) ${\mathbb{E}}_v\left[T_k\right]\le c_2{k}^3$ .

Here $T_k=\inf \left\{t\ge 0:\left|\left\{X_0,X_1,\cdots ,X_t\right\}\right|=k\right\}$ is the first time the walk has visited $k$ distinct vertices.

Remark 1.4. The bounds in Theorems 1.2 and 1.3 are consequences of the general $O\left(mn\right)$ mixing-time theorem and $O\left(k^2\right)/O\left(k^3\right)$ exploration-time theorems of [23] applied with $m=n$ (one directed arc per vertex in a functional digraph). The novelty of the present work lies in 1) identifying exactly which elements of $T_n$ give rise to connected Eulerian functional digraphs and computing their count, 2) establishing tight bounds for the single-cycle case, 3) demonstrating sensitivity for a natural two-cycle family arising from $T_n$ , and 4) the explicit connection between the algebraic cycle structure of $S_n$ and the mixing behaviour of the associated random walk.

Theorem 1.5 (Sensitivity of mixing). Let $n$ be even and let ${\alpha }_n\in S_n$ be a permutation of cycle type $\left(n/2,n/2\right)$ , so that ${\Gamma }_{{\alpha }_n}$ consists of two directed cycles $C_1,C_2$ of length $n/2$ sharing a common base vertex 0. Define a modified laziness assignment: vertices in the segment $\left[n/4,3n/4\right]$ (indices modulo $n/2$ ) of $C_1$ have laziness ${\alpha }^{*}=2/\left(\sqrt{5}+1\right)$ ; all other vertices have laziness 1/2. Then there exist positive constants $c_1,c_2$ (independent of $n$ ) such that for all $n$ :

$c_1{n}^{3/2}\le t_{mix}\le t_{unif}\le c_2{n}^{3/2}.$

By contrast, with laziness 1/2 uniformly at all vertices, $t_{mix}\asymp n^2$ .

1.2. Organisation of the Paper

Section 2 collects background on $T_n$ , functional digraphs, and Markov chain mixing. Section 3 proves Theorem 1.1. Section 4 establishes Theorem 1.2, including the lower bound and a cover-time corollary. Section 5 proves Theorem 1.3. Section 6 proves Theorem 1.5, the sensitivity result.

2. Preliminaries

2.1. The Full Transformation Semigroup

Let $X_n=\left\{1,2,\cdots ,n\right\}$ . The full transformation semigroup $T_n$ is the set of all functions $\alpha :X_n\to X_n$ , equipped with the composition $\left(\alpha \beta \right)\left(x\right)=\beta \left(\alpha \left(x\right)\right)$ . It satisfies $\left|T_n\right|=n^n$ . The image and rank of $\alpha \in T_n$ are

$\text{im}\left(\alpha \right)=\left\{\alpha \left(x\right):x\in X_n\right\},\text{rank}\left(\alpha \right)=\left|\text{im}\left(\alpha \right)\right|.$

The symmetric group $S_n\subset T_n$ consists of all bijections $\alpha :X_n\to X_n$ ; it has $n!$ elements and is the (unique) group of units of $T_n$ .

2.2. Functional Digraphs

Definition 2.1. The functional digraph of $\alpha \in T_n$ is ${\Gamma }_{\alpha }=\left(X_n,A_{\alpha }\right)$ with $A_{\alpha }=\left\{\left(x,\alpha \left(x\right)\right):x\in X_n\right\}$ .

Every vertex of ${\Gamma }_{\alpha }$ satisfies $d^{+}\left(v\right)=1$ . The in-degree of a vertex $y$ equals $\left|{\alpha }^{-1}\left(y\right)\right|$ . The following structural fact is standard; see, for instance, ([1], Chapter 1).

Proposition 2.1 (Structure theorem for functional digraphs). Each weakly connected component of ${\Gamma }_{\alpha }$ contains exactly one directed cycle, together with directed trees rooted at the cycle vertices (with edges directed toward the root).

Example 2.2. For $n=4$ and $\alpha =\left(\begin{array}{cccc}1& 2& 3& 4\\ 2& 3& 1& 2\end{array}\right)$ (so $\alpha \left(1\right)=2$ , $\alpha \left(2\right)=3$ , $\alpha \left(3\right)=1$ , $\alpha \left(4\right)=2$ ), the digraph ${\Gamma }_{\alpha }$ has the directed 3-cycle $1\to 2\to 3\to 1$ with vertex 4 feeding into vertex 2 via the arc (4, 2). Here $\text{rank}\left(\alpha \right)=3$ .

2.3. Connectivity and Rank

The following characterisation is proved in the work [12]; we recall it here for the reader’s convenience.

Proposition 2.2 ([12]). Let $\alpha \in T_n$ . Then:

(1) ${\Gamma }_{\alpha }$ is strongly connected if and only if $\text{rank}\left(\alpha \right)=n$ , equivalently $\alpha \in S_n$ .

(2) ${\Gamma }_{\alpha }$ is strictly unilaterally connected if and only if $\text{rank}\left(\alpha \right)=n-1$ .

(3) ${\Gamma }_{\alpha }$ is strictly weakly connected if and only if $\text{rank}\left(\alpha \right)\in \left\{2,\cdots ,n-2\right\}$ and ${\Gamma }_{\alpha }$ has exactly one directed cycle.

(4) ${\Gamma }_{\alpha }$ is disconnected if and only if ${\Gamma }_{\alpha }$ has at least two directed cycles.

Moreover, the number of $\alpha \in T_n$ for which ${\Gamma }_{\alpha }$ is strongly connected is $\left(n-1\right)!$ .

2.4. Lazy Random Walk and Mixing Times

Definition 2.3. Let $G=\left(V,E\right)$ be a strongly connected directed graph with $d^{+}\left(v\right)\ge 1$ for all $v$ . The lazy simple random walk on $G$ is the Markov chain $X={\left(X_t\right)}_{t\ge 0}$ on $V$ with transition probabilities

$P\left(v,v\right)=\frac{1}{2},P\left(v,w\right)=\frac{1}{2d^{+}\left(v\right)}1\left[\left(v,w\right)\in E\right],v\ne w.$

When $G$ is Eulerian (and hence strongly connected for connected $G$ ), the uniform distribution $\pi \left(v\right)=1/n$ is stationary for $P$ . For an irreducible Markov chain with transition matrix $P$ and stationary distribution $\pi$ , we define the ${ℒ}^{\infty }$ mixing time (also called the uniform mixing time)

$t_{unif}\left(\epsilon \right)=\min \left\{t\ge 0:\underset{x,y\in V}{\max }\left|\frac{P^t\left(x,y\right)}{\pi \left(y\right)}-1\right|\le \epsilon \right\},t_{unif}=t_{unif}\left(1/4\right),$ (2.1)

and the total variation mixing time

$t_{mix}\left(\epsilon \right)=\min \left\{t\ge 0:\underset{x\in V}{\max }{\Vert P^t\left(x,\cdot \right)-\pi \Vert }_{\text{TV}}\le \epsilon \right\},t_{mix}=t_{mix}\left(1/4\right).$ (2.2)

These are related by $t_{mix}\le t_{unif}$ ; see ([29], Chapter 4).

2.5. The Spectral Profile

The main analytic tool is the spectral profile introduced by Goel, Montenegro and Tetali [30]. Let $P$ be the transition matrix of the lazy walk on a connected Eulerian digraph with stationary distribution $\pi$ . The Dirichlet form of a function $f:V\to R$ is

${ℰ}_P\left(f,f\right)=\frac{1}{2}{\displaystyle \sum }_{v,w\in V}{\left(f\left(v\right)-f\left(w\right)\right)}^2\pi \left(v\right)P\left(v,w\right).$ (2.3)

For $\varnothing \ne S\subseteq V$ define

$\lambda \left(S\right)=\underset{f\ge 0,\text{supp}\left(f\right)\subseteq S}{\inf }\frac{{ℰ}_{P\left(f,f\right)}}{\text{Var}\pi \left(f\right)},$

and the spectral profile $\Lambda :\left[{\pi }_{*},1\right]\to \left[0,\infty \right)$ by

$\Lambda \left(r\right)=\underset{{\pi }_{*}\le \pi \left(S\right)\le r}{\inf }\lambda \left(S\right),{\pi }_{*}=\underset{v\in V}{\min }\pi \left(v\right).$

Theorem 2.4 {Spectral profile theorem, ([30], Theorem 1.1)}. Let $P$ be an irreducible transition matrix with $P\left(x,x\right)\ge \delta >0$ for all $x$ . Then for every $a>0$ ,

$t_{unif}\left(a\right)\le 2\lceil {\displaystyle {\int }_{4{\pi }_{*}}^{4/a}\frac{\text{d}r}{\delta r\Lambda \left(r\right)}}\rceil .$

2.6. Symmetrisation and the Eulerian Property

A crucial tool for analysing non-reversible Eulerian chains is the following. Let $\widehat{P}$ be the time-reversal of $P$ , defined by $\pi \left(v\right)\widehat{P}\left(v,u\right)=\pi \left(u\right)P\left(u,v\right)$ . On an Eulerian digraph, reversing time is equivalent to reversing all arc directions. The symmetrisation is $Q=\left(P+\widehat{P}\right)/2$ .

Lemma 2.1 ([23]). For any function $f:V\to R$ ,

${ℰ}_P\left(f,f\right)={ℰ}_{\widehat{P}}\left(f,f\right)={ℰ}_Q\left(f,f\right).$ (2.4)

Moreover, $Q$ is reversible with stationary distribution $\pi$ , so standard commute-time estimates apply to $Q$ .

3. Eulerian Structure of Γ_α

3.1. Proof of Theorem 1.1

Proof. 1) Since ${\Gamma }_{\alpha }$ is functional, $d^{+}\left(v\right)=1$ for all $x\in X_n$ . The digraph is Eulerian if and only if also $d^{-}\left(v\right)=1$ for all $x$ , i.e. every vertex has exactly one pre-image under $\alpha .$ This is precisely the condition that $\alpha$ is a bijection, so $\alpha \in S_n$ . Since $\left|S_n\right|=n!$ , there are $n!$ Eulerian functional digraphs.

2) By Proposition 2.2(1), ${\Gamma }_{\alpha }$ is strongly connected (equivalently, connected and Eulerian) if and only if $\alpha \in S_n$ and $\text{rank}\left(\alpha \right)=n$ , which forces ${\Gamma }_{\alpha }$ to be a single directed cycle. The number of $n$ -cycles in $S_n$ is $\left(n-1\right)!$ , giving the second count.

3) An Eulerian functional digraph ${\Gamma }_{\alpha }$ ($\alpha \in S_n$ ) consists of $k$ disjoint directed cycles of lengths ${\lambda }_1\ge \cdots \ge {\lambda }_k$ with ${\displaystyle {\sum }_i{\lambda }_i}=n$ . Its arc-reversal ${\Gamma }_{\alpha }^{\text{rev}}$ has the same multiset of directed cycle lengths, so ${\Gamma }_{\alpha }\cong {\Gamma }_{\alpha }^{\text{rev}}$ (both are unions of directed cycles of the same lengths), hence ${\Gamma }_{\alpha }$ is self-converse. Isomorphism classes correspond to cycle-type partitions of $n$ , of which there are $p\left(n\right)$ (the number of partitions of $n$ ).

Remark 3.1. The self-converse property gives a clean semigroup-theoretic meaning to the Eulerian condition: the Eulerian elements of $T_n$ are precisely those whose functional digraph is invariant (up to isomorphism) under arc reversal.

3.2. Cycle-Type Decomposition

Every $\alpha \in S_n$ has a unique cycle-type partition $\lambda \left(\alpha \right)=\left({\lambda }_1\ge \cdots \ge {\lambda }_k\right)$ of $n$ , and ${\Gamma }_{\alpha }$ is the disjoint union of $k$ directed cycles of lengths ${\lambda }_1,\cdots ,{\lambda }_k$ . We record the following for later use.

Proposition 3.1. For $\alpha \in S_n$ , the lazy walk on any connected component of ${\Gamma }_{\alpha }$ is irreducible, and the uniform distribution $\pi \left(v\right)=1/n$ (over all $v\in X_n$ ) is stationary for the lazy walk on ${\Gamma }_{\alpha }$ .

Proof. Each component is a directed cycle, so the walk on it is irreducible, with the uniform distribution on the component being stationary. The global stationary distribution (over disconnected components) is uniform by the bi-stochastic property of the transition matrix.

Remark 3.2. Since Theorem 1.2 concerns connected Eulerian functional digraphs (${\Gamma }_{\alpha }$ a single $n$ -cycle, or more generally $\alpha \in S_n$ with connected ${\Gamma }_{\alpha }$ ), the mixing-time analysis is restricted to the strongly connected case throughout Sections 4 and 6.

4. Mixing-Time Bounds

4.1. Upper Bounds via the Spectral Profile

Lemma 4.1 (Spectral profile bound). Let $\alpha \in S_n$ be such that ${\Gamma }_{\alpha }$ is connected (a single directed $n$ -cycle, $m=n$ ). For every $r\in \left[{\pi }_{*},1\right]$ ,

$\Lambda \left(r\right)\ge \frac{1}{r{n}^2}.$ (4.1)

Proof. We consider the lazy simple random walk on a directed $n$ -cycle ${\Gamma }_{\alpha }$ , which represents the unique connected Eulerian functional digraph topology. Let $P$ denote the transition matrix of this lazy walk, defined by:

$P\left(v,v\right)=\frac{1}{2},P\left(v,w\right)=\frac{1}{2}{1}_{\left\{w=\alpha \left(v\right)\right\}},v\ne w.$

The uniform distribution $\pi \left(v\right)=1/n$ is stationary because the underlying digraph is Eulerian. We evaluate the spectral profile $\Lambda \left(r\right)$ introduced in [30]:

$\Lambda \left(r\right)=\underset{\pi \left(S\right)\le r}{\inf }\lambda \left(S\right),\lambda \left(S\right)=\underset{\begin{array}{c}f\ge 0\\ suppf\subseteq S\end{array}}{\inf }\frac{{ℰ}_P\left(f,f\right)}{Va{r}_{\pi }\left(f\right)},$

where ${ℰ}_P\left(f,f\right)=\frac{1}{2}{\displaystyle {\sum }_{v,w}\pi \left(v\right)P\left(v,w\right){\left(f\left(v\right)-f\left(w\right)\right)}^2}$ is the associated Dirichlet form.

Step 1—Symmetrisation. For a non-reversible Markov chain, the spectral profile is controlled by the reversible symmetrisation:

$Q=\frac{P+\widehat{P}}{2},$

where $\widehat{P}$ is the time-reversal defined by $\pi \left(v\right)P\left(v,w\right)=\pi \left(w\right)P\left(w,v\right)$ . By ([23], Equation (2.3)), the Dirichlet form satisfies the invariant identity:

${ℰ}_P\left(f,f\right)={ℰ}_{\widehat{P}}\left(f,f\right)={ℰ}_Q\left(f,f\right)\text{for}\text{all}f.$

Consequently, the localized eigenvalue $\lambda \left(S\right)$ for $P$ is identical to the corresponding quantity for $Q$ , implying that $\Lambda \left(r\right)$ is preserved under symmetrisation. The reversible chain $Q$ corresponds exactly to a simple symmetric random walk on an undirected $n$ -cycle with holding probability 1/2.

Step 2—Exit time estimate via the Dirichlet form. For a reversible Markov chain with stationary distribution $\pi$ , it holds for any set $S\subset V$ {see e.g., ([30], Lemma 4.3) or [29]} that:

$\lambda \left(S\right)\ge \frac{1}{\underset{v\in S}{\max }{\mathbb{E}}_v\left[{\tau }_{S^c}\right]},$

where ${\tau }_{S^c}=\inf \left\{t\ge 0:X_t\notin S\right\}$ and ${\mathbb{E}}_v$ denotes the expectation under the symmetrised chain $Q$ initiated at $v$ . This bound confirms that the worst-case expected exit time from $S$ controls the localized spectral gap.

Step 3—Bounding the exit time by the commute time. Under the reversible chain $Q$ , the commute time $\mathcal{C}\left(v,w\right)={\mathbb{E}}_v\left[{\tau }_w\right]+{\mathbb{E}}_w\left[{\tau }_v\right]$ satisfies the commute-time identity {cf. ([29], Proposition 10.6)}:

$\mathcal{C}\left(v,w\right)=\frac{1}{\pi \left(w\right)}{ℛ}_{\text{eff}}\left(v,w\right),$

where ${ℛ}_{\text{eff}}\left(v,w\right)$ is the effective resistance between $v$ and $w$ in the corresponding electrical network. For an undirected $n$ -cycle, the effective resistance between two vertices at distance $\ell$ is exactly $\ell$ . Thus, for any $v,w\in X_n$ , we have:

$\mathcal{C}\left(v,w\right)=n\cdot \ell \left(v,w\right).$

Let $S\subset V$ such that $\pi \left(S\right)=\left|S\right|/n\le r$ . For any $v\in S$ , the undirected distance from $v$ to the complement $S^c$ is at most $\left|S\right|$ , with equality occurring when $S$ forms a contiguous arc. Choosing a vertex $w\in S^c$ that achieves this minimal boundary distance yields $\ell \left(v,w\right)\le \left|S\right|$ . By the commute-time identity and the fact that ${\tau }_{S^c}\le {\tau }_w$ , we obtain:

${\mathbb{E}}_v\left[{\tau }_{S^c}\right]\le {\mathbb{E}}_v\left[{\tau }_w\right]\le \mathcal{C}\left(v,w\right)=n\ell \left(v,w\right)\le n\left|S\right|.$

Step 4—Relating $\left|S\right|$ to $\pi \left(S\right)$ . Substituting the cardinality relation $\left|S\right|=n\pi \left(S\right)\le nr$ into the exit time bound yields:

$\underset{v\in S}{\max }{\mathbb{E}}_v\left[{\tau }_{S^c}\right]\le n\cdot \left(nr\right)=n^{2}r.$

Step 5—Spectral profile lower bound. Applying the exit time maximization to the Dirichlet relation from Step 2 establishes that for every subset $S$ satisfying $\pi \left(S\right)\le r$ :

$\lambda \left(S\right)\ge \frac{1}{n^{2}r}.$

Taking the infimum over all such valid subsets yields the uniform lower bound:

$\Lambda \left(r\right)=\underset{\pi \left(S\right)\le r}{\inf }\lambda \left(S\right)\ge \frac{1}{r{n}^2}\text{for}\text{all}r\in \left[{\pi }_{*},1\right],$

as required to establish the uniform mixing time order.

4.2. Upper and Lower Bound for Single n-Cycle

Proof of Theorem 1.2. On a single $n$ -cycle, the minimal stationary mass is ${\pi }_{*}=1/n$ and the laziness parameter is $\delta =1/2$ . Substituting the spectral profile bound (4.1) into the general convergence framework of Theorem 2.4 yields:

$\begin{array}{c}{t}_{unif}\left(a\right)\le 2\lceil {\displaystyle {\int }_{4/n}^{4/a}\frac{r{n}^2}{\left(1/2\right)r}\text{d}r}\rceil =2\lceil 2n^2{\displaystyle {\int }_{4/n}^{4/a}\text{d}r}\rceil \\ \le 2\lceil 2n^2\cdot \frac{4}{a}\rceil \le \frac{16n^2}{a}+2\end{array}$ (4.2)

Setting $a=1/4$ delivers $t_{unif}\le 64n^2+2=O\left(n^2\right)$ , which establishes the upper bound of Theorem 1.2. For the matching lower bound, let $\alpha \in S_n$ be a single $n$ -cycle. The lazy random walk on this directed cycle is equivalent to a lazy biased random walk on ${\mathbb{Z}}_n$ that moves clockwise with probability 1/2 and remains stationary with probability 1/2. Starting from a fixed vertex $v$ , the position of the walk at time $t$ concentrates near the expected position $v+\frac{t}{2}\left(\mathrm{mod}n\right)$ with a standard deviation of order $O\left(\sqrt{t}\right)$ . The distribution achieves total variation mixing only when this standard deviation scales to the order of the space circumference $n$ , which requires $t=\Omega \left(n^2\right)$ . More precisely, letting ${\mu }_t$ denote the distribution of $X_t$ initialized at $v$ , choosing $t=c_0{n}^2$ for a sufficiently small absolute constant $c_0$ confines the probability mass of ${\mu }_t$ to an arc of length $O\left(n\right)$ in ${\mathbb{Z}}_n$ . This yields the total variation distance inequality ${\Vert {\mu }_t-\pi \Vert }_{TV}\ge 1/4$ , which completes the proof.

4.3. Cover Time

Corollary 4.1. For the lazy random walk on a connected Eulerian functional digraph ${\Gamma }_{\alpha }$ ($\alpha \in S_n$ , $n$ -cycle),

$\underset{v\in X_n}{\max }{\mathbb{E}}_v\left[{\tau }_{cov}\right]\le c{n}^2$

for an absolute constant $c>0$ .

Proof. We use the DFS spanning-tree argument of ([23], Section 4). For the undirected version of ${\Gamma }_{\alpha }$ (the $n$ -cycle), the only spanning tree is a path, and its two directed commute times each satisfy $\text{Com}\left(v_i,v_{i+1}\right)\le m\cdot 1=n$ by the commute-time bound of ([23], Lemma 4.1). Summing over the $n-1$ edges of the spanning path gives ${\mathbb{E}}_v\left[{\tau }_{cov}\right]\le \left(n-1\right)\cdot n\le n^2$ .

5. Exploration Times

5.1. Commute-Time Bound for Functional Digraphs

Lemma 5.1 (Commute times). Let $\alpha \in S_n$ with ${\Gamma }_{\alpha }$ connected, and let $v,w\in X_n$ be at undirected distance $\ell$ in ${\Gamma }_{\alpha }$ . Then the commute time $\text{Com}\left(v,w\right)=\text{H}\left(v,w\right)+\text{H}\left(w,v\right)$ satisfies

$\text{Com}\left(v,w\right)\le n\ell .$

Proof. Since ${\Gamma }_{\alpha }$ is a connected Eulerian functional digraph with $\alpha \in S_n$ , it is a single directed $n$ -cycle (Theorem 1.1), which implies $m=n$ . The result follows directly from ([23], Lemma 4.1) with $m=n$ : on each excursion from $v$ back to itself, $w$ is hit with probability at least $1/d^{+}\left(v\right)=1$ , so $\text{H}\left(v,w\right)\le n$ . Accounting for the path length $\ell$ along the cycle yields $\text{H}\left(w,v\right)\le n\left(\ell -1\right)+n=n\ell$ . Both the Eulerian and strong connectivity conditions required by [23] hold uniformly for the directed $n$ -cycle.

5.2. Proof of Theorem 1.3(1): Equidistributed Case

Proof. We may assume $k\le n/2$ ; otherwise, the exploration time is bounded by the total cover time $\mathbb{E}\left[{\tau }_{cov}\right]=O\left(n^2\right)=O\left(k^2\right)$ via Corollary 4.1. Set $t=C{k}^2$ for a constant $C$ to be determined. Since the stationary distribution $\pi \left(v\right)=1/n$ is uniform (Proposition 3.1) and the transition matrix $P$ is bi-stochastic, it holds for every $v\in X_n$ that:

${\displaystyle \sum }_{w\in X_n}{\mathbb{E}}_w\left[N_v\left(t\right)\right]=t,$

where $N_v\left(t\right)=\left|\left\{s<t:X_s=v\right\}\right|$ counts the visits to $v$ up to time $t$ . By Markov’s inequality, the set of states $A=\left\{w:{\mathbb{E}}_w\left[N_v\left(t\right)\right]>s\right\}$ has cardinality bounded by $\left|A\right|\le t/s$ .

For $v\in A$ , we invoke the return-time bounding technique of ([23], Lemma 5.1). Because the transition matrix on our directed cycle is bi-stochastic, the uniform mass balance ensures that the green-function potential estimates hold without requiring a reversible step. Applying the commute-time bounds from Lemma 5.1 yields:

${\mathbb{E}}_v\left[N_v\left(t\right)\right]\le {\mathbb{E}}_v\left[N_v\left(A^c\right)\right]+s\le 10\cdot \frac{t}{s}+s.$

Optimizing over the threshold parameter by setting $s=\sqrt{10t}$ gives ${\mathbb{E}}_v\left[N_v\left(t\right)\right]\le 2\sqrt{10t}\le 7\sqrt{t}$ . Let $v_1,v_2,\cdots$ be the distinctly visited vertices in chronological order. Applying Markov’s inequality to the total allocation sum ${\displaystyle {\sum }_{i=1}^{k-1}{N}_{v_i}\left(t\right)}=t$ , we obtain:

${\mathbb{P}}_v\left[T_k\ge t\right]\le \frac{7k\sqrt{t}}{t}=\frac{7k}{\sqrt{t}}.$

Setting $t=196k^2$ forces this exit probability to be ≤1/2. A standard geometric trials argument then confirms that the total expected exploration time satisfies ${\mathbb{E}}_v\left[T_k\right]\le 2t=392k^2=O\left(k^2\right)$ .

5.3. Hamiltonian Cube and Phase Decomposition

To obtain the general $O\left(k^3\right)$ bound (Theorem 1.3(2)), we control the number of distinct vertices visited by the walk in the worst case, which may scale up to $n$ . The strategy decomposes the walk into phases whose lengths are bounded by the expected hitting times to specific target sets. This decomposition relies on a Hamiltonian cycle in the undirected cube of the graph, a combinatorial property independent of edge orientation.

Lemma 5.2 (Hamiltonian cycle in $G^3$ ). For any connected undirected graph $G$ , the graph $G^3$ (where vertices are adjacent if their distance in $G$ is at most 3) contains a Hamiltonian cycle.

Proof. See [23]. The proof proceeds via induction on a spanning tree to construct an explicit vertex ordering.

Fix a Hamiltonian cycle $v_1,v_2,\cdots ,v_n,v_{n+1}=v_1$ in the undirected cube of ${\Gamma }_{\alpha }$ . Because the underlying digraph is a directed $n$ -cycle, the undirected distances between vertices are given by the minimal arc distance around the cycle, ensuring that $d_{undir}\left(v_i,v_{i+1}\right)\le 3$ for all $i$ . Following the frameworks of [23] and [25], we implement a phase decomposition of the walk on the original directed $n$ -cycle, utilizing the fixed ordering of the undirected cube to categorize vertices.

Phase definition. At the beginning of phase $i$ , let $Y_i$ denote the set of previously visited vertices. The final vertex visited in phase $i-1$ is $s_i$ , and its successor on the Hamiltonian cycle according to the fixed ordering is $r_i$ . A vertex $v_j\notin Y_i$ is defined as good in phase $i$ if for every $\ell \le n$ :

$\left|\left\{v_j,v_{j+1},\cdots ,v_{j+\ell -1}\right\}\cap Y_i\right|\le \frac{\ell }{2},$

where indices are taken modulo $n$ . Let $U_i$ denote the set of good vertices, and $B_i=V\setminus \left(U_i\cup Y_i\right)$ denote the set of bad vertices. Phase $i$ terminates when the walk either reaches $r_i$ or hits any vertex in $U_i$ . This configuration ensures that each successive phase either advances along the cycle ordering or discovers a good vertex.

Lemma 5.3 (Number of phases, [25]). At most $2k$ phases are required before $k$ distinct vertices are visited. Moreover, if $\left|Y_i\right|\le n/2$ , then $\left|B_i\right|\le \left|Y_i\right|$ .

Proof. See [23] or the original combinatorial formulation in [25].

Lemma 5.4 (Phase length bound). For a connected Eulerian functional digraph, let $W\bigsqcup Z=X_n$ be a partition such that $W$ induces a connected subgraph, and let $s\in W\cap \partial Z$ under undirected adjacency. Then

$\text{H}\left(s,Z\right)\le 12{\left|W\right|}^2.$

Proof. We specialize the proof of [23] to the functional case where $m=n$ . Let

$W_1=\left\{v\in W:d^{+}\left(v\right)\le 2\left|W\right|\right\},W_2=W\setminus W_1.$

Because each vertex in the directed $n$ -cycle satisfies $d^{+}\left(v\right)=1$ , the condition $d^{+}\left(v\right)\le 2\left|W\right|$ holds automatically for all $\left|W\right|\ge 1$ . Thus, $W_2=\varnothing$ and $W_1=W$ . For any $s\in W\cap \partial Z$ , since $W_2$ is empty, we apply the general Eulerian contraction bound from [23]:

$\text{H}\left(s,Z\right)\le {\left|W_1\right|}^2+2\left|E\left(W_1,Z\cup W_2\right)\right|\le {\left|W\right|}^2+2\cdot \left(2\left|W\right|\cdot \left|W\right|\right)=5{\left|W\right|}^2.$

The factor $2\left|E\left(W_1,Z\cup W_2\right)\right|$ is bounded by $4{\left|W\right|}^2$ because each vertex has degree 2 on the underlying cycle. To maintain structural consistency with universal bounds in the literature and account for boundary configurations where $W_2$ is non-empty, we retain the conservative assignment $\text{H}\left(s,Z\right)\le 12{\left|W\right|}^2$ .

5.4. Proof of Theorem 1.3(2)

Proof. If $2k>n$ , the expectation $\mathbb{E}\left[T_k\right]$ is bounded directly by the global cover time, which via Corollary 4.1 satisfies $\mathbb{E}\left[T_k\right]\le c{n}^2\le 8c{k}^3$ . We therefore assume for the remainder of the proof that $2k\le n$ .

Let ${\Phi }_i$ denote the length of phase $i$ executed prior to visiting $k$ distinct vertices. The phase starts at $s_i$ with target set $Z_i=\left\{r_i\right\}\cup U_i$ , where $r_i$ is the successor of $s_i$ on the Hamiltonian cycle and $U_i$ represents the good vertices. The complement $W_i=Y_i\cup B_i\setminus \left\{r_i\right\}$ satisfies the conditions of Lemma 5.4 with$Z=Z_i$ . Because the Hamiltonian cycle lies in the undirected cube $G^3$ , the undirected distance satisfies $d_{undir}\left(s_i,r_i\right)\le 3$ . Mapping these tracking constraints to the general Eulerian framework of ([23], Theorem 1.8, proof), the phase lengths are governed by the quadratic volume of the transient subsets, yielding the conditional estimate:

$\mathbb{E}\left[{\Phi }_i|Y_i,s_i\right]\le 3\times 12{\left(2\left|Y_i\right|\right)}^2=144{\left|Y_i\right|}^2\le 144k^2.$

The scalar factor of 3 accounts for the maximum path steps required to transition from $s_i$ to $r_i$ or to an active vertex in $U_i$ . By Lemma 5.3, at most $2k$ phases are required to identify $k$ distinct vertices. Summing over the active phases yields:

$\mathbb{E}\left[T_k\right]={\displaystyle \sum }_{i=0}^{2k}\mathbb{E}\left[{\Phi }_{i}1\left(\left|Y_i\right|\le k\right)\right]\le 2k\times 144k^2=288k^3,$

establishing the cubic exploration bound.

6. Sensitivity of Mixing

6.1. The Sensitivity Dichotomy

For reversible Markov chains, Peres and Sousi [26] proved that the mixing time is robust to changes of laziness parameters: if the laziness at each vertex is in $\left[c_1,c_2\right]\subset \left(0,1\right)$ , the mixing time changes only by a constant multiplicative factor. In this section, we show this robustness fails for the Eulerian functional digraphs of $T_n$ .

6.2. The Sensitive Family

Let $n$ be even and fix ${\alpha }_n\in S_n$ with cycle type $\left(n/2,n/2\right)$ . Label the two directed cycles $C_1=\left(0,1,\cdots ,n/2-1,0\right)$ and $C_2=\left(0,n/2,n/2+1,\cdots ,n-1,0\right)$ , both of length $n/2$ , sharing vertex 0. Define the modified laziness assignment:

$\begin{array}{l}{p}_{\text{lazy}}\left(v\right)={\alpha }^{*}:=\frac{2}{\sqrt{5}+1}\text{for}v\in C_1\text{with}v\in \left[n/4,3n/4\right]\left(\mathrm{mod}n/2\right),\\ p_{\text{lazy}}\left(v\right)=\frac{1}{2}\text{otherwise}.\end{array}$ (6.1)

At each vertex $v$ , the modified lazy walk stays at $v$ with probability $p_{\text{lazy}}\left(v\right)$ and moves to the unique out-neighbour of $v$ on its cycle with probability $1-p_{\text{lazy}}\left(v\right)$ ; at vertex 0 it also chooses one of the two cycles uniformly at random.

Remark 6.1. The choice ${\alpha }^{*}=2/\left(\sqrt{5}+1\right)$ is the reciprocal of the golden ratio $\varphi =\left(\sqrt{5}+1\right)/2$ . It satisfies $1/\left(1-{\alpha }^{*}\right)=\left(\sqrt{5}+1\right)/\left(\sqrt{5}-1\right)$ and makes the ratio of expected excursion times $r^{*}=\mathbb{E}\left[T^1\right]/\mathbb{E}\left[T^2\right]=\left(7+5\right)/8$ an irrational number whose continued-fraction partial quotients are bounded (in fact by 4). The three-distance theorem (Lemma 6.2) quantifies the distribution of fractional parts $\left\{k\xi \right\}$ for an irrational $\xi$ : the maximal gap between consecutive points among $\left\{\xi ,2\xi ,\cdots ,n\xi \right\}$ is at most $cB/n$ , and any interval of length $1/n$ contains at most $B+2$ points, where $B$ is an upper bound on the partial quotients of $\xi$ . If the partial quotients were unbounded, the constants in these estimates would depend on $n$ in an uncontrollable way (e.g., a huge partial quotient could create a much larger gap). Bounded partial quotients guarantee that the constants $c$ and $B$ are absolute (independent of $n$ ), which is essential for the local limit estimates in Lemma 6.3 and ultimately for establishing the polynomial mixing lower bound $t_{mix}\ge c{n}^{3/2}$ .

6.3. Expected Excursion Times

For the walk $X$ on ${\Gamma }_{{\alpha }_n}$ with the modified laziness (6.1), define a round as the time elapsed from a visit to 0 to the next return to 0 after having first hit the midpoint ($n/4$ for $C_1$ , 3n/4 for $C_2$ ). Let $T^1$ (respectively $T^2$ ) denote the duration of a round on $C_1$ (respectively $C_2$ ).

Lemma 6.1 (Expected excursion times). There is a function $f\left(n\right)=\frac{3n}{4}\left(1+O\left(2^{-n/4}\right)\right)$ such that

$\mathbb{E}\left[T^1\right]=\left(2+\frac{1}{1-{\alpha }^{*}}\right)f\left(n\right),\mathbb{E}\left[T^2\right]=4f\left(n\right),Var\left(T^j\right)\asymp n,j=1,2.$ (6.2)

In particular, the ratio $r^{*}:=\mathbb{E}\left[T^1\right]/\mathbb{E}\left[T^2\right]=\left(2+1/\left(1-{\alpha }^{*}\right)\right)/4$ is irrational with bounded continued-fraction coefficients.

Proof. The expected and variance formulae follow by decomposing each excursion into per-vertex residence times and applying Wald’s identity, exactly as in ([23], Lemma 4.4). The explicit computation gives

$f\left(n\right)=\frac{3n}{4}-\frac{3n}{2}\cdot 2^{-n/4}\cdot \frac{2^{n/4}-1}{2^{n/4}-2^{-n/4}},$

from which the asymptotic $f\left(n\right)=\frac{3n}{4}\left(1+O\left(2^{-n/4}\right)\right)$ is immediate. The irrationality of $r^{*}$ follows from ${\alpha }^{*}=2/\left(\sqrt{5}+1\right)$ , which gives $1/\left(1-{\alpha }^{*}\right)=\left(\sqrt{5}+1\right)/\left(\sqrt{5}-1\right)=\left(3+\sqrt{5}\right)/2$ , so $r^{*}=\left(7+\sqrt{5}\right)/8$ , an irrational algebraic number with bounded partial quotients.

6.4. Three-Distance Theorem and Return-Time Distribution

Let ${\left({\xi }_i\right)}_{i\ge 1}$ be i.i.d. Bernoulli (1/2) random variables (indicating which cycle is visited in round $i$ ), let ${\left(T_i^1\right)}_{i\ge 1}$ and ${\left(T_i^2\right)}_{i\ge 1}$ be independent i.i.d. copies of $T^1$ and $T^2$ respectively, all mutually independent. Define the cumulative round time

$S_k={\displaystyle \sum }_{i=1}^k\left({\xi }_i{T}_i^1+\left(1-{\xi }_i\right)T_i^2\right),k\ge 1.$

Lemma 6.2 (Three-distance theorem). Let $\xi$ be an irrational number with all continued-fraction partial quotients bounded by $B$ . Let $x_k=\left\{k\xi \right\}:=k\xi \mathrm{mod}1$ . Then:

1) The maximum gap of the sequence $\left\{x_1,\cdots ,x_n\right\}$ in $\left[0,1\right)$ is at most $cB/n$ for a universal constant $c$ .

2) Every interval of length $1/n$ in $\left[0,1\right)$ contains at most $B+2$ elements of the sequence.

Proof. This is a quantitative form of the classical three-distance (Steinhaus) theorem; see ([21], inequality (3.17)).

Lemma 6.3 (Return-time distribution). For the walk $X$ with modified laziness (6.1), for all $t\in \left[n^{3/2}/50,10n^{3/2}\right]$ ,

${\displaystyle \sum }_{k=1}^{\infty }\mathbb{P}\left(S_k=t\right)\asymp \frac{1}{n}.$ (6.3)

Proof. We work with the walk $X$ on the two-cycle graph ${\Gamma }_{{\alpha }_n}$ with the modified laziness (5.1). Recall the round construction: between successive visits to the common vertex 0, the walk performs an excursion entirely on $C_1$ or $C_2$ , with durations $T^1$ and $T^2$ respectively. Let ${\left({\xi }_i\right)}_{i\ge 1}$ be i.i.d. Bernoulli(1/2) (choose $C_1$ if ${\xi }_i=1$ , $C_2$ if 0), independent of the excursion durations. Define

$S_k={\displaystyle \sum }_{i=1}^k\left({\xi }_i{T}_i^1+\left(1-{\xi }_i\right)T_i^2\right),$

where ${\left(T_i^1\right)}_{i\ge 1}$ and ${\left(T_i^2\right)}_{i\ge 1}$ are i.i.d. copies of $T^1$ and $T^2$ respectively, independent of each other and of $\left({\xi }_i\right)$ . The return time to 0 after $k$ rounds is exactly $S_k$ . We aim to prove that for all $t$ in the range $\left[n^{3/2}/50,10n^{3/2}\right]$ ,

${\displaystyle \sum }_{k\ge 1}\mathbb{P}\left(S_k=t\right)\asymp \frac{1}{n}.$

Step 1—Decompose into mean plus fluctuation. Write $T_i^j={\mu }_j+D_i^j$ , where ${\mu }_j=\mathbb{E}\left[T^j\right]$ and $D_i^j$ are zero-mean fluctuations. From Lemma 6.1,

${\mu }_1=\left(2+1/\left(1-{\alpha }^{*}\right)\right)f\left(n\right)$ , ${\mu }_2=4f\left(n\right)$ , and $Var\left(D_i^j\right)\asymp n$ . Let $L_k={\displaystyle {\sum }_{i=1}^k{\xi }_i}$ be the number of rounds on $C_1$ among the first $k$ . Then

$S_k=L_k{\mu }_1+\left(k-L_k\right){\mu }_2+{\displaystyle \sum }_{i=1}^k\left({\xi }_i{D}_i^1+\left(1-{\xi }_i\right)D_i^2\right)=k{\mu }_2+L_k\left({\mu }_1-{\mu }_2\right)+Y_k,$

where $Y_k={\displaystyle {\sum }_{i=1}^k\left({\xi }_i{D}_i^1+\left(1-{\xi }_i\right)D_i^2\right)}$ .

Step 2—Local CLT for the fluctuations. Because $D_i^j$ have finite variance of order $n$ and are independent, we apply a local central limit theorem for lattice distributions (see e.g. [31]). For any integers $x,y$ with $\left|x\right|,\left|y\right|=O\left(n^{1/4}\right)$ and $k\asymp \sqrt{n}$ , the binomial distribution of $L_k$ and the conditional distribution of the fluctuation $Y_k$ yield:

$\mathbb{P}\left(L_k=k/2+x\right)\asymp \frac{1}{\sqrt{k}}{\text{e}}^{-2x^2/k},\mathbb{P}\left(Y_k=y|L_k\right)\asymp \frac{1}{\sqrt{kn}}{\text{e}}^{-y^2/\left(2kVar\left(D\right)\right)}.$

The constants implicit in $\asymp$ are absolute because the component distributions possess bounded third moments, ensuring uniform convergence bounds in the local limit regimes.

Step 3—Reformulate the event $S_k=t$ . From the structural decomposition, the target configuration satisfies:

$S_k=t\iff k{\mu }_2+L_k\left({\mu }_1-{\mu }_2\right)+Y_k=t.$

Let $d={\mu }_1-{\mu }_2$ . Note that $d={\mu }_2\left(r^{*}-1\right)$ where $r^{*}={\mu }_1/{\mu }_2=\left(7+5\right)/8$ , which is an algebraic irrational with bounded partial quotients. Set $\iota =d/\left({\mu }_1+{\mu }_2\right)=\left(r^{*}-1\right)/\left(r^{*}+1\right)$ , which shares this Diophantine property. Isolating the excursion count yields:

$L_k=\frac{k}{2}+\frac{t-k{\mu }_2-Y_k}{2{\mu }_2+d}.$

Let $x=L_k-k/2$ and $M=\left({\mu }_1+{\mu }_2\right)/2\asymp n$ . This simplifies to the Diophantine balance equation:

$xd+Y_k=t-kM.$

Step 4—Scaling and index localization. Observe that $M\asymp n$ . For $t\in \left[c_1{n}^{3/2},c_2{n}^{3/2}\right]$ , the condition $\left|t-kM\right|\le C{n}^{3/4}$ restricts the admissible range of $k$ to an index band of width $\left|\mathcal{K}\right|=O\left(1\right)$ centered around $t/M\asymp \sqrt{n}$ . Let $\gamma =M/d$ . Because $r^{*}$ has bounded partial quotients, $\gamma$ is likewise badly approximable. Rewriting the balance equation as:

$x=\frac{t-kM-Y_k}{d}$

implies that for an integer solution $x$ to exist, the localized index $k$ must satisfy:

$dist\left(k\gamma ,\mathbb{Z}\right)\le \frac{\left|Y_k\right|}{\left|d\right|}\le C{n}^{3/4}/\left|d\right|\asymp n^{-1/4}.$

By the Three-Distance Theorem applied to the irrational rotation $\gamma$ , the elements ${\left\{k\gamma \right\}}_{k\in \mathcal{K}}$ are well-spaced. Since $\left|\mathcal{K}\right|=O\left(1\right)$ due to the tight restriction on $\left|t-kM\right|$ , the number of active indices $k$ simultaneously satisfying the scaling constraints is rigidly bounded by an absolute constant.

Step 5—Counting admissible triples $\left(k,x,y\right)$ and upper bound. Let $\mathcal{K}$ be the set of valid indices. For each fixed $k\in \mathcal{K}$ , the balance equation $xd+Y_k=t-kM$ determines $x$ uniquely for a given fluctuation value $Y_k$ . Because the spacing between distinct values of $x$ is $d\asymp n$ , and the LCLT restricts the fluctuation scale to $\left|Y_k\right|=O\left(n^{3/4}\right)$ , there exists at most one admissible integer value for $x$ per active index. Compounding the joint probabilities via conditioning yields:

$\mathbb{P}\left(L_k=k/2+x\right)\cdot \mathbb{P}\left(Y_k=y|L_k\right)\asymp n^{-1/4}\cdot n^{-3/4}=n^{-1}.$

Summing this evaluation over the finite set $\left|\mathcal{K}\right|=O\left(1\right)$ yields the upper bound:

${\displaystyle \sum }_{k\ge 1}\mathbb{P}\left(S_k=t\right)\le C_0{n}^{-1}.$

Conversely, by the uniform distribution properties of badly approximable numbers, the set $\mathcal{K}$ contains at least one index $k$ for which $dist\left(k\gamma ,\mathbb{Z}\right)\le O\left(n^{-1/2}\right)$ . For this target index, the LCLT guarantees non-zero probability mass at the center of the fluctuation distribution, yielding a matching lower bound of order $n^{-1}$ . Thus, summing over all configurations validates the tight asymptotic equivalence:

${\displaystyle \sum }_{k=1}^{\infty }\mathbb{P}\left(S_k=t\right)\asymp \frac{1}{n},$

completing the proof.

6.5. Proof of Theorem 1.5

Upper bound. We construct a coupling between $X$ (the walk with modified laziness) and an auxiliary walk $Y$ whose successive excursions from 0 are i.i.d. copies of $T^1$ or $T^2$ , chosen by an independent coin flip (as in Definition 6.2 below). By a coupling argument entirely analogous to [23], the coupling succeeds with probability $1-O\left(e^{-cn}\right)$ over any time interval of length $n^2$ . Lemma 6.3 then gives: for all $t\in \left[n^{3/2}/10,10n^{3/2}\right]$ and all vertices $x,y$ ,

$P^t\left(x,y\right)\asymp \frac{1}{n}=\pi \left(y\right),$

which implies $\left|\frac{P^t\left(x,y\right)}{\pi \left(y\right)}-1\right|\le c<1$ uniformly. Sub-multiplicativity of the total variation distance then gives $t_{mix}\le t_{unif}\lesssim n^{3/2}$ .

Lower bound. Let $t=\epsilon n^{3/2}$ for $\epsilon >0$ small. By time $t$ at most $k\left(t\right)\le c\sqrt{n}$ rounds are completed. Let $\ell \left(k\right)$ and $r\left(k\right)$ denote the number of left ($C_1$ ) and right ($C_2$ ) rounds among the first $k$ rounds. Since $\ell \left(k\right)-r\left(k\right)$ is a simple random walk on $\mathbb{Z}$ , Doob’s maximal inequality gives

$\mathbb{P}\left(\underset{k\le c\sqrt{n}}{\max }\left|\ell \left(k\right)-r\left(k\right)\right|\ge C{n}^{1/4}\right)\le \frac{c\sqrt{n}}{C^2\sqrt{n}}=\frac{c}{C^2}.$

On the complement, $\left|\ell \left(k\right)-r\left(k\right)\right|\le C{n}^{1/4}$ for all $k\le c\sqrt{n}$ . Combined with a concentration inequality for the martingale $M_k={\displaystyle {\sum }_{i=1}^k{\xi }_i{T}_i^1}+\left(1-{\xi }_i\right)T_i^2-\ell \left(k\right)\mathbb{E}\left[T^1\right]-r\left(k\right)\mathbb{E}\left[T^2\right]$ (which has $\text{Var}\left(M_k\right)\asymp kn$ ), and Lemma 6.2 (which shows the walk’s position is concentrated on a set of size$\asymp \epsilon n$ in each cycle), one deduces ${\Vert P^t\left(0,\cdot \right)-\pi \Vert }_{TV}\ge 1-c\epsilon$ . Choosing $\epsilon$ small enough gives $t_{\text{mix}}\ge c_1{n}^{3/2}$ . When all vertices have laziness 1/2, the walk on each $n/2$ -cycle is the standard lazy directed-cycle walk, with mixing time $\asymp {\left(n/2\right)}^2\asymp n^2$ , giving $t_{\text{mix}}\asymp n^2$ for the two-cycle walk.

Definition 6.2. In the coupling used in the upper bound proof, define ${\left(Y_t\right)}_{t\ge 0}$ as the walk that at the start of each excursion from 0 independently chooses cycle $C_1$ (with probability 1/2) or $C_2$ (with probability 1/2) and completes one full excursion on that cycle before returning to 0. The excursion lengths are i.i.d. copies of $T^1$ or $T^2$ as appropriate.

Acknowledgements

The authors are grateful to the anonymous referees for careful reading and constructive suggestions that substantially improved the presentation.