{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T01:54:35Z","timestamp":1760147675940,"version":"build-2065373602"},"reference-count":37,"publisher":"MDPI AG","issue":"3","license":[{"start":{"date-parts":[[2023,2,21]],"date-time":"2023-02-21T00:00:00Z","timestamp":1676937600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"name":"IMI-EU HARMONY","award":["#116026","#945406","#101017549","#26216"],"award-info":[{"award-number":["#116026","#945406","#101017549","#26216"]}]},{"name":"EU Horizon 2020 programme: GenoMed4All","award":["#116026","#945406","#101017549","#26216"],"award-info":[{"award-number":["#116026","#945406","#101017549","#26216"]}]},{"name":"AIRC Foundation (Associazione Italiana per la Ricerca contro il Cancro), Milan, Italy","award":["#116026","#945406","#101017549","#26216"],"award-info":[{"award-number":["#116026","#945406","#101017549","#26216"]}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Entropy"],"abstract":"<jats:p>We introduce the Random Walk Approximation (RWA), a new method to approximate the stationary solution of master equations describing stochastic processes taking place on graphs. Our approximation can be used for all processes governed by non-linear master equations without long-range interactions and with a conserved number of entities, which are typical in biological systems, such as gene regulatory or chemical reaction networks, where no exact solution exists. For linear systems, the RWA becomes the exact result obtained from the maximum entropy principle. The RWA allows having a simple analytical, even though approximated, form of the solution, which is global and easier to deal with than the standard System Size Expansion (SSE). Here, we give some theoretically sufficient conditions for the validity of the RWA and estimate the order of error calculated by the approximation with respect to the number of particles. We compare RWA with SSE for two examples, a toy model and the more realistic dual phosphorylation cycle, governed by the same underlying process. Both approximations are compared with the exact integration of the master equation, showing for the RWA good performances of the same order or better than the SSE, even in regions where sufficient conditions are not met.<\/jats:p>","DOI":"10.3390\/e25030394","type":"journal-article","created":{"date-parts":[[2023,2,22]],"date-time":"2023-02-22T02:57:38Z","timestamp":1677034658000},"page":"394","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Random Walk Approximation for Stochastic Processes on Graphs"],"prefix":"10.3390","volume":"25","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-5264-5156","authenticated-orcid":false,"given":"Stefano","family":"Polizzi","sequence":"first","affiliation":[{"name":"Department of Physics and Astronomy A. Righi, University of Bologna, 40127 Bologna, Italy"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-8232-9621","authenticated-orcid":false,"given":"Tommaso","family":"Marzi","sequence":"additional","affiliation":[{"name":"Department of Physics and Astronomy A. Righi, University of Bologna, 40127 Bologna, Italy"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Tommaso","family":"Matteuzzi","sequence":"additional","affiliation":[{"name":"Department of Physics and Astronomy, University of Florence, 50019 Sesto Fiorentino, Italy"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-4892-925X","authenticated-orcid":false,"given":"Gastone","family":"Castellani","sequence":"additional","affiliation":[{"name":"Department of Experimental, Diagnostic and Specialty Medicine, University of Bologna, 40138 Bologna, Italy"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-9633-0017","authenticated-orcid":false,"given":"Armando","family":"Bazzani","sequence":"additional","affiliation":[{"name":"Department of Physics and Astronomy A. Righi, University of Bologna, 40127 Bologna, Italy"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"1968","published-online":{"date-parts":[[2023,2,21]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","first-page":"987","DOI":"10.1002\/bies.950171112","article-title":"Does replication-induced transcription regulate synthesis of the myriad low copy number proteins of Escherichia coli?","volume":"17","author":"Guptasarma","year":"1995","journal-title":"Bioessays"},{"key":"ref_2","doi-asserted-by":"crossref","first-page":"69","DOI":"10.1038\/ng869","article-title":"Regulation of noise in the expression of a single gene","volume":"31","author":"Ozbudak","year":"2002","journal-title":"Nat. Genet."},{"key":"ref_3","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1017\/S0033583501003663","article-title":"Noise in a minimal regulatory network: Plasmid copy number control","volume":"34","author":"Paulsson","year":"2001","journal-title":"Q. Rev. Biophys."},{"key":"ref_4","doi-asserted-by":"crossref","first-page":"183","DOI":"10.1126\/science.1216379","article-title":"Using gene expression noise to understand gene regulation","volume":"336","author":"Munsky","year":"2012","journal-title":"Science"},{"key":"ref_5","doi-asserted-by":"crossref","first-page":"170","DOI":"10.1038\/msb.2008.11","article-title":"Selection to minimise noise in living systems and its implications for the evolution of gene expression","volume":"4","author":"Lehner","year":"2008","journal-title":"Mol. Syst. Biol."},{"key":"ref_6","doi-asserted-by":"crossref","first-page":"106309","DOI":"10.1063\/1.5039668","article-title":"Harnessing stochasticity: How do organisms make choices?","volume":"28","author":"Noble","year":"2018","journal-title":"Chaos Interdiscip. J. Nonlinear Sci."},{"key":"ref_7","unstructured":"Horsthemke, W., and Lefever, R. (1984). Noise-Induced Transitions: Theory and Applications in Physics, Chemistry, and Biology, Springer."},{"key":"ref_8","unstructured":"Kampen, N.V. (2007). Stochastic Processes in Physics and Chemistry, North Holland."},{"key":"ref_9","doi-asserted-by":"crossref","first-page":"06B611","DOI":"10.1063\/1.4725180","article-title":"Bistability in the chemical master equation for dual phosphorylation cycles","volume":"136","author":"Bazzani","year":"2012","journal-title":"J. Chem. Phys."},{"key":"ref_10","doi-asserted-by":"crossref","first-page":"460","DOI":"10.1038\/nature02089","article-title":"A positive-feedback-based bistable \u2018memory module\u2019that governs a cell fate decision","volume":"426","author":"Xiong","year":"2003","journal-title":"Nature"},{"key":"ref_11","doi-asserted-by":"crossref","first-page":"149","DOI":"10.1002\/bies.201100031","article-title":"The molecular and mathematical basis of Waddington\u2019s epigenetic landscape: A framework for post-Darwinian biology?","volume":"34","author":"Huang","year":"2012","journal-title":"Bioessays"},{"key":"ref_12","doi-asserted-by":"crossref","first-page":"633","DOI":"10.1016\/j.combustflame.2010.10.002","article-title":"An improved H2\/O2 mechanism based on recent shock tube\/laser absorption measurements","volume":"158","author":"Hong","year":"2011","journal-title":"Combust. Flame"},{"key":"ref_13","doi-asserted-by":"crossref","first-page":"10376","DOI":"10.1073\/pnas.152007599","article-title":"Concentration fluctuations in a mesoscopic oscillating chemical reaction system","volume":"99","author":"Qian","year":"2002","journal-title":"Proc. Natl. Acad. Sci. USA"},{"key":"ref_14","doi-asserted-by":"crossref","first-page":"065102","DOI":"10.1063\/1.4891515","article-title":"The role of non-equilibrium fluxes in the relaxation processes of the linear chemical master equation","volume":"141","author":"Bazzani","year":"2014","journal-title":"J. Chem. Phys."},{"key":"ref_15","doi-asserted-by":"crossref","first-page":"339","DOI":"10.1016\/S0952-7915(00)00224-7","article-title":"MAP-kinase signaling pathways in T cells","volume":"13","year":"2001","journal-title":"Curr. Opin. Immunol."},{"key":"ref_16","doi-asserted-by":"crossref","first-page":"14091","DOI":"10.1073\/pnas.0905988106","article-title":"Toward a microscopic model of bidirectional synaptic plasticity","volume":"106","author":"Castellani","year":"2009","journal-title":"Proc. Natl. Acad. Sci. USA"},{"key":"ref_17","doi-asserted-by":"crossref","first-page":"345","DOI":"10.1016\/S0167-9473(98)00062-0","article-title":"A numerical study of large sparse matrix exponentials arising in Markov chains","volume":"29","author":"Sidje","year":"1999","journal-title":"Comput. Stat. Data Anal."},{"key":"ref_18","doi-asserted-by":"crossref","first-page":"2340","DOI":"10.1021\/j100540a008","article-title":"Exact stochastic simulation of coupled chemical reactions","volume":"81","author":"Gillespie","year":"1977","journal-title":"J. Phys. Chem."},{"key":"ref_19","doi-asserted-by":"crossref","unstructured":"Jenkinson, G., and Goutsias, J. (2012). Numerical integration of the master equation in some models of stochastic epidemiology. PLoS ONE, 7.","DOI":"10.1371\/journal.pone.0036160"},{"key":"ref_20","doi-asserted-by":"crossref","first-page":"2475","DOI":"10.1101\/gr.1196503","article-title":"Fast Evaluation of Fluctuations in Biochemical Networks With the Linear Noise Approximation","volume":"13","author":"Elf","year":"2003","journal-title":"Genome Res."},{"key":"ref_21","doi-asserted-by":"crossref","first-page":"37","DOI":"10.1007\/s00791-006-0045-6","article-title":"Fokker\u2013Planck approximation of the master equation in molecular biology","volume":"12","author":"Elf","year":"2009","journal-title":"Comput. Vis. Sci."},{"key":"ref_22","doi-asserted-by":"crossref","first-page":"203","DOI":"10.1080\/03081080500054810","article-title":"Algebraic connectivity of directed graphs","volume":"53","author":"Wu","year":"2005","journal-title":"Linear Multilinear Algebra"},{"key":"ref_23","doi-asserted-by":"crossref","first-page":"571","DOI":"10.1103\/RevModPhys.48.571","article-title":"Network theory of microscopic and macroscopic behavior of master equation systems","volume":"48","author":"Schnakenberg","year":"1976","journal-title":"Rev. Mod. Phys."},{"key":"ref_24","doi-asserted-by":"crossref","first-page":"135","DOI":"10.1090\/S0025-5718-1986-0815836-3","article-title":"Some practical runge-kutta formulas","volume":"46","author":"Shampine","year":"1986","journal-title":"Math. Comput."},{"key":"ref_25","doi-asserted-by":"crossref","first-page":"19","DOI":"10.1016\/0771-050X(80)90013-3","article-title":"A family of embedded Runge-Kutta formulae","volume":"6","author":"Dormand","year":"1980","journal-title":"J. Comput. Appl. Math."},{"key":"ref_26","doi-asserted-by":"crossref","first-page":"410","DOI":"10.1016\/j.cam.2015.10.008","article-title":"Block-tridiagonal state-space realization of Chemical Master Equations: A tool to compute explicit solutions","volume":"296","author":"Borri","year":"2016","journal-title":"J. Comput. Appl. Math."},{"key":"ref_27","unstructured":"Marzi, T., and Polizzi, S. (2023, February 17). Random Walk Approximation and System Size Expansion for the Dual Phospho\/Dephosphorylation Cycles. Available online: https:\/\/github.com\/tommasomarzi\/random-walk-approximation."},{"key":"ref_28","doi-asserted-by":"crossref","first-page":"1538","DOI":"10.1021\/ed2001329","article-title":"The approach to equilibrium: Detailed balance and the master equation","volume":"88","author":"Alexander","year":"2011","journal-title":"J. Chem. Educ."},{"key":"ref_29","doi-asserted-by":"crossref","first-page":"3915","DOI":"10.1111\/j.1742-4658.2006.05394.x","article-title":"Bistability from double phosphorylation in signal transduction: Kinetic and structural requirements","volume":"273","author":"Ortega","year":"2006","journal-title":"FEBS J."},{"key":"ref_30","doi-asserted-by":"crossref","first-page":"261","DOI":"10.2140\/memocs.2020.8.261","article-title":"On a stochastic approach to model the double phosphorylation\/dephosphorylation cycle","volume":"8","author":"Bersani","year":"2020","journal-title":"Math. Mech. Complex Syst."},{"key":"ref_31","doi-asserted-by":"crossref","first-page":"599","DOI":"10.1109\/TPAMI.1985.4767707","article-title":"Entropy and distance of random graphs with application to structural pattern recognition","volume":"PAMI-7","author":"Wong","year":"1985","journal-title":"IEEE Trans. Pattern Anal. Mach. Intell."},{"key":"ref_32","unstructured":"Fuglede, B., and Topsoe, F. (July, January 27). Jensen-Shannon divergence and Hilbert space embedding. Proceedings of the International Symposium on Information Theory, Chicago, IL, USA."},{"key":"ref_33","doi-asserted-by":"crossref","first-page":"1373","DOI":"10.1162\/089976603321780317","article-title":"Laplacian eigenmaps for dimensionality reduction and data representation","volume":"15","author":"Belkin","year":"2003","journal-title":"Neural Comput."},{"key":"ref_34","unstructured":"Bruderer, M. (2022). Clusters determine local fluctuations of random walks on graphs. arXiv."},{"key":"ref_35","doi-asserted-by":"crossref","unstructured":"Pan, V.Y., and Chen, Z.Q. (1999, January 1\u20134). The complexity of the matrix eigenproblem. Proceedings of the Thirty-First Annual ACM Symposium on Theory of Computing, Atlanta, GA, USA.","DOI":"10.1145\/301250.301389"},{"key":"ref_36","unstructured":"Hairer, E., Norsett, S., and Wanner, G. (1993). Solving Ordinary Differential Equations I: Nonstiff Problems, Springer."},{"key":"ref_37","unstructured":"Garcia, A.L. (2000). Numerical Methods for Physics, Prentice-Hall, Inc.. [2nd ed.]."}],"container-title":["Entropy"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1099-4300\/25\/3\/394\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,10]],"date-time":"2025-10-10T18:38:14Z","timestamp":1760121494000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1099-4300\/25\/3\/394"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,2,21]]},"references-count":37,"journal-issue":{"issue":"3","published-online":{"date-parts":[[2023,3]]}},"alternative-id":["e25030394"],"URL":"https:\/\/doi.org\/10.3390\/e25030394","relation":{},"ISSN":["1099-4300"],"issn-type":[{"type":"electronic","value":"1099-4300"}],"subject":[],"published":{"date-parts":[[2023,2,21]]}}}