Random Walk and the Area Below its Path

A simple random walk with reflected origin is considered. The walk starts at the origin and it must return to the origin at time 2n. We show that the expected area below the path of this walk is n2²ⁿ⁻¹/C_n²ⁿ. If, however, the walk is required to return to the origin for the first time at time 2n, then the expected area below the path of this Bernoulli excursion is (2n − 1)2²ⁿ⁻¹/C_n²ⁿ.

We also show that if V₁ < ⋯ < V_n is the order statistics based on a sample of size n from a uniform distribution over (0, 1), and that if U₁ < ⋯ < U_n is another independent set of order statistics from the same distribution, then

E [∑_i=1ⁿ |V_i − U_i|] = n2²ⁿ⁻¹/[(2n + 1)C_n²ⁿ]

We use this result to find an average-case performance of the Earliest Due Date (EDD) heuristic for one machine scheduling problem with earliness and tardiness penalties. We also apply some of the results to Larson's Queue Inference Engine (1990).