caching - 使用离散时间马尔可夫链和概率进行缓存

Question

假设 Web 服务器有三个网页，分别标记为 1、2 和 3。用户从一个页面移动到另一个页面的概率为：

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

（例如，当用户当前位于第 1 页时，他们接下来以概率 x 请求第 2 页，并以概率 (1-x) 请求第 3 页。）假设 0 < x < y < 1/2。假设 Web 服务器的缓存有足够的内存来存储两个页面。每当请求针对不在缓存中的页面时，浏览器都会将该页面存储在缓存中，替换下一个最不可能被请求的页面。例如，如果缓存包含页面 2 和 3，并且请求了页面 1，则缓存将更新为包含页面 1 和 3（因为 x < 1-x）。

(a) 找出缓存包含第 1 页和第 2 页的时间（请求）比例。（提示：注意您选择的状态。）

(b) 找出缓存未命中的概率（一个请求在缓存中不可用）。

点击这里查看问题的图片版本

标签： cachingprobabilitymarkov-chains

Answer 1

请看这些图片。

第 1 部分。

第 2 部分。

第 3 部分。