Generalized and reinforced dependencies in the elephant random walk

Abstract

The Elephant Random Walk (ERW), introduced as a memory-dependent random walk model, has inspired a diverse body of literature exploring its long-term behavior and memory structures. This thesis presents a comprehensive survey of key developments in the analysis of ERW and its variants, with a particular focus on how memory shapes the walk's statistical properties. In the first part, we provide a literature review highlighting martingale-based approaches, stochastic approximation techniques, and connections to generalized Pólya urns, which have been instrumental in establishing functional limit theorems and identifying phase transitions. The second part of the thesis introduces new contributions: we study a generalization of the memory parameter beyond the classical form (where we consider, instead of a single memory parameter p, a sequence {p_n}_n of memory parameters with suitable assumptions imposed on {p_n}_n and explore the dynamics of an ERW with k-step memory (i.e. where the walker remembers the last or most recent k steps, for various values of k). Additionally, we initiate a preliminary investigation into a new variant we term the Déjà Vu Random Walk, where a sample step is repeated according to a probability that is a function of the proportion of times that step has been sampled, and agreed with, in the past. This, pending further analysis, ought to exhibit an even heavier reliance of the behaviour of the walker on its memory, giving rise to a new and fascinating class of memory-reinforced random walk models. Although the duration of the thesis is over, I continue to explore this new variant of ERW in collaboration with Dr. Moumanti Podder and Archi Roy. We develop a novel diagrammatic representation of the new variant of ERW described above using random recursive forests, where the n-th vertex represents the n-th time-stamp, for each n in N, and a spin (which could either be +1 or -1) assigned to the n-th vertex represents the value of the step taken during the n-th time-stamp by the walker. This graphical approach offers a new perspective on the evolution of this walk, and may serve as a tool for the analysis of further variants of ERW, endowed with complex memory-dependent schemes, in the future.