Proving a random walk with a drift is recurrent Given the following set of independent random variables $\mathbb{P}(X_n=1)=\frac{1+n^{-\beta}}{2}, \mathbb{P}(X_n=-1)=\frac{1-n^{-\beta}}{2}$ and the sum $S_n=\sum^n_{i=1}X_n$ I managed to prove that if $\beta<0.5$ then $S_n$ is transient by using Hoeffding's bound and that if $\beta > 1$ $S_n$ is recurrent by treating the random variables as a simple random walk with a drift - which I proved is finite almost surely.
I am now trying to prove the case of $0.5\leq\beta\leq1$. I am pretty sure intuitively that it is recurrent however I am not successful in proving the case.
Any help will be appreciated.
 A: One way to prove this is to use the Lindeberg central limit theorem.  Let $m_1=2$, $m_2$, $m_3$, $\dots$ be a sequence of positive integers with $m_{i+1}\ge m_i^2$ for all $i$, and let $T_i:=X_{m_i+1}+\cdots+X_{m_{i+1}}$.  To apply the Lindeberg CLT to $T_i$, the first step is to compute the mean
\begin{eqnarray*}\mu_i&:=&{\Bbb E}X_{m_i+1}+\cdots+{\Bbb E}X_{m_{i+1}}\\
&=&(m_i+1)^{-\beta}+\cdots+m_{i+1}^{-\beta}\\
&\le&\int_{m_i}^{m_{i+1}} x^{-\beta} \, d\beta\\
&=&\frac{1}{1-\beta}(m_{i+1}^{1-\beta}-m_i^{1-\beta})&\qquad&\hbox{(if $\beta<1$; $\log(m_{i+1}/m_i)$ if $\beta=1$)}\\
&=&O(m_{i+1}^{1-\beta})&\qquad&\hbox{(if $\beta<1$; $O(\log m_{i+1})$ if $\beta=1$)}\\
&=&O(m_{i+1}^{1/2})
\end{eqnarray*}
and the variance
$$\sigma_i^2:={\Bbb E}[(X_{m_i+1}-(m_i+1)^{-\beta})^2]
+\cdots+{\Bbb E}[(X_{m_{i+1}}-m_{i+1}^{-\beta})^2].$$
Since $m_i\ge 2$ and $\beta\ge \frac 1 2 $, each term $(X_j-j^{-\beta})^2$ in this sum is always between $(1-3^{-1/2})^2$ and $(1+3^{-1/2})^2$.  Therefore, $\sigma_i^2=\Theta(m_{i+1}-m_i)$, and since $m_{i+1}\ge m_i^2\ge 2 m_i$, we also have $\sigma_i^2=\Theta(m_{i+1})$ and so  $\sigma_i=\Theta(m_{i+1}^{1/2})$.
Now, the Lindeberg condition is that, for all fixed $\epsilon>0$,
$$
\frac{1}{\sigma_i^2}\sum_{m_i+1\le j\le m_{i+1}} \mathbb{E} \left[(X_j - j^{-\beta})^2 \cdot \mathbf{1}(| X_j - j^{-\beta} | \ge \epsilon \sigma_i ) \right]\qquad\qquad(*)
$$
approaches zero as $i$ becomes large, but
since $|X_j-j^{-\beta}|$ is bounded and $\sigma_i\to\infty$, for $i$ large enough, (*) will be zero.  This means that we can apply the Lindeberg CLT to find that
$(T_i-\mu_i)/\sigma_i$ converges in distribution to a standard normal distribution.
Now, $$S_{m_{i+1}}=S_{m_i}+T_i \le T_i + m_i \le T_i + m_{i+1}^{1/2}$$ so
$${\Bbb P}(S_{m_{i+1}}\le 0\mid S_{m_i})\ge {\Bbb P}((T_i-\mu_i)/\sigma_i\le (-m_{i+1}^{1/2}-\mu_i)/\sigma_i)$$
and, by our estimates on $\mu_i$ and $\sigma_i$, there are constants $K>0$ and $L>0$ so that, for all sufficiently large $i$,
$$
m_{i+1}^{1/2}+\mu_i\le K m_{i+1}^{1/2}, \qquad \qquad
\sigma_i\ge L m_{i+1}^{1/2},
$$
so for sufficiently large $i$,
$${\Bbb P}(S_{m_{i+1}}\le 0\mid S_{m_i})\ge {\Bbb P}((T_i-\mu_i)/\sigma_i\le -K/L)\qquad(**)$$
and, by convergence in distribution, the right-hand side of (**) approaches $\Phi(-K/L)$ as $i\to\infty$, so for sufficiently large $i$,
$${\Bbb P}(S_{m_{i+1}}\le 0\mid S_{m_i})\ge\frac{\Phi(-K/L)}{2}.$$
This proves that $S_n$ is almost surely nonpositive infinitely often.  Similarly, $S_n$ is almost surely nonnegative infinitely often, so $S_n$ is recurrent.
