$\newcommand{\Z}{\mathbb Z}$ $\newcommand{\w}{\omega}$ $\newcommand{\vp}{\mathrm{v}_0}$

PRiME 2017: Purdue Research in Mathematics Experience

Research Projects in Probability Theory

Research projects in Probability Theory will be directed by Jonathon Peterson, Assistant Professor of Mathematics at Purdue University.

Random walks and the corresponding continuous model of Brownian motion are a simple models for random motion, and are some of the most classical objects of study in probability theory with far reaching applications in physics, biology, computer science, economics and other fields outside of mathematics. The behavior of $d$-dimensional random walks are very well understood since the walk can be represented as the sum of independent, identically distributed random variables (representing the successive jumps/steps of the random walk). However, this homogeneity may not be realistic for certain applications of random walks, and there has been a lot of interest the past few decades in studying more general models of random motion. Potential research projects involve studying some self-interacting random walk models such as Excited Random Walks and their relation to continuous models of self-interacting motion such as Perturbed Brownian Motion.

Excited Random Walks

Excited random walks are a type of self-interacting random walk; that is, a non-Markovian model for random motion where the future behavior of the walk is influenced in some way by the past behavior of the walk. In the case of excited random walks the self-interaction is such that the transition probabilities for the next step of the walk is determined by the number of times the walk has previously visited its current location.

The simplest model of excited random walks (on $\Z$) is defined as follows. Fix an integer $M\geq 1$ and a $p \in (\frac{1}{2},1)$. The excited random walk $\{X_n\}_{n\geq 0}$ is then generated as follows. On the $j$-th visit of the walk to a site $x \in \Z$ the walk jumps to the right (resp. left) with probability $p$ (resp. $1-p$) if $j\leq M$, while if $j>M$ then the walk jumps to the left/right with probability $1/2$ each. Thus, on the first $M$ visits to each site the walk makes jumps like a random walk that is biased to the right whereas on all subsequent visits the walk makes jumps like a simple symmetric random walk. The interest in this model of random motion is not based on any particular application but instead as a toy model for other more complicated self-interacting random walks which are not yet as well understood.

Excited random walks are sometimes called cookie random walks since one can give the following "cookie" interpretation to the dynamics. When the walker starts out, there are $M$ cookies at each site. As the walker moves around he eats a cookie every time he visits a site. When he is at a site with at least one cookie left, he eats a cookie which gives him some "excitement" which makes him move to the right with probability $p$ or left with probability $1-p$ (top and left above). On the other hand, if the walker returns to a site where he has already eaten all the cookies, then there is no "excitement" left and he moves right/left with probability $1/2$ each (right above).

Since self-interacting random walks are non-Markovian processes, this generally makes their study very difficult. Somewhat surprisingly, however, a great deal about the behavior of excited random walks is known and many of the results depend on the simple, explicit parameter $\delta = M(2p-1)$. For instance, the following explicit criteria for transience and positive limiting speed are given by the parameter $\delta$.

Project #1: The limiting speed of excited random walks

While the criterion for positive speed ($\delta = M(2p-1) > 2$) is explicit, there is unfortunately not yet an explicit formula for the speed $\vp(M,p)$ when it is non-zero. There are several interesting research projects related to better understanding the speed function $\vp(M,p)$.

Perturbed Brownian motion

If you simulate a classical simple symmetric random walk (a walk which always steps left or right with probability $1/2$) for a large number of steps and plot a corresponding graph of the location of the walk versus time you will get a very "rough" or "jagged" plot that might look somewhat similar to the charts you see of stock prices over time. This graph of the path of the random walk is approximately the same as what is known as Brownian motion.
The above figure shows a plot of a simulation of Brownian motion.
A Brownian motion is a random continuous function $(B(t))_{t\geq 0}$ with the properties that
  1. $B(t)$ is normally distributed with mean $0$ and variance $t$ for any $t>0$.
  2. The increments are sationary; that is $B(t+s)-B(t)$ has the same distribution as $B(s)$ for any $s,t>0$.
  3. The increments are independent; that is, $B(t+s)-B(t)$ is independent of $B(t)$ for any $s,t>0$.

It is a classical result in probability theory (Donsker's invariance principle) that the graph of the path of any classical random walk (when properly centered) will approximately be a Brownian motion (we say that the "scaling limit" of the random walk is a Brownian motion). However, for other models of random motion (like excited random walks) the scaling limit isn't necessarily always a Brownian motion. In particular, for the model of excited random walks described above with parameter $\delta \in (-1,1)$ the scaling limit is instead what is known as a $(\delta,-\delta)$-perturbed Brownian motion.

For any parameters $\alpha,\beta < 1$ an $(\alpha,\beta)$-perturbed Brownian motion is a continuous random process $(Y(t))_{t\geq 0}$ that solves the functional equation \[Y(t) = B(t) + \alpha \sup_{s\leq t} Y(s) + \beta \inf_{s\leq t} Y(s), \qquad \text{for } t>0, \] where $B(t)$ is a standard Brownian motion. It can be seen from this equation that a perturbed Brownian motion behaves exactly like a Brownian motion except when it reaches a new global maximum or minimum point.

Project #2: Perturbed Brownian motion as a scaling limit of self-interacting random walks

There are a number of self-interacting random walk models for which scaling limits are not known, but partial results suggest that the scaling limit may be a perturbed Brownian motion. Two such models are Potential project ideas include