- Physical Review Journals
All JournalsPhysics Magazine
Access Provided by Xinjiang University

Physical Review E

Export citation

Export citation

Choose format for download:

Download Citation
  • Access by Xinjiang University

Minimum memory for generating rare events

Cina Aghamohammadi* and James P. Crutchfield†

  • Complexity Sciences Center and Department of Physics, University of California at Davis, One Shields Avenue, Davis, California 95616, USA

  • *caghamohammadi@ucdavis.edu
  • †chaos@ucdavis.edu
PDF

Phys. Rev. E 95, 032101 – Published 1 March, 2017

DOI: https://doi.org/10.1103/PhysRevE.95.032101

Abstract

We classify the rare events of structured, memoryful stochastic processes and use this to analyze sequential and parallel generators for these events. Given a stochastic process, we introduce a method to construct a process whose typical realizations are a given process' rare events. This leads to an expression for the minimum memory required to generate rare events. We then show that the recently discovered classical-quantum ambiguity of simplicity also occurs when comparing the structure of process fluctuations.

View figure in article

Physics Subject Headings (PhySH)

Article Text

References (80)

  1. J. P. Crutchfield, in Cultures of Change—Changing Cultures, edited by P. Alsina and J. Perello (ACTAR, Barcelona, Spain, 2009), pp. 98–111.
  2. J. D. Deuschel and D. W. Stroock, Large Deviations (Academic Press, New York, 1989).
  3. J. A. Bucklew, Large Deviation Techniques in Decision, Simulation, and Estimation (Wiley-Interscience, New York, 1990).
  4. K. Young and J. P. Crutchfield, Chaos Solitons Fractals 4, 5 (1994).
  5. H. Touchette, Phys. Rep. 478, 1 (2009).
  6. A. Dembo and O. Zeitouni, Large Deviations Techniques and Applications, Stochastic Modelling and Applied Probability, 2nd ed. (Springer, New York, 2009).
  7. R. S. Ellis, Entropy, Large Deviations, and Statistical Mechanics, A Series of Comprehensive Studies in Mathematics (Springer, New York, 2012), Vol. 271.
  8. T. M. Cover and J. A. Thomas, Elements of Information Theory, 2nd ed. (Wiley-Interscience, New York, 2006).
  9. P. H. Algoet and T. M. Cover, Ann. Prob. 16, 899 (1988).
  10. M. D. Donsker and S. R. S. Varadhan, Commun. Pure Appl. Math. 28, 1 (1975).
  11. W. Feller, An Introduction to Probability Theory and Its Applications, 3rd ed. (Wiley, New York, 1970).
  12. A. Einstein, Ann. Phys. 17, 549 (1905).
  13. A. Einstein, Ann. Phys. 19, 371 (1906).
  14. Y. Oono, Prog. Theor. Phys. 99, 165 (1989).
  15. O. E. Lanford, in Statistical Mechanics and Mathematical Problems (Springer, Berlin, 1973), pp. 1–113.
  16. D. Ruelle, Thermodynamic Formalism (Addison-Wesley, Reading, MA, 1978).
  17. N. F. Travers, Ph.D. thesis, , Davis, 2013.
  18. D. R. Upper, Ph.D. thesis, University of California, Berkeley, 1997.
  19. D. A. Levin, Y. Peres, and E. L. Wilmer, Markov Chains and Mixing Times (American Mathematical Society, New York, 2009).
  20. J. R. Norris, Markov Chains (Cambridge University Press, Cambridge, UK, 1998), Vol. 2.
  21. L. R. Rabiner and B. H. Juang, IEEE ASSP Mag. 3, 4 (1986).
  22. L. R. Rabiner, Proc. IEEE 77, 257 (1989).
  23. J. P. Crutchfield and D. P. Feldman, Chaos 13, 25 (2003).
  24. C. E. Shannon, Bell Syst. Tech. J. 27, 379 (1948).
  25. J. P. Crutchfield and K. Young, Phys. Rev. Lett. 63, 105 (1989).
  26. J. P. Crutchfield, Nat. Phys. 8, 17 (2012).
  27. C. R. Shalizi and J. P. Crutchfield, J. Stat. Phys. 104, 817 (2001).
  28. A. Witt, A. Neiman, and J. Kurths, Phys. Rev. E 55, 5050 (1997).
  29. W. M. Gonçalves, R. D. Pinto, J. C. Sartorelli, and M. J. de Oliveira, Phys. A (Amsterdam, Neth.) 257, 385 (1998).
  30. A. J. Palmer, C. W. Fairall, and W. A. Brewer, IEEE Trans. Geosci. Remote Sens. 38, 2056 (2000).
  31. R. W. Clarke, M. P. Freeman, and N. W. Watkins, Phys. Rev. E 67, 016203 (2003).
  32. C.-B. Li and T. Komatsuzaki, Phys. Rev. Lett. 111, 058301 (2013).
  33. D. Nerukh, C. H. Jensen, and R. C. Glen, J. Chem. Phys. 132, 084104 (2010).
  34. D. Kelly, M. Dillingham, A. Hudson, and K. Wiesner, PLoS One 7, e29703, (2012).
  35. R. Durrett, Probability: Theory and Examples (Cambridge University Press, Cambridge, UK, 2010).
  36. S. Kullback, Information Theory and Statistics (Dover, New York, 1968).
  37. R. W. Yeung, Information Theory and Network Coding (Springer, New York, 2008).
  38. G. Han and B. Marcus, IEEE Trans. Inf. Theory 52, 5251 (2006).
  39. B. McMillan, Ann. Math. Stat. 24, 196 (1953).
  40. L. Breiman, Ann. Math. Stat. 28, 809 (1957).
  41. L. Boltzmann, Lectures on Gas Theory (Dover, New York, 2013).
  42. H. D. Miller, Ann. Math. Stat. 32, 1260 (1961).
  43. J. P. Garrahan, R. L. Jack, V. Lecomte, E. Pitard, K. van Duijvendijk, and F. van Wijland, J. Phys. A: Math. Theor. 42, 075007 (2009).
  44. L. O. Hedges, R. L. Jack, J. P. Garrahan, and D. Chandler, Science 323, 1309 (2009).
  45. R. L. Jack and P. Sollich, Prog. Theor. Phys. Suppl. 184, 304 (2010).
  46. J. Van Campenhout and T. M. Cover, IEEE Trans. Inf. Theory 27, 483 (1981).
  47. I. Csiszár, Ann. Probab. 12, 768 (1984).
  48. J. P. Crutchfield and S. Marzen, Phys. Rev. E 91, 050106(R) (2015).
  49. J. R. Mahoney, C. Aghamohammadi, and J. P. Crutchfield, Sci. Rep. 6, 20495 (2016).
  50. J. P. Crutchfield, Phys. D (Amsterdam, Neth.) 75, 11 (1994).
  51. W. Löhr and N. Ay, in International Conference on Complex Sciences (Springer, New York, 2009), pp. 265–276.
  52. W. Löhr and N. Ay, Adv. Complex Syst. 12, 169 (2009).
  53. W. Löhr, J. Syst. Sci. Complexity 25, 30 (2012).
  54. P. Gmeiner, arXiv:1108.5303.
  55. C. Aghamohammadi, J. R. Mahoney, and J. P. Crutchfield, Phys. Lett. A. (2016).
  56. J. P. Crutchfield and C. Aghamohammadi, arXiv:1609.02519.
  57. M. Anvari, C. Aghamohammadi, H. Dashti-Naserabadi, E. Salehi, E. Behjat, M. Qorbani, M. Khazaei Nezhad, M. Zirak, A. Hadjihosseini, J. Peinke, and M. R. Tabar, Phys. Rev. E 87, 062139 (2013).
  58. Y. Tsuji and T. Ishihara, Phys. Rev. E 68, 026309 (2003).
  59. T. Kuusela, Phys. Rev. E 69, 031916 (2004).
  60. J. Prusseit and K. Lehnertz, Phys. Rev. Lett. 98, 138103 (2007).
  61. M. Waechter, F. Riess, T. Schimmel, U. Wendt, and J. Peinke, Euro. Phys. J. B 41, 259 (2004).
  62. Alvin L.-S. Chua, C. A. Haselwandter, C. Baggio, and D. D. Vvedensky, Phys. Rev. E 72, 051103 (2005).
  63. P. Sura, J. Atmos. Sci. 60, 654 (2003).
  64. M. S. Movahed, F. Ghasemi, S. Rahvar, and M. R. R. Tabar, Phys. Rev. E 84, 021103 (2011).
  65. P. Manshour, S. Saberi, M. Sahimi, J. Peinke, A. F. Pacheco, and M. R. Rahimi Tabar, Phys. Rev. Lett. 102, 014101 (2009).
  66. A. H. Shirazi, C. Aghamohammadi, M. Anvari, A. Bahraminasab, M. R. R. Tabar, J. Peinke, M. Sahimi, and M. Marsili, J. Stat. Mech.: Th. Exp. (2013) P02042.
  67. C. Aghamohammadi, M. Ebrahimian, and H. Tahmooresi, Phys. A (Amsterdam, Neth.) 413, 25 (2014).
  68. F. Ghasemi, M. Sahimi, J. Peinke, R. Friedrich, G. R. Jafari, and M. R. R. Tabar, Phys. Rev. E 75, 060102(R) (2007).
  69. J. P. Huang, Phys. Rep. 564, 1 (2015).
  70. M. R. R. Tabar, M. Anvari, G. Lohmann, D. Heinemann, M. Wächter, P. Milan, E. Lorenz, and J. Peinke, Euro. Phys. J. Spec. Top. 223, 2637 (2014).
  71. M. Anvari, G. Lohmann, M. Wächter, P. Milan, E. Lorenz, D. Heinemann, M. R. R. Tabar, and J. Peinke, New J. Phys. 18, 063027 (2016).
  72. S. Kriso, J. Peinke, R. Friedrich, and P. Wagner, Phys. Lett. A 299, 287 (2002).
  73. T. Nagatani, Phys. Rev. E 61, 3534 (2000).
  74. P. M. Riechers, J. R. Mahoney, C. Aghamohammadi, and J. P. Crutchfield, Phys. Rev. A 93, 052317 (2016).
  75. M. Gu, K. Wiesner, E. Rieper, and V. Vedral, Nat. Commun. 3, 762 (2012).
  76. R. Tan, D. R. Terno, J. Thompson, V. Vedral, and M. Gu, Euro. Phys. J. Plus 129, 1 (2014).
  77. C. Aghamohammadi, J. R. Mahoney, and J. P. Crutchfield, arXiv:1609.03650.
  78. J. P. Crutchfield, C. J. Ellison, and J. R. Mahoney, Phys. Rev. Lett. 103, 094101 (2009).
  79. N. Merhav, M. Gutman, and J. Ziv, IEEE Trans. Inf. Theory 35, 1014 (1989).
  80. C. J. Ellison, J. R. Mahoney, and J. P. Crutchfield, J. Stat. Phys. 136, 1005 (2009).

Outline

Information

Phys. Rev. E 95, 032101– Published 1 March, 2017
  • Received 25 October 2016
Article part of CHORUS

©2017 American Physical Society

Sign In to Your Journals Account

Filter

Filter

Article Lookup

Enter a citation