Elephant random walk

Abstract

In this bachelor thesis, we will look a variant of the random walk, namely the elephant random walk. The elephant random walk, named after the elephant due to its excellent memory, is a random walk where future steps are based on previous steps taken in the walk based on the memory parameter p. To that end, we will be looking at the differences between the normal random walk and elephant random walk: we will look at the differences in behavior and properties of both types of random walks. In particular, we will focus on the gambler’s ruin problem, where we discuss the chances of player A winning, ν(α), and the expected number of steps until either player wins, e(α). To do so, we will make use of martingales and known theorems about martingales to prove the theorems about the elephant random walk. For the gambler’s ruin problem for the elephant random walk, we use simulations to look at the behavior of the gambler’s ruin for the elephant random walk.

We found that in general, the elephant random walk behaves differently from the normal random walk: while the expected value of the normal random walk increases or decreases linearly or stays at zero, the elephant random walk either diverges to infinity less than linearly or converges to zero based on the memory parameter p. In addition to this, one finds that the elephant random walk has three different diffusion regimes based on p: compared to the normal random walk, which only has a diffusive regime, the elephant random walk has a diffusive, marginally superdiffusive and superdiffusive regime. Looking at the properties, we see that some of the results of the normal random walk also hold for the elephant random walk, in particular the law of large numbers. However, it turns out that the central limit theorem only holds for certain values of p, and that the central limit theorem stops holding for larger p due to the dependence of steps on each other being too high. In addition, we found that the memory parameter p and initial parameter q for the gambler’s ruin for the elephant random walk affects how ν(α) and e(α) behaves, with the influence of q increasing as p increases on both ν(α) and e(α). The total capital N has little influence on the behavior of the gambler’s ruin for the elephant random walk, with N only affecting the maximal expected number of steps.