7
$\begingroup$

Execute a random walk from the origin on the integer lattice, but bias the four compass-direction probabilities from $\frac{1}{4}$ each to prefer to step in a spiraling direction. Calling the four step vectors $c_0,c_1,c_2,c_3$, with $c_i=(\cos (i \, \pi/2), \sin (i \, \pi/2))$, adjust the probabilities as follows. Let $v$ be the vector from the origin to the last point on the path, and $n$ the unit normal to $v$, counterclockwise $90^\circ$ to $v$. Then select step $c_i$ with probability $\frac{1}{4} (1+ c_i \cdot n)$.


          SpiralVecs
          $\theta=60^\circ$. $\frac{1}{4}(1+c_2 \cdot n) = (1+\sqrt{3}/2)/4 \approx 0.47$.
Unsurprisingly, the random walks spiral around the origin:
    3RandWalks
   
    5RandWalks
$2000$-step random walks. Origin: green. Last point: red. Three examples, followed by five examples at reduced scale.


Q. Does Pólya's recurrence theorem hold for these walks? Do the walks return to the origin with probability $1$?

All but one of the above examples (the penultimate) returned to the origin, but usually rather quickly.

$\endgroup$
3
  • 5
    $\begingroup$ I'm not immediately sure what the answer is, but I think the spiral thing is a bit of a red herring. What you should look at is does this random walk give the same parameter for the corresponding Bessel process. For d dimensional BM the parameter is $\frac{d-1}{2}$ and $\frac12$ is the critical parameter for recurrence, corresponding to $d=2$. I don't have time right now to calculate the parameter for the spiral RW. $\endgroup$ Jun 23, 2017 at 14:49
  • 1
    $\begingroup$ I believe the answer is that this is recurrent. If you let $R_n=|X_n|$, this has the same kind of decaying drift to $+\infty$ as the standard 2D Brownian motion: $R_{n+1}\approx R_n + c/\sqrt{R_n}$. $\endgroup$ Jun 23, 2017 at 20:37
  • 1
    $\begingroup$ The scaling limit of the norm seems to be a Bessel 3 process, so it should be transient... $\endgroup$ Jun 23, 2017 at 20:47

3 Answers 3

7
$\begingroup$

It seems to me that this random walk is recurrent. Denote $Y_n=\|X_n\|$, where $(X_n, n\geq 0)$ is your "spiral" walk. Then, as $x\to \infty$, my calculations imply that $$ \mathbb{E}(Y_{n+1}-Y_n\mid Y_n=x) = \frac{1}{4\|x\|} + O(\|x\|^{-2}), $$ and $$ \mathbb{E}((Y_{n+1}-Y_n)^2\mid Y_n=x) = \frac{1}{2} + O(\|x\|^{-1}). $$ Then, (null) recurrence follows from Theorem 3.5.2 of [Menshikov, Popov, Wade, "Non-homogeneous random walks", C.U.P.-2017, http://www.ime.unicamp.br/~popov/book_lyapunov.pdf ].

$\endgroup$
5
$\begingroup$

Here is the theorem cited in Serguei Popov's answer:


Thm352
and here are the three assumptions:
L012


$\endgroup$
1
  • $\begingroup$ Just complementing: $\bar{\mu}_1(t)$ and $\underline{\mu}_2(t)$ are essentially the two displays in my answer above, with $t=\|x\|$. $\endgroup$ Jun 24, 2017 at 17:06
2
$\begingroup$

Forgive this simple-minded approach, but it may be instructive when made rigorous by someone who knows what they are doing.

I think Anthony Quas's suggestion of looking at radius good, but I do not understand his use of the word 'recurrent'. The probability of going east-west is 1/2, as is going north-south. However, most of the time, the probability for increasing the distance from the origin is greater than 1/2. This is because one of (say) east west is biased toward increasing distance, while the other (say) is half increasing and half decreasing. So for near the origin, there is a chance of returning, but (as Martin Hairer suggests) once you get far enough away, the dynamic seems transient.

I turn the calculation of "far enough away" over to those with more experience. I suspect the probability of returning to within S distance of the origin given one is at distance R in this dynamic is exponential in S-R (I assume S less than R).

Gerhard "Wonders About Inward Spiral Dynamics" Paseman, 2017.06.23.

$\endgroup$
2
  • $\begingroup$ I am purposely ignoring the expected change of distance from origin which might lead to a different interpretation. Again, those who are more experienced should explain the probability angle correctly. Gerhard "Dynamic Model For Thought Processes?" Paseman, 2017.06.23. $\endgroup$ Jun 23, 2017 at 22:22
  • $\begingroup$ "the probability for increasing the distance from the origin is greater than 1/2": Yes, this is my intuition. But precise calculations are needed. $\endgroup$ Jun 23, 2017 at 23:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.