Given a simple symmetric random walk $X_1,X_2,…,X_n,…$ where $X_t,t=1,2,…$ are i.i.d random variables distributed according to $\Bbb P(X_t=1)=1/2$ and $\Bbb P(X_t=-1)=1/2$. Define partial sum $S_t=∑_{k=1}^tX_k$ . Define $T_x=\min\{t∈N:S_t=x\}$. Use $\Bbb P_0 (T_x=k)$ to denote the probability of a random walk first reaching position $x$ at time $k$ (the subscript $0$ of $\Bbb P_0$ means the random walk is assumed to start at position $0$).
It can be shown by reflection that $\Bbb P{_0}\left( {{T_1} = 2k - 1} \right) = \frac{{\left( {\begin{array}{*{20}{c}} {2k}\\ k \end{array}} \right)}}{{{2^{2k}}\left( {2k - 1} \right)}}$. The problem is to show
$\Bbb P_0 (T_x≥N)\simeq cN^{-\frac{1}{2}}$ when N→∞ where $\simeq$ means infinitesimal of the same order.
The textbook offers the following hint:
Use induction. For $x=a+b$, $\Bbb P_0 (T_x≥N)$ is the sum of $\Bbb P_0 (T_a≥i)\Bbb P_0 (T_b≥j)$ over $i+j≥N$. Also, bulk of the sum comes from $i≤L,j≥N-i$ and $j≤L,i≥N-j$ for some large number $L$.
I tried to follow the hint. It is not hard to show $\Bbb P_0 (T_1≥N) \simeq N^{-1/2}$. Also Suppose $\Bbb P_0 (T_x≥N) \simeq N^{-\frac{1}{2}}$ holds for $x$.
Then for $x+1$, first breaks $\Bbb P_0 (T_{x+1}≥N)=∑_{i+j≥N}\Bbb P_0 (T_x=i) \Bbb P_0 (T_1=j)=p_1+p_2+p_3$ where
$p_1=∑_{i=1}^L∑_{j≥N-i}\Bbb P_0 (T_x=i) \Bbb P_0 (T_1=j)=∑_{i=1}^L \Bbb P_0 (T_x=i) ∑_{j≥N-i}\Bbb P_0 (T_1=j)$
$p_2=∑_{j=1}^L∑_{i≥N-j}\Bbb P_0 (T_1=j) \Bbb P_0 (T_x=i)=∑_{j=1}^L \Bbb P_0 (T_1=j) ∑_{i≥N-j}\Bbb P_0 (T_x=i)$
$p_3=∑_{i=L}^∞ ∑_{j≥\max(L+1,N-i) }P_0 (T_x=i) P_0 (T_1=j)$
The following graph illustrates the breakdown.
For $p_1$, we have $\mathop {\lim }\limits_{N \to \infty } \frac{{{p_1}}}{{{N^{ - \frac{1}{2}}}}} = \mathop \sum \limits_{i = 1}^L {\Bbb P_0}\left( {{T_x} = i} \right)\mathop {{\rm{lim}}}\limits_{N \to \infty } \frac{{\mathop \sum \limits_{j \ge N - i} {\Bbb P_0}\left( {{T_1} = j} \right)}}{{{N^{ - \frac{1}{2}}}}} = \mathop \sum \limits_{i = 1}^L {\Bbb P_0}\left( {{T_x} = i} \right){c_i} \Rightarrow {p_1} \simeq {N^{ - \frac{1}{2}}}$
The same thing for $p_2$. However, I encountered difficulty to show $p_3$ is an infinitesimal of order not lower than $N^-{\frac{1}{2}}$. By hint, I think $p_3$ should decrease faster than $N^{-\frac{1}{2}}$.
Hint: For a symmetric random walk with $p=q=1/2$, you can use the reflection principle directly to show that, if $x+N$ is odd, then $\mathbb{P}_0(T_x>N)=\mathbb{P}_0(-x<S_N<x).$