An Analysis of Learning Processes Through Reinforced Random Walks

: (Alternative Format Thesis)

Abstract

This thesis concerns two reinforced random walk models designed to explain natural phenomena: the forward loop-erased ant walk, as introduced in this thesis, and the preferential monkey walk, as originally dened in [BFCGM19]. Both processes require memory of the entire history of the process which makes them non-Markovian. In this thesis, we consider the asymptotic behaviour of the walks and interpret this behaviour within the context of the original natural phenomena. In particular, we examine the proportion of ants that traverse each edge in the ants walk and the proportion of times we revisit a vertex in the monkey walk. We highlight the novel behaviour of these models that distinguish them from the existing literature and present the novel techniques used to analyse them.

For the ant walk, we introduce the ant walk as dened in [KMS20, KMS21] and motivate why this new model is of interest by highlighting the link with weighted uniform spanning trees. We then go on to show that this new ant walk "finds the shortest path" when the nest and food are a distance 2 apart, a class of graphs not previously covered in [KMS20, KMS21]. We prove this result using stochastic approximation theory, electrical networks and the aforementioned link with weighted uniform spanning trees.

For the monkey walk, we explore a variant of the original model introduced in [BSS14] that shows preference towards remaining near the origin. We show that this preference can result in localisation, where the occupation measure converges to some nondegenerate limit, under the right choice of model parameters. This supports the argument of [BFCGM19] that a phase transition occurs in this model from diffusion (as observed in the original model of [BSS14]) to localisation. We prove this localisation using measure-valued Pólya processes and their link with the quasistationary distributions of certain killed continuous-time jump processes.

Date of Award	22 Apr 2026
Original language	English
Awarding Institution	University of Bath
Supervisor	Cecile Mailler (Supervisor) & Daniel Kious (Supervisor)