<s>[INST] Probability of reaching node A from node B in exactly X steps I have a three-node matrix with two edges (A-B and A-C). I would like to determine what the probability is starting from B and ending at C in exactly 100 steps.
I have only written out probabilities:
P(A|B) = 1
P(B|A) = 0.5
P(A|C) = 1
P(C|A) = 0.5

But there are so many combinations of ways to get from B to C in exactly 100 steps using these probabilities. Any suggestions on how to continue this problem?
 [/INST] After an odd number of steps you must be at A and after an even number of steps you will be in either B or C, each with probability 0.5, therefore after 100 steps the probability of being in C is 0.5
Edit
More formally we can define a Markov chain with transition matrix:
$$ T = \left(\array{0&\tfrac{1}{2}&\tfrac{1}{2}\\1&0&0\\1&0&0}\right) $$
Now we can compute $T^2$ and $T^3$ to show that for $n\ge 1$, $T^{2n-1}=T$:
$$ T^2 = \left(\array{1&0&0\\0&\tfrac{1}{2}&\tfrac{1}{2}\\0&\tfrac{1}{2}&\tfrac{1}{2}}\right) $$
$$ T^3 = \left(\array{0&\tfrac{1}{2}&\tfrac{1}{2}\\1&0&0\\1&0&0}\right) = T $$
Therefore we calculate that $T^{100}=T^2$ and that $x_0 T^{100} = x_0 T^2$
$$ x_0 T^2 = \left(\array{0&1&0}\right) \left(\array{1&0&0\\0&\tfrac{1}{2}&\tfrac{1}{2}\\0&\tfrac{1}{2}&\tfrac{1}{2}}\right) = \left(\array{0&\tfrac{1}{2}&\tfrac{1}{2}}\right) $$
</s>