Crikey Math

Having fun exploring mathematics

  • Home
  • About
  • Blog
  • Contribute
en English
af Afrikaanssq Albanianam Amharicar Arabichy Armenianaz Azerbaijanieu Basquebe Belarusianbn Bengalibs Bosnianbg Bulgarianca Catalanceb Cebuanony Chichewazh-CN Chinese (Simplified)zh-TW Chinese (Traditional)co Corsicanhr Croatiancs Czechda Danishnl Dutchen Englisheo Esperantoet Estoniantl Filipinofi Finnishfr Frenchfy Frisiangl Galicianka Georgiande Germanel Greekgu Gujaratiht Haitian Creoleha Hausahaw Hawaiianiw Hebrewhi Hindihmn Hmonghu Hungarianis Icelandicig Igboid Indonesianga Irishit Italianja Japanesejw Javanesekn Kannadakk Kazakhkm Khmerko Koreanku Kurdish (Kurmanji)ky Kyrgyzlo Laola Latinlv Latvianlt Lithuanianlb Luxembourgishmk Macedonianmg Malagasyms Malayml Malayalammt Maltesemi Maorimr Marathimn Mongolianmy Myanmar (Burmese)ne Nepalino Norwegianps Pashtofa Persianpl Polishpt Portuguesepa Punjabiro Romanianru Russiansm Samoangd Scottish Gaelicsr Serbianst Sesothosn Shonasd Sindhisi Sinhalask Slovaksl Slovenianso Somalies Spanishsu Sudanesesw Swahilisv Swedishtg Tajikta Tamilte Teluguth Thaitr Turkishuk Ukrainianur Urduuz Uzbekvi Vietnamesecy Welshxh Xhosayi Yiddishyo Yorubazu Zulu

Random walks with memory: Background

February 7, 2018 By Gary Ernest Davis

A simple random walk on a graph (finite or infinite) is a sequence of transitions from a vertex to a neighboring vertex where the transition to a neighboring vertex  is given by a probability distribution.

Commonly, in a so-called symmetric simple random walk, the probability of making a transition from a vertex v to a neighboring vertex is 1/p where p is the number of neighboring vertices  for v: in other words the random walk transitions from vertex v to each of the neighboring vertices with equal probability. This assumes, of course, that the graph is locally finite: each vertex has only a finite number of neighboring vertices.

No backtracking

Simple random walks do not have memory: a random walk may transition from a vertex v_0 to a neighboring vertex v_1 and then make a next transition from v_1 back to v_0.

Random walks that never do this – that is, have a memory of the previous vertex last visited and do not immediately re-visit it – are called random walks with no-backtracking. They are, in an obvious sense of the phrase, random walks with memory 1.

Random walks with memory 1 generally cover all, or a significant portion, of the graph faster then random walks with no memory. This takes some work to prove in particular cases, yet is sort of obvious in that a random walk with memory 1 is prohibited from going back to whence it immediately came, and so will spread to its other neighbors with slightly greater probability.

Yet a random walk pays a price for memory. On the graph \mathbb{Z} consisting of the integers with an edge joining successive integers, a random walk with memory 1 must head off entirely in one direction after the first step:


Total recall

Random walks with total recall – also known, for obvious reasons, as self-avoiding walks – have an additional issue in that they commonly become trapped: because such a random walk remembers every place it has ever been, and typically gets stuck in a cul-de-sac where each of the possible next transition vertices have been visited already.

 

A self-avoiding walk that has not – yet – got stuck

 


Recent memory

This getting-stuck phenomenon can happen for a random walk on the infinite lattice \mathbb{Z}\times \mathbb{Z}  – where there is an edge from vertex (m,n) to vertex (p,q) if and only if \vert m-p\vert + \vert n-q\vert = 1  – when the random walk has memory 7:

 


Basic questions

So … for random walks with memory of the previous m sites visited where 1 \leq m \leq \infty there are a number of issues to settle:

  • With what probability will the random walk get trapped?
  • Will the walk be transient or recurrent? (A random walk is recurrent if it visits its starting position infinitely often with probability one and transient if it visits its starting position finitely often with probability one.)
  • At what rate will the random walk cover the graph (if at all)?

We know, for example, that for a simple random walk with memory 0 on the integer lattice \mathbb{Z}^d that the walk is recurrent for d = 1 or 2 and transient for d \geq 3. This is a basic result of George Polya.  Recently, Mark Kempton has proved that a simple random walk with memory 1 (i.e. no backtracking) on the integer lattice \mathbb{Z}^d is recurrent only for d=2.


And then there’s Levy flights …

A Levy flight is a random walk in which step lengths are not discrete but are given by some – usually heavy-tailed- probability distribution.

One can think of foragers, such as birds pecking in a region and then flying off in a uniformly random direction for a random distance and pecking around that region before repeating the action.

Steps in a 2-dimensional Levy flight

A Levy flight, by definition, has memory 0. What, however, if we introduce a small \epsilon > 0 amount of memory, in that the Levy walk could not return to a region of radius \epsilon > 0 around its last transition point? What would such Levy flights with memory look like?

http://www.crikeymath.com/wp-content/uploads/2017/09/crikey.wav

Filed Under: Uncategorized

Recent Posts

  • Does the DNA test say guilty or not guilty?
  • The Turtleback Diagram for Conditional Probability
  • Numbers that, base 2, are blindingly obviously divisible by 3
  • A mysterious sequence of 1s and 2s
  • Does one have to be a genius to do mathematics? Neither necessary nor sufficient.
  • Alexander Bogomolny
  • Binary disjoints of an integer
  • A cycle of length 5 for iterated squaring modulo a prime
  • The diagonal of the Wythoff array
  • Leonardo Bigollo, accountant, son of Bill Bonacci

Archives

Copyright © 2023 · Dynamik Website Builder on Genesis Framework · WordPress · Log in