CS Paper Radar

A subquadratic upper bound for the mixing time of the Thorp shuffle

Yunjiang Jiang

cs.DS math.PR ·submitted 2026-10-03 18:03 UTC · v1
theory

Abstract

Let $n=2^d$. We prove that the worst-start total-variation mixing time of the full labelled Thorp shuffle satisfies, for every fixed $0<\varepsilon<1$, \[ t_{\mathrm{mix}}(\varepsilon) \le C_* d^{5/3}+O_\varepsilon\!\left(d^{4/3}\log(d+2)\right), \qquad C_*=5.1536951454\ldots . \] Time is measured in ordinary Thorp shuffles. This improves the previously published full-deck upper bound $O(d^3)$ of Morris. The geometric starting point is elementary: label the $n=2^d$ positions by binary strings. One physical Thorp shuffle is a random swap layer on one coordinate matching of the $d$-dimensional cube, followed by a deterministic cyclic rotation of the coordinates. In a rotating frame that deterministic rotation disappears, so $d$ successive physical shuffles become one \emph{sweep}: one independent random swap layer in each coordinate direction. The proof then combines five ingredients. First, a collision-graph representation and negative dependence give pointwise smoothing for ordered marked cards. Second, an entropy argument is sharpened by moving an endpoint moment up to the critical exponent $β_c=\log_2(3/2)$, yielding an entropy-preparation clock $s^2/(2\log(3/2))+O(s\log s)$. Third, exact multiplicities in the ordered $h$-tuple permutation representation amplify marked-card bounds into Fourier operator and energy estimates on low representation levels. Fourth, entropy truncation produces a positive mixture whose regular component retains the marked-card budget. Finally, only two long blocks need this entropy regularization: a shorter third block is used solely for additional low-level smoothing. Optimizing the three block lengths gives the constant above.

Comment
31 pages

Closest papers

Nearest neighbours by meaning across the whole index.

Mixing Time of the Random-Pair Monte Shuffle

cs.DM math.PR ·2026-11-02 ·Ilya Mironov
theory similarity 0.67
Abstract

In the random-pair Monte shuffle on $n$ cards, each step chooses two positions independently and uniformly and exchanges their cards with probability $1/2$. The chosen positions are public; the decisions to exchange cards remain hidden. We prove that the mixing time in expected conditional total variation distance is $2n\log n+O(n)$, with an exact leading constant and an $O(n)$ cutoff window. To our knowledge, this is the first public-schedule Monte shuffle whose full-permutation mixing time has been determined up to an additive $O(n)$ term. The upper bound follows by comparing two executions with the same public schedule to a classical random-transposition walk. For the lower bound, we construct a schedule-dependent test function and estimate its variance using a matrix-averaging operator. Combined with the depth bound of Czumaj and Lingas, the mixing estimate gives public switching networks with at most $2n\log n+O(n)$ switches and $O(\log n)$ depth for fixed error and failure probabilities. The author obtained this result through interaction with GPT-6 Astra.

0.20

Optimal mixing of random-to-random shuffling on linear extensions

cs.DS math.PR ·2026-11-15 ·Haoran Wang
theory similarity 0.62
Abstract

Uniform sampling of linear extensions is a basic problem in randomized algorithms and the study of finite posets. We prove that the random-to-random shuffle of Ayyer, Schilling, and Thiéry mixes in $O(n\log n+n\log(1/\varepsilon))$ steps on every $n$-element poset, establishing their conjectured mixing order. With constant-time order queries, this gives an $\varepsilon$-approximate uniform sampler using $O(n^2(\log n+\log(1/\varepsilon)))$ elementary operations after preprocessing. The proof establishes relative-entropy contraction by a factor $1-1/n$ for the promotion half-step. Consequently, the uniform extended-promotion chain has the same mixing order. We represent complete promotion scans as reflected coordinate paths in the order polytope and prove that a convex potential with gradients in the same polytope has diagonal Hessian mass at most one along each path. Applying this estimate to an optimal transport potential yields a sharp entropy factorization for every finite-entropy input. Linearization also gives the spectral-gap lower bound $(n+1)/n^2$.

0.32

Sampling Colorings on $G(n, d/n)$ via Glauber Dynamics

cs.DS math.COmath.PR ·2026-11-09 ·Leon Schiller
similarity 0.61
Abstract

We study the mixing time of Glauber dynamics for sampling uniformly from the proper $q$-colorings of sparse Erdős-Rényi random graphs $G(n,d/n)$. Our main result establishes that with probability $1-o(1)$ over the draw of $G$, Glauber dynamics is rapidly mixing for every $q\geq d+d^{1/2+\varepsilon}$, given any fixed $0<\varepsilon\leq1/2$ and any sufficiently large fixed $d$. In particular, the surplus of colors above $d$ is sublinear and close to $\sqrt{d}$. The achieved color range therefore approaches the tree uniqueness threshold and improves over the previously best achievable number of colors $q > 1.763 d$ due to Efthymiou, Hayes, Stefankovic, and Vigoda [SODA 2018]. Moreover, our mixing-time bound is $O(n^{2+o_d(1)})$, and hence almost quadratic as $d\rightarrow\infty$. Our proof is based on establishing a spectral gap for block dynamics resulting from a suitable decomposition of $G(n,d/n)$ into blocks and singleton vertices, ensuring that every high-degree vertex is encapsulated within a block. Our main technical contribution is a novel way of establishing rapid mixing of block dynamics via an integrated Bochner-Bakry-Émery approach, which we expect to have applications beyond sampling colorings. We further devise a new block decomposition of $G(n,d/n)$ that strengthens and simplifies similar constructions used in previous work. Finally, to compare block and Glauber dynamics, we establish a novel recursive separator decomposition of tree-like blocks, together with a coupling argument that avoids the need for nearly uniform color marginals at vertices adjacent to hubs. This comparison argument might be of independent interest.

