$25\mathrm{.}8$ Caching

If you think about it$,$ web browsing is basically a Markov chain $-$ the page

you will go to next depends on the page you are currently at$.$ Suppose

our web server has three pages, and we have the following transition

probabilities:

$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,$

where $P_{i,j}$ represents the probability that I will next request page $j,$ given

that I last requested page $i.$ Assume that $0.$

Recall that web browsers cache pages $so$ that they can $be$ quickly retrieved

later. $We$ will assume that the cache has enough memory $to$ store two

pages. Whenever a request comes $in$ for a page that $is$ not cached, the

browser will store that page $in$ the cache, replacing the page least likely $to$