We maintain a number of "bookmarks" of pages that have been ejected. There is no limit to the number of bookmarks. The most recently used page we call the "MRU page," the other the "LRU page." Any page that is not in the cache and not bookmarked is called a "new page" (though we might have seen it before since we sometimes erase bookmarks). Initially, there are no bookmarks. Action of the algorithm at each step: 1. If the MRU page is requested, nothing happens. 2. If the LRU page is requested, all bookmarks are erased. 3. If a bookmarked page is requested, the LRU is ejected and all bookmarks are erased. 4. If a new page is requested, the LRU is ejected with probability p, and the MRU is ejected with probability 1-p, where p = [Formula to be given]. The ejected page is bookmarked. (This increases the number of bookmarks by 1.) The formula for p, as well as the proof that this algorithm is 3/2- competitive, will be given in class. This algorithm can be generalized to any k, although that generalization is very complex, as it requires different kinds of marks on the cache pages and different kinds of bookmarks. The larger k, the more different kinds of marks and bookmarks we need. This complex algorithm is H_k-competitive, the best possible. The memory requirement is O(n), where n is the number of requests, so it grows without bound. Open Problem: What is the minimum memory needed for an H_k-competitive randomized online algorithm for the k-cache problem? Ans: if k = 2, one bookmark is necessary and sufficient. Ans: if k > 2, it is known that 5k^2H_k-k bookmarks are sufficient, but that has to be way too many. Maybe we'll solve this problem this semester.