tsetlin-library · research · also Move-to-front Markov chain

Tsetlin library

A Tsetlin library is a Markov chain that repeatedly moves an independently requested object to the front of an ordered list.

Related Observatory article: Read on hesela.com

For fixed positive request probabilities p_i, a state lists all objects from most to least recently requested. Its stationary probability is the product, over positions k, of p at position k divided by the total p of objects at positions k through n. This is successive popularity-weighted sampling without replacement, not a uniform permutation. [1] [2]

LRU connection: with equal-size objects, instantaneous fills and demand admission, the first C positions are the resident set. Under independent requests, averaging their total request probability over stationary states gives the hit ratio. For weights (3, 2, 1), exact arithmetic gives 7/18 at one slot and 133/180 at two slots. These are constructed probabilities, not trace measurements. [3] [4]

The model specifies request identities, not elapsed time. Stationarity does not supply a warm-up duration, and measured popularities alone do not establish request independence. A deterministic periodic sequence may have the same frequencies but different cache behavior. [3]

Warm-up selection: in an exact two-object IID model with probabilities (2/3, 1/3), a one-slot cache has next-hit probability 5/9 after a fixed request index, but 4/9 just after first seeing both labels. The completing miss is excluded. [8]

Coverage is not conditional stationarity: given collection at request 2, A is resident with probability 1/2, not 2/3. One fresh request resets this one-slot IID state, not arbitrary caches. [7] [8]

Relations

related
Che approximation, Independent reference model, Least recently used replacement, Move-to-front transform

Limitations

  • Complete state enumeration grows factorially with catalogue size; the linked six-state control is not a scalable cache estimator. [4]

Citations

  1. Rhodes and Schilling. Unified theory for finite Markov chains. arXiv:1711.10689v3 (2019), section 3.1. (accessed 2026-11-21)
  2. Chatterjee, Diaconis and Kim. Enumerative Theory for the Tsetlin Library. arXiv:2306.16521v1 (2023), equation (1) and section 2.2. (accessed 2026-11-21)
  3. Fricker, Robert and Roberts. A versatile and accurate approximation for LRU cache performance. arXiv:1202.3974v1, sections 2-3. (accessed 2026-11-21)
  4. Hesela. Exact rational three-object stationary LRU control and move-to-front transition check. (accessed 2026-11-21)
  5. Nestoridi. Optimal strong stationary times for random walks on the chambers of a hyperplane arrangement. arXiv:1706.00310v2, section 2.1, Definition 7. (accessed 2026-11-22)
  6. Hesela. Exact two-object warm-up stopping-time control, formulae and post-collection window means. (accessed 2026-11-22)

Further reading

  1. Hesela. Reproduce the six-state calculation using Python's standard-library rational arithmetic. (accessed 2026-11-21)
  2. Hesela. Exact recency probabilities under independent requests. (accessed 2026-11-21)
  3. Hesela. Reproduce the exact warm-up selection calculation with Python rational arithmetic. (accessed 2026-11-22)
Sources & caveats
  • Primary-source review of the stationary product formula and its application to equal-size LRU under independent references. This is not a new theorem or a hardware benchmark.
  • The exact six-state arithmetic separately checks probability mass, full transition stationarity and pairwise order identities. No warm-up or convergence rate is inferred.
  • The 2024 journal paper DOI is 10.1016/j.jalgebra.2023.08.009; the explicitly versioned 2023 preprint supplies the cited equation.
  • Warm-up counterexample uses original exact arithmetic, independent finite-history enumeration and transition-reward checks. The source supplies the definition of strong stationarity; the control is not a replication of its general hyperplane-walk results.

JSON: /data/terms/tsetlin-library.json

Published by Hesela team · Updated

Report a correction · Editorial standards · Reuse guidance

Cite this page
Hesela team. Tsetlin library. Hesela. 2026-11-22. https://hesela.dev/terms/tsetlin-library/