The maximum of a random walk and its application to rectangle packing

Let S-0,...,S-n be a symmetric random walk that starts at the origin (S-0 = 0) 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(0 less than or equal to k less than or equal to n) S-k = root 2n/3 pi - c + 1/5 root 2/3 pi n(-1/2) + O(n(-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 max(0 less than or equal to j less than or equal to n) S-j + 1/2 = n/4 + O(n(1/2)), when the rectangle sides are 2n independent uniform random draws from [0,1].