Recurrence of walks with growing range of step

Question

Let $f:\Bbb{N}\to\Bbb{N}$ be a function where $f(n)\to\infty$ as $n\to \infty$.

Given $f$, we can define a random walk on $\Bbb{Z}$, $Y(f,1)=Y_0,Y_1,\dots$, where $Y_0=0$, and $Y_{n+1}-Y_n=X_n$, where $X_n$ is chosen uniformly at random from $[-f(n),f(n)]\cap\Bbb{Z}$ and independent of the outcomes of all other $X_i$.

Similarly, given $f$, we can define a random walk on $\Bbb{Z}^2$, $Y(f,2)=Y_0,Y_1,\dots$, where $Y_0=(0,0)$, and $Y_{n+1}-Y_n=X_n'$, with $X_n': = X_n\cdot v_n$, where $v_n$ uniformly samples the two vectors $(0,1),(1,0)$, and $X_n$ is distributed as before. (here, we should have the set of random variables $\{v_i: i\in \Bbb{N}\}\cup\{X_i: i\in \Bbb{N}\}$ be independent)

I believe that if $f$ "does not grow too fast", then the walks $Y(f,1)$ and $Y(f,2)$ will be recurrent. In particular, I believe it would be sufficient for $\sum_{n=1} 1/f(n)^2$ to diverge. I am interested in proofs or disproofs for either case, as well as any techniques/gadgets which are useful for analyzing these kinds of walks.

Here is a sketch of the first case which a grad student showed me, I don't fully understand it yet:

1. Let $f(n) = \sqrt{n}, Y_n = Y(f,1),$ with $X_n$ defined as above.
2. We have that $\textrm{Var}(X_n) = O(n),\textrm{Var}(Y_n) = \sigma_n^2 = O(n^2), \sigma_n = O(n)$.
3. Thus, as the standard deviation of $Y_n, \sigma_n$ is $O(n)$, almost surely, the long-run proportion of time where $|Y_n- 0|\le \sqrt{n+1}$ is $\Omega(1/\sqrt{n})$. (i.e. Let $\chi_n$ be the characteristic function that is one if $|Y_n-0|\le\sqrt{n+1}$ is true and zero otherwise. Let $V_n:= \sum_{i=0}^{n-1}\chi_i$. We have that there exists some absolute $C>0$ such that $\Bbb{P}\left(\lim_{n\to\infty} \frac{V_n}{n} > \frac{C}{\sqrt{n}}\right) =1$)
4. It follows that almost surely, the long-run proportion of the time where $Y_{n+1} = 0$ is $\Omega(1/n)$, as $\Bbb{P}(Y_{n+1} = 0|\chi_n = 1) = \frac{1}{2\lfloor\sqrt{n+1}\rfloor+1}$.
5. Through the same argument, replacing 0 with any $m\in \Bbb{Z}$, we have that almost surely, the long-run proportion of times where $Y_{n+1} = m$ is $\Omega(1/n)$. (alternatively, since $\Bbb{P}(Y_{n+1} = m| \chi_n=1, \textrm{sign}(Y_n)=\textrm{sign}(m),\sqrt{n+1}\ge m) = \frac{1}{2\lfloor\sqrt{n+1}\rfloor}$ so since the sign of $Y_n$ given $\chi_n$ should not be biased, and for all large $n$ we have $\sqrt{n+1}\ge m$ holds, the long-run proportion of times where $|Y_{n+1} = m|$ should also be $\Omega(1/n)$ almost surely)
6. As the are countably many integers, and the intersection of countably many events that occur with probability 1 still occurs with probability 1, we have that almost surely for each integer $m$, the long-run proportion of times where $Y_{n+1} =m$ is $\Omega(1/n)$, implying each integer will be visited infinitely often.

For the most part, this makes sense, but I would appreciate some clarification on Step 3. I would assume that step 3 is "morally" supposed to follow from Chebyshev's inequality. However, formally I don't know how to justify this for our walk. A sketch explaining what conditions (independence and perhaps other stuff) allow us to prove step 3 would be much appreciated. Any commentary about what the most sound/clear way to justify step 5 is also welcome!

Update: the grad student further clarified that Step 3 should follow by Hoeffding's Inequality.

Answer 1

Let $G(n)=\sum_{k=1}^n f(k)^2$.

CLAIM: $Y(f,1)$ is recurrent iff $\sum_n G(n)^{-1/2}=\infty$.

In particular, $f(n)=n^{1/2}\log(n)^\alpha$ yields recurrence of $Y(f,1) $ iff $\alpha \le 1$. (Note that for $\alpha>1/2$ the sum $\sum_n f(n)^{-2} $ converges.)

Proof sketch of CLAIM: Let $\varphi_n(t)=E(e^{itXn})$ and $\psi_n(t)=E(e^{itY_n})=\prod_{k=1}^n \varphi_k(t)$. Taylor expansion shows that $\phi_k(t)$ behaves like $e^{-cf(k)^2 t^2}$ near the origin, where $c$ is a constant. Since $\int_{-\infty}^\infty e^{-a t^2}= (\pi/a)^{1/2}$, it follows that

$$P(Y_n=0)=\int_{-\infty}^\infty \psi_n(t)=\Theta(G(n)^{-1/2}) \,.$$ See [1] for a lovely account of such calculations. To conclude that $Y_n$ visits zero infinitely often iff the sum in the claim diverges, use the Kochen-Stone lemma [2].

---

For $Y(f,2)$ to be recurrent, $f$ has to grow much more slowly: $Y(f,2)$ is recurrent iff $\sum_n G(n)^{-1}=\infty$. In particular, $f(n)=\log(n)^\beta$ yields recurrence of $Y(f,2)$ iff $\beta \le 1/2$. This can be verified by the same method.

For other methods to tackle related problems see [3].

[1] Kac, Mark. Statistical Independence in Probability, Analysis and Number Theory. Courier Dover Publications, 2018.

[2] https://projecteuclid.org/euclid.ijm/1256059668

[3] Benjamini, Itai, Robin Pemantle, and Yuval Peres. "Random walks in varying dimensions." Journal of Theoretical Probability 9, no. 1 (1996): 231-244.