MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I have an $n$ step random walk which starts at zero $X_0 = 0 = S_0$ where the steps $X_i$ are independent uniform random variates in $[-1,1]$, but the walk is conditioned on the hypothesis that it stays in the right half-line $[0,\infty)$ (that is, $S_k = X_0 + X_1 + \dots + X_k \geq 0$ for $k \in 0, \dots, n$).

I'm interested in the maximum of the walk, or the random variable $M_n = \max_{0 \leq i \leq n} S_i$.

  1. What is the distribution of $M_n$ (as a function of $n$)?
  2. Can one derive (upper or lower) bounds on the probability $P[M_n < a]$ that the walk is actually contained in the interval $[0,a]$ instead of $[0,\infty)$? Both types of bounds would be interesting, for different reasons, in a polymer physics question.

I've looked at the classical references (eg. Feller, or Spitzer, Chapter 4), but Spitzer at least seems to deal only with the integer valued case. However, it seems that I'm either missing it, or I can't quite find the right reference.

Are these standard results with a standard reference? It's clearly related to A random walk with uniformly distributed steps, which deals with the overall volume of the space of walks with uniform random variates as steps conditioned to stay positive, but not the maximum.

share|cite|improve this question
Do you need small $n$ or only the large $n$ limit? The last one can, probably, be derived from the Brownian motion approximation where you have neat formulae for everything; the exact nature of the steps shouldn't really matter much. – fedja Feb 20 '13 at 21:30
Ideally, we'd have small $n$ too. But I'd be happy with the large-$n$ limit. – Jason Cantarella Feb 20 '13 at 23:59
There is a way to solve this problem even for more general Markov processes, but could you please tell me more precise about your conditioning. In your case $\mathsf P(Y_k\geq 0\;\forall k) = 0$ so I guess you are interested rather in $$ \mathsf P(M_n \geq m|Y_k\geq 0 \; \forall 0\leq k\leq n) $$ am I right? – Ilya Feb 21 '13 at 9:45
@Ilya, you are completely correct (forehead smack). I edited the question to make it more clear that I'm thinking about the max of a finite walk which is conditioned to stay in $[0,\infty)$ for $n$ steps. – Jason Cantarella Feb 21 '13 at 21:21
I second the fedja's suggestion: to consider the Brownian approximation. Here, your problem is easily solvable: well, you can say that you are comparing the probability of a Brownian path starting from $\eps>0$ to stay positive during the time $n$, and to stay between $0$ and $a$ for the same time. (And pass to the limit as $\esp\to 0$.) This, you can study by the reflection method (what is the same, by studying the behavior of the heat equation with zero boundary condition, what corresponds to an odd extension of the initial condition)... – Victor Kleptsyn Feb 24 '13 at 21:14

1) I believe it is possible to obtain $P(M_n<a\ | \tau>n)$, where $\tau:=\inf\{n\ge 1: S_n\le 0\}$ in more or less explicit way only for the case of the simple random walk. These computations can be found in Billingsley, Convergence of Probability measures, Chapter 2.11. For large $n$ these computations become universal as you can apply FCLT, see below.

2) Generally, one can use Brownian motion approximations as was suggested by fedja. Mathematic justification is given in the references below. Before going into this I will say a few words about conditioning of random walks to stay positive.

There are two ways to condition random walk to be positive. First way is to condition on $\{\tau>n\}$, where $\tau:=\inf\{n\ge 1: S_n\le 0\}$. Second way, is to ''condition'' on $\{\tau=\infty\}$. Here you cannot use direct conditioning as $\mathbf P(\tau=\infty)=0$ (for the zero-mean finite variance random walk). So, the way to proceed is to use Doob's $h$ transform. As a result one obtains a Markov chain (Lamperti Markov chain, in fact) which is a discrete-time analogue of Bessel process.

Now I can move on to approximations as $n\to\infty$.

a) When $a$ is of order $\sqrt n$, you need to use corresponding Functional Central Limit Theorem (FCLT). You need functional central limit theorem as the maximum depends on the whole trajectory of the random walk. The way to use functional limit theorems is described in the above Billinsley's book, you can see an example for unconditioned random walk in Chapter 2.11.

For the first type of conditioning FCLT is proved in Iglehart, 1974, Functional Central Limit Theorems for Random Walks Conditioned to Stay Positive (doi:10.1214/aop/1176996607), see also Bolthausen, 1976, On a Functional Central Limit Theorem for Random Walks Conditioned to Stay Positive. Conditioning of the second type was considered in Bertoin and Doney (1994), On Conditioning a Random Walk to Stay Nonnegative (doi:10.1214/aop/1176988497). FCLT for the second type of conditioning can be found in Caravenna, Chaumont (2008), Invariance principles for random walks conditioned to stay positive (doi:10.1214/07-AIHP119). Finally, in higher dimensions you can use FCLT from

b) When $a$ is much larger then $\sqrt n,$ then $\mathbf P(M_n<a\ |\ \tau>n)\to 1$.

c) When $a<<\sqrt n$ you are dealing with small deviations probability. If you write $\mathbf P(M_n<a | \tau>n)=\mathbf P(M_n<a , \tau>n)/\mathbf P(\tau>n)$, then approximation for $\mathbf P(\tau>n)\sim Cn^{-1/2}, n\to\infty$, and $$ \mathbf P(\tau>n, M_n<a)=\mathbf P(\mbox{random walk $S_k$ stays in (0,n) for all } 0<k\le n) $$ Now, if $a\sim An^{1/2-\delta}$ for $\delta\in(0,1/2)$ you can split this trajectory in $n/a^2$ parts of length $a^2$ and use independence to obtain estimate $$ \mathbf P(\tau>n, M_n<a)\le \left(\mathbf P(\mbox{random walk $S_k$ stays in (0,2a) for all } 0<k\le a^2)\right)^{n/a^2} $$ Now, the probability inside the parenthesis is on the right scale and you can apply the FCLT to get $$ \mathbf P(\mbox{random walk $S_k$ stays in (0,2a) for all } 0<k\le a^2)\to C(A)\in(0,1). $$ This results in the following upper bound $$ \mathbf P(\tau>n, M_n<a) \le C(A)^{n/a^2}\approx C(A)^{n^{2\delta}}. $$ As $C(A)$ is in $(0,1)$ this probability is quite small. .

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.