Transposition is Nearly Optimal for IID List Update
Christian Coester · 2026
Read Transposition is Nearly Optimal for IID List Update by Christian Coester (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2603-10244.txt.
Introduction
Christian Coester settles a fifty year old conjecture by Rivest about the transposition rule for the list update problem. In that problem, each request costs the requested item's position in a list, and requests arrive independently from a fixed unknown distribution. Simply swapping each requested item with its predecessor, Coester proves, costs at most one more than the optimal static order in stationarity. The proof rests on a sign eliminating combinatorial injection.
Catalog record
| CREATOR | Christian Coester |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 46184 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2603.10244
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Transposition is Nearly Optimal for IID List Update Christian Coester Abstract The list update problem is one of the oldest and simplest problems in online algorithms: A set of items must be maintained in a list while requests to these items arrive over time. Whenever an item is requested, the algorithm pays a cost equal to the position of the item in the list. In the i.i.d. model, where requests are drawn independently from a fixed distribution, the static ordering by decreasing access probabilities p 1 ≥ p 2 ≥ ⋯ ≥ p n p_{1}\geq p_{2}\geq\dots\geq p_{n} achieves the minimal expected access cost OPT = ∑ i = 1 n i p i \mathrm{OPT}=\sum_{i=1}^{n}ip_{i} . However, p p is typically unknown, and approximating it by tracking access frequencies creates undesirable overheads. We prove that the Transposition rule (swap the requested item with its predecessor) has expected access cost at most OPT + 1 \mathrm{OPT}+1 in its stationary distribution. This confirms a 50-year-old conjecture by Rivest up to an unavoidable additive constant. More abstractly, it yields a purely memoryless procedure to approximately sort probabilities via sampling. Our proof is based on a decomposition of excess cost, and its technical core is a “sign-eliminating” combinatorial injection to witness nonnegativity of a constrained multivariate polynomial. 1 Introduction Maintaining frequently accessed objects near the front of a list is a ubiquitous primitive: linked-list dictionaries, symbol tables, rule lists, and hash-table buckets all reduce to repeatedly searching a linear list and occasionally reorganizing it. The list update problem formalizes this: n items must be arranged in a list. At each time step, one of the items is requested, incurring cost equal to the position of the item in the list. After each request, the algorithm is allowed to rearrange the list. Moving the requested item closer to the front of the list is usually considered free, while any other exchanges would incur a cost of 1. The problem has been studied for over six decades, going back to McCabe [ 34 ] . Most of the early work on the problem considered the i.i.d. model , where requests at different time steps are sampled independently from the same distribution. Later, it was also studied in the adversarial setting, and became foundational to the area of competitive analysis [ 38 ] . We focus here on the original i.i.d. setting [ 34 ] . Our main result is that the Transposition rule (swap the requested item with its predecessor) is nearly optimal, confirming a 50-year old conjecture by Rivest [ 37 ] up to an unavoidable additive constant. Denote by p_{i} the probability of requesting item i , and assume without loss of generality that items are labeled such that p_{1}\geq p_{2}\geq\dots\geq p_{n} . Clearly, the optimal policy is to maintain the static ordering by decreasing probabilities, which achieves the minimal expected access cost of \displaystyle\mathrm{OPT}=\sum_{i=1}^{n}ip_{i}. This strategy presumes exact knowledge of the access probabilities, which is typically unavailable. A natural alternative is to order items by their observed request frequencies, which converges asymptotically to the same expected cost. However, as noted by Knuth [ 32 ] and Rivest [ 37 ] , the extra memory space required for maintaining frequency counters would be undesirable as it could be better used for alternative nonsequential search techniques. Research has therefore focused on memoryless (self-organizing) heuristics, which do not maintain any memory beyond the current ordering of items. The two rules that have been studied by far the most extensively since the 1960s are Move-to-Front and Transposition : Move-to-Front: Move the requested item to the front of the list, without changing the relative order of other items. Transposition: Swap the requested item with its immediate predecessor (unless it is already at the front). If requests are adversarial, then Move-to-Front is known to be superior, achieving a constant competitive ratio whereas the competitive ratio of Transposition is unbounded [ 38 ] . Indeed, consider alternately requesting the last two items of the list; then Transposition incurs a cost of n per time step, whereas an optimal algorithm could bring those two items to the front. Move-to-Front is also known to perform better on request sequences exhibiting strong locality of reference [ 28 , 7 , 2 ] . The situation reverses in the i.i.d. setting: For any distribution p , any memoryless rule induces a Markov chain whose states are the permutations of the items. The rules are then typically evaluated by their stationary expected cost, capturing long-run behavior when the access law is stable. For Move-to-Front, [ 18 ] showed that its stationary expected cost is within a factor \frac{\pi}{2}\approx 1.57 of \mathrm{OPT} for any distribution p , and this is tight when p_{i}\propto 1/i^{2} [ 25 ] . Rivest [ 37 ] showed that Transposition has stationary expected cost less than or equal to Move-to-Front, with equality only in trivial cases ( n\leq 2 or p_{i}=1/n ). Thus, Transposition is preferable in the i.i.d. setting, or if the distribution evolves only slowly. Transposition has also been noted for its efficient implementation using arrays, since swapping adjacent entries is very fast. This avoids the overhead of maintaining pointers as needed for linked list implementations, which are typically used for Move-to-Front [ 28 ] . A 50-year-old conjecture by Rivest [ 37 ] states that Transposition is optimal among memoryless rules for any distribution p , and Andrew Yao showed that there exist distributions where Transposition is the unique optimal memoryless rule (see [ 37 ] ). The literal version of Rivest’s conjecture was shown to be false by a counterexample with n=6 items [ 6 ] . This counterexample does not settle the broader conjecture that Transposition is asymptotically optimal in a suitable sense, which has continued to attract attention. However, improving performance bounds on Transposition has resisted progress for decades, with advances restricted to specific distributions [ 33 , 22 , 29 ] . For example, [ 22 ] showed that the logarithm of tail probabilities of the search cost is asymptotically optimal for two families of distributions. Very recently, Indyk, Quaye, Rubinfeld and Silwal [ 29 ] showed that the stationary expected cost of Transposition is at most (1+o(1))\mathrm{OPT} as n\to\infty in the case of a Zipfian distribution p_{i}\propto 1/i^{\alpha} with 0<\alpha\leq 2 . Note that n\to\infty alone does not suffice to achieve ratio 1+o(1) in general, as the example in [ 6 ] can be extended to arbitrary n by adding items with vanishing probability. For general distributions, prior to our work the best upper bound on the cost of Transposition was \frac{\pi}{2}\mathrm{OPT} , inherited from the according tight bound on Move-to-Front and the aforementioned property that Transposition is no worse than Move-to-Front. An intuitive reason why Move-to-Front is comparatively easier to analyze is that it maintains a simple structure: at any time, the list is ordered by last request times. In contrast, under Transposition the position of an item is shaped by a more intricate interaction of past requests. The difficulty of analyzing Transposition has been noted explicitly in the literature; for example, Hester and Hirschberg [ 28 ] write: “Transpose is widely mentioned in the literature, but authors merely state an inability