MURAL - Maynooth University Research Archive Library

    Random number selection in self-assembly

    Doty, David and Lutz, Jack H. and Patitz, Mathhew J. and Summers, Scott M. and Woods, Damien (2009) Random number selection in self-assembly. In: Unconventional Computation. Springer, pp. 143-157. ISBN 3-642-03744-5

    Download (514kB) | Preview

    Share your research

    Twitter Facebook LinkedIn GooglePlus Email more...

    Add this article to your Mendeley library


    We investigate methods for exploiting nondeterminism inherent within the Tile Assembly Model in order to generate uniform random numbers. Namely, given an integer range {0,...,n − 1}, we exhibit methods for randomly selecting a number within that range. We present three constructions exhibiting a trade-off between space requirements and closeness to uniformity. The first selector selects a random number with probability Θ(1/n) using O(log2 n) tiles. The second selector takes a user-specified parameter that guarantees the probabilities are arbitrarily close to uniform, at the cost of additional space. The third selector selects a random number with probability exactly 1/n, and uses no more space than the first selector with high probability, but uses potentially unbounded space.

    Item Type: Book Section
    Keywords: Tile Type; Pseudorandom Generator; Nondeterministic Choice; Tile Assembly Model; Perfect Uniformity;
    Academic Unit: Faculty of Science and Engineering > Computer Science
    Faculty of Science and Engineering > Research Institutes > Hamilton Institute
    Item ID: 15729
    Depositing User: Damien Woods
    Date Deposited: 23 Mar 2022 12:34
    Publisher: Springer
    Refereed: Yes
    Use Licence: This item is available under a Creative Commons Attribution Non Commercial Share Alike Licence (CC BY-NC-SA). Details of this licence are available here

    Repository Staff Only(login required)

    View Item Item control page


    Downloads per month over past year

    Origin of downloads