Cross Validated is a question and answer site for people interested in statistics, machine learning, data analysis, data mining, and data visualization. It only takes a minute to sign up.
Sign up to join this community
Let's say we have a discrete-time Markov chain with a transition matrix $P$. If we know the initial state $x_0$, we can predict the probabilities of future states by iterating the chain as $x_{t+1}$ = $x_t P$.
But what if we know $x_0$ and also some future state $x_k$? What can we say about the probabilities of states $x_1..x_{k-1}$?
Besides direct answers, I would appreciate pointers to relevant literature. My Google search was fruitless, probably because I don't know what to look for.
I'll assume a finite state space $\mathcal{S} = \{s_1, \dots, s_m\}$. Let $X_t$ be a random variable representing the state at time $t$, and let $x_t \in \mathcal{S}$ denote a particular realization of this random variable. Transition probabilities are given by $m \times m$ stochastic matrix $P$, where $P_{ij}$ gives the probability of transitioning from state $s_i$ to state $s_j$ in a single timestep. I'll assume the Markov chain is time-homogeneous, so the transition probabilities are constant across time.
The question is essentially asking for the conditional distribution of the intermediate states $X_1, \dots, X_{k-1}$, given known initial state $X_0=x_0$ and final state $X_k=x_k$. By the definition of conditional probability, this is:
$$p(x_1, \dots, x_{k-1} \mid x_0, x_k) \ = \ \frac{p(x_0, \dots, x_k)}{p(x_0, x_k)} \tag{1}$$
Note that the numerator in $(1)$ can be rewritten as $p(x_1, \dots, x_k \mid x_0) p(x_0)$ and the denominator as $p(x_k \mid x_0) p(x_0)$. Substituting these in, the $p(x_0)$ terms cancel and we can rewrite $(1)$ as:
$$p(x_1, \dots, x_{k-1} \mid x_0, x_k) \ = \ \frac{p(x_1, \dots, x_k \mid x_0)}{p(x_k \mid x_0)} \tag{2}$$
The numerator and denominator in $(2)$ can be calculated as follows.
The numerator $p(x_1, \dots, x_k \mid x_0)$ is the probability of the sequence $x_1, \dots, x_k$ following starting state $x_0$. Recall that, for a Markov chain, this is given by:
$$p(x_1, \dots, x_k \mid x_0) = \prod_{t=1}^k p(x_t \mid x_{t-1}) \tag{3}$$
where the transition probabilities $p(x_t \mid x_{t-1})$ are specified by the transition probability matrix $P$.
The denominator $p(x_k \mid x_0)$ is a normalizing constant, representing the probability of ending in state $x_k$ after $k$ time steps, given that we start in state $x_0$. Recall that $k$-step transition probabilities for a Markov chain are given by $P^k$, the $k$th power of transition probability matrix. The $(i,j)$th element of this matrix gives the probability of ending in state $s_j$ after $k$ timesteps, given that we start in state $s_i$. Therefore, if $x_0 = s_i$ and $x_k = s_j$:
$$p(x_k \mid x_0) = (P^k)_{ij} \tag{4}$$
I'm going to use a different notation to that you used in your question for this answer.
We say $X_n$ (for $n >= 0$) is a markov chain with initial distribution $\lambda$ and transition matrix $P$ if for all $n >= 0$ and states $i_0, i_1, ..., i_{n+1}$ if the two conditions below are met:
(i) $P(X_0 = i_0) = \lambda_{i_0}$, which is the initial state distribution
(ii) $P(X_{n+1} = i_{n+1} | X_0 = i_0, ... , X_n = i_n) = P(X_{n+1} = i_{n+1} | X_n = i_n) = P_{i_n i_{n+1}}$
where $P_{i_n i_{n+1}}$ is the transition from state $i_n$ to $i_{n+1}$.
With regards to predicting probabilities of future states, you refer to both probabilities and states with the same notation. But I think I understand what you mean. If you knew the initial state distribution, and wanted to predict the probabilities of future distributions, you wouldn't really have an iterative function. If you look at the probability
$P(X_0 = i_0, X_1 = i_1, ... , X_n = i_n)$ you are asking the question "what is the probability that I start in $i_0$ at time $0$, and then moved to $i_1$ ... then finish in $i_{n}$ at time $n$?". You would then get:
$= P(X_0 = i_0)P(X_1 = i_1 | P(X_0 = i_0)...P(X_n = i_n | X_{n-1} = i_{n-1})$
$= \lambda_{i_0}P_{i_0 i_1}...P_{i_{n-1}i_n}$
(The proof of the above can be found here on page 2: http://www.statslab.cam.ac.uk/~rrw1/markov/M.pdf )
You would use the initial distribution only when you are working with $X_0$ in the sense that you wouldn't need to use it if you are finding a conditional probability.
Now if you knew $x_0$ and $x_k$, which I interpret at $X_0$ and $X_k$ I assume you want to know the answer to $P(X_k = i_k | X_0 = i_0 )$. Because you are only specifying one condition, that the chain starts at a certain state at $X_0$, there are many paths to get to its final destination at time $k$. So you would have to calculate the probability for every path (e.g. $\lambda_{i_0}P_{i_0 i_4}P_{i_4 i_3}.... P_{i_{k-1} i_k}$) and sum them up, this post might explain it better: Checking whether a given formula is correct for a homogeneous Markov chain . A shorter calculation would just be to look at the transition from $i_0$ to $i_k$ on the calculated transition matrix $\lambda_{i_0} P_{i_0 i_n}^{(k)}$.
Finally for references:
'Introduction to Stochastic Modelling' by Howard Taylor and Samuel Karlin is a great book which I am reading now. Chapter 3 focuses on these issues you are dealing with.
