Rice Univesrity Logo
    • FAQ
    • Deposit your work
    • Login
    View Item 
    •   Rice Scholarship Home
    • Faculty & Staff Research
    • George R. Brown School of Engineering
    • Computer Science
    • Computer Science Technical Reports
    • View Item
    •   Rice Scholarship Home
    • Faculty & Staff Research
    • George R. Brown School of Engineering
    • Computer Science
    • Computer Science Technical Reports
    • View Item
    JavaScript is disabled for your browser. Some features of this site may not work without it.

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

    Thumbnail
    Name:
    TR97-283.pdf
    Size:
    519.4Kb
    Format:
    PDF
    View/Open
    Author
    Coffman, Edward G.
    Flajolet, Philippe
    Hofri, Micha
    Leopold, Flatto
    Date
    1997-07-28
    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.
    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].
    Type
    Technical report
    Citable link to this page
    https://hdl.handle.net/1911/96468
    Metadata
    Show full item record
    Collections
    • Computer Science Technical Reports [244]

    Home | FAQ | Contact Us
    Managed by the Digital Scholarship Services at Fondren Library, Rice University
    Physical Address: 6100 Main Street, Houston, Texas 77005
    Mailing Address: MS-44, P.O.BOX 1892, Houston, Texas 77251-1892
     

     

    Searching scope

    Browse

    Entire ArchiveCommunities & CollectionsBy Issue DateAuthorsTitlesSubjectsTypeThis CollectionBy Issue DateAuthorsTitlesSubjectsType

    My Account

    Login

    Statistics

    View Usage Statistics

    Home | FAQ | Contact Us
    Managed by the Digital Scholarship Services at Fondren Library, Rice University
    Physical Address: 6100 Main Street, Houston, Texas 77005
    Mailing Address: MS-44, P.O.BOX 1892, Houston, Texas 77251-1892