Picture a random search process that usually moves toward its goal but sometimes jumps far backward, like a randomized selection algorithm with a "back button." Intuition says that making backward jumps more likely should make the search take longer. For walks that move one step at a time this is easy to prove: run a faster and a slower walker side by side, and they cannot pass each other without landing on the same spot, at which point you glue them together. Once long jumps are allowed, a walker can leap over the other without ever meeting it, and the argument collapses. That is why the general monotonicity conjecture for Vishnoi's back-jump walk is still open (Non Uniform Random Walks).
We propose replacing the "walkers must collide" argument with a small optimal-transport computation at each step. Optimal transport here means finding the cheapest way to pair up the mass of two probability distributions. Two walkers do not need to collide to stay ordered; they only need to jump in a coordinated way. Whether such a coordinated jump exists is exactly a transport problem between the two rows of the transition matrix, with a cost that charges for any pairing that inverts the order. If that cost is zero, it certifies that the full distribution of absorption times, not just its mean, is ordered. We apply this to walks on the symmetric group $S_n$, a non-Abelian group, meaning one where the order of operations matters. There, long-range transpositions are the non-local moves, and the Bruhat order on permutations supplies a natural partial order. Where exact certificates are too large to compute, we test the same orderings from simulated hitting times, using limit theory built for the case where the null hypothesis sits on a boundary.
Core Claim
For a chain whose absorbing state is the bottom of a partial order $\preceq$, call the kernel $P$ $\preceq$-monotone if, for every pair $x \preceq y$, the rows $P(x,\cdot)$ and $P(y,\cdot)$ admit a coupling supported on pairs $x' \preceq y'$. Then the hitting time from $x$ is stochastically smaller than the hitting time from $y$. The same holds when comparing two kernels $P \le P'$ row by row. The condition is local, one step at a time, and it is indifferent to how far the jumps go. Leapfrogging is harmless as long as the coupled jumps are chosen jointly.
Checking the condition is an optimal transport problem with crossing cost $c(x',y') = \mathbf{1}\{x' \not\preceq y'\}$:
$$\delta(x,y) = \min_{\pi \in \Pi(P(x,\cdot),\,P(y,\cdot))} \sum_{x',y'} \pi(x',y')\, c(x',y').$$
Here $\Pi$ is the set of couplings with the given marginals. A certificate is $\delta \equiv 0$ over all comparable pairs. When $\delta > 0$, its value measures how far the chain is from monotone.
For total orders this reduces to comparing cumulative distribution functions, which is the classical Strassen condition. For partial orders such as Bruhat order on $S_n$, it is a genuine linear program. For first moments, the condition pairs with an exact identity. Let $h = N\mathbf{1}$ be the vector of expected absorption times, where $N=(I-Q)^{-1}$ is Vishnoi's fundamental matrix. Shifting mass at state $i$ from forward targets $f_i$ to backward targets $b_i$ gives
$$\frac{\partial h(x)}{\partial \epsilon_i} = N_{xi}\,\big(b_i^\top h - f_i^\top h\big).$$
Mean monotonicity is therefore equivalent to a sign condition on $h$. This identity is elementary and restates the conjecture rather than solving it. The certificate is the tool that can prove the condition for whole families of parameters, and for the entire law of the absorption time. The law of the absorption time beyond its mean is listed as uncharacterized in the non-local walk literature.
Research Program
Theory. The first strand develops the certificate itself. We prove the comparison theorem for partial orders in the form needed here: perturbations of the kernel that increase rows in transport order increase absorption times stochastically. We then ask which order makes the certificate succeed.
On Vishnoi's line, the natural integer order may fail for some back-jump vectors. Ordering states by $h$ is an alternative that is self-referential but checkable. The question is whether some fixed order certifies an entire parameter region, for example all $\epsilon$ in Vishnoi's family $\epsilon_i = (n-i)/(n-i+\alpha(i-1))$. Vishnoi gives closed-form scalings for this family: $\Theta(\log n)$ at $\alpha=\infty$ and $\alpha=n$, and $\Theta(n)$ at $\alpha=1$. These serve as ground truth for any monotonicity claim.
When $\delta>0$ somewhere, we aim for a quantitative statement. A small per-step crossing probability should bound how badly monotonicity can fail. Proving this, rather than asserting it, is part of the work.
Non-Abelian regime. On $S_n$ with absorption at the identity, multiplying by a transposition moves a permutation either up or down in Bruhat order. That makes Bruhat order the candidate ordering for walks with long-range transpositions, which can jump many adjacent-transposition steps at once.
We study two families. The first is conjugation-equivariant: at each step, pick a transposition that splits a cycle (toward the identity) or merges two cycles (away from it), with a merge bias $\epsilon$. Because the bias depends only on the current cycle structure, the walk projects exactly to a Markov chain on cycle types. For $n \le 30$ that chain has at most 5604 states, so exact certificates and exact fundamental matrices are feasible. This chain is non-local on the partition lattice, since a single merge can jump far.
The second family is not equivariant. It consists of Cayley graphs generated by adjacent plus long-range transpositions, and the LX/LRX generators studied in CayleyPy Growth. We use their breadth-first search tools for word metrics. For $n \le 9$, Bruhat-order linear programs are solved exactly over 362,880 states.
Inference. The third strand applies when exact computation is impossible, either for larger $n$ or when the kernel is only observed through traces of a randomized algorithm. In that case we test stochastic dominance between simulated hitting-time laws.
The statistic is the one-sided transport violation $V = \sum_t (\hat F_{\epsilon}(t) - \hat F_{\epsilon'}(t))_+$. This is the positive part of the one-dimensional Wasserstein-1 integrand for integer-valued times. Under the least-favorable null of equal laws, $\sqrt{n}V$ converges to a functional of the positive part of a Gaussian process, which is not Gaussian. Under strict dominance with separated distribution functions, $V$ is exactly zero with high probability.
This mirrors the degenerate-null phenomenon that Limit theorems for entropic optimal transport maps and Sinkhorn divergence established for the Sinkhorn divergence. In that setting the $n^{-1}$ scaling showed that concentration-based critical values were overly conservative. Our setting is simpler because it is one-dimensional and discrete. We use their second-order lesson, not their Hölder-space machinery, which is tied to compact Euclidean domains. The continuous central limit theorems of del Barrio and Loubes and del Barrio, González-Sanz and Loubes cover the case $P \ne Q$ only. They inform the power analysis away from the boundary.
Positioning. Three neighbors define the gap, and this proposal differs from each. Markovian Linearization of Random Walks on Groups turns finitely supported walks on non-Abelian groups into nearest-neighbor walks on an enlarged space, but it studies drift, entropy and harmonic measure, not hitting times or monotonicity. We reuse its construction only as an ablation. The tree walk of Yazidi and Oommen restores tractability through time-reversibility on balanced binary trees. Our certificate does not need reversibility, and we test it on their chain. Hallin, Mordant and Segers use group actions to make Wasserstein tests distribution-free on $\mathbb{R}^d$. We instead use transport as a proof device on a discrete non-Abelian state space, and use statistics only for the one-dimensional hitting-time comparison.
Baselines
Naive coupling. The reference point is to drive both walkers with the same random numbers through each row's own sampling order, which is the usual implementation of "identical noise," or to run them independently. We record how often the coupled walkers cross, to measure empirically how badly leapfrogging breaks pathwise arguments on each test chain. Both versions use identical simulation budgets. The certificate beats this baseline if it yields zero crossings by construction on chains where naive coupling crosses with nonnegligible frequency.
Exact fundamental-matrix check. The strongest competitor for first moments is to solve $(I-Q)h=\mathbf{1}$ exactly, as in Vishnoi's analysis, and read off the derivative sign from the identity above. It is exact wherever it fits in memory, so it is the yardstick for correctness of mean claims. We run it on every chain where a sparse solve is feasible: the line up to $n=2000$, cycle types up to $n=30$, and full $S_9$. We give it the same parameter grids. No reported numerical result on Lacuna exists for monotonicity checks on these chains; Vishnoi's $\Theta(\log n)$ and $\Theta(n)$ scalings are the only reported reference. The certificate counts as beating this baseline if, at matched compute, it proves monotonicity uniformly over a continuous parameter region, or proves ordering of the full law (variance, tail quantiles). The grid-based solve can do neither.
Monte Carlo with a mean comparison. For the inference regime, the competitor is a Welch t-test on simulated mean hitting times, alongside a $\sqrt{n}$-Gaussian calibration of $V$. Both use the same simulated trajectories. Our test beats them if it holds nominal type-I error at the boundary null where the Gaussian calibration does not, and if it has higher power against alternatives that cross in the tails but agree in mean.
Ablations. Two ablations isolate the key ingredient. The first swaps the order, comparing Bruhat order, word distance, cycle count and $h$-order. The second applies the certificate to the Bordenave–Dubail linearized chain instead of the original. Together they show whether success comes from the jointly chosen transport coupling, from the choice of order, or from linearization.
Why not just…?
Why not just solve the linear system and check the derivative sign? For small chains and first moments this is a real threat, and we adopt it as ground truth rather than argue against it. Its limits are threefold. It certifies one parameter point per solve, not a region. It says nothing about the distribution of absorption times beyond the mean. And it cannot run on $S_n$ beyond $n \approx 9$ without the conjugation reduction. The experiments make the comparison direct. If grid solves at matched compute identify the same monotone regions, and the certificate adds no full-law or uniform statements, we will report that the transport step contributes only presentation.
Why not just linearize the walk into a nearest-neighbor walk and use classical coupling? Markovian Linearization of Random Walks on Groups does produce a nearest-neighbor walk on $G \times \{1,\dots,r\}$. However, "nearest-neighbor" on a tree-like non-Abelian Cayley graph does not supply a linear order in which walkers must collide; the collision argument relies on one-dimensional geometry. Linearization also inflates the state space through the number of colors $r$, which that paper flags as potentially large. The linearization ablation tests this directly. If certificates on the linearized chain succeed where they fail on the original, linearization is doing the work and we will say so.
Why not just simulate and compare means with standard tests? Mean comparisons cannot detect ordering failures confined to the tails. Gaussian calibration is miscalibrated exactly at the equality boundary, where a monotonicity hypothesis lives. This is the same failure mode Goldfeld et al. documented for degenerate Sinkhorn nulls. The calibration experiment below measures the size of the effect rather than assuming it.
Why not compare walker positions with Wasserstein distance on the word metric? Vishnoi shows that monotone expected position can hold where absorption monotonicity is hard to establish, so positional laws are the wrong target. We report positional $W_1$ alongside, as a diagnostic only.
Proposed Experiments
Experiment 1: Vishnoi's line. For $n \le 12$ we sweep $\epsilon$ over a dense grid. For $n$ up to 2000 we draw random back-jump vectors and also take Vishnoi's $\alpha$-family. For each, we compute certificates under the integer order and under $h$-order, together with exact derivative signs. The decisive outcome is one of two: an $\epsilon$ with a negative derivative, which would be a counterexample to the conjecture, or a fixed order certifying the entire $\alpha$-family. Either is informative.
Experiment 2: faulty dichotomous search. We run the same checks on Yazidi and Oommen's tree chain for oracle accuracy $p \in [0.6, 0.95]$. They report target-neighborhood stationary mass above 0.999 at $p=0.95$. The question here is whether monotonicity of search time in $p$ is certifiable without reversibility.
Experiment 3: $S_n$ with split/merge bias. On the cycle-type chain for $n \le 30$, we test whether increasing the merge bias stochastically increases absorption time at the identity. We test under partition dominance order and under cycle count, reporting $\delta$ wherever the certificate fails.
Experiment 4: non-equivariant Cayley walks. For $n \le 9$, using the CayleyPy generator sets, we solve exact Bruhat-order linear programs. For $n$ from 10 to 20, we simulate hitting times and apply the violation test.
Experiment 5: calibration and power. Two chains with identical laws, plus constructed tail-crossing alternatives, measure type-I error at the 5% level and power for $V$ under the boundary limit, against the Welch and $\sqrt{n}$-Gaussian baselines.
Decisive checks. The project succeeds if certificates prove full-law monotonicity on at least one parameter family where only pointwise mean checks existed before, and if the boundary-calibrated test holds size where Gaussian calibration does not. It fails if Bruhat-order certificates never close on non-equivariant walks. That would be a clean negative result: non-Abelian non-locality breaks even coordinated coupling, and a different tool would be needed.
References
- Non Uniform Random Walks
- CayleyPy Growth: Efficient growth computations and hundreds of new conjectures on Cayley graphs
- Limit theorems for entropic optimal transport maps and Sinkhorn divergence
- Central limit theorems for empirical transportation cost in general dimension
- Central limit theorems for general transportation costs
- Markovian Linearization of Random Walks on Groups
- On the analysis of a random walk-jump chain with tree-based transitions and its applications to faulty dichotomous search
- Multivariate goodness-of-fit tests based on Wasserstein distance