0.11

Hit-and-Run Mixes as Fast as the Ball Walk

cs.DS math.PR ·2026-08-13 ·Ruizhe Zhang
theory similarity 0.59
Abstract

Let $K\subset\mathbb{R}^n$ be an isotropic convex body. We prove that the hit-and-run walk, started from any $M$-warm distribution, reaches total-variation distance $\varepsilon$ from the uniform distribution on $K$ in $O\!\left(n^2ψ_n^{-2}\log^3(M/\varepsilon)\right)$ steps, where $ψ_n^{-1}$ is the Kannan-Lovász-Simonovits (KLS) constant. Up to logarithmic factors, this matches the best-known warm-start mixing time for the ball walk. Chen and Eldan [Discrete Comput. Geom. 2026] obtained the same $n^2ψ_n^{-2}$ dependence for hit-and-run, but with polynomial dependence on $M/\varepsilon$. Our result improves that polynomial dependence to a polylogarithmic one, fully resolving their open question about warm-start mixing of hit-and-run in isotropic convex bodies.

0.04

On the Impossibility of Estimating the Average Mixing Time

cs.IT math.ST ·2026-10-07 ·Nathan A. Judd, Amedeo Roberto Esposito
similarity 0.59
Abstract

We establish nearly-matching converse bounds on the sample complexity of estimating the average mixing time of a Markov chain from a single stationary trajectory. Unlike the worst-case mixing time, which maximises the total-variation distance to stationarity over all initial states, the average mixing time averages this distance under the stationary distribution and can therefore be substantially smaller. Our converse bounds establish when estimation is impossible, and match the key dependencies in existing achievability bounds, up to logarithmic factors. Together, these bounds provide nearly-tight PAC guarantees for estimating the average mixing time.

0.18

The Movement Complexity of Sorting

cs.DS cs.CC ·2026-10-31 ·Sichen Wang
theory similarity 0.58
Abstract · 39 pages

The complexity of sorting is usually measured by the number of comparisons. This measure ignores the movement of the read heads between comparisons, which is a real cost on many machines. We study this cost on its own. Keys lie on a $d$-dimensional grid, two heads move over the grid and compare the keys beneath them, and the only cost is the total movement of the heads. The algorithm plans its route in $r$ rounds and sees the outcomes of each round only after running it. For every $d$ and $r$ we determine the expected movement needed to sort $n$ keys: it is $n^β$ up to polylogarithmic factors, where $β=1+D^{r-1}/(D^{r}-(D-1)^{r})$ and $D=2d$, falling from $n^{2}$ at $r=1$ to $n^{1+1/(2d)}$ with unlimited rounds. Our algorithm makes every round move about the same amount, and a matching lower bound holds against every algorithm.

0.32

Rapid Mixing for Sampling Colorings of Random Graphs up to Tree Uniqueness Threshold

cs.DM math.PRcs.DS ·2026-10-18 ·Zhidan Li, Kuan Yang
theory similarity 0.57
Abstract · 52 pages

We study the mixing time of the single-site Glauber dynamics for sampling proper $q$-colorings on sparse Erdős-Rényi random graphs $\mathcal{G}(n, d/n)$. We prove that, whenever $q \ge (1 + o_d(1))d$, Glauber dynamics mixes in polynomial time with high probability over $\mathcal{G}(n, d/n)$ for all sufficiently large integers $n$. This improves the previous bound $q = (α^* + o_d(1))d$ where $α^* = 1.7632...$ is the unique solution of $x = \exp(1/x)$ on $[1, \infty)$ by Efthymiou, Hayes, Štefankovič, and Vigoda (SODA, 2018) and asymptotically matches the uniqueness threshold on infinite regular trees. Our proof has three main ingredients. First we establish logarithmic bounds on the spectral and coupling independence constants of the Gibbs distribution by extending the tree analysis of Chen, Liu, Mani, and Moitra (J. ACM, 2026). Second, we extend the entropy-factorization framework for two-spin systems on random graphs, developed by Bezáková, Galanis, Goldberg, and Štefankovič (TALG, 2024), to proper colorings by introducing a buffer around high-degree vertices. Finally, we compare the resulting heat-bath block dynamics with the single-site Glauber dynamics.

0.49

Spatial Mixing and Deterministic Approximate Counting of Multi-spin Systems beyond Bounded Degree Graphs

cs.DS math.PR ·2026-09-11 ·Zhidan Li, Kuan Yang
similarity 0.57
Abstract · A revised version

We develop a framework for deterministic approximate counting of multi-spin systems beyond bounded-degree graphs. The algorithm recursively constructs rational polytopes containing the true marginal vectors and uses linear-fractional programming to obtain certified bounds on marginal ratios. For positive interactions on graphs of polynomial connective constant $D$, we establish strong spatial mixing whenever $Dc<1$, where $c$ bounds the Birkhoff contraction coefficients of the interactions. Under the same condition, we also give a deterministic fully polynomial-time approximation scheme (\textbf{FPTAS}) for the partition function. We further extend the framework to proper colorings of sparse Erdős-Rényi random graphs using recursion on permissive blocks. For every fixed $η\in(0,1)$, sufficiently large fixed $d$, and fixed integer $q\ge(2+η)d$, we obtain an \textbf{FPTAS} for counting proper $q$-colorings of $G\sim\mathcal G(n,d/n)$ with high probability over $G$. This improves the leading constant $3$ in the earlier counting guarantee of Yin and Zhang (APPROX/RANDOM, 2016) to $2$, and asymptotically matches the spatial mixing regime established by Yin (ICALP, 2014).

0.26