Consider a finite-state Markov chain with transition matrix $P$. The chain starts in a state chosen uniformly over all the states and runs indefinitely from there.
We're going to examine only the $k ≥ 0$ most recent steps of the chain. In particular, we will consider the number of states that appear $0, 1,\ldots, k$ times in those most recent $k$ steps. Let's define a vector $C = [c_0, c_1, \ldots,c_k]$ whose $i$-th element is the number of states that have been visited $i$ times within the past $k$ steps.
For example, if $k = 4$, if the state space is $1, 2, \ldots, 10$, and if the chain is $$1, 2, 1, 4, 3, 2, 4, 3, 3, 2, 4, 5, 5, 3, 2, 1, 2, 3$$ then $c = [7, 2, 1, 0, 0]$.
What is the expected value of $C$ and, ideally, how is $C$ distributed?