I wonder what is the expected behavior of this process?

Let

$f^2_{\mathrm{next}}(n) =$ the next prime after $n^2$.

$g_{\mathrm{sqrt}}(n) = \lfloor \sqrt{n} \rfloor$.

Now iterate as follows, with $n = n_0$:

\begin{eqnarray} n &=& f^2_{\mathrm{next}}(n)\\ n &=& g_{\mathrm{sqrt}}(n)\\ n &=& n \pm 1 \;, \end{eqnarray} where $n$ is augmented in the last equation by $\{-1,1\}$ with equal probability.

So, for $n_0=20$, $f^2_{\mathrm{next}}(20)$ is $401$, the next prime after $20^2$, and then $\lfloor \sqrt{401} \rfloor = 20$. But then, the random $\pm 1$ leads to $\lfloor \sqrt{401} \rfloor -1 = 19$, which leads to $f^2_{\mathrm{next}}(19)=$ the next prime after $361$, which is $367$. Etc. So in one random sequence, we see development like this:

So there is a push-forward toward the next prime by $f^2_{\mathrm{next}}(n)$, counterbalanced by a fall-backward via the floor-function in $g_{\mathrm{sqrt}}(n)$, and confused by the $\pm 1$.

Q. What is the ultimate behavior of this sequence for a given $n_0$?