MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

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

Can anyone help with the following (slightly weird) random walk question? I have a random walk starting at $X_0 = 1 = S_0$ where the steps $X_i$ are independent uniform random variates in $[-1,1]$. The entire walk is conditioned on two hypotheses:

  1. The walk terminates after $n$ steps at $0$ (so $S_n = X_0 + X_1 + \cdots + X_n = 0$).
  2. Each partial sum $S_k \geq \frac{X_k - 1}{2}$. Alternatively, the weighted partial sum $2 X_0 + 2 X_1 + 2 X_2 + \cdots + 2 X_{k-1} + X_k \geq -1$.

I'm interested in the variable $M_n = \max_{0 \leq i \leq n} S_i$.

  1. What's the distribution of $M_n$?
  2. Can one find upper or lower bounds on $P[M_n < a]$?

This came up in the same project as Distribution of maximum of random walk conditioned to stay positive, which is certainly more standard. For this one, I completely don't know whether this is standard or difficult.

I've looked up some standard stuff (eg. on sequential sampling) where you have a boundary condition given by absorbing boundaries at $0$ and $a$, but the weighted sum seems to make things harder. Again, I'd be very happy to learn that this is a standard thing with a good reference, or for advice as well as complete solutions. Any thoughts?

share|cite|improve this question
How is your hypothesis 2 different from simply demanding that each $S_k \ge -1$? – Greg Martin Feb 20 '13 at 22:25
The $X_i$ aren't equally weighted to form an $S_k$: in particular, everything BUT the last step occurs twice, while the last step only once. – Jason Cantarella Feb 21 '13 at 0:01
Sorry, the last step occurs only once. – Jason Cantarella Feb 21 '13 at 0:02

Your Answer


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

Browse other questions tagged or ask your own question.