Consider $X_1, X_2, X_3$ ... random variables i.i.d. such that $P(X_i=1)=p$ and $P(X_i=-1)=1-p$. Consider the random walk $(S_n)_{n\ge 0}$ with $S_0=0$ and for $n\ge 1$, $S_n = \displaystyle\sum^{n}_{i=1} X_i$. Let $d=2p-1=E X_i$ be the drift of $S_n$. Assume that $d>0.$

Define $T_x= \inf \{n\ge0; S_n=x\}$. I want to prove that $\displaystyle\sup_{y>0}\{T_y-\frac {2(y-1)}{d}\}$ is finite. It's clear that $T_y$ is finite, because $S_n$ is transient to right, but I can not control the difference. I thought of using the fact that the time the walker needs to go from $0$ to $y$ is of the ordem of $\frac {y}{d}$ since d is intuitively the speed of the random walk. Help?

• You can show that $ET_y=\frac{y}{d}$. If you can argue that $\lim_{y \to \infty} T_y/ET_y = 1$ a.s., then you are done. This is sort of like a strong law of large numbers. – Ian Jun 16 '18 at 16:35
• (Note that $ET_y=y/d$ is a nontrivial fact, it does not simply follow from the drift being $d$.) – Ian Jun 16 '18 at 16:41
• Sorry but I do not understand the bounty. 1. By the usual one step-decomposition, $E(T_1)=1/d$. 2. By the Markov property, the sequence $(T_y-T_{y-1})_{y>0}$ is i.i.d. and distributed as $T_1$. 3. By the law of large numbers applied to the i.i.d. sequence $(T_y-T_{y-1})_{y>0}$, $T_y/y\to1/d$ almost surely when $y\to\infty$. 4. For every real valued sequence $(t_y)$ such that $t_y/y\to c$ when $y\to\infty$ and for every $(a,b)$ such that $a>c$, $\sup\limits_{y>0}(t_y-ay-b)$ is finite. 5. When $d>0$, $2/d>1/d$. QED. – Did Jun 16 '18 at 17:33