有効期間の更新と、切れたときのコスト

定義 4.1 の標準の設定で、次が成り立つ。

1. すべての $k$ について $t_{k+1} - t_k \lt \tau$ ならば、各 $k \ge 2$ の要求の時点で項目 $(\mu, x_{k-1})$ は生きている。会話がどれだけ長く続いても（$t_k - t_1$ が $\tau$ をどれだけ超えても）、キャッシュは切れない。
2. ある $k \ge 1$ について、$i \lt k$ では $t_{i+1} - t_i \lt \tau$ で、$t_{k+1} - t_k \ge \tau$ とする。このとき $k + 1$ 回目の要求の命中の長さは $0$ で、コストは $w L_{k+1}$ である。これは、切れなかった場合のコスト $r L_k + w d_{k+1}$ より $(w - r)L_k$ だけ大きい。
3. 2 種類の有効期間 $\tau_1 \lt \tau_2$ があり、書き込みの倍率が $w_1 \lt w_2$、読み取りの倍率はどちらも $r$ とする。$k + 1$ 回目の要求までの間隔 $G = t_{k+1} - t_k$ が確率変数で、$\Pr[G \lt \tau_1] = 1 - q$、$\Pr[\tau_1 \le G \lt \tau_2] = q$ とし、$k$ 回目までは切れていないとする。$k + 1$ 回目の要求のコストの期待値は、短い有効期間で $r L_k + w_1 d_{k+1} + q(w_1 - r)L_k$、長い有効期間で $r L_k + w_2 d_{k+1}$ である。したがって、長い有効期間のほうが期待値が小さいのは

のとき、またそのときに限る。