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

Abstract

Let S0,...,Sn be a symmetric random walk that starts at the origin (S0 = 0), and takes steps uniformly distributed on [-1,+1]. We study the large-n behavior of the expected maximum excursion and prove the estimate$$ \exd \max_{0 \leq k \leq n} S_k = \sqrt{\frac{2n}{3\pi}} c +\frac{1}{5}\sqrt{\frac{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/2 \exd \max_{0 \leq j \leq n} S_j + 1/2 = n/4 +O(n^(1/2)),$ when the rectangle sides are 2n independent uniform random draws from [0,1].