Find the value $\alpha$ so the random walk is recurrent Consider a random walk on $\mathbb{Z}$ with step distribution
$$\mathbb{P}(X_1 = n) = \frac{1}{2}\left ( \frac{1}{|n|^{\alpha}} - \frac{1}{(|n| + 1)^{\alpha}} \right ), \ \ \ \ n \neq 0.$$
I am trying to find the values $\alpha >0$ that makes the random walk recurrent.  I know that, if the random walk starts at $1$, I need to show that
$$\sum_{n=1}^{\infty}\mathbb{P}(S_n = 1) = \infty.$$
However, I cannot find a closed formula for the return probability. For example, if the random walk starts at $1$, then $\mathbb{P}(S_2 = 1)$ is easy to find since that means the random walk went up $n$ steps and then went down $n$ steps. But for $n>2$ it becomes much more complicated.
Can anyone help? Thanks!
 A: I'd reason like this:
we know from the general theory that
$$\mathbb{E}[N] = \lim_{t \to 1}\int_{[-\pi,\pi]}\frac{dk}{\sqrt{2\pi}(1-t \varphi(k))}$$
where $\varphi(k)$ is the characteristic function of $X_1$ and $N = \sum_{n \ge 0}\mathbb{I}_{S_n = S_0}$.
First we notice that
$$ \varphi(k) = \sum_{n \ne 0}\frac{e^{ikn}}{2} \bigg[ \frac{1}{|n|^{\alpha}} -\frac{1}{(|n| + 1)^{\alpha}}  \bigg] = \sum_{n = 1}^{\infty} \cos(nk) \bigg[ \frac{1}{|n|^{\alpha}} -\frac{1}{(|n| + 1)^{\alpha}}  \bigg]$$
Then
$$ 1 - \varphi(k) = \sum_{n = 1}^{\infty} (1-\cos(nk)) \bigg[ \frac{1}{|n|^{\alpha}} -\frac{1}{(|n| + 1)^{\alpha}}  \bigg] \le \sum_{n \ge 1} \frac{1-\cos(nk)}{n^{\alpha}}$$
Remembering the inequality $\cos(x) \ge 1 - x^2 / 2$, we finally obtain
$$ 1 -\varphi(k) \le \sum_{n \ge 1} \frac{k^2}{2 n^{\alpha -2}} = C k^2$$
when it is convergent, hence when $\alpha > 3$. By Fatou's Lemma we can say that
$$ \liminf_{t \to 1}\int_{[-\pi,\pi]}\frac{dk}{\sqrt{2\pi}(1-t \varphi(k))} \ge \int_{[-\pi,\pi]}\frac{dk}{\sqrt{2\pi}(1-\varphi(k))} = \infty$$
Therefore it is recurrent whenever $\alpha > 3$.
A: This is a complement to finch's answer. We show the walk is recurrent when $\alpha\gt1$. By finch's method, if suffices to  show $(1-\phi(k))\leq c*|k|$ for $c>0$. Note that for $\alpha>1$, $E[|X_{1}|] <\infty$ (see the remarks after finch's answer). Then by the mean value theorem,
$(1-\phi(k)) = E[1-\cos(kX_{1})]\leq E[|k||X_{1}|] = c|k|$.
I also suspect that $\alpha=1$ is the marginal case, that is for $\alpha\lt 1$, the walk is transient.
Added:
For $\alpha =1 $, the walk is also recurrent. since in this case, $(1-\phi(k))\leq a\sum_{n=1}^{n=\infty}\frac{1-cos(nk)}{n^2}$ for some $a>0$ and the infinite sum can be computed according to Series $\sum_{n=1}^{\infty}\frac{\cos(nx)}{n^2}$ as $-\frac{k^2}{4}+\frac{\pi k}{2}$ for $0<k<2\pi$. Hence the integral is again divergent.
