Probability Question involving Random Walk 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?
 A: 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}
A: Let $P_n=(A_n,B_n)^T$ and let $M$ be a 2x2 matrix with the obvious meaning. The system is
$$ P_n = M P_{n-1}.$$
If the initial state is $P_0$, we have
$$P_n = M^n P_0. $$
Now we need the $n$th power of a 2x2 matrix.
We write the matrix $M$ as $M = A^{-1} D A$, where $D$ is diagonal. The matrix $A$ is formed with the eigenvectors of $M$. Label these as $M v_\pm = \lambda_\pm v_\pm.$ Obviously these quantities are quite complicated for arbitrary matrix elements $p_{ij}$.
Then $A = (v_-, v_+)$ is a 2x2 matrix and
$$ D = \begin{pmatrix} \lambda_- & 0 \\ 0 & \lambda_+ \end{pmatrix} $$
is a diagonal matrix. With this we have
$$ P_n = A^{-1} D^n A P_0.$$
or since $D$ is diagonal,
$$ P_n = A^{-1} \begin{pmatrix} \lambda_-^n & 0 \\ 0 & \lambda_+^n \end{pmatrix} A P_0. $$
I'll leave the rest to you. Typically one specifies the matrix $M$ for concrete results.
