Prove that $ P(T>n)=P\left(X_{n}>Y_{n}\right)-P\left(X_{n}<Y_{n}\right) $

Question

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} $$

Answer 1

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)$$

Answer 2

$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$$