Tsetlin library
A Tsetlin library is a Markov chain that repeatedly moves an independently requested object to the front of an ordered list.
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
- Rhodes and Schilling. Unified theory for finite Markov chains. arXiv:1711.10689v3 (2019), section 3.1.
- Chatterjee, Diaconis and Kim. Enumerative Theory for the Tsetlin Library. arXiv:2306.16521v1 (2023), equation (1) and section 2.2.
- Fricker, Robert and Roberts. A versatile and accurate approximation for LRU cache performance. arXiv:1202.3974v1, sections 2-3.
- Hesela. Exact rational three-object stationary LRU control and move-to-front transition check.
- Nestoridi. Optimal strong stationary times for random walks on the chambers of a hyperplane arrangement. arXiv:1706.00310v2, section 2.1, Definition 7.
- Hesela. Exact two-object warm-up stopping-time control, formulae and post-collection window means.
Further reading
- Hesela. Reproduce the six-state calculation using Python's standard-library rational arithmetic.
- Hesela. Exact recency probabilities under independent requests.
- Hesela. Reproduce the exact warm-up selection calculation with Python rational arithmetic.
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.