Show simple item record

dc.contributor.authorCoffman, Edward G.
Flajolet, Philippe
Hofri, Micha
Leopold, Flatto
dc.date.accessioned 2017-08-02T22:03:32Z
dc.date.available 2017-08-02T22:03:32Z
dc.date.issued 1997-07-28
dc.identifier.urihttps://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 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].
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 forty-five (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 TR97-283
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.


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record