# SPDX-License-Identifier: CC0-1.0 """Exact two-object IID warm-up selection control, not a workload benchmark.""" from fractions import Fraction import json from pathlib import Path import sys def probability(p): if isinstance(p, bool) or not isinstance(p, (int, Fraction)): raise ValueError("p must be an exact rational probability") p = Fraction(p) if not 0 < p < 1: raise ValueError("Both objects must have positive probability") return p def positive_integer(n, minimum=1): if type(n) is not int or n < minimum: raise ValueError("Expected an integer at least " + str(minimum)) return n def stationary_hit(p): p = probability(p) return p * p + (1 - p) ** 2 def collection_atom(p, t): p = probability(p) positive_integer(t, 2) q = 1 - p # Before the first change, every draw is the same object. a = q ** (t - 1) * p b = p ** (t - 1) * q return {"lastA": a, "lastB": b, "mass": a + b} def uncollected_mass(p, horizon): p = probability(p) positive_integer(horizon) return p ** horizon + (1 - p) ** horizon def stopped_window_hit(p, length): p = probability(p) positive_integer(length) h = stationary_hit(p) return (2 * p * (1 - p) + (length - 1) * h) / length def report(): p = Fraction(2, 3) q = 1 - p h = stationary_hit(p) rows = [ ("After a fixed request index t >= 1", p, h), ("At first collection of both objects T", q, 2 * p * q), ("At collection, conditional on T = 2", Fraction(1, 2), Fraction(1, 2)), ("One fresh request after collection T + 1", p, h), ] return { "schemaVersion": 1, "generated": "2026-11-22", "license": "CC0-1.0", "scope": "Constructed exact probabilities, not observed hit counts or a paper reproduction.", "method": "Rational two-object calculation with geometric tails and independent enumerated and state-transition tests.", "requestProbabilities": {"A": str(p), "B": str(q)}, "assumptions": [ "IID requests with fixed probabilities p and 1-p, with 0 < p < 1", "One-slot demand-admitted cache; instantaneous fills; no TTL or prefetch", "T is the first request index at which both object identities have appeared", "Next-hit probability refers to the request AFTER the stated observation", ], "rows": [ {"observation": label, "residentAFraction": str(a), "nextHitFraction": str(hit), "nextHitProbability": float(hit)} for label, a, hit in rows ], "formulae": { "stationaryNextHit": "p^2 + (1-p)^2", "stoppedNextHit": "2*p*(1-p)", "stationaryMinusStopped": "(2*p-1)^2", "meanNextMHitIndicators": "stationaryNextHit - (2*p-1)^2/m", "collectionTail": "P(T>t) = p^t + (1-p)^t, t>=1", }, "windows": [ {"requestsAfterT": m, "expectedHitFraction": str(stopped_window_hit(p, m))} for m in [1, 2, 10, 100] ], "conditionalControls": [ {"collectionAt": t, "probability": str(collection_atom(p, t)["mass"]), "residentA": str(collection_atom(p, t)["lastA"] / collection_atom(p, t)["mass"])} for t in [2, 3, 4] ], "limitations": [ "The stopping request is a miss and is excluded from all next-hit and post-T window metrics.", "One fresh request resets this one-slot IID model; that is not a warm-up prescription for larger caches.", "A fixed cutoff alone does not establish stationarity in a different model.", "Fractions have no Monte Carlo uncertainty; uncertainty about real workload assumptions remains.", ], } if __name__ == "__main__": result = report() if sys.argv[1:] == ["--check"]: if json.loads(Path(__file__).with_name("warmup.json").read_text()) != result: raise SystemExit("Generated warm-up evidence differs") print("Exact warm-up evidence verified") elif not sys.argv[1:]: print(json.dumps(result, indent=2)) else: raise SystemExit("Usage: python3 -B warmup.py [--check]")