What is the probability that a Markov chain transitions between states if it passes through a specified intermediate transition? Consider a discrete-time finite Markov chain with transition probability matrix $P$. One of the foundational results of Markov theory is, of course, that the probability that the chain transitions from state $i$ to state $j$ in $n$ time steps equals $(P^n)_{ij}$. We can derive many other useful results from this fact, such as the expected number of times that the chain will visit state $j$ starting from state $i$.
Is there an analytic formula for the conditional probability that the chain transitions from state $i$ to state $j$, given that at some point in between it makes a specified transition $k \to l$?
There are many natural generalizations to this kind of question, e.g.: what is the conditional probability that the transition occurs in exactly (or at least, or at most) $n$ time steps? What is the conditional probability that the chain transitions from $i \to j$ given that the intermediate transition $k \to l$ occurs (exactly, at least, at most) $m$ times?
Conversely, you could turn it around and say that conditioned on an overall transition $i \to j$ in $n$ time steps, what is the probability that there was (exactly/at least/at most) $m$ intermediate transitions $k \to k$.
I guess one way to approach it would be that the probability of an overall transition $i \to j$ over $n$ time steps with an intermediate transition $k \to l$ at step $t$ is $(P^{t-1})_{ik} P_{kl} (P^{n-t})_{lj}$. I don't think you can just sum this quantity up from $t=2$ to $t = n-1$ though, because you'll double-count sequences where that intermediate transition occurs multiple times.
Are there any nice analytic results for this kind of thing, or do you need to do Monte Carlo simulations?
 A: 
Is there an analytic formula for the conditional probability that the chain transitions from state $i$ to state $j$, given that at some point in between it makes a specified transition $k \to l$?

This is an interesting question, and while I do not know of existing analytical formalisms that deal with questions like this specifically, I suppose we can explore a couple of ideas.

*

*Trajectory Segregation: Let $P^{(n)}_{ij}$ denote the $n$-step transition probability of going from $i$ to $j$. We can write:
$$ P^{(n)}_{ij} = p^{(n)}_{ij}  + q^{(n)}_{ij} $$
where $p^{(n)}_{ij}$ denotes the probability weight of trajectories that go from $i$ to $j$ in exactly $n$ steps and $\textit{do not}$ contain an intermediate $k \to l$ transition, whereas $q^{(n)}_{ij}$ is the weight of trajectories in which there is an intermediate $k\to l$ transition. Clearly,
$$  q^{(n)}_{ij} = P^{(n)}_{ij} - p^{(n)}_{ij}.  $$
Evaluating $P^{(n)}_{ij}$ is, as you say, a foundational result in the study of Markov chains. How can we compute $p^{(n)}_{ij}$? I suppose it will suffice to "remove" the $k \to l$ bond from your Markov network of transitions (essentially equivalent to an "absorbing edge" in your Markov chain). Just remember that once you remove that bond, your transition matrix will no longer be a Markov matrix and in ergodic Markov chains, $ \lim_{n\to \infty} p^{(n)}_{ij} \to 0$, which also makes sense as in that limit, you would expect $  q^{(n)}_{ij} \approx P^{(n)}_{ij}$ (in the long time limit, the $k \to l$ transition must have happened at least once).


*Moving to the Markov chain of transitions: In the canonical formulation of Markov chains, one considers a chain with states $\{s_1,s_2,\dots, s_N\}$ and an $N\times N$ transition matrix which determines the time evolution of the process. However, one can construct another Markov chain where each state a possible transition in the original Markov chain. Thus this new Markov chain can in principle have $N^2$ states (some of which may be inaccessible), and you can now use can canonical Markov chain theory to study the statistics of transitions. In this way, you will also avoid the over-counting issue as you can define a "first-passage" to a transition, and subsequent "first-return" to that transition. I do not know of many approaches for formally constructing this Markov chain of transitions, but here is a simple example for clarity. Consider a two-state Markov chain with states $1$ and $2$: 
for this, we can construct a three-state Markov chain of transitions with the following structure

In summary, I believe approach 1 can solve one of the specific questions you raised, and approach 2 can allow you to address the more general questions. I was also thinking of an approach 3 (closely related to approach 2), where we could write down the master equation for the joint-probability of being in a specific state at a time-step and having made a specific transition in the previous step. However, getting meaningful results there would require some more time from my side. I will continue to think about this, and am happy to discuss further.
