Heterogeneous random walk in one dimension
![]() | This article provides insufficient context for those unfamiliar with the subject.(June 2021) |
![](http://upload.wikimedia.org/wikipedia/commons/thumb/7/75/Random_walk_in1d.jpg/220px-Random_walk_in1d.jpg)
In dynamics, probability, physics, chemistry and related fields, a heterogeneous random walk in one dimension is a random walk in a one dimensional interval with jumping rules that depend on the location of the random walker in the interval.
For example: say that the time is discrete and also the interval. Namely, the random walker jumps every time step either left or right. A possible heterogeneous random walk draws in each time step a random number that determines the local jumping probabilities and then a random number that determines the actual jump direction. Specifically, say that the interval has 9 sites (labeled 1 through 9), and the sites (also termed states) are connected with each other linearly (where the edges sites are connected their adjacent sites and together). In each time step, the jump probabilities (from the actual site) are determined when flipping a coin; for head we set: probability jumping left =1/3, where for tail we set: probability jumping left = 0.55. Then, a random number is drawn from a uniform distribution: when the random number is smaller than probability jumping left, the jump is for the left, otherwise, the jump is for the right. Usually, in such a system, we are interested in the probability of staying in each of the various sites after t jumps, and in the limit of this probability when t is very large, .
Generally, the time in such processes can also vary in a continuous way, and the interval is also either discrete or continuous. Moreover, the interval is either finite or without bounds. In a discrete system, the connections are among adjacent states. The basic dynamics are either Markovian, semi-Markovian, or even not Markovian depending on the model. In discrete systems, heterogeneous random walks in 1d have jump probabilities that depend on the location in the system, and/or different jumping time (JT) probability density functions (PDFs) that depend on the location in the system.[citation needed] ,,,,,,,,,,,,,,,,, General solutions for heterogeneous random walks in 1d obey equations (1)-(5), presented in what follows.
Introduction
[edit]Random walks in applications
[edit]Random walks[1][2][3][4][5][6][7][8][9][10][11] can be used to describe processes in biology,[12][failed verification] chemistry,[13] and physics,[14][15] including chemical kinetics[13] and polymer dynamics.[14][15] In individual molecules, random walks appear when studying individual molecules,[16][17][18][19][20][21][22][23][24][25] individual channels,[26][27] individual biomolecules,[28] individual enzymes,[18][20][21][22][29][30][31][32][33] and quantum dots.[34][35][36] Importantly, PDFs and special correlation functions[clarification needed] can be easily calculated from single molecule measurements but not from ensemble measurements. This unique information can be used for discriminating between distinct random walk models that share some properties[which?],[18][19][20][21][22][23][24][25][26] and this demands a detailed theoretical analysis of random walk models. In this context, utilizing the information content in single molecule data is a matter of ongoing research.[weasel words]
Formulations of random walks
[edit]The actual random walk obeys a stochastic equation of motion, but its probability density function (PDF) obeys a deterministic equation. PDFs of random walks can be formulated in terms of the (discrete in space) master equation[1][12][13] and the generalized master equation[3] or the (continuous in space and time) Fokker Planck equation[37] and its generalizations.[10] Continuous time random walks,[1] renewal theory,[38] and the path representation[3][6][8][9] are also useful formulations of random walks. The network of relationships between the various descriptions provides a powerful tool in the analysis of random walks. Arbitrarily heterogeneous environments make the analysis difficult, especially in high dimensions.[weasel words]
Results for random walks in one dimension
[edit]Simple systems
[edit]Known important results in simple systems include:
- In a symmetric Markovian random walk, the Green's function (also termed the PDF of the walker) for occupying state i is a Gaussian in the position and has a variance that scales like the time. This is correct for a system with discrete time and space, yet also in a system with continuous time and space. These results is for systems without bounds.
- When there is a simple bias in the system (i.e. a constant force is applied on the system in a particular direction), the average distance of the random walker from its starting position is linear with time.
- When trying to reach a distance L from the starting position in a finite interval of length L, the time for reaching this distance is exponential with the length L: . Here, the diffusion is against a linear potential.[citation needed]
Heterogeneous systems
[edit]The solution for the Green's function for a semi-Markovian random walk in an arbitrarily heterogeneous environment in 1D was recently given using the path representation.[6][8][9] (The function is the PDF for occupying state i at time t given that the process started at state j exactly at time 0.) A semi-Markovian random walk in 1D is defined as follows: a random walk whose dynamics are described by the (possibly) state- and direction-dependent JT-PDFs, , for transitions between states i and i ± 1, that generates stochastic trajectories of uncorrelated waiting times that are not-exponential distributed. obeys the normalization conditions (see fig. 1)
The dynamics can also include state- and direction-dependent irreversible trapping JT-PDFs, , with I=i+L. The environment is heterogeneous when depends on i. The above process is also a continuous time random walk and has an equivalent generalized master equation representation for the Green's function..[3][6][8][9]
Explicit expressions for heterogeneous random walks in 1D
[edit]In a completely heterogeneous semi-Markovian random walk in a discrete system of L (> 1) states, the Green's function was found in Laplace space (the Laplace transform of a function is defined with, ). Here, the system is defined through the jumping time (JT) PDFs: connecting state i with state j (the jump is from state i). The solution is based on the path representation of the Green's function, calculated when including all the path probability density functions of all lengths:
(1) |
Here,
and
Also, in Eq. (1),
(2) |
and
(3) |
with
(4) |
and
(5) |
For L = 1, . In this paper, the symbol [L/2], as appearing in the upper bound of the sum in eq. (5) is the floor operation (round towards zero). Finally, the factor in eq. (1) has the same form as in in eqs. (3)-(5), yet it is calculated on a lattice . Lattice is constructed from the original lattice by taking out from it the states i and j and the states between them, and then connecting the obtained two fragments. For cases in which a fragment is a single state, this fragment is excluded; namely, lattice is the longer fragment. When each fragment is a single state, .
Equations (1)-(5) hold for any 1D semi-Markovian random walk in a L-state chain, and form the most general solution in an explicit form for random walks in 1d.
Path representation of heterogeneous random walks
[edit]Clearly, in Eqs. (1)-(5) solves the corresponding continuous time random walk problem and the equivalent generalized master equation. Equations (1)-(5) enable analyzing semi-Markovian random walks in 1D chains from a wide variety of aspects. Inversion to time domain gives the Green’s function, but also moments and correlation functions can be calculated from Eqs. (1)-(5), and then inverted into time domain (for relevant quantities). The closed-form also manifests its utility when numerical inversion of the generalized master equation is unstable. Moreover, using in simple analytical manipulations gives,[6][8][9] (i) the first passage time PDF, (ii)–(iii) the Green’s functions for a random walk with a special WT-PDF for the first event and for a random walk in a circular L-state 1D chain, and (iv) joint PDFs in space and time with many arguments.
Still, the formalism used in this article is the path representation of the Green's function , and this supplies further information on the process. The path representation follows:
(6) |
The expression for in Eq. (6) follows,
(7) |
is the PDF of reaching state i exactly at time t when starting at state j exactly at time 0. This is the path PDF in time that is built from all paths with transitions that connect states j with i. Two different path types contribute to :[8][9] paths made of the same states appearing in different orders and different paths of the same length of transitions. Path PDFs for translation invariant chains are mono-peaked. Path PDF for translation invariant chains mostly contribute to the Green's function in the vicinity of its peak, but this behavior is believed to characterize heterogeneous chains as well.
We also note that the following relation holds, . Using this relation, we focus in what follows on solving .
Path PDFs
[edit]Complementary information on the random walk with that supplied with the Green’s function is contained in path PDFs. This is evident, when constructing approximations for Green’s functions, in which path PDFs are the building blocks in the analysis.[8][9] Also, analytical properties of the Green’s function are clarified only in path PDF analysis. Here, presented is the recursion relation for in the length n of path PDFs for any fixed value of L. The recursion relation is linear in path PDFs with the s in Eq. (5) serving as the n independent coefficients, and is of order [L / 2]:
(8) |
The recursion relation is used for explaining the universal formula for the coefficients in Eq. (1). The solution of the recursion relation is obtained by applying a z transform:
(9) |
Setting in Eq. (9) gives . The Taylor expansion of Eq. (9) gives . The result follows:
(10) |
In Eq. (10) is one for , and otherwise,
(11) |
where
(12) |
The initial number follow:
(13) |
and,
(14) |
References
[edit]- ^ a b c Weiss, George H. (1994), Aspects and Applications of the Random Walk, Random Materials and Processes, North-Holland Publishing Co., Amsterdam, ISBN 0-444-81606-2, MR 1280031.
- ^ Van den Broeck, C.; Bouten, M. (1986). "Decay times in one-dimensional chains". Journal of Statistical Physics. 45 (5–6). Springer Science and Business Media LLC: 1031–1047. Bibcode:1986JSP....45.1031V. doi:10.1007/bf01020587. ISSN 0022-4715. S2CID 122944293.
- ^ a b c d Kenkre, V. M.; Montroll, E. W.; Shlesinger, M. F. (1973). "Generalized master equations for continuous-time random walks". Journal of Statistical Physics. 9 (1). Springer Science and Business Media LLC: 45–50. Bibcode:1973JSP.....9...45K. doi:10.1007/bf01016796. ISSN 0022-4715. S2CID 119993553.
- ^ Montroll, Elliott W.; Weiss, George H. (1965), "Random walks on lattices. II", Journal of Mathematical Physics, 6 (2): 167–181, Bibcode:1965JMP.....6..167M, doi:10.1063/1.1704269, MR 0172344.
- ^ Scher, H.; Lax, M. (1973-05-15). "Stochastic Transport in a Disordered Solid. I. Theory". Physical Review B. 7 (10). American Physical Society (APS): 4491–4502. Bibcode:1973PhRvB...7.4491S. doi:10.1103/physrevb.7.4491. ISSN 0556-2805.
- ^ a b c d e Flomenbom, Ophir; Klafter, Joseph (2005-08-26). "Closed-Form Solutions for Continuous Time Random Walks on Finite Chains". Physical Review Letters. 95 (9): 098105. arXiv:cond-mat/0702561. Bibcode:2005PhRvL..95i8105F. doi:10.1103/physrevlett.95.098105. ISSN 0031-9007. PMID 16197257. S2CID 16316240.
- ^ Flomenbom, O.; Klafter, J.; Silbey, R. J. (2006-10-23). "Comment on "Path Summation Formulation of the Master Equation"". Physical Review Letters. 97 (17): 178901. arXiv:cond-mat/0702503. Bibcode:2006PhRvL..97q8901F. doi:10.1103/physrevlett.97.178901. ISSN 0031-9007. PMID 17155514. S2CID 16461793.
- ^ a b c d e f g Flomenbom, Ophir; Silbey, Robert J. (2007-07-21). "Properties of the generalized master equation: Green's functions and probability density functions in the path representation". The Journal of Chemical Physics. 127 (3). AIP Publishing: 034103. Bibcode:2007JChPh.127c4103F. doi:10.1063/1.2743969. ISSN 0021-9606. PMID 17655427.
- ^ a b c d e f g Flomenbom, O.; Silbey, R. J. (2007-10-01). "Path-probability density functions for semi-Markovian random walks" (PDF). Physical Review E. 76 (4): 041101. arXiv:0706.3211. Bibcode:2007PhRvE..76d1101F. doi:10.1103/physreve.76.041101. ISSN 1539-3755. PMID 17994930. S2CID 14742889. Archived from the original (PDF) on 2012-03-23. Retrieved 2011-05-29.
- ^ a b Metzler, Ralf; Klafter, Joseph (2000). "The random walk's guide to anomalous diffusion: a fractional dynamics approach". Physics Reports. 339 (1). Elsevier BV: 1–77. Bibcode:2000PhR...339....1M. doi:10.1016/s0370-1573(00)00070-3. ISSN 0370-1573.
- ^ Qian, H; Wang, H (2006). "Continuous time random walks in closed and open single-molecule systems with microscopic reversibility". Europhysics Letters (EPL). 76 (1). IOP Publishing: 15–21. Bibcode:2006EL.....76...15Q. doi:10.1209/epl/i2006-10239-9. ISSN 0295-5075. S2CID 250811921.
- ^ a b Goel N. W. and Richter-Dyn N., Stochastic Models in Biology (Academic Press, New York) 1974; ISBN 978-0-12-287460-4.
- ^ a b c Van Kampen N. G., Stochastic Processes in Physics and Chemistry, revised and enlarged edition (North-Holland, Amsterdam) 1992; ISBN 978-0-444-52965-7.
- ^ a b Doi M. and Edwards S. F., The Theory of Polymer Dynamics (Clarendon Press, Oxford) 1986; ISBN 978-0-19-852033-7.
- ^ a b De Gennes P. G., Scaling Concepts in Polymer Physics (Cornell University Press, Ithaca and London) 1979; ISBN 978-0-8014-1203-5.
- ^ Moerner, W. E. (1999-03-12). "Illuminating Single Molecules in Condensed Matter". Science. 283 (5408). American Association for the Advancement of Science (AAAS): 1670–1676. Bibcode:1999Sci...283.1670M. doi:10.1126/science.283.5408.1670. ISSN 0036-8075. PMID 10073924.
- ^ Weiss, S. (1999-03-12). "Fluorescence Spectroscopy of Single Biomolecules". Science. 283 (5408). American Association for the Advancement of Science (AAAS): 1676–1683. Bibcode:1999Sci...283.1676W. doi:10.1126/science.283.5408.1676. ISSN 0036-8075. PMID 10073925.
- ^ a b c Flomenbom, O.; Silbey, R. J. (2006-07-10). "Utilizing the information content in two-state trajectories". Proceedings of the National Academy of Sciences. 103 (29): 10907–10910. arXiv:q-bio/0703013. Bibcode:2006PNAS..10310907F. doi:10.1073/pnas.0604546103. ISSN 0027-8424. PMC 1544147. PMID 16832051.
- ^ a b Bruno, W. J.; Yang, J.; Pearson, J. E. (2005-04-20). "Using independent open-to-closed transitions to simplify aggregated Markov models of ion channel gating kinetics". Proceedings of the National Academy of Sciences USA. 102 (18). Proceedings of the National Academy of Sciences: 6326–6331. Bibcode:2005PNAS..102.6326B. doi:10.1073/pnas.0409110102. ISSN 0027-8424. PMC 1088360. PMID 15843461.
- ^ a b c Flomenbom, Ophir; Klafter, Joseph; Szabo, Attila (2005). "What Can One Learn from Two-State Single-Molecule Trajectories?". Biophysical Journal. 88 (6): 3780–3783. arXiv:q-bio/0502006. Bibcode:2005BpJ....88.3780F. doi:10.1529/biophysj.104.055905. ISSN 0006-3495. PMC 1305612. PMID 15764653.
- ^ a b c Flomenbom, O.; Silbey, R. J. (2008-12-15). "Toolbox for analyzing finite two-state trajectories". Physical Review E. 78 (6): 066105. arXiv:0802.1520. Bibcode:2008PhRvE..78f6105F. doi:10.1103/physreve.78.066105. hdl:1721.1/51348. ISSN 1539-3755. PMID 19256903. S2CID 16196911.
- ^ a b c Flomenbom O, Adv. Chem. Phys. 2011; 146, 367; The full paper
- ^ a b Cao, Jianshu (2000). "Event-averaged measurements of single-molecule kinetics". Chemical Physics Letters. 327 (1–2). Elsevier BV: 38–44. Bibcode:2000CPL...327...38C. doi:10.1016/s0009-2614(00)00809-5. ISSN 0009-2614.
- ^ a b Yang, Shilong; Cao, Jianshu (2002-12-22). "Direct measurements of memory effects in single-molecule kinetics". The Journal of Chemical Physics. 117 (24). AIP Publishing: 10996–11009. Bibcode:2002JChPh.11710996Y. doi:10.1063/1.1521155. ISSN 0021-9606.
- ^ a b Witkoskie, James B.; Cao, Jianshu (2004). "Single molecule kinetics. I. Theoretical analysis of indicators". The Journal of Chemical Physics. 121 (13). AIP Publishing: 6361–6372. Bibcode:2004JChPh.121.6361W. doi:10.1063/1.1785783. ISSN 0021-9606. PMID 15446933.
- ^ a b Colquhoun, D.; Hawkes, A. G. (1982-12-24). "On the Stochastic Properties of Bursts of Single Ion Channel Openings and of Clusters of Bursts". Philosophical Transactions of the Royal Society B: Biological Sciences. 300 (1098). The Royal Society: 1–59. Bibcode:1982RSPTB.300....1C. doi:10.1098/rstb.1982.0156. ISSN 0962-8436. PMID 6131450.
- ^ Meller, Amit (2003-04-22). "Dynamics of polynucleotide transport through nanometre-scale pores". Journal of Physics: Condensed Matter. 15 (17). IOP Publishing: R581–R607. doi:10.1088/0953-8984/15/17/202. ISSN 0953-8984. S2CID 250907343.
- ^ Zhuang, Xiaowei (2005). "Single-Molecule RNA Science". Annual Review of Biophysics and Biomolecular Structure. 34 (1). Annual Reviews: 399–414. doi:10.1146/annurev.biophys.34.040204.144641. ISSN 1056-8700. PMID 15869396.
- ^ Lu, H. P.; Xun, L.; Xie, X. S. (1998-12-04). "Single-Molecule Enzymatic Dynamics". Science. 282 (5395). American Association for the Advancement of Science (AAAS): 1877–1882. Bibcode:1998Sci...282.1877P. doi:10.1126/science.282.5395.1877. PMID 9836635.
- ^ Edman, Lars; Földes-Papp, Zeno; Wennmalm, Stefan; Rigler, Rudolf (1999). "The fluctuating enzyme: a single molecule approach". Chemical Physics. 247 (1). Elsevier BV: 11–22. Bibcode:1999CP....247...11E. doi:10.1016/s0301-0104(99)00098-1. ISSN 0301-0104.
- ^ Flomenbom, O.; Velonia, K.; Loos, D.; Masuo, S.; Cotlet, M.; et al. (2005-02-04). "Stretched exponential decay and correlations in the catalytic activity of fluctuating single lipase molecules". Proceedings of the National Academy of Sciences. 102 (7): 2368–2372. Bibcode:2005PNAS..102.2368F. doi:10.1073/pnas.0409039102. ISSN 0027-8424. PMC 548972. PMID 15695587.
- ^ Flomenbom, Ophir; Hofkens, Johan; Velonia, Kelly; de Schryver, Frans C.; Rowan, Alan E.; et al. (2006). "Correctly validating results from single molecule data: The case of stretched exponential decay in the catalytic activity of single lipase B molecules". Chemical Physics Letters. 432 (1–3): 371–374. arXiv:q-bio/0702045. Bibcode:2006CPL...432..371F. doi:10.1016/j.cplett.2006.10.060. ISSN 0009-2614. S2CID 18680839.
- ^ Velonia, Kelly; Flomenbom, Ophir; Loos, Davey; Masuo, Sadahiro; Cotlet, Mircea; et al. (2005-01-14). "Single-Enzyme Kinetics of CALB-Catalyzed Hydrolysis". Angewandte Chemie International Edition. 44 (4). Wiley: 560–564. doi:10.1002/anie.200460625. ISSN 1433-7851. PMID 15619259.
- ^ Chung, Inhee; Bawendi, Moungi G. (2004-10-11). "Relationship between single quantum-dot intermittency and fluorescence intensity decays from collections of dots". Physical Review B. 70 (16). American Physical Society (APS): 165304. Bibcode:2004PhRvB..70p5304C. doi:10.1103/physrevb.70.165304. ISSN 1098-0121.
- ^ Barkai, Eli; Jung, YounJoon; Silbey, Robert (2004). "THEORY OF SINGLE-MOLECULE SPECTROSCOPY: Beyond the Ensemble Average". Annual Review of Physical Chemistry. 55 (1). Annual Reviews: 457–507. Bibcode:2004ARPC...55..457B. doi:10.1146/annurev.physchem.55.111803.143246. ISSN 0066-426X. PMID 15117260.
- ^ Brown, Frank L. H. (2006). "Generating Function Methods in Single-Molecule Spectroscopy". Accounts of Chemical Research. 39 (6). American Chemical Society (ACS): 363–373. doi:10.1021/ar050028l. ISSN 0001-4842. PMID 16784214.
- ^ Risken H., The Fokker-Planck Equation (Springer, Berlin) 1984; ISBN 978-3-642-08409-6.
- ^ Cox D. R., Renewal Theory (Methuen, London) 1962.
Other Bibliography
[edit]- Zwanzig, R. (2001). Nonequilibrium Statistical Mechanics. New York: OXFORD, University Press. ISBN 0-19-514018-4.
- Schuss, Zeev (2010). Theory and Applications of Stochastic Processes: An Analytical Approach (Applied Mathematical Sciences). New York Dordrecht Heilderberg London: Springer. ISBN 978-1-4419-1605-1.
- Redner, S. (2001). A Guide to First-Passage Process. Cambridge, UK: Cambridge University Press. ISBN 0-521-65248-0.