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$.
The walk is transient to the right (i.e., $P(X_n \rightarrow +\infty) = 1$) if and only if $\delta>1$.
The limiting speed of the walk $\vp = \vp(M,p) = \lim_{n\rightarrow\infty} \frac{X_n}{n}$ is positive if and only if $\delta>2$.
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)$.
Explicit upper/lower bounds.
While there are no explicit formulas for the speed of excited random walks, there is a probabilistic formulation of the speed. However, using this formula to compute the speed would require identifying the stationary distribution of a certain Markov chain on $\Z_+$; somewhat surprisingly, this has eluded all efforts thus far.
While an explicit characterization of the speed is currently out of reach, students in the 2016 PRiME program developed methods for obtaining explicit upper and lower bounds on the speed. They implemented their methods in the case of $M=3$ cookies per site to obtain very tight bounds on the speed function. It remains to see how well these methods work when there are $M\geq 4$ cookies per site.
The above figure shows various estimates and rigorous upper and lower bounds for the speed function $\vp(3,p)$. The blue dots represent precise estimates of the true speed. The other curves represent various rigorous upper and lower bounds for $\vp(3,p)$. The best upper and lower bounds are given by the solid green and red curves, respectively (note that these bounds are almost indistinguishable from each other and from the estimates given by the blue dots).
Qualitative properties.
Even if one cannot explicitly compute the speed, one still may be able to use the probabilistic formulation of the speed to explore certain qualitative properties of the speed. For instance, one may consider the following questions.
Is the function $\vp(M,p)$ differentiable in $p$ on $(\frac{1}{2} + \frac{1}{M},1)$? (Note that $\vp(M,p)>0 \iff \delta>2 \iff p>\frac{1}{2} + \frac{1}{M}$.) It is known that the function $\vp(M,p)$ is continuous and monotone in $p$. Graphs obtained by simulations suggest that it is also differentiable, but this is not yet known.
To obtain a larger limiting speed for the walk is it better to have a few cookies with strong drift or many cookies with small drift? That is, for positive integers $M,M'$ and parameters $p,p' \in (1/2,1)$ is there a way to compare the speeds $\vp(M,p)$ and $\vp(M',p')$? For instance, if $\delta = M(2p-1)=M'(2p'-1)$ are the limiting speeds equal, $\vp(M,p) = \vp(M',p')$? (certain monotonicity results that have already been obtained by Professor Peterson suggest they are probably not).
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
$B(t)$ is normally distributed with mean $0$ and variance $t$ for any $t>0$.
The increments are sationary; that is $B(t+s)-B(t)$ has the same distribution as $B(s)$ for any $s,t>0$.
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
A generalization of the excited random walk model discussed above where there are infinitely many cookies at each site. See the recent paper by Elena Kosygina and Professor Peterson which introduces this model.
Potential project ideas include
Statistical analysis. For these models (and others which may be suspected to have perturbed Brownian motion as a scaling limit), a research project would be to do a statistical analysis of simulations of these random walks to compare with the known theoretical properties of perturbed Brownian motions.
Preliminary computations. A general outline for proving perturbed Brownian motion as a scaling limit has already been put together. The first step in completing this outline requires computing some asymptotics of the mean and variance of a certain Markov chain that is related to the random walk. These asymptotics would be a major step toward proving the conjectured scaling limits.
