• 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.

    Markov chains and emergent behavior for problems from discrete geometry

    Thumbnail
    View/Open
    CANNON-DISSERTATION-2018.pdf (34.85Mb)
    Date
    2018-07-02
    Author
    Cannon, Sarah
    Metadata
    Show full item record
    Abstract
    The problem of generating random samples from large, complex sets is widespread across the sciences, where such samples provide one way to begin to learn about the sets' typical properties. However, when the samples generated are unexpectedly correlated or drawn from the wrong distribution, this can produce misleading conclusions. One way to generate random samples is with Markov chains, which are widely used but often applied without careful analysis of their mixing time, how long they must run for until they are guaranteed to produce good samples. We present new mixing time bounds for two sampling problems from discrete geometry: dyadic tilings, combinatorial structures with applications in machine learning and harmonic analysis, and 3-colorings on a grid, an instance of the celebrated antiferromagnetic Potts model from statistical physics. Both of these results required the development of new techniques. In addition, we use Markov chains in a novel way to address research questions in programmable matter. Here, a main goal is to understand how simple computational elements can collectively accomplish complicated system-level goals. In an abstracted setting, we show that groups of particles executing our simple processes, based on Markov chains, can accomplish various tasks. This includes compression, a behavior exhibited by natural distributed systems such as fire ants and honey bees, and shortcut bridging, where the particles build bridges that optimize the same global trade-off as certain bridge-building ant colonies. Throughout, a key ingredient is the interplay between global properties of Markov chains, including but not limited to mixing time, and their dependence on local moves, or Markov chain transitions that change only a small part of the configuration. We call the global behavior that arises out of these local moves and their probabilities emergent behavior. In addition to understanding the relationship between local moves and mixing times in order to give sampling guarantees, our work on programmable matter harnesses this interaction between local and emergent behavior in a novel way, to develop distributed algorithms.
    URI
    http://hdl.handle.net/1853/60265
    Collections
    • College of Computing Theses and Dissertations [1191]
    • Georgia Tech Theses and Dissertations [23877]
    • School of Computer Science Theses and Dissertations [79]

    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