Source-linked AI summary
Transposition achieves OPT$+O(1)$ in polynomial time for IID list update
Clayton Mizgerd
TL;DR
In the IID list update problem, the optimal probability-sorted order is generally unavailable because users do not know the query probabilities, and stationarity does not give a uniform mixing-time bound. This paper proves a finite-time guarantee for the transposition rule from any initial ordering: after polynomially many queries, expected cost is within an additive constant of OPT.
Problem
Users generally do not know the query probability vector p and thus cannot access the optimal order; moreover, transposition's mixing time cannot be bounded uniformly in n over all p.
Source: §1 · pp. 1–2Method
The paper analyzes the transposition rule, which moves a queried item forward one position, to establish a guarantee for arbitrary probability vectors and initial orderings.
Source: §1 · pp. 1–2Results
For every p and initial ordering, after t ≥ n^29 steps, E[Cost(σ_t)] ≤ OPT + 1250.
Source: §1 · p. 2Takeaways & Limitations
The result confirms that transposition achieves OPT + O(1) after polynomially many requests for any p and initial ordering.
Source: §1 · p. 2The exponent 29 and additive constant 1250 are not optimized.
Source: §1 · p. 2
Abstract
from arXiv · showhide
In the classical list update problem, a set of items must be stored in a list-type structure, where accessing the $i$-th element costs $i$. Items will be queried in an IID manner according to some probability distribution $p$ on the items. We want to minimize the expected cost of each query. The optimal order is to place the items in decreasing order of probability $p_1 \geq p_2 \geq \cdots$ with expected cost $\mathsf{OPT} = \sum_j j p_j$, but the probability vector $p$ is generally unknown. Thus we use a self-organizing list following the transposition rule: an item is transposed 1 position forward whenever it is queried. Coester (2026) proved that, at stationarity measure for the transposition rule, the expected cost of a query is at most $\mathsf{OPT} + 1$. However, this Markov chain may have arbitrarily slow mixing time. We prove that, for arbitrary $p$ and arbitrary initial orderings $\sigma$, after polynomially many queries in the number of items, the expected cost of a query is at most $\mathsf{OPT} + O(1)$.
1. Introduction
The introduction motivates transposition as a self-organizing rule when query probabilities are unknown and proves a uniform finite-time additive-cost guarantee for every probability vector and initial ordering. Its proof overview controls inversions across logarithmic probability scales using an adaptive buffer and an exclusion-process comparison.
1. Introduction
- The optimal ordering places items in decreasing probability order, with ties broken arbitrarily.Source: §1 · p. 1
- Because users generally do not know p, they cannot access the probability-sorted optimal order, while estimating p adds undesirable overhead.Source: §1 · p. 1
- Under transposition, a queried item moves forward one position by swapping with its front neighbor, unless it is already first.Source: §1 · p. 1
- The result confirms Coester's conjecture that transposition achieves OPT + O(1) after polynomially many requests for any p and initial ordering.The mixing time itself cannot be bounded uniformly in n over all p.Source: §1 · p. 2
- For every probability vector and initial ordering, after t ≥ n^29 steps the expected cost is at most OPT + 1250.The proof does not optimize the exponent or additive constant.Source: §1 · p. 2
1.1. Proof overview.
- The proof overview separates inversions by logarithmic probability scales, bounding nearby inversions with an adaptive buffer and surprising ones through an exclusion-process comparison.The overview states that the latter comparison gives O(θ^-2) expected surprising inversions at stationarity, contributing O(1) to E[F].Source: §1.1 · pp. 2–3
AI usage statement.
The manuscript reports AI assistance in proof development and preparation, while assigning mathematical content and errors to the author.
AI usage statement.
- The author reports using Astra to generalize a proof, then rewriting it, and using Codex to assist manuscript preparation; mathematical content and errors remain the author's responsibility.Source: AI usage statement · p. 3
2. The adaptive buffer
For positive probabilities, the transposition chain is reversible with a stationary measure. The adaptive buffer has controlled scale and regularity, and supports bounding the contribution of inverted pairs.
2.1. Preliminaries.
- For positive probabilities, the transposition chain is reversible; swapping j ahead of predecessor i has forward and reverse probabilities matched by the stationary-weight ratio.Source: §2.1 · p. 3
2.2. Integrability of the buffer.
- The adaptive buffer θ is 1/2-Lipschitz and lies between 1/(2n) and 1/2.The proof also notes that when many logarithmic probabilities lie near a point, the buffer scale is small.Source: §2.2 · pp. 3–4
2.3. Discarding local contributions.
- Inversions with lower endpoints near b_i contribute at most 2 in total; remaining inversions are related to the integral involving J and bounded using θ(b_i) ≤ 1/2.Source: §2.3 · p. 5
3. Auxiliary exclusion chains
The section analyzes binary exclusion chains to control how low- and high-probability labels are ordered. It then compares an auxiliary chain with the biased exclusion chain and realizes auxiliary exchanges through sorting paths in the original chain.
3.2. Comparison with the auxiliary chain.
- The auxiliary chain freezes intermediate labels and within-class order, while allowing adjacent low–high pairs in the remaining subsequence to exchange.It classifies labels using x and θ, and rejects exchanges between labels in the same class.Source: §3 · p. 5, §3.2 · p. 6
3.1. The biased exclusion chain.
- The biased exclusion chain resamples adjacent unlike letters with a bias toward placing H first, and Lemma 3.2 bounds its inversion count from arbitrary starts.V counts pairs in which an L precedes an H.Source: §3.1 · p. 5
3.2. Comparison with the auxiliary chain.
- The auxiliary exchange rule is a heat-bath rule with respect to µ, making µ stationary, though not generally the unique stationary measure.Canonical paths realize exchanges in the original chain using sequences of requested labels that increase weight.Source: §3.2 · pp. 6–7
- Coupling the auxiliary chain with the biased exclusion chain preserves prefix dominance, so the auxiliary chain’s inversion count is no larger.The coupling uses shared adjacent-pair choices and maximally coupled resampling outcomes.Source: §3.2 · pp. 6–7
4. A cost bound via entropy decay
The section bounds the transposition rule’s cost by connecting cost control to entropy decay for reversible chains. It handles zero and extremely small request probabilities by perturbing the distribution and coupling the resulting chain to the original.
4.2. Entropy decay.
- For reversible finite-state chains, relative entropy decreases under the transition matrix, and the argument bounds the distance between laws two steps apart using entropy.The section applies this general entropy-decay argument to the transposition chain and combines it with the cost-to-Dirichlet-form result.Source: §4.2 · pp. 9–10
4.3. Extremely small and zero probabilities.
- An exponentially small perturbation produces a positive distribution q with the same weak ordering as p, and the chains started together remain coupled with high probability through time T.The probability of a request mismatch by time t is at most tne^-n; the expected-cost comparison incurs an additive error of (t + 1)n^2e^-n.Source: §4.3 · p. 10
- T = n^29 and C = 1250 suffice for the proof of Theorem 1.2, with the bound applying for every integer t ≥ T.For n < 1024, the proof uses Fp ≤ n < C; for larger n it sets T = n^29 and verifies 3C0 + 3 < C.Source: §4.3 · pp. 10–11