Great question—this part of the randomized caching chapter in Kleinberg & Tardos's Algorithm Design definitely trips up a lot of people when they first encounter it. Let me break down why the padding is necessary, and what you'd have to account for if you tried proving with the original sequence σ instead.

Why the Padding Is Used #

The extra requests added to the start and end of σ serve to eliminate messy edge cases, making the phase-based analysis clean and uniform across the entire sequence. Here's the breakdown for each padding step:

1. Phase 0 (Requesting all initial cache items) #

Marking algorithms rely on strict phase boundaries defined by "processing k distinct items before starting a new phase." The original sequence σ starts with an arbitrary initial cache state—some items might already be present, others not, and none are marked at the start.

By adding Phase 0, we:

• Force all items in the initial cache to be marked, aligning the starting state of Marking algorithms with the phase definition (all items unmarked at the start of a phase, then marked as requested).
• Ensure the first "real" phase (Phase 1) starts with a clean slate: all cache items are unmarked, and the phase will strictly trigger a new phase only when the k+1th distinct item is requested. This eliminates any ambiguity in how we count phases and their associated cache misses.

2. The Final Tail (Requesting each item in the optimal algorithm's cache twice) #

The original sequence σ might end mid-phase—meaning Marking algorithms haven't encountered a request that forces them to "declare the phase over" (i.e., not all cache items are marked yet). This would break the clean "each phase has exactly k distinct items, and at most k misses" rule we use for the upper bound.

The tail padding fixes this by:

• Forcing the final phase to complete: requesting each item in the optimal algorithm's cache twice ensures that Marking algorithms will mark all remaining unmarked items in their cache, triggering the phase end condition.
• Aligning the cache states of the Marking algorithm and optimal algorithm at the end of the sequence, which is critical for comparing their total miss counts (a core part of proving the competitive ratio).

What Special Cases Arise Without Padding #

If you tried to prove using the original sequence σ directly, you'd have to handle two major edge cases that complicate the analysis:

1. Non-uniform Initial Phase #

The first phase of σ might not follow the "k distinct items" rule because some items are already in the initial cache. For example:

• If the initial cache contains 3 of the first k distinct items in σ, the Marking algorithm would only miss k-3 times in this phase, not k.
• You'd have to separately analyze this initial phase's miss count instead of applying the general "each phase ≤k misses" rule, adding extra steps to the proof.

2. Incomplete Final Phase #

The end of σ might leave the Marking algorithm in a phase that never completes. This means:

• You can't count this partial phase towards the total kr miss bound (since r is the number of complete phases).
• You'd have to prove that even this partial phase can't have more than k misses, which requires additional reasoning about unmarked items and eviction behavior that the padding avoids.

3. Misaligned Cache States at Sequence End #

Without the tail padding, the optimal algorithm's cache state at the end of σ might have no clear relationship to the Marking algorithm's cache. This makes it harder to bound the ratio of Marking's misses to the optimal algorithm's misses, which is the goal of the competitive analysis.

Bottom Line #

Padding the sequence is a standard trick in algorithm analysis to normalize boundary conditions—it lets us apply a single, uniform rule (each phase has k distinct items, ≤k misses) across the entire sequence without special-case handling. You could technically prove the result with the original σ, but it would be longer, more error-prone, and distract from the core intuition of how Marking algorithms work.

内容的提问来源于stack exchange，提问作者Luca