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

PRiME 2016: 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 are a simple model for random motion, and are one 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 two such models of interacting random walks: random walks in random environments and excited random walks.

Project #1: 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 (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, it is known that the walk is transient to the right (i.e., $P(X_n \rightarrow +\infty) = 1$) if and only if $\delta>1$. Also, it is known that the random walk has a limiting speed $\vp = \vp(M,p) = \lim_{n\rightarrow\infty} X_n/n$ and that the speed is positive if and only if $\delta>2$. However, while the exact criterion for positive speed is easy to calculate, there is no 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)$.

Project #2: Random Walks in Random Environments

Random walks in random environments (RWRE) are a simple discrete model for random motion in an inhomogeneous medium or environment. An environment $\w = \{\w(x,y)\}_{x,y\in \Z^d}$ is a collection of transition probabilities where $\w(x,y) = P_\w( X_{n+1} = y | \, X_n = x)$ is the probability that the random walk jumps from $x$ to $y$. To give some structure to the environment, one assumes that the environment $\w$ is chosen randomly according to some distribution $P$ on the space of environments. Thus, a RWRE has two layers of randomness: (1) choosing a random environment $\w$, and (2) for the fixed environment $\w$ generating a random walk $\{X_n\}_{n\geq 0}$ in the environment $\w$.

In spite of the simplicity of the model of RWRE, it is known that RWRE can exhibit a number of surprising behaviors. For instance, while the Central Limit Theorem asserts that classical simple random walks always have Gaussian limiting distributions, it is known that one-dimensional RWRE can exhibit a rich array of limiting distributions related to the stable distributions, where the particular limiting distribution obtained depends critically on the distribution $P$ on environments.

RWRE are typically studied by inferring information about the behavior of the walk from known information about the environment. That is, given the distribution $P$ on the space of environments, one tries to predict/describe the behavior of the random walk. Recently, however, there has been interest in reversing this process: inferring information about the environment based on an observation of the path of the walk. Some of these results are motivated by problems in biology where a process can be modeled by a RWRE (such as mechanically unzipping a DNA sequence), with the goal of obtaining information about the environment. Some potential research projects in this direction are the following.