# A problem about the expectation of maximum rise up for a random walk.

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

and

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

-
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

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:
with the simulation suggesting $\sim \sqrt{n}$ behavior, at least for large $n$.
+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