Skip to main content
added 168 characters in body
Source Link
Joseph O'Rourke
  • 150.9k
  • 36
  • 358
  • 958

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][1]][1]
          $\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][2]][2][3RandWalks][3]][3]
   
    [![5RandWalks][2]][2]
$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 threebut one of the above examples (the penultimate) returned to the origin, but usually rather quickly: within $12$ steps.

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][1]][1]
          $\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][2]][2]
    $2000$-step random walks. Origin: green. Last point: red.

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

All three of the above examples returned to the origin, but rather quickly: within $12$ steps.

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][1]][1]
          $\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][3]][3]
   
    [![5RandWalks][2]][2]
$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.

Source Link
Joseph O'Rourke
  • 150.9k
  • 36
  • 358
  • 958

Spiral lattice random walk

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][1]][1]
          $\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][2]][2]
    $2000$-step random walks. Origin: green. Last point: red.

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

All three of the above examples returned to the origin, but rather quickly: within $12$ steps.