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

Question

假设网络服务器有三个网页，分别标记为 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 页时，他们接下来请求第 2 页的概率为 x，第 3 页的概率为 (1-x)。）假设 0 < x < y < 1/2。假设 Web 服务器的缓存有足够的内存来存储两个页面。每当请求的页面不在缓存中时，浏览器都会将该页面存储在缓存中，替换下一个最不可能被请求的页面。例如，如果缓存包含第 2 页和第 3 页，并且请求第 1 页，则缓存将更新为包含第 1 页和第 3 页（因为 x < 1-x）。

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

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

Click here for picture version of question

Answer 1

请看这些图片。

Part 1.

Part 2.

Part 3.