DIMACS TR: 97-70

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



Authors: E. G. Coffman, Jr., Philippe Flajolet, Leopold Flatto and Micha Hofri

ABSTRACT

Let $S_0, \ldots ,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

\[ \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\ldots$. 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, $\frac{n}{4} + \frac{1}{2} \exd \max_{0 \leq j \leq n} S_j +\frac{1}{2} = \frac{n}{4} + O(n^{1/2}),$ when the rectangle sides are $2n$ independent uniform random draws from $[0,1]$.

Paper Available at: ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1997/97-70.ps.gz


DIMACS Home Page