Random walks with reinforcement

: (Alternative Format Thesis)

Abstract

The purpose of this thesis is to study the phase transition between recurrence and transience of random walks with reinforcement, which are self-interacting non-Markovian processes. Since the successive jumps of the random walk depend on its previous steps, random walks with reinforcement are inherently often challenging to analyse as standard techniques cannot usually be applied.

The branching-ruin number, which can be interpreted as a polynomial version of the branching number, has been identified as the critical parameter of the phase transition of once-reinforced random walks (ORRW) as well as M-digging random walks on trees. In this thesis, we attempt to create a general framework for random walks with reinforcement by introducing a class of new processes called reinforced digging random walks (RDRW) that we study on trees. We show that their critical parameter is also the branching-ruin number. In fact, ORRW and M-digging random walks are examples of RDRW, and thus we recover phase transition results for them when the underlying graph is a tree. The second objective of this thesis is to investigate ORRW on tree-like graphs with double edges; that is, graphs obtained from trees by inserting an additional parallel edge between each pair of neighbouring vertices. Under the assumption on some exit distribution (Conjecture 7.1 of Chapter 3), we obtain using diffusion approximation the asymptotic behaviour of the probability that, after the first step, ORRW reaches a vertex at distance n before returning to the root for the first time. This then allows us to establish a recurrent regime by applying the first moment method. On the other hand, proving transience poses many more challenges. Nonetheless, we achieve a transient regime by constructing a comparison process, which is always dominated by ORRW such that if the comparison process is transient, then so is ORRW. This process is then identified as a certain RDRW, for which we instantaneously obtain the phase transition by application of our previous results. As a consequence, we establish a novel result for ORRW on a new type of graphs that contain cycles, and thus expanding upon a narrow research area concerning ORRW on non-simple graphs.

Date of Award	13 Nov 2024
Original language	English
Awarding Institution	University of Bath
Supervisor	Daniel Kious (Supervisor) & Hendrik Weber (Supervisor)