online paging and caching
Your computer keeps a small, fast memory (a cache, or pages of RAM) that can hold only k items, while the data you might want lives in a huge, slow store. When the program asks for an item already in the cache, that is a 'hit' and is essentially free. When it asks for one that is not there, that is a 'miss': you must fetch it (slow) and, if the cache is full, throw out one of the k items to make room. The whole game is choosing WHICH item to evict, again and again, without knowing what will be requested next. This is paging, and it is online by its very nature.
Because evictions are irrevocable and the future is hidden, we measure caching rules by their competitive ratio against OPT, the offline optimum that knows the entire request sequence. OPT has a famously simple rule (Belady's): on a miss, evict the item whose next use is farthest in the future. We cannot run OPT online — it needs the future — but it is the yardstick. The natural online rule is LRU (Least Recently Used): evict the item that has gone unused the longest, betting that the recent past predicts the near future. A beautiful theorem says LRU (and FIFO) is exactly k-competitive: on any sequence it suffers at most about k times as many misses as OPT, and no deterministic online rule can promise better than k. The proof idea is a phase argument: chop the sequence into phases each containing k+1 distinct pages; OPT must miss at least once per phase, while LRU misses at most k times per phase.
Paging is the original and most influential online problem, and it explains why your CPU, browser, and database all use LRU-like policies. It also teaches a humbling lesson: k-competitive sounds bad (LRU could miss k times more than the all-knowing optimum), yet that factor only appears on adversarial sequences engineered to defeat it; on real workloads with locality, LRU is excellent. The honest caveats: the k-competitive bound is worst-case, randomized policies (like MARKER) improve the expected ratio to about 2*ln(k), and 'evict least recently used' is a heuristic for the future, not a guarantee about it.
Cache size k = 3, currently holding {A, B, C}. Requests: A (hit), D (miss, full -> evict). LRU evicts the least-recently-used, say B, giving {A, C, D}. OPT, seeing the future, evicts whatever is needed last. Across a long stream, LRU's total misses stay within a factor k of OPT's — and on locality-rich real traces, far closer than that.
LRU is k-competitive against the future-knowing optimum OPT (Belady's farthest-future rule).
LRU is k-competitive, and k is the best any deterministic policy can guarantee — but this is a worst-case bound on adversarial inputs. On real workloads with temporal locality LRU is near-optimal; the alarming factor of k rarely shows up. Randomized policies do better in expectation.