Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. 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

Give such a random walk moving on the x-axis:

  1. Start from $x_0=0$;
  2. After the $i^{th}$ step, the location is $x_i$.
  3. The length for the $i^{th}$ step $x_i-x_{i-1}$ is a uniformly generated real number in $[-1,1]$. Negative length means to move to the positive direction.

The problem is to compute

$$\text{Expectation}\left(\max\limits_{0\leq i,j \leq n}(x_i-x_j)\right)$$


$$\text{Expectation}\left(\max\limits_{0\leq i \leq j \leq n}(x_i-x_j)\right)$$

share|cite|improve this question
It would be helpful if you put the question into some context. Is it an open problem? If not, you could tell us how you approached it, that will help to gauge responses to the appropriate level. Are you interested in large $n$ asymptotics? – Sasha Jul 3 '12 at 15:18
@Sasha This problem is abstracted from a bigger problem. The original problem is much more complex. And I think it is unnecessary to know the original problem, because it may make us more confused. Large $n$ asymptotics also will be appreciated, though I do need to know if there is a close form for such problems. – konjac Jul 3 '12 at 16:00
up vote 2 down vote accepted

This is meant to be a comment, but grew too large. First simplify the formula a little: $$ \mathbb{E}\left( \max_{0\leqslant i,j \leqslant n}\left(x_i - x_j\right) \right) = \mathbb{E}\left( \max_{0 \leqslant i \leqslant n}(x_i) - \min_{0 \leqslant j \leqslant n}(x_j) \right) \stackrel{\text{symmetry}}{=} 2 \mathbb{E}\left( \max_{0 \leqslant i \leqslant n}(x_i) \right) $$ This can now be simulated:

enter image description here

with the simulation suggesting $\sim \sqrt{n}$ behavior, at least for large $n$.

share|cite|improve this answer
+1 although I think that your "simplification" is not totally intuitive, even though true. For large $n$, I suspect based on the running maximum of a standard Wiener process the expectation is close to $\sqrt{\frac{8n}{3\pi}} \approx 0.921 \sqrt{n}$, not far away from your simulation. – Henry Nov 18 '12 at 1:57

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.