1
$\begingroup$

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

  • 0
    @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.2012-07-03

1 Answers 1

2

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

  • 0
    +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.2012-11-18