I'm working on the following problem which has confused me. Suppose that a particle can move between two points $A$ and $B$ with probabilities as shown in the diagram. Given that the particle starts at $A$, what is the probability that particle ends at point $A$ after $n$ moves?
I've approached this in a few ways and I'm finding some inconsistencies which I'm unable to resolve. My approach was a recursive one: let $\text{P}_n(A)$ be the probability that the particle, starting from $A$, ends up at $A$ after $n$ moves. Then we can say that:
\begin{align*}
\text{P}_n(A) &= p_{11}\text{P}_{n-1}(A) + p_{21}\text{P}_{n-1}(B),\ \text{and}\\
\text{P}_n(B) &= p_{12}\text{P}_{n-1}(A) + p_{22}\text{P}_{n-1}(B).
\end{align*}
This is where I have a problem. I think it is true to say that $\text{P}_n(A) + \text{P}_n(B) = 1$ which leads me to
\begin{align*}
1 = (p_{11} + p_{12})\text{P}_{n-1}(A) + (p_{21} + p_{22})\text{P}_{n-1}(B).
\end{align*}
Then if I use again the fact that $\text{P}_{n-1}(A) + \text{P}_{n-1}(B) = 1$, I will get an expression for $\text{P}_{n-1}(A)$ which is independent of $n$. Where am I going wrong?
Best Answer
I think your notation is obfuscating a distinction between (i) the event you are conditioning on and (ii) the event whose conditional probability you are looking for.
Let $X_n$ be the particle's position after $n$ steps.
What is true is $$P(X_n = A \mid X_0 = A) + P(X_n = B \mid X_0 = A) = 1.$$
However, $$P(X_n = A \mid X_0 = A) + P(X_n = A \mid X_0 = B)$$ does not necessarily equals $1$.
Upon closer inspection I think your recursion is not quite right either, although we may not be on the same page since you never defined what $P_{n-1}(B)$ and $P_n(B)$ are. I think revisiting how you define $P_n(B)$ may point to the source of your confusion.
Using my notation above,
\begin{align} &P(X_n = A \mid X_0 = A) \\ &= P(X_n = A, X_1 = A \mid X_0 = A) + P(X_n = A, X_1 = B \mid X_0 = A) \\ &= P(X_n = A \mid X_1 = A, X_0 = A) P(X_1 = A \mid X_0 = A) \\ &\qquad + P(X_n = A \mid X_1 = B, X_0 = A) P(X_1 = B \mid X_0 = A) \\ &= P(X_{n-1} = A \mid X_0 = A) p_{11} + P(X_{n-1} = A \mid X_0 = B) p_{12}. \end{align}