Abstract
We address the generic problem of random search for a point-like target on a line. Using the measures of search reliability and efficiency to quantify the random search quality, we compare Brownian search with Lévy search based on long-tailed jump length distributions. We then compare these results with a search process combined of two different long-tailed jump length distributions. Moreover, we study the case of multiple targets located by a Lévy searcher.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
G. Kolesov, Z. Wunderlich, O.N. Laikova, M.S. Gelfand, L.A. Mirny, Proc. Natl. Acad. Sci. USA 104, 13948 (2007)
M. Bauer, R. Metzler, PLoS One 8, e53956 (2013)
H.C. Berg, E.M. Purcell, Biophys. J. 20, 193 (1977)
W. Bialek, S. Setayeshgar, Proc. Natl. Acad. Sci. USA 102, 10040 (2005)
K. Wang, W.-J. Rappel, R. Kerr, H. Levine, Phys. Rev. E. 75, 061905 (2007)
A. Godec, R. Metzler, Phys. Rev. E 92, 010701(R) (2015)
T. Harris, E. Banigan, D. Christian, C. Konradt, E.T. Wojno, K. Norose, E. Wilson, B. John, W. Weninger, A. Luster, Nature 486, 545 (2012)
G. Ramos-Fernández, J.L. Mateos, O. Miramontes, G. Cocho, H. Larralde, B. Ayala-Orozco, Behav. Ecol. Sociobiol. 55, 223 (2003)
M. Becker, F. Blatt, H. Szczerbicka, Multiagent System Technologies, Lecture Notes in Computer Science, (Springer Berlin Heidelberg, 2013), Vol. 8076, p. 1928
M. Shlesinger, Nature 443, 281 (2006)
I. Pavlyukevich, J. Comput. Phys. 226, 1830 (2007)
L. Stone, Theory of Optimal Search (Informs, Hanover, MD, 2007), 2nd edn.
S. Alpern, S. Gal, The theory of search games and rendezvous, International Series in Operations Research and Managment Science (Kluwer Academic Publishers, Boston, 2003)
R. Nathan, W.M. Getz, E. Revilla, M. Holyoak, R. Kadmon, D. Saltz, P.E. Smouse, Proc. Natl. Acad. Sci. 105, 19052 (2008)
V. Méndez, D. Campos, F. Bartumeus, Stochastic Foundations in Movement Ecology, Springer Series in Synergetics (Springer, Berlin, 2014)
G. Viswanathan, V. Afanasyev, S. Buldyrev, E. Murphy, P. Prince, H. Stanley, Nature 381, 413 (1996)
G. Viswanathan, S. Buldyrev, S. Havlin, M. da Luz, E. Raposo, H. Stanley, Nature 401, 911 (1999)
A. Edwards, R. Phillips, N. Watkins, M. Freeman, E. Murphy, V. Afanasyev, S. Buldyrev, M. da Luz, E. Raposo, H. Stanley et al., Nature 449, 1044 (2007)
D. Sims, E. Southall, N. Humphries, G.C. Hays, C.J.A. Bradshaw, J.W. Pitchford, A. James, M.Z. Ahmed, A.S. Brierley, M.A. Hindell et al., Nature 451, 1098 (2008)
N. Humphries, N. Queiroz, J. Dyer, N. Pade, M. Musy, K. Schaefer, D. Fuller, J. Brunnschweiler, T. Doyle, J. Houghton et al., Nature 465, 1066 (2010)
F. Lenz, T.C. Ings, L. Chittka, A.V. Chechkin, R. Klages, Phys. Rev. Lett. 108, 098103 (2012)
M.F. Shlesinger, J. Klafter, On Growth and Form, edited by H.E. Stanley, N. Ostrowsky (Martinus Nijhoff, Dordrecht, 1986)
M. Shlesinger, G. Zaslavsky, J. Klafter, Nature 363, 31 (1993)
G. Viswanathan, M. da Luz, E. Raposo, H. Stanley, The Physics of Foraging (Cambridge University Press, Cambridge, 2011)
K. Pearson, Biometric Ser. 3, 54 (1906)
W.J. OBrien, H.I. Browman, B.I. Evans, Am. Sci. 78, 152 (1990)
D.L. Kramer, R.L. MacLaughlin, Am. Zool. 41, 137 (2001)
O. Bénichou, C. Loverdo, M. Moreau, R. Voituriez, Rev. Mod. Phys. 83, 81 (2011)
O. Bénichou, M. Coppey, M. Moreau, P.H. Suet, R. Voiturierz, Phys. Rev. Lett. 94, 198101 (2005)
C. Loverdo, O. Bénichou, M. Moreau, R. Voiturierz, Nat. Phys. 4, 134 (2008)
A. Reynolds, Physica A 388, 561 (2009)
G. Oshanin, H.S. Wio, K. Lindenberg, S.F. Burlatsky, J. Phys.: Condens. Matter 19, 065142 (2007)
G. Oshanin, K. Lindenberg, H.S. Wio, S. Burlatsky, J. Phys. A: Math. Theor. 42, 434008 (2009)
M.A. Lomholt, T. Ambjörnsson, R. Metzler, Phys. Rev. Lett. 85, 260603 (2005)
M.A. Lomholt, T. Koren, R. Metzler, J. Klafter, Proc. Natl. Acad. Sci. USA 105, 11055 (2008)
O. Bénichou, C. Loverdo, M. Moreau, R. Voituriez, Phys. Rev. E 74, 020102 (2006)
O. Bénichou, C. Loverdo, M. Moreau, R. Voituriez, J. Phys.: Condens. Matter 19, 065141 (2007)
V.V. Palyulin, A.V. Chechkin, R. Metzler, Proc. Natl. Acad. Sci. USA 111, 2931 (2014)
V.V. Palyulin, A.V. Chechkin, R. Metzler, J. Stat. Mech. P11031 (2014)
S. Redner, A Guide to First-Passage Processes (Cambridge University Press, Cambridge, 2001)
R. Metzler, G. Oshanin, S. Redner, First-Passage Phenomena, Their Applications (World Scientific, 2014)
A.V. Chechkin, R. Metzler, V. Yu. Gonchar, J. Klafter, L.V. Tanatarov, J. Phys. A: Math. Gen. 36, L537 (2003)
S. Condamin, O. Bénichou, V. Tejedor, R. Voituriez, J. Klafter, Nature 450, 77 (2007)
O. Bénichou, C. Chevalier, J. Klafter, B. Meyer, R. Voituriez, Nat. Chem. 2, 472 (2010)
C. Mejia-Monasterio, G. Oshanin, G. Schehr, J. Stat. Phys. P06022 (2011)
T. Mattos, C. Mejia-Monasterio, R. Metzler, G. Oshanin, Phys. Rev. E 86, 031143 (2012)
A. Godec, R. Metzler, Sci. Rep. 6, 20349 (2016)
A. Godec, R. Metzler, Phys. Rev. X 6, 041037 (2016)
D. Aldous, J. Theor. Prob. 2, 87 (1989)
M. Chupeau, O. Bénichou, R. Voituriez, Nat. Phys. 11, 844 (2015)
O. Bénichou, M. Coppey, M. Moreau, R. Voituriez, Europhys. Lett. 75, 349 (2006)
H.J. de Knegt, G.M. Hengeveld, F. van Langevelde, W.F. de Boer, K.P. Kirkman, Behav. Ecol. 18, 1065 (2007)
S. Focardi, P. Montanaro, E. Pecchioli, PLoS One 4, e6587 (2009)
F. Bartumeus, F. Peters, S. Pueyo, C. Marrasé, J. Catalan, Proc. Natl. Acad. Sci. 100, 12771 (2003)
D. Brockmann, Phys. World 2, 31 (2010)
D. Brockmann, L. Hufnagel, T. Geisel, Nature 439, 462 (2006)
A.M. Edwards et al., Nature 449, 1044 (2007)
N.E. Humphries, H. Weimerskirch, N. Queiroza, E.J. Southalla, D.W. Sims, Proc. Natl. Acad. Sci. USA 109, 7169 (2012)
P. Lévy, Théorie de L’addition des Variables Aléatories (Gauthier-Villars, Paris, 1937)
B. Gnedenko, A. Kolmogorov, Limit distributions for sums of independent random variables (Addison-Wesley, 1954)
J.-P. Bouchaud, A. Georges, Phys. Rev. 195, 127 (2000)
B.R. Hughes, Random Walks, Random Environments, Random Walks (Clarendon, Oxford, 1995), Vol. 1
R. Klages, G. Radons, I. Sokolov, eds., Anomalous transport (Wiley-VCH, Berlin, 2008)
R. Metzler, J. Klafter, Phys. Rep. 339, 1 (2000)
M.F. Shlesinger, J. Klafter, Y.M. Wong, J. Stat. Phys. 27, 499 (1982)
V. Zaburdaev, S. Denisov, J. Klafter, Rev. Mod. Phys. 87, 483 (2015)
J. Klafter, I. Sokolov, First Steps in Random Walks: From Tools to Applications (Oxford University Press, Oxford, 2011)
M. Buchanan, Nature 453, 714 (2008)
M. de Jager, F.J. Weissing, P.M.J. Herman, B.A. Nolet, J. van de Koppel, Science 332, 1551 (2011)
A. James, M.J. Plank, A.M. Edwards, J. Roy. Soc. Interf. 8, 1233 (2011)
G. Pyke, Meth. Ecol. Evol. 6, 1 (2015)
A. Reynolds, Phys. Life Rev. 14, 59 (2015)
M. Smoluchowski, Physikal. Zeitschr. 17, 557 (1916)
A.D. Riggs, S. Bourgeois, M. Cohn, J. Mol. Biol. 53, 401 (1970)
G. Adam, M. Delbrück, in Structural Chemistry, Molecular Biology, edited by A. Rich, N. Davidson (W.H. Freeman, San Francisco, CA, 1968)
P.H. Richter, M. Eigen, Biophys. Chem. 2, 255 (1974)
O.G. Berg, C. Blomberg, Biophys. Chem. 7, 33 (1977)
O.G. Berg, R.B. Winter, P.H. von Hippel, Biochemistry 20, 6929 (1981)
P.H. von Hippel, Otto G. Berg, J. Biol. Chem. 264, 675 (1989)
M. Sheinman, O. Bénichou, Y. Kafri, R. Voituriez, Rep. Prog. Phys. 75, 026601 (2012)
H. Kabata, O. Kurosawa, I. Arai, M. Washizu, S.A. Margarson, R.E. Glass, N. Shimamoto, Science 262, 1561 (1993)
Y.M. Wang, R.H. Austin, E.C. Cox, Phys. Rev. Lett. 97, 048302 (2006)
I.M. Sokolov, R. Metzler, K. Pant, M.C. Williams, Biophys. J. 89, 895 (2005)
Y. Harada, T. Funatsu, K. Murakami, Y. Nonoyama, A. Ishihama, T. Yanagida, Biophys. J. 76, 709 (1999)
C. Bustamante, M. Gutholdi, X. Zhu, G. Yang, J. Biol. Chem. 274, 16665 (1999)
B. van den Broek, M.A. Lomholt, S.-M.J. Kalisch, R. Metzler, G.J.L. Wuite, Proc. Natl. Acad. Sci. USA 105, 15738 (2008)
S.E. Halford, J.F. Marko, Nucleic Acids Res. 32, 3040 (2004)
M. Coppey, O. Bénichou, R. Voituriez, M. Moreau, Biophys. J. 87, 1640 (2004)
S.G. Erskine, G.S. Baldwin, S.E. Halford, Biochemistry 36, 7567 (1997)
O. Givaty, Y. Levy, J. Mol. Biol. 385, 1087 (2009)
K.V. Klenin, H. Merlitz, J. Langowski, C.-X. Wu, Phys. Rev. Lett. 96, 018104 (2006)
M. Slutsky, L.A. Mirny, Biophys. J. 87, 4021 (2004)
M.A. Lomholt, B. van den Broek, S.-M.J. Kalisch, G.J.L. Wuite, R. Metzler, Proc. Natl. Acad. Sci. USA 106, 8204 (2009)
T. Hu, B.I. Shklovskii, Phys. Rev. E 76, 051909 (2007)
G.-W. Li, O.G. Berg, J. Elf, Nat. Phys. 5, 294 (2009)
A. Marcovitz, Y. Levy, Biophys. J. 104, 2042 (2013)
M. Bauer, R. Metzler, Biophys. J. 102, 2321 (2012)
A. Veksler, A.B. Kolomeisky, J. Phys. Chem. B 117, 12695 (2013)
S. Yu, S. Wang, R.G. Larson, J. Biol. Phys. 39, 565 (2013)
M. Bauer, E.S. Rasmussen, M.A. Lomholt, R. Metzler, Sci. Rep. 5, 10072 (2015)
E. F Koslover, M.A.D. Rosa, A.J. Spakowitz, Biophys. J. 101, 856 (2011)
L. Liu, A.G. Cherstvy, R. Metzler, J. Phys. Chem. 121, 1284 (2017)
A. Raj, A. van Oudenaarden, Cell 135, 216 (2008)
O. Pulkkinen, R. Metzler, Phys. Rev. Lett. 110, 198101 (2013)
S.E. Halford, Biochem. Soc. Trans. 37, 343 (2009)
F. Wang, S. Redding, I.J. Finkelstein, J. Gorman, D.R. Reichman, E.C. Greene, Nat. Struct. Mol. Biol. 20, 174 (2013)
P. Hammar, P. Leroy, A. Mahmutovic, E.G. Marklund, O.G. Berg, J. Elf, Science 336, 1595 (2012)
F. Spitzer, Principles of random walk (Springer, 1976)
A. James, J.W. Pitchford, M.J. Plank, Bull. Math. Biol. 72, 896 (2010)
T. Koren, M.A. Lomholt, A.V. Chechkin, J. Klafter, R. Metzler, Phys. Rev. Lett. 99, 160602 (2007)
D. Janakiraman, Phys. Rev. E 95, 012154 (2017)
V.V. Palyulin, A.V. Chechkin, R. Klages, R. Metzler, J. Phys. A 49, 394002 (2016)
E.H. Bareiss, Numer. Math. 13, 404424 (1969)
M. Abramowitz, I.A. Stegun, Handbook of Mathematical Functions with Formulas, Graphs, and Mathematical Tables (NBS, 1964)
I.S. Gradshteyn, I.M. Ryzhik, Table of the Integrals, Series and Products (Academic Press, San Diego, CA, 2007)
L. Mirny, M. Slutsky, Z. Wunderlich, A. Tafvizi, J. Leith, A. Kosmrlj, J. Phys. A: Math. Theor. 42, 434013 (2009)
M. Sheinman, O. Bénichou, Y. Kafri, R. Voituriez, Rep. Prog. Phys. 75, 026601 (2012)
Author information
Authors and Affiliations
Corresponding author
Additional information
Contribution to the Topical Issue “Continuous Time Random Walk Still Trendy: Fifty-year History, Current State and Outlook”, edited by Ryszard Kutner and Jaume Masoliver.
Rights and permissions
About this article
Cite this article
Palyulin, V.V., Mantsevich, V.N., Klages, R. et al. Comparison of pure and combined search strategies for single and multiple targets. Eur. Phys. J. B 90, 170 (2017). https://doi.org/10.1140/epjb/e2017-80372-4
Received:
Published:
DOI: https://doi.org/10.1140/epjb/e2017-80372-4