Hostname: page-component-cd9895bd7-p9bg8 Total loading time: 0 Render date: 2024-12-23T05:23:32.940Z Has data issue: false hasContentIssue false
  • English
  • Français

On Monte Carlo algebra

Published online by Cambridge University Press:  14 July 2016

Richard Gordon
Richard Gordon*
Affiliation:
University of Massachusetts and Columbia University
Get access Rights & Permissions [Opens in a new window]

Abstract

A Monte Carlo method is proposed and demonstrated for obtaining an approximate algebraic solution to linear equations with algebraic coefficients arising from first order master equations at steady state. Exact solutions are hypothetically obtainable from the spanning trees of an associated graph, each tree contributing an algebraic term. The number of trees can be enormous. However, because of a high degeneracy, many trees yield the same algebraic term. Thus an approximate algebraic solution may be obtained by taking a Monte Carlo sampling of the trees, which yields an estimate of the frequency of each algebraic term. The accuracy of such solutions is discussed and algorithms are given for picking spanning trees of a graph with uniform probability. The argument is developed in terms of a lattice model for membrane transport, but should be generally applicable to problems in unimolecular kinetics and network analysis. The solution of partition functions and multivariable problems by analogous methods is discussed.

Type
Research Papers
Information
Journal of Applied Probability , Volume 7 , Issue 2 , August 1970 , pp. 373 - 387
Copyright
Copyright © Applied Probability Trust 1970 

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

Ashby, W. R. (1968) Some consequences of Bremermann's limit for information-processing systems. In Cybernetic Problems in Bionics. Eds. Oestreicher, H. L. and Moore, D. L., Gordon and Breach Science Publishers, Inc., New York. 69–76.Google Scholar
Berge, E. (1962) The Theory of Graphs and Its Applications John Wiley. New York. 159.Google Scholar
Bremermann, H. J. (1966) Quantum noise and information. Proc. Fifth Berkeley Symp. on Math. Statist. and Prob. 15–20.Google Scholar
Brown, W. S. (1963) The ALPAK system for non-numerical algebra on a digital computer I. Polynomials in several variables and truncated power series with polynomial coefficients. Bell Syst. Tech. J. 42, 2081–2119.CrossRefGoogle Scholar
Brown, W. S., Hyde, J. P. and Tague, B. A. (1964) The ALPAK system for non-numerical algebra on a digital computer II. Rational functions of several variables and truncated power series with rational-function coefficients. Bell Syst. Tech. J. 43, 785–804.CrossRefGoogle Scholar
Campbell, J. A. (1966) Mechanization of Algebraic Procedures in Quantum Field Theory. Thesis, University of Oxford, England.Google Scholar
Chen, W. K. (1967) On directed graph solutions of linear algebraic equations. SIAM Rev. 9, 692–707.CrossRefGoogle Scholar
Feller, W. (1957) An Introduction to Probability Theory and Its Applications. Vol. I, 2nd Ed. John Wiley. New York. 36.Google Scholar
Goldstein, A. J. (1967) Recursive techniques in problem solving AFIPS Conf. Proc. (Spring Joint Computer Conf.) 30, 325–329.Google Scholar
Gordon, R. (1967) Steady State Properties of Ising Lattice Membranes. Part 2 of Ph.D. Thesis, Department of Chemistry, University of Oregon.Google Scholar
Gordon, R. (1968) Steady state properties of Ising lattice membranes. J. Chem. Phys. 49, 570–580.CrossRefGoogle Scholar
Gross, A. R. (1968) Comparison of Topological Methods for Analysis of Linear Networks. M. S. thesis, The Moore School of Electrical Engineering, University of Pennsylvania.Google Scholar
Hammersley, J. M. (1960) Monte Carlo methods for solving multivariable problems. Ann. N. Y. Acad. Sci. 86, 844–874.CrossRefGoogle Scholar
Hammersley, J. M. (1966) Existence theorems and Monte Carlo methods for the monomerdimer problem. In Research Papers in Statistics. Ed. David, F. N. John Wiley, London. 125–146.Google Scholar
Hammersley, J. M. and Handscomb, D. C. (1965) Monte Carlo Methods. Methuen, London.Google Scholar
Hill, T. L. (1966) Studies in irreversible thermodynamics IV. Diagrammatic representation of steady state fluxes for unimolecular systems. J. Theoret. Biol. 10, 442–459.CrossRefGoogle ScholarPubMed
Hill, T. L. (1968) Thermodynamics for Chemists and Biologists. Addison-Wesley, Reading, Mass. Section 7.5.Google Scholar
Hill, T. L., and Kedem, O. (1966) Studies in irreversible thermodynamics III. Models for steady state and active transport across membranes. J. Theoret. Biol. 10, 399–441.CrossRefGoogle Scholar
Howard, J. C. (1967) Computer formulation of the equations of motion using tensor notation. Comm. ACM. 10, 543–548.CrossRefGoogle Scholar
Howard, J. C. and Tashjian, H. (1968) An algorithm for deriving the equations of mathematical physics by symbolic manipulation. Comm. ACM. 11, 814–818, 826.CrossRefGoogle Scholar
Hyde, J. P. (1964) The ALPAK system for non-numerical algebra on a digital computer III. Systems of linear equations and a class of side relations. Bell Syst. Tech. J. 43, 1547–1562.CrossRefGoogle Scholar
Lapidus, A. and Goldstein, M. (1965) Some experiments in algebraic manipulation by computer. Comm. ACM. 8, 501–508.CrossRefGoogle Scholar
Mazur, J. and Mccrackin, F. L. (1968) Monte Carlo studies of configurational and thermodynamic properties of selfinteracting linear polymer chains. J. Chem. Phys. 49, 648–665.CrossRefGoogle Scholar
Mcilroy, M. D. (1969) Generator of spanning trees. Comm. ACM., 12, 511.CrossRefGoogle Scholar
Mcquarrie, D. A. (1967) Stochastic approach to chemical kinetics. J. Appl. Prob. 4, 413–478.CrossRefGoogle Scholar
Rhoads, D. G. and Pring, M. (1968) Simulation and analysis by digital computer of biochemical systems in terms of kinetic models IV. Automatic derivation of enzymic rate laws. J. Theoret. Biol. 20, 297–313.CrossRefGoogle ScholarPubMed
Sammet, J. E. (1969) Programming Languages: History and Fundamentals. Prentice-Hall New Jersey, Chapter 7.Google Scholar
Slagle, J. R. (1963) A heuristic program that solves symbolic integration problems in freshman calculus. J. Assoc. Comput. Mach. 10, 507–520.CrossRefGoogle Scholar
Tobey, R. G. (1966) Eliminating monotonous mathematics with Formac. Comm. ACM. 9, 742–751.CrossRefGoogle Scholar
Tobey, R. G., Baker, J., Crews, R., Marks, P. and Victor, K. (1967) PL/I-Formac interpreter user's reference manual. IBM-Boston Programming Center, Cambridge, Mass. Google Scholar
Wall, F. T. and Mazur, J. (1961) Statistical thermodynamics of coiling-type polymers. Ann. N.Y. Acad. Sci. 89, 608–619.CrossRefGoogle Scholar