Prove that $ P(T>n)=P\left(X_{n}>Y_{n}\right)-P\left(X_{n}I am having a very hard time proving the below statement. I keep getting the wrong result so I feel like I am using the wrong probability identities. I would appreciate any help!
$\operatorname{Let}\left(X_{n}\right)_{n \geq 0}$ and $\left(Y_{n}\right)_{n \geq 0}$ be two independent simple symmetric random walks with $X_{0}=x$ and $Y_{0}=y$ where $x, y$ have the same parity and $x>y$
Define $T=\inf \left\{n \geq 1: X_{n}=Y_{n}\right\}$. Prove that
$$
P(T>n)=P\left(X_{n}>Y_{n}\right)-P\left(X_{n}<Y_{n}\right)
$$
This is what I did:
$$
P\left(T_{a}>n\right)=1-\mathbb{P}\left(T_{n} \leq n\right)
$$
By theorem 29 , since $X_{n}$ and $Y_{n}$ are simple symmetric random walk then:
$$
P_{0}\left(T_{a} \leq n\right)=2 P_{0}\left(X_{n} \geq a\right)-P_{0}\left(X_{n}=a\right)
$$
Hence:
$$
\begin{aligned}
&\mathbb{P}\left(T_{n}>n\right)=1-2 P\left(X_{n} \geq Y_{n}\right)+P\left(X_{n}=Y_{n}\right)\\
&=1-2 P\left(X_{n}>Y_{n}\right)-2 P\left(X_{n}=Y_{n}\right)+P\left(X_{n}=Y_{n}\right)\\
&=1-2 P\left(X_{n}>Y_{n}\right)-P\left(X_{n}=Y_{n}\right)
\end{aligned}
$$
$$
1-P\left(X_{n}=Y_{n}\right)=P\left(X_{n}>Y_{n}\right)+P\left(X_{n}<Y_{n}\right)
$$
$$
\begin{aligned}
P\left(T_{a}>n\right) &=R\left(X_{n}>Y_{n}\right)+P\left(X_{n}<Y_{n}\right)-2 P\left(X_{n}>Y_{n}\right) \\
&=\mathbb{P}\left(X_{n}<Y_{n}\right)-\mathbb{P}\left(X_{n}>Y_{n}\right)
\end{aligned}
$$
 A: This can be done from first principles.
Note that $T>n$ is equivalent to $X$ and $Y$ don't meet before $n+1$, i.e. $X_i\not=Y_i$ for $i=0, \cdots, n$. This is because $X_0$ and $Y_0$ have the same parity, therefore $X_i$ and $Y_i$ have the same parity for all $i\ge 0$, so it's impossible for them to cross each other through the state transition $(X,Y) = (a+1,a)\rightarrow (a, a+1)$.
Let $$E_i = \{X_0\not=Y_0, \cdots, X_{i-1}\not=Y_{i-1}, X_i=Y_i\}$$ then $$F = (\cup E_i)^c = \{X_0\not=Y_0, X_1\not=Y_1, \cdots, X_n\not=Y_n\} = \{T>n\}$$
Then we have $$P(X_n>Y_n) = P(X_n>Y_n|F)P(F) + \sum_{i=1}^n P(X_n>Y_n|E_i) P(E_i) \text{ --- } (1)$$ $$P(X_n<Y_n) = P(X_n<Y_n|F)P(F) + \sum_{i=1}^n P(X_n<Y_n|E_i) P(E_i)\text{ --- } (2)$$
Note that $P(X_n>Y_n |E_i) = P(X_n<Y_n|X_i)$ by symmetry for all $i=1, \cdots, n$.
And $P(X_n>Y_n |F) = 1$, $P(X_n<Y_n|F)=0$. Hence take the difference (1)-(2), $$P(X_n>Y_n) - P(X_n<Y_n) = P(F)$$
A: $Z_n=X_n-Y_n$ is walk with $Z_0=x-y$ but with steps $-2, 0, 2$, now:
$$P(Z_n=k|T<n)=P(Z_n=-k|T<n)$$
$$\forall k>0: P(Z_n=k) = P(Z_n=k|T>n)+P(Z_n=k|T<n)= \\ =P(Z_n=k|T>n)+P(Z_n=-k|T<n) => \\
P(Z_n=k|T>n)=P(Z_n=k)-P(Z_n=-k|T<n)$$
now
$$L=P(T>n) = \sum_{k=1}^{2n+Z_0}P(Z_n=k|T>n) = \sum_{k=1}^{2n+Z_0}(P(Z_n=k)-P(Z_n=-k|T<n))= \\ =\sum_{k=1}^{2n+Z_0}P(Z_n=k)-\sum_{k=1}^{2n+Z_0}P(Z_n=-k|T<n)=P(Z_n>0) - P(Z_n < 0) =\\ =P(X_n>Y_n)-P(X_n<Y_n)=R$$
