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

# Research Projects in Probability Theory

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

## Background

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.

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)$.

• 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 probably out of reach, a simpler problem would be to compute explicit bounds on the speed. For instance, while the Markov chain in the formula for the speed is difficult to analyze, one can truncate the Markov chain to get a Markov chain on a finite state space whose stationary distribution could be explicitly computed. This would then lead to an upper bound for the limiting speed of the random walk. A more difficult, but still reasonable problem would be to find a related Markov chain that can be explicitly solved to give a lower bound for the speed.
• 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, 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}$.) Also, if $\delta = M(2p-1) = M'(2p'-1)$ for integers $M,M'$ and $p,p' \in (1/2,1)$ are the speeds $\vp(M,p) = \vp(M',p')$? (certain monotonicity results that have already been obtained by Professor Peterson suggest they are probably not).

### 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.

• Estimation of parameters. For one-dimensional RWRE, many aspects of the random walk can be explicitly described through the distribution $P$ on environments. For instance, it is known that one-dimensional RWRE have a limiting speed $\vp(P) := \lim_{n\rightarrow\infty} X_n/n$ which can be explicitly calculated in terms of the distribution $P$. However, what if one wishes to estimate the speed of the walk when the distribution $P$ is unknown? If the random walk is observed for $n$ steps, a natural estimator for the speed would be $\hat{v}_n = X_n/n$, but known large deviation results show that this is somewhat likely to underestimate the true speed $\vp$. An interesting research project would be to see if the recent results on estimating the distribution $P$ from the observation of path of the walk can lead to improved estimators for the speed. In addition to estimating the speed, several other aspects of the walk could be studied in this way including recurrence/transience of the walk and a parameter $\kappa = \kappa(P)$ which governs the limiting distributions of transient RWRE. It should be noted that numerical simulations in a 2012 paper by Avena and Thomann showed that a more naive direct approach to estimating the parameter $\kappa$ does not perform very well.
• Inference on the environment for other graphs. All of the prior research for inference on the environment of a RWRE has been for one-dimensional RWRE. Can the techniques in these papers be adapted to RWRE on graphs other than $\Z$? In particular, RWRE on a two-dimensional strip $\Z \times \{1,2,\ldots,m\}$ may be an interesting first case to consider. It is known that RWRE on strips are similar in many ways to RWRE on $\Z$, and the proofs of results on strips were often adaptations of the corresponding proofs on $\Z$. One interesting difference with RWRE on strips, however, is that while parameters such as the speed $\vp(P)$ can usually be explicitly calculated for RWRE on $\Z$ the formulas for the corresponding parameters for RWRE on a strip typically cannot be computed explicitly. Thus, techniques for estimating these parameters for RWRE on a strip may prove useful even in the cases where the distribution $P$ on environments is known.