Motivation
Deterministic paging has a worst-case competitive factor of for a cache of size . Randomization can change the comparison when the request sequence is fixed independently of the algorithm's random choices. A randomized marking algorithm keeps recently requested pages safe within a phase and chooses uniformly among the remaining candidates when it must evict.
The expected number of faults is controlled by a harmonic sum. The proof separates newly appearing pages, which must fault, from old pages that may have been evicted at random. It also states the adversary model explicitly: the fixed sequence cannot be chosen after observing the algorithm's private random evictions.
Definitions
Definition 7.5.1
(Demand paging against an oblivious adversary)
Use the demand-paging model with cache capacity and identical initial caches for online and offline schedules. A fault costs one. The input is a finite request sequence fixed before any random choices; this is an oblivious adversary. Expectations below are over the algorithm's random choices for that fixed input.
Definition 7.5.2
(Randomized marking algorithm)
Partition the sequence greedily into phases, starting a new phase when a request would introduce a st distinct page. Thus every phase except possibly the last has exactly distinct pages. At the start of each phase clear all marks. After serving a request, mark its page. On a fault, evict a uniformly random unmarked cached page. Before a request to a new page in the phase, fewer than pages are marked, so an unmarked cached page exists.
Definition 7.5.3
(Clean and stale pages)
For a phase after the first, call a distinct requested page clean if it did not occur in the preceding phase, and stale otherwise. Let be the number of clean pages in phase . Since the preceding phase is complete, its pages are exactly the cache contents at the beginning of the next phase: each was marked on request and could not subsequently be evicted in that phase.
Definition 7.5.4
(Harmonic number)
Write .
Theorems
Theorem 7.5.5
(Expected randomized marking cost)
For every fixed finite request sequence, randomized marking satisfies
The expectation is over the algorithm's choices, while is the minimum offline fault count on that same fixed sequence.
Theorem 7.5.6
(Expected faults in one phase)
Conditioned on the fixed request sequence, the expected number of faults in any phase after the first is at most .
Proofs
Proof: a uniform set of missing stale pages
Proof
(Expected cost of one phase)
Fix a phase after the first and its preceding phase set , which contains exactly pages. After distinct stale pages have been requested in the current phase, there are pages of that have not yet been requested in this phase. Let be the number of distinct clean pages already requested. All requested pages are marked and remain in the cache. Exactly of the unrequested pages of are absent from the cache: the cache has slots, and the marked clean pages occupy slots that were occupied by pages of at the boundary.
Among the unrequested pages of , the missing pages form a uniformly random -element subset. This invariant holds initially because . A new clean request faults and evicts a uniformly chosen unmarked cached page of ; adding that victim to the missing set gives a uniform subset of size . For a new stale request, if the requested page is present, marking it removes a present page from consideration. If it is absent, loading and marking it removes a missing page from consideration and a uniformly chosen present unmarked page is evicted. In either case, conditional on that hit or miss, the remaining missing set is uniform among subsets of the appropriate remaining size. Repeated requests to marked pages do not change the invariant.
The sequence is fixed independently of the random choices, so its next previously unrequested stale page is not selected by inspecting the random missing set. Its fault probability is therefore , at most . There can be at most distinct stale requests. Summing the bound over their possible positions gives at most expected stale faults. Every clean page faults exactly once, and repeated requests to marked pages hit. The total expected phase cost is at most .
Proof X-ray
Why the next page must be fixed independently
Three ingredients combine, and each is used once. Counting: every requested page is marked and so stays cached, and the cache has slots, so exactly of the unrequested old pages are present and are missing. Symmetry: each eviction picks uniformly among the unmarked cached pages, so no unrequested old page is more likely than another to be among the missing ones, and a stale page requested next is missing with probability . Obliviousness: this last step uses that the next requested page was fixed before the coins were tossed. A request chosen by looking at the cache could always name a missing page, giving probability one instead of , and the harmonic bound would fail. Finally and a sum over the possible values of give .
Proof: comparing clean pages with offline faults
Proof
(Summing phases against the offline optimum)
For , the union of the page sets of phases and contains the pages of phase plus clean pages. During those two phases, an offline cache of size must fault at least times: starting with at most pages, each fault can introduce at most one additional distinct requested page.
Summing this inequality over phase boundaries counts any offline fault in at most two adjacent phase pairs. Therefore . The randomized algorithm faults at most times in the first phase, since each page is marked after its first request. Linearity of expectation and the phase bound yield
No independence between phases is required for linearity of expectation. The invariant holds at every phase boundary because marking leaves the entire preceding phase set in cache. The additive accommodates the initial phase without assigning it a fictitious preceding request set.
Worked examples
Worked example 7.5.7
(One clean page with capacity two)
Let the previous phase set be and begin the next phase with a request to a new page . The algorithm faults and evicts or with probability one half each. If the next request is the fixed stale page , it faults with probability one half. The expected number of faults in these two requests is .
Worked example 7.5.8
(Harmonic estimate for capacity three)
For and one clean page in a phase, . The theorem bounds the expected phase cost by . This is an upper bound, not necessarily the exact expectation for a given request order; the proof replaces the number of clean pages requested so far by its maximum value .
Worked example 7.5.9
(A phase with no clean pages)
If the current phase requests only pages of the preceding phase, all of them are cached at the boundary. No request faults, so the phase cost is zero. This agrees with the bound , including for a final incomplete phase.
Worked example 7.5.10
(The offline pair certificate)
With , suppose phase requests and phase requests . There are two clean pages, , and five distinct pages across the two phases. An offline cache beginning the pair with only three pages must incur at least two faults during the pair, regardless of its initial contents and eviction choices.
Common mistakes
Counterexample mode
Observing the random eviction changes the game
With cache and , request a clean page . A fixed next request to faults with probability one half. An adversary that watches whether or was evicted and then requests that evicted page forces a fault with probability one. The latter sequence depends on the random choice and is outside the fixed-input calculation.
Common mistake
(Applying uniformity to the whole universe)
The uniform-subset statement concerns unrequested pages of the preceding phase, not arbitrary pages of the universe. Clean pages already requested are marked and cached. A stale page requested twice can fault only on the first request; afterward it is marked until the next phase.
Common mistake
(Overstating what the logarithmic bound shows)
The theorem supplies an upper bound because for . It does not establish an optimal randomized lower bound or claim the displayed constant is sharp. The offline optimum is evaluated on the same fixed sequence, not on an average over sequences generated in response to the random cache.
Understanding the uniform invariant
Imagine labeling the unrequested old pages without assigning them different future importance. At a clean fault, every currently cached unmarked old page is equally likely to be evicted. A missing set that was uniformly distributed stays uniform after adding this random victim. At a stale fault, the requested missing page is restored and the uniformly chosen victim takes its place among the remaining old pages. These operations are symmetric in the other unrequested old pages.
The next stale identity can be arbitrary as long as it was fixed before the random choices. It need not itself be chosen uniformly. The randomness is in which pages are missing, and symmetry gives the same miss probability for each particular unrequested stale page. This distinction is essential when using the argument on an arbitrary fixed sequence rather than a random input distribution.
The harmonic sum appears because the number of eligible old pages shrinks as distinct stale requests arrive. We bound the miss probability by a reciprocal of the number remaining and sum over possible positions. This can be loose, but it gives a simple upper bound without assuming that miss events are independent.
From reciprocal terms to a logarithm
For each integer , the reciprocal is at most the integral of from to . Adding these inequalities gives , including . The resulting bound grows logarithmically in cache size, whereas the deterministic lower bound grows linearly. Those statements use different adversary assumptions, so they should not be compared without carrying the quantifiers along.
The proof of the phase estimate sums probabilities, not products of probabilities. Let an indicator equal one if a particular first stale request faults and zero otherwise. Its expectation is its fault probability. The total number of stale faults is the sum of these indicators, so its expectation is the sum of their expectations even when one eviction affects later faults. Assuming independent faults would be both unnecessary and generally wrong.
A phase may end before all old pages are requested. The analysis can still sum reciprocal bounds over all possible stale positions: the absent positions contribute no actual fault, and adding nonnegative terms only weakens the upper bound. This is why the argument also handles the final incomplete phase without requiring it to contain different requests.
Every randomized algorithm has a ratio of at least H_k against an oblivious adversary.
A natural next question
Is logarithmic growth unavoidable?
Every randomized algorithm has a ratio of at least H_k against an oblivious adversary.
Yes. It is known that no randomized paging algorithm has competitive ratio below against an oblivious adversary, so a factor growing like cannot be avoided. The marking bound is therefore of the right order; the matching lower-bound proof is outside this unit.
Summary
Random marking preserves the requested pages of a phase and makes the missing unrequested old pages uniformly distributed. Their marginal miss probabilities sum to a harmonic bound. Adjacent-phase counting then compares the number of clean pages to offline faults, giving an guarantee against fixed sequences.
Exercises
Quick check
(Compute and the displayed phase bound when and .)
Solution · Answer
. The upper bound is . A bound can exceed the maximum possible two faults in that phase; it remains valid but is not tight.
Quick check
(At the beginning of a phase after a complete preceding phase, why are all preceding-phase pages in the cache?)
Solution · Answer
The preceding phase requested exactly distinct pages. Each was marked when requested, and a marked page cannot be evicted before the phase ends. Since the cache has slots, it contains exactly those pages at the boundary.
Quick check
(If two adjacent phases contain distinct pages in total, why must any offline schedule fault at least three times during the pair?)
Solution · Answer
The offline cache contains at most distinct pages before the pair starts. Each of the additional three distinct requested pages must be brought into the cache on some fault. A single fault loads at most one requested page, so at least three faults are necessary.
Quick check
(Explain why repeated requests to a page already marked in a phase cause no additional fault in that phase.)
Solution · Answer
Once the first request is served, the page is marked. The eviction rule chooses only unmarked pages until all marks are cleared at the next phase boundary, so the page stays in cache during the rest of the current phase.