Doty, David, Lutz, Jack H., Patitz, Mathhew J., 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
dW_random.pdf
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 |
Related URLs: | |
URI: | https://mu.eprints-hosting.org/id/eprint/15729 |
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)
Downloads
Downloads per month over past year