Random walk $S_n$ on $\mathbb{Z}$ with variable step $X_1$ - recurrent or transient? Is a random walk $S_N$ on $\mathbb{Z}$ with variable step $X_1$, where
$\mathbb{P}\left(X_1= x\right) = \frac{C}{1+x^2}$, transient or recurring?
I tried to proceed with this well known result that random walk is transient iff:
$\mathbb{E}N = \lim_{t \to 1^-} \int_{[-\pi , \pi]^d}\frac{ds}{(2 \pi)^d(1-t\varphi(s))} < \infty$, where $N = \sum_{n \geq 0}\mathbb{1}_{\{S_n = S_0\}}$.
I was stuck on figuring out the $\varphi(t)$, any help there and in the next steps will be appreciated.
 A: For $s \in \left(-\pi, \pi\right]$:
$$
\phi(s) = \mathbb{E}e^{isX} = \sum_{n \in \mathbb{Z}} \frac{C}{1+n^2} e^{ins} = C \cdot 1 + \sum_{n=1}^\infty \frac{C}{1+n^2}\left(e^{ins}+e^{-ins}\right)= \\C+\sum_{n=1}^\infty \frac{2C}{1+n^2}\cos(ns) = C + \sum_{n\neq 0}\frac{C}{1+n^2}\cos(ns) = \sum_{n \in \mathbb{Z}} \frac{C}{1+n^2}\cos(ns).
$$
Right now we have to work on restricting $1 - \phi(s)$ from above:
$$
1 - \phi(s) = \underbrace{\sum_{n\in\mathbb{Z}}\frac{C}{1+n^2}}_{= 1} - \sum_{n\in\mathbb{Z}}\frac{C}{1+n^2}\cos(ns)  \\
=\sum_{n\in\mathbb{Z}}\frac{C}{1+n^2}\left(1 - \cos(ns)\right) \\
\leq 2C\sum_{n=1}^\infty \frac{1-\cos(ns)}{n^2}.
$$
Out task now - calculate $\sum_{n=1}\frac{1 - \cos(ns)}{n^2}$.
We will use Fourier series of triangle distribution ($h(t) = \frac{s - t}{s}$) on the interval of $\left(-s, s\right)$. Because it is a Lipschitz function (so the Fourier series converges uniformly to it), we could find trigonometric series on $\left(-\pi, \pi\right]$.
\begin{aligned}
a_n =& \frac{1}{d}\int_{-s}^{s}h(t)\cos(nt) \text{d}t~\left(n=0,1,\ldots\right) \\=&\frac{2}{s}\int_0^s\frac{1}{s}\left(1-\frac{t}{s}\right)\cos(nt)\text{d}t 
\\=& \frac{2}{s^2}\int_0^s \left(1 - \frac{t}{s}\right)\left(\frac{1}{n}\sin(nt)\right)'\text{d}t \left(n=1,2,\ldots\right) 
\\=&\frac{2}{s^2}\left[\left(1-\frac{t}{s}\right)\frac{1}{n} \sin(nt)\Big|^s_{t=0} + \int_0^s\frac{1}{s}\frac{1}{n}\sin(nt)\text{d}t\right] 
\\=&-\frac{2}{s^3}\frac{1}{n^2}\cos (nt)\Big|_0^s 
\\=& \frac{2}{s^3}\frac{1-\cos(ns)}{n^2}, \\
b_n =& \frac{1}{s}\int_{-s}^s h(t)\sin(nt)\text{d}t = 0,
\end{aligned}
because it's an integral over symmetric interval of sinus function.
We got, from convergence mentioned above, for $t \in \left(-\pi, \pi\right]$:
\begin{aligned}
h(t) =& \frac{1}{2s} + \sum_{n=1}^\infty\frac{2}{s^3}\frac{1 - \cos(ns)}{n^2}\\
h(0) =& \frac{1}{s}\\
\Rightarrow\\
&\sum_{n=1}^\infty \frac{2}{s^3} \frac{1 - \cos (ns)}{n^2} = \frac{1}{2s}.
\end{aligned}
Conclusion - for $s \in \left(0,\pi\right)$
\begin{align}
\sum_{n=1}^\infty \frac{1 - \cos (ns)}{n^2} = \frac{s^2}{4}.
\end{align}
Therefore $1 - \phi(s) \leq Cs^2$, so $\int_{-\pi}^\pi \frac{1}{1-\phi(s)}\text{d}s = \infty$ (because of the singularity in zero).
Then $\liminf_{t\rightarrow1^-}\int_{-\pi}^\pi\frac{1}{1-t\phi(s)} \text{d}s \underbrace{\geq}_{\text{Fatou's lemma}} \int_{-\pi}^\pi \frac{1}{1-\phi(s)}\text{d}s = \infty$.
So the random walk $S_n$ is recurrent.

Random trivia - this problem was really hard for me and others, because there was a second power (instead of 4 or bigger) in the denominator. With bigger power, this problem is relatively easier, without use of the Fourier series, but a Taylor's theorem for $\cos(nx) = 1 - \frac{n^2x^2}{2}+\ldots$ and $1 - \cos(nx) \leq \frac{n^2s^2}{2}$, used to limit the value of $1 - \phi(s)$ by $\frac{C}{2}\sum_{n\in\mathbb{Z}}\frac{n^2s^2}{1+n^4}\leq \frac{C}{2}s^2\sum_{n=1}^\infty\frac{2}{n^2} = Ds^2$. Thus, the whole integral diverges and $S_n$ is recurrent.
