dc.contributor.author  Coffman, Edward G. Flajolet, Philippe Hofri, Micha Leopold, Flatto

dc.date.accessioned 
20170802T22:03:32Z

dc.date.available 
20170802T22:03:32Z

dc.date.issued 
19970728

dc.identifier.uri  https://hdl.handle.net/1911/96468 
dc.description.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 largen 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 unitwidth 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].

dc.format.extent 
14 pp

dc.language.iso 
eng

dc.rights 
You are granted permission for the noncommercial reproduction, distribution, display, and performance of this technical report in any format, but this permission is only for a period of fortyfive (45) days from the most recent time that you verified that this technical report is still available from the Computer Science Department of Rice University under terms that include this permission. All other rights are reserved by the author(s).

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

dc.type 
Technical report

dc.date.note 
July 28, 1997

dc.identifier.digital 
TR97283

dc.type.dcmi 
Text

dc.identifier.citation 
Coffman, Edward G., Flajolet, Philippe, Hofri, Micha, et al.. "The Maximum of a Random Walk and Its Application to Rectangle Packing." (1997) https://hdl.handle.net/1911/96468.
