## 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