• Login
    View Item 
    •   SMARTech Home
    • Georgia Tech Theses and Dissertations
    • Georgia Tech Theses and Dissertations
    • View Item
    •   SMARTech Home
    • Georgia Tech Theses and Dissertations
    • Georgia Tech Theses and Dissertations
    • View Item
    JavaScript is disabled for your browser. Some features of this site may not work without it.

    Randomness as a tool for modeling and uncovering structure

    Thumbnail
    View/Open
    PETTI-DISSERTATION-2020.pdf (2.039Mb)
    Date
    2020-03-12
    Author
    Petti, Samantha N.
    Metadata
    Show full item record
    Abstract
    This thesis contains four main research directions, united by the themes of using randomness to (i) construct structure and (ii) uncover structure. Randomness has long been used for these tasks. Random models are defined to mirror some system, and the probabilistic analysis of the model then provides insight into the properties and behavior of the system. Using random choices in algorithms yields faster results that are very accurate for most cases. (1) Inspired by how computation may happen in the brain, we describe a method of building a threshold function by randomly connecting small primitive Boolean circuits. Our construction demonstrates the theme that a series of random choices can produce a structured object, in this case a Boolean circuit that computes a threshold function. (2) We introduce the Random Overlapping Communities (ROC) model in order to model the local structure of sparse graphs. We show that the model can be tuned to produce graphs with a wide range of normalized closed walk counts, including the closed walk counts of the hypercube sequence. This direction also illustrates the first theme; the randomness in the model produces graphs with a specified set of closed walk counts. (3) Fitting with the second theme, we explore the extent to which a small sample of a large graph can be used to deduce properties of the large graph. We introduce the Community Configuration model (CCM) to model graphs with overlapping community structure and varied degree distributions. We describe the sampling limit for sequences of CCMs and use the limit to draw parallels between CCMs and random graph models established in the literature. We also describe a hypothesis test to determine whether a graph was x produced from a CCM or a configuration model without community structure given access to a small random sample. (4) The hard sphere model is a well-known statistical physics model of monatomic gases. We describe a Markov chain for sampling from the model that achieves rapid mixing for a wider range of fugacity parameters than previously known. Analyzing the sampling process governed by the Markov chain allows us deduce properties of the infinite volume limit of the model, thus demonstrating the second theme.
    URI
    http://hdl.handle.net/1853/62767
    Collections
    • Georgia Tech Theses and Dissertations [23877]
    • School of Mathematics Theses and Dissertations [440]

    Browse

    All of SMARTechCommunities & CollectionsDatesAuthorsTitlesSubjectsTypesThis CollectionDatesAuthorsTitlesSubjectsTypes

    My SMARTech

    Login

    Statistics

    View Usage StatisticsView Google Analytics Statistics
    facebook instagram twitter youtube
    • My Account
    • Contact us
    • Directory
    • Campus Map
    • Support/Give
    • Library Accessibility
      • About SMARTech
      • SMARTech Terms of Use
    Georgia Tech Library266 4th Street NW, Atlanta, GA 30332
    404.894.4500
    • Emergency Information
    • Legal and Privacy Information
    • Human Trafficking Notice
    • Accessibility
    • Accountability
    • Accreditation
    • Employment
    © 2020 Georgia Institute of Technology