Let $(X_n)_{n}$ a random walk over $\mathbb Z$ starting at $0$, i.e. $\mathbb P\{X_0=0\}=1$. I denote $T_k=\inf\{n\geq 1\mid X_n=k\}$. I suppose that $$\mathbb P\{X_{n+1}=X_n+1\mid X_n,...,X_0\}=p\quad \text{and}\quad \mathbb P\{X_{n+1}=X_n-1\mid X_n,...,X_0\}=q.$$ Remark that $q=1-p$. How can I compute $\mathbb P\{T_n<T_0\}$, i.e. the probability to touch $n$ before touching $0$ ? In fact I have problem to interpret $\{T_n<T_0\}$ using $(X_n)_n$.
I tired as follow :
$\mathbb P\{T_1<T_0\}=\mathbb P\{X_1=1\mid X_0=0\}=p$.
$\mathbb P\{T_2<T_0\}=\mathbb P\{X_1=1\mid X_0=0\}+\mathbb P\{X_2=2\mid X_1=1\}=2p$
$\mathbb P\{T_3<T_0\}=\mathbb P\{X_1=1\mid X_0=0\}+\mathbb P\{X_2=2\mid X_1=1\}+\mathbb P\{X_3=3\mid X_2=2\}+\mathbb P\{X_3=2\mid X_2=2\}(\mathbb P\{X_4=3\mid X_3=2\}+\mathbb P\{X_4=1\mid X_3=2\})$
I know that the last one is not clear at all, but I don't know how to interpret that fact that the walker can past many time between 1 and 2 many times before arriving at $3$.
Any explanation would be appreciated.
Good question! For your three examples, I think you shouldn't condition on $X_0 =0$ because it does not change anything ($P(X_0=0)=1$). Instead we should condition on the value of $X_1$ (for $n\geq 2$) and use Bayesian formula. $P(T_1<T_0) = P(X_1 = 1) = p$ is obvious. For $T_2$, we have $$ P(T_2<T_0) = P(T_2<T_0|X_1=1) \cdot P(X_1=1)+P(T_2<T_0|X_1=-1) \cdot P(X_1=-1). $$ Since $P(T_2<T_0|X_1=1) = P(X_2=2|X_1=1) = p$, and $P(T_2<T_0|X_1=-1)=0$ (starting at $-1$, you must pass $0$ before arrive at $2$), we have $P(T_2<T_0) = p^2$.
For general $n>2$, we can still do $$ P(T_n<T_0) = P(T_n<T_0|X_1=1) \cdot P(X_1=1)+P(T_n<T_0|X_1=-1) \cdot P(X_1=-1) $$ and get $P(T_n<T_0) = P(T_n<T_0|X_1=1) \cdot P(X_1=1)$ because $P(T_n<T_0|X_1=-1) = 0$. So it remains to get $P(T_n<T_0|X_1=1)$.
Now it turns to a special case of the Gambler's ruin problem: we start at $1$, and we want to find the probability that we hit $n$ before hitting $0$. Doing a shift, it's equivalent to the probability that we start at $0$ and hit $n-1$ before hitting $-1$.
Thus by the well-known result (see at the bottom of page 3) for Gambler's ruin problem, where $a = n-1$ and $b=1$ for our problem, we get $$ P(T_n<T_0|X_1=1) = \begin{cases} \frac{1-(q/p)^{n-1}}{1-(q/p)^{n}},\ p\neq 0.5\\ \frac{1}{n},\ p=0.5. \end{cases} $$ In conclusion, we have $$ P(T_n<T_0) = P(T_n<T_0|X_1=1) \cdot P(X_1=1) = \begin{cases} p\frac{1-(q/p)^{n-1}}{1-(q/p)^{n}},\ p\neq 0.5\\ \frac{1}{2n},\ p=0.5. \end{cases} $$