Theorem: Bookmarks is 3/2-competitive.

Proof:  Define a "phase" as follows.  Before the first request of a phase,
the support of the work function consists of one configuration.  The last
request of a phase is when the support of the work function is once again
just one configuration, except for a possibly incomplete phase at the end.

The proof consists of first verifying the following claims.

Claim 1: The cardinality of Supp(w) is M+1, where M is the number of
bookmarks.  If b_1, ... b_M are the bookmarked pages, Supp(w) consists
of the pairs (mru,lru), (mru,b_1), ... (mru,b_M).

Claim 2: If X in Supp(w), the probability that (mru,lru) = X is 1/(M+1).

Claim 3: If the length of a complete phase is d, then the optimal cost for that
phase is at least d-1.  For an imcomplete phase of length d, the optimal cost
is d.

Claim 4: If the length of a phase is d, then Bookmark's cost for that phase
is d - 1/d.  For an incomplete phase of length d, the Bookmark's cost is d.

The Theorem follows immediately from the claims.
