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

Preview

Download (514kB) | Preview

Abstract

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
URI:	Publisher
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)

Item control page

Downloads

Origin of downloads