Suppose that a web server has three web pages, labelled 1, 2, and 3. The probabilities that a user moves from one page to another are:
P(1->1) = 0 P(1->2) = x P(1->3) = 1-x P(2->1) = y P(2->2) = 0 P(2->3) = 1-y P(3->1) = 0 P(3->2) = 1 P(3->3) = 0
(For example, when a user is currently at page 1, they request page 2 next with probability x and page 3 with probability (1-x).) Assume that 0 < x < y < 1/2. Suppose that the web server's cache has enough memory to store two pages. Whenever a request is for a page that is not in the cache, the browser will store that page in the cache, replacing the page least likely to be requested next. For example, if the cache contained pages 2 and 3, and page 1 was requested, the cache would be updated to contain pages 1 and 3 (since x < 1-x).
(a) Find the proportion of time (requests) that the cache contains pages 1 and 2. (Hint:be careful about your choice of state.)
(b) Find the probability of a cache miss (a request is not available in the cache).
