RANDOM-WALK AND THE AREA BELOW ITS PATH

A simple random walk with reflected origin is considered. The walk sta rts 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(2n-1)/(2n/n) . If however, the walk is required to return to the origin for the fir st time at time 2n, then the expected area below the path of this Bern oulli excursion is (2n-1)2(2n-1/)/(2n/n). We also show that if V1 < .. . < V(n) is the order statistics based on a sample of size n from a un iform distribution over (0, 1), and that if U1 < ... < U(n) is another independent set of order statistics from the same distribution, then [GRAPHICS] We use this result to find an average-case performance of t he Earliest Due Date (EDD) heuristic for one machine scheduling proble m with earliness and tardiness penalties. We also apply some of the re sults to Larson's Queue Inference Engine (1990).