Consider a discrete-time random process X(t) taking values {1,2,...,n} for integer n>1. For all times s not t, X(s) and X(t) are independent.
Let $p_k=P(X(t)=k)$, meaning X is stationary.
(a) Find the probability that $X(t+1)$ is not equal to $X(s)$ for any interval {t-T+1, t-T+2,...,t} of length T>1.
(b) Find the expected number of different values of X in this interval.
(c) Consider a cache that keeps track of the last B>1 different values of X. Considering (a) and (b), find an approximate expression for the miss rate of the cache.
I am stuck on part b and c.
For part a, I want to compute the probability that
$$P[X(t+1)\ne X(t-T+1)]\cap P[X(t+1)\ne X(t-T+2)]\cap\cdots \cap P[X(t+1)\ne X(t)]$$
I start this by defining the conditional probability:
$$P[(X(t-T+1)\neq X(t+1)) \cap \cdots \cap (X(t)\neq X(t+1)) \mid X(t+1)=n]$$
Since the prior is independent of X(t-T+1) for all t, these can be split into:
$$P[X(t-T+1)\neq X(t+1)\mid X(t+1)=n] \cdots P[X(t)\neq X(t+1)\mid X(t+1)=n] $$
which is equal to:
$$\sum_{k=1}^{N}(1-p_k)^Tp_k$$
I am pretty confident this is correct. Now for part b....
For part b, I have to find the expected number of different values of X in this interval. My thought is to approach this problem as computing the number of unique values of set {1,2,3,...,n} which can fill the interval of size T where T>1. I think this is equivalant to saying if you choose T items from n with replacement modulated by the probabilities $p_k$, what is the number of expected unique items you will have.
Suppose $T=2$ and I want compute part b. For the first slot, I have $p_k$ probability of the first item. For the second slot, I have a probability $1-p_k$ of it not being item k. I am stumped at this point.