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

Question

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

Answer 1

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