Difference between revisions of "Random Number Selection in Self-Assembly"
(Created page with "{{PaperTemplate |title=Random Number Selection in Self-Assembly |abstract=We investigate methods for exploiting nondeterminism inherent within the Tile Assembly Model in order to...") |
|||
| Line 1: | Line 1: | ||
{{PaperTemplate | {{PaperTemplate | ||
|title=Random Number Selection in Self-Assembly | |title=Random Number Selection in Self-Assembly | ||
| − | |abstract=We investigate methods for exploiting nondeterminism inherent within the Tile Assembly Model in order to generate uniform | + | |abstract=<p>We investigate methods for exploiting nondeterminism inherent within the Tile Assembly Model in order to generate uniform random numbers. Namely, given an integer range <m>\{0, ... , n - 1\}</m>, 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.</p> |
| − | random numbers. Namely, given an integer range {0, . . . , n | + | |
| − | present three constructions exhibiting a trade-off between space requirements and closeness to uniformity. | + | <p>The first selector selects a random number with probability <m>\Theta(1/n)</m> using |
| − | The first selector selects a random number with probability | + | <m>O(log^2 n)</m> 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 <m>1/n</m>, and uses no more space than the first selector with high probability, but uses potentially unbounded space.</p> |
| − | <m>O(log^2 n)</m> 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. | ||
|authors=David Doty, Jack H. Lutz, Matthew J. Patitz, Scott M. Summers, and Damien Woods | |authors=David Doty, Jack H. Lutz, Matthew J. Patitz, Scott M. Summers, and Damien Woods | ||
|file=[http://www.cs.iastate.edu/~mpatitz/papers/RNSSA.pdf PDF] | |file=[http://www.cs.iastate.edu/~mpatitz/papers/RNSSA.pdf PDF] | ||
}} | }} | ||
Revision as of 22:42, 29 November 2011
Published on:
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 <m>\{0, ... , n - 1\}</m>, 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 <m>\Theta(1/n)</m> using <m>O(log^2 n)</m> 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 <m>1/n</m>, and uses no more space than the first selector with high probability, but uses potentially unbounded space.
Authors
David Doty, Jack H. Lutz, Matthew J. Patitz, Scott M. Summers, and Damien Woods
