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.
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Adleman, L., Cheng, Q., Goel, A., Huang, M.-D.: Running time and program size for self-assembled squares. In: STOC 2001: Proceedings of the thirty-third annual ACM Symposium on Theory of Computing, pp. 740–748. ACM, New York (2001)
Becker, F., Rapaport, I., Rémila, E.: Self-assembling classes of shapes with a minimum number of tiles, and in optimal time. In: Arun-Kumar, S., Garg, N. (eds.) FSTTCS 2006. LNCS, vol. 4337, pp. 45–56. Springer, Heidelberg (2006)
Chen, H.-L., Goel, A.: Error free self-assembly with error prone tiles. In: Proceedings of the 10th International Meeting on DNA Based Computers (2004)
Demaine, E.D., Demaine, M.L., Fekete, S.P., Ishaque, M., Rafalin, E., Schweller, R.T., Souvaine, D.L.: Staged self-assembly: nanomanufacture of arbitrary shapes with O(1) glues. Natural Computing 7(3), 347–370 (2008)
Doty, D.: Randomized self-assembly for exact shapes, Tech. Report 0901.1849, Computing Research Repository (2009)
Fujibayashi, K., Zhang, D.Y., Winfree, E., Murata, S.: Error suppression mechanisms for dna tile self-assembly and their simulation. Natural Computing (to appear)
Kao, M.-Y., Schweller, R.T.: Randomized self-assembly for approximate shapes. In: Aceto, L., Damgård, I., Goldberg, L.A., Halldórsson, M.M., Ingólfsdóttir, A., Walukiewicz, I. (eds.) ICALP 2008, Part I. LNCS, vol. 5125, pp. 370–384. Springer, Heidelberg (2008)
Knuth, D.E.: The art of computer programming. Seminumerical algorithms, vol. 2. Addison-Wesley, Reading (1997)
Lathrop, J.I., Lutz, J.H., Patitz, M.J., Summers, S.M.: Computability and complexity in self-assembly. In: Beckmann, A., Dimitracopoulos, C., Löwe, B. (eds.) CiE 2008. LNCS, vol. 5028, pp. 349–358. Springer, Heidelberg (2008)
Lathrop, J.I., Lutz, J.H., Summers, S.M.: Strict self-assembly of discrete Sierpinski triangles. Theoretical Computer Science 410, 384–405 (2009)
Majumder, U., LaBean, T.H., Reif, J.H.: Activatable tiles: Compact, robust programmable assembly and other applications. In: Garzon, M.H., Yan, H. (eds.) DNA 2007. LNCS, vol. 4848, pp. 15–25. Springer, Heidelberg (2008)
Patitz, M.J., Summers, S.M.: Self-assembly of decidable sets. In: Calude, C.S., Costa, J.F., Freund, R., Oswald, M., Rozenberg, G. (eds.) UC 2008. LNCS, vol. 5204, pp. 206–219. Springer, Heidelberg (2008)
Patitz, M.J., Summers, S.M.: Self-assembly of discrete self-similar fractals (extended abstract). In: Proceedings of The Fourteenth International Meeting on DNA Computing, Prague, Czech Republic, June 2-6 (2008) (to appear)
Rothemund, P.W.K.: Theory and experiments in algorithmic self-assembly, Ph.D. thesis, University of Southern California (December 2001)
Rothemund, P.W.K., Winfree, E.: The program-size complexity of self-assembled squares (extended abstract). In: STOC 2000: Proceedings of the thirty-second annual ACM Symposium on Theory of Computing, pp. 459–468. ACM, New York (2000)
Rothemund, P.W.K., Papadakis, N., Winfree, E.: Algorithmic self-assembly of dna sierpinski triangles. PLoS Biology 2(12) (2004)
Seeman, N.C.: Nucleic-acid junctions and lattices. Journal of Theoretical Biology 99, 237–247 (1982)
Soloveichik, D., Winfree, E.: Complexity of compact proofreading for self-assembled patterns. In: Carbone, A., Pierce, N.A. (eds.) DNA 2005. LNCS, vol. 3892, pp. 305–324. Springer, Heidelberg (2006)
Soloveichik, D., Winfree, E.: Complexity of self-assembled shapes. SIAM Journal on Computing 36(6), 1544–1569 (2007)
LaBean, T.H., Majumder, U., Sahu, S., Reif, J.H.: Design and simulation of self-repairing DNA lattices. In: Mao, C., Yokomori, T. (eds.) DNA12. LNCS, vol. 4287, pp. 195–214. Springer, Heidelberg (2006)
von Neumann, J.: Various techniques for use in connection with random digits. In: von Neumann’s Collected Works, vol. 5, pp. 768–770. Pergamon, Oxford (1963)
Winfree, E.: Algorithmic self-assembly of DNA, Ph.D. thesis, California Institute of Technology (June 1998)
Winfree, E., Bekbolatov, R.: Proofreading tile sets: Error correction for algorithmic self-assembly. In: Chen, J., Reif, J.H. (eds.) DNA 2003. LNCS, vol. 2943, pp. 126–144. Springer, Heidelberg (2004)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2009 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Doty, D., Lutz, J.H., Patitz, M.J., Summers, S.M., Woods, D. (2009). Random Number Selection in Self-assembly. In: Calude, C.S., Costa, J.F., Dershowitz, N., Freire, E., Rozenberg, G. (eds) Unconventional Computation. UC 2009. Lecture Notes in Computer Science, vol 5715. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-03745-0_19
Download citation
DOI: https://doi.org/10.1007/978-3-642-03745-0_19
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-03744-3
Online ISBN: 978-3-642-03745-0
eBook Packages: Computer ScienceComputer Science (R0)