A balanced excited random walker returns home

A balanced excited random walker returns home

Title: Balanced Excited Random Walk in Two Dimensions

Authors and Year: Omer Angel, Mark Holmes, Alejandro Ramirez; 2023

Journal: Annals of Probability

Will balance and excitement always lead a random walker home? A new paper in the Annals of Probability attempts to answer this question and explores paths along the way.

Random Walks

Imagine you moved into a new neighborhood and you are excited to go on a walk to explore. The neighborhood is arranged in a grid structure, so at each intersection you have four choices for which direction to take: left, right, forwards, or backwards. Since you don’t know where you’re going, you decide to use some randomness to pick which direction to take. This is a random walk: a type of random process that is just a succession of steps on some sort of graph according to some probabilistic rules. The neighborhood grid gives a walk in two dimensions, because at each intersection you can go forward/backward or left/right.

In a balanced random walk, every direction has the same probability – there is always a ¼ chance each that you go left, right, forward, or backward. You could flip a coin to first decide whether to move in the forward/backward or left/right direction, and then flip it again to decide which of the two options to take. In an excited random walk, the first time you visit an intersection there is some bias in one direction – maybe you know that the cool park is somewhere to the left, so you always try that at a new intersection – but on future visits to the intersection you go back to the rule that every direction has the same probability.

The balanced excited random walk combines these two ideas. Maybe you’ve decided that instead of exploring everything completely randomly, you want to be more strategic to try to cover more ground. Now, the first time you reach a new intersection, you flip a coin to decide whether to keep going straight or turn around, but whenever you reach an intersection you recognize, you flip a coin to decide to turn left or right. Figure 1 shows one simulation of this random process, which tracks the path of a balanced excited random walker starting from (0, 0) on the grid.

Figure 1: A simulation of the 2-dimensional excited balanced random walk after 108 steps.

Returning Home

Let’s suppose that your new neighborhood is infinite! You could keep on walking forever … What are the odds of eventually returning home to where you started? Perhaps at the beginning you circle back and return to where you started, but eventually you head off in some direction and never return again. This property of a random walk is called transience – the walk returns to its starting point only a finite number of times. In contrast, recurrence means that the walk returns to its starting point infinitely many times.

It’s not obvious whether a random walk is always recurrent or transient. Consider the balanced random walk (remember, at each step every direction is equally likely). In one dimension, there are only two choices for each step, either forwards or backwards – imagine moving up and down an infinite ladder. In this case, the random walk is always recurrent. The balanced random walk is also recurrent in two dimensions, like walking on the neighborhood grid. However, in three dimensions (now you could go left-right, forward-back, or up-down), the random walk is transient.

What about the balanced excited random walk? The balanced random walk is a special type of random process called a Markov chain. This means that the probability of the walker’s position at the next step only depends on its current position. Maybe the walker happened to take 10 steps to the right in a row; this past history doesn’t matter, there is still the same chance of moving to the right at the next step. However, the balanced excited random walk does not have this property. Your probability of taking a step at a given position does depend on your past, because it matters whether or not you’ve visited this position before. This makes the balanced excited random walk much more difficult to study.

Some Findings

The conjecture is that in two dimensions the balanced excited random walk is always recurrent, just like the balanced random walk. The authors of the paper “Balanced Excited Random Walk in Two Dimensions” prove that the set of recurrent sites (the sites which are visited infinitely many times) is either everything or nothing. The next question is, is the set of recurrent sites always either everything or nothing? It could be possible that you set out on a balanced excited random walk and you will visit every site infinitely often, but your friend set out on their own walk and will head off in some direction so they will visit every site only a finite number of times. 

The authors also prove a result about how the total number of sites visited by the random walk grows as the total number of steps grows. This still leaves much to be studied, but it is a first step to understanding the balanced excited random walk in two dimensions.

More to Explore

Random walks are used to study randomness in many areas. For example, mutations accumulating randomly in DNA, users randomly exploring webpages, or neurons firing in the brain. Different types of random walks are needed to model different scenarios and understanding the long-term properties is important mathematically and in applications. 

The balanced excited random walk is a non-Markov process and still poses many unanswered questions. Mathematicians will need to keep on walking to explore the mysteries of this random process.