# Probability a transition is taken in a Markov Chain within a certain number of steps

Given a Markov Chain ${\{X_t\}}_{t \in T}$ which has a transition matrix $P$, and a random variable $N$ of possible transitions.

The probability that a transition $n = (i, j)$ from $i$ to $j$ is taken on the $\lambda^{\mathrm{th}}$ step, given that the starting state is at node $q$ is: $$\Pr(N = n \mid T = \lambda , X_0 = q) = [P]_{i j} [P^{\lambda-1}]_{q i}$$

I want to find $\Pr(N = n \mid T \leq \lambda , X_0 = q)$ the probability that a transition $n$ is taken within $\lambda$ steps.

I can work this out intuitively for the $P$ matrix, but need a way to solve this for larger transition matrices. My intuition was to do the following, but this does not work correctly with the absorbing state at 0 as it leads to probability values larger than 1. $$\Pr(N = n \mid T \leq \lambda , X_0 = q) \neq \sum_{\mu = 1}^{\lambda} \Pr(N = n \mid T = \mu , X_0 = q)$$

$$P = \left(\begin{array}{c c c c} 1 & 0 & 0 & 0 \\ 1 & 0 & 0 & 0 \\ 1 & 0 & 0 & 0 \\ 0 & 0.5 & 0.5 & 0 \end{array}\right)$$

• To see your error, consider the simple one-state Markov chain where $P(0,0)=1$ (by necessity.) On the left hand side of your inequality, you have a calculated probability of 1, which is the probability that a transition to state 0 occurs within say 10 steps. 10 such transitions occur, but all you care about is whether or not at least one occurs. On the right hand side you have a calculated number of 10, which is the (expected) number of transitions into state 0 that occur within those same 10 steps. You are not eliminating transitions from state 0 into itself in the summation. – jbowman Sep 17 '18 at 18:25
• So my solution to this would be $1 - \prod_{\mu = 1}^{\lambda} 1 - \Pr(N = n \mid T = \mu , X_0 = q)$? – Matthew Bradbury Sep 17 '18 at 20:49