The Maximum of a Random Walk and Its Application to Rectangle Packing

Let S sub o, ..., S sub n be a symmetric random walk that starts at the origin (S sub o = O), and takes steps uniformly distributed on [-1, +1]. We study the large-n behavior of the expected maximum excursion and prove the estimate E max over o=k=n S sub k = sqrt 2n over 3pi - c+ 1/5 sqrt 2 over 3pi n sup (-1/2) + O(n sup (-3/2), where c - 0.297952.... This estimate applies to the problem of packing n rectangles into a unit-width strip; in particular, it makes much more precise the known upper bound on the expected minimum height, n/4 + 1/2E maxo=j=nS sub j + 1/2 =n/4 + O(n sup (1/2), when the rectangle sides are 2n independent uniform random draws from [0,1].