Probability of a time-dependent set of states in Markov chain Consider a Markov matrix $P$ defining $m$ states. For each time $n$, define a set of states $S_n$ that contains a predefined subset of the states $\left\{ {1,...,m} \right\}$.
For time $n=k$, I would like to calculate the probability that at time $n=1$ the state was one of the states in $S_1$, AND at time $n=2$ the state was one of the states in $S_2$ and so on, such that at time $n=k$ the state was one of the states in $S_k$. Is there any simple formula for calculating this probability?
As an example, consider a Markov chain with $5$ states $\left\{ {1,2,3,4,5} \right\}$, with ${S_1} = \left\{ {1,2,3} \right\},{S_2} = \left\{ {2,3} \right\},{S_3} = \left\{ {2,3,4,5} \right\}$. The question in this case is: What is the probability that at time $n=1$ the state is either $1$,$2$ or $3$, AND at time $n=2$ the state is either $2$ or $3$, AND at time $n=3$ the state is either $2,3,4$ or $5$?
Edit:
As a concrete example, consider the balls-and-bins model, where there are $m$ balls and $N$ bins, each ball is assigned independently at random to one of the bins. The states correspond to the number of non-empty bins. I would like to find the probability that the $n^{\rm th}$ ball is assigned such that at least $f(n)$ bins are already non-empty. It can be assumed that $f(n)$ is a monotonically increasing function of $n$.
 A: Define $A_k = \{X_k \in S_k, X_{k-1} \in S_{k-1}, \ldots, X_1 \in S_1\}$. Assume that $Pr[X_1=j]$ is known for all $j \in S_1$. 
For $k>1$, note that $Pr[A_k|A_{k-1}] = \frac{Pr[A_k, A_{k-1}]}{Pr[A_{k-1}]} = \frac{Pr[A_k]}{Pr[A_{k-1}]}$. 
For $k>1$ define: 
\begin{align} 
q[k] &= Pr[A_k|A_{k-1}]\\
r_j[k] &= Pr[X_k=j|A_{k-1}] \: \: \forall j \in S_k
\end{align}
Define $q[0]=1$, $r_j[1] = Pr[X_1=j]$.  Define $Pr[A_0]=1$.
Iterate on the following for $k\in\{1, 2, 3, \ldots\}$:
On iteration $k$:  
Assume the following is known: 
$q[k-1]$, $Pr[A_{k-1}]$, and $r_j[k]$ for $j \in S_{k}$ (these are indeed known for $k=1$). 
Then do the following steps: 
1) Compute $q[k]$ in terms of the knowns. 
2) For each $j \in S_{k+1}$, compute $r_j[k+1]$ in terms of the knowns. 
3) $Pr[A_k]=q[k]Pr[A_{k-1}]$.

Each iteration has roughly the same complexity. On each iteration, the complexity of step 2 is about the same as the complexity of multiplying a matrix by a vector.

Another method would be to augment the state space by adding a "state 0" that is a "trapping state" from which, if entered, you can never leave.  Then appropriately adjust the transition probabilities. 
