Document Open Access Logo

Choice and Bias in Random Walks

Authors Agelos Georgakopoulos , John Haslegrave , Thomas Sauerwald , John Sylvester

PDF
Thumbnail PDF

File

LIPIcs.ITCS.2020.76.pdf
  • Filesize: 0.62 MB
  • 19 pages

Document Identifiers

Author Details

Agelos Georgakopoulos
  • Mathematics Institute, University of Warwick, UK
John Haslegrave
  • Mathematics Institute, University of Warwick, UK
Thomas Sauerwald
  • Department of Computer Science & Technology, University of Cambridge, UK
John Sylvester
  • Department of Computer Science & Technology, University of Cambridge, UK

Funding

A. G. & J. H. were supported by ERC Starting Grant no. 639046 (RGGC). T. S. & J. S. were supported by ERC Starting Grant no. 679660 (DYNAMIC MARCH).

Cite AsGet BibTex

Agelos Georgakopoulos, John Haslegrave, Thomas Sauerwald, and John Sylvester. Choice and Bias in Random Walks. In 11th Innovations in Theoretical Computer Science Conference (ITCS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 151, pp. 76:1-76:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
https://doi.org/10.4230/LIPIcs.ITCS.2020.76

Abstract

We analyse the following random walk process inspired by the power-of-two-choice paradigm: starting from a given vertex, at each step, unlike the simple random walk (SRW) that always moves to a randomly chosen neighbour, we have the choice between two uniformly and independently chosen neighbours. We call this process the choice random walk (CRW). We first prove that for any graph, there is a strategy for the CRW that visits any given vertex in expected time ?(|E|). Then we introduce a general tool that quantifies by how much the probability of a rare event in the simple random walk can be boosted under a suitable CRW strategy. We believe this result to be of independent interest, and apply it here to derive an almost optimal ?(n log log n) bound for the cover time of bounded-degree expanders. This tool also applies to so-called biased walks, and allows us to make progress towards a conjecture of Azar et al. [STOC 1992]. Finally, we prove the following dichotomy: computing an optimal strategy to minimise the hitting time of a vertex takes polynomial time, whereas computing one to minimise the cover time is NP-hard.

Subject Classification

ACM Subject Classification
  • Theory of computation → Random walks and Markov chains
  • Mathematics of computing → Stochastic processes
Keywords
  • Power of Two Choices
  • Markov Chains
  • Random Walks
  • Cover Time
  • Markov Decision Processes

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

References

  1. Mohammed Amin Abdullah, Colin Cooper, and Moez Draief. Speeding up cover time of sparse graphs using local knowledge. In Combinatorial algorithms, volume 9538 of Lecture Notes in Comput. Sci., pages 1-12. Springer, [Cham], 2016. URL: https://doi.org/10.1007/978-3-319-29516-9_1.
  2. Dimitris Achlioptas, Raissa M. D'Souza, and Joel Spencer. Explosive percolation in random networks. Science, 323(5920):1453-1455, 2009. URL: https://doi.org/10.1126/science.1167782.
  3. Noga Alon, Chen Avin, Michal Koucký, Gady Kozma, Zvi Lotker, and Mark R. Tuttle. Many random walks are faster than one. Combin. Probab. Comput., 20(4):481-502, 2011. URL: https://doi.org/10.1017/S0963548311000125.
  4. Noga Alon, Itai Benjamini, Eyal Lubetzky, and Sasha Sodin. Non-backtracking random walks mix faster. Commun. Contemp. Math., 9(4):585-603, 2007. URL: https://doi.org/10.1142/S0219199707002551.
  5. Chen Avin and Bhaskar Krishnamachari. The power of choice in random walks: An empirical study. Computer Networks, 52(1):44-60, 2008. (1) Performance of Wireless Networks (2) Synergy of Telecommunication and Broadcasting Networks. URL: https://doi.org/10.1016/j.comnet.2007.09.012.
  6. Yossi Azar, Andrei Z. Broder, Anna R. Karlin, Nathan Linial, and Steven Phillips. Biased random walks. Combinatorica, 16(1):1-18, 1996. URL: https://doi.org/10.1007/BF01300124.
  7. Yossi Azar, Andrei Z. Broder, Anna R. Karlin, and Eli Upfal. Balanced allocations. SIAM J. Comput., 29(1):180-200, 1999. URL: https://doi.org/10.1137/S0097539795288490.
  8. Katy E. Beeler, Kenneth S. Berenhaut, Joshua N. Cooper, Meagan N. Hunter, and Peter S. Barr. Deterministic walks with choice. Discrete Appl. Math., 162:100-107, 2014. URL: https://doi.org/10.1016/j.dam.2013.08.031.
  9. Michael Ben-Or and Nathan Linial. Collective coin flipping. In S. Micali, editor, Randomness and Computation, pages 91-115. Academic Press, New York, 1989. Google Scholar
  10. Petra Berenbrink, Colin Cooper, and Tom Friedetzky. Random walks which prefer unvisited edges: exploring high girth even degree expanders in linear time. Random Structures Algorithms, 46(1):36-54, 2015. URL: https://doi.org/10.1002/rsa.20504.
  11. Petra Berenbrink, Artur Czumaj, Angelika Steger, and Berthold Vöcking. Balanced allocations: the heavily loaded case. In Proceedings of the Thirty-Second Annual ACM Symposium on Theory of Computing, pages 745-754. ACM, New York, 2000. URL: https://doi.org/10.1145/335305.335411.
  12. Tom Bohman and Alan Frieze. Addendum to "Avoiding a giant component" [Random Structures Algorithms 19 (2001), no. 1, 75-85; MR1848028]. Random Structures Algorithms, 20(1):126-130, 2002. URL: https://doi.org/10.1002/rsa.10018.
  13. Tom Bohman and David Kravitz. Creating a giant component. Combin. Probab. Comput., 15(4):489-511, 2006. URL: https://doi.org/10.1017/S0963548306007486.
  14. Charles Bordenave, Marc Lelarge, and Laurent Massoulié. Nonbacktracking spectrum of random graphs: community detection and nonregular Ramanujan graphs. Ann. Probab., 46(1):1-71, 2018. URL: https://doi.org/10.1214/16-AOP1142.
  15. Colin Cooper, Alan M. Frieze, and Tony Johansson. The Cover Time of a Biased Random Walk on a Random Cubic Graph. In James Allen Fill and Mark Daniel Ward, editors, 29th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms, AofA 2018, June 25-29, 2018, Uppsala, Sweden, volume 110 of LIPIcs, pages 16:1-16:12. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2018. URL: https://doi.org/10.4230/LIPIcs.AofA.2018.16.
  16. Colin Cooper, David Ilcinkas, Ralf Klasing, and Adrian Kosowski. Derandomizing random walks in undirected graphs using locally fair exploration strategies. Distributed Computing, 24(2):91-99, 2011. URL: https://doi.org/10.1007/s00446-011-0138-4.
  17. Roee David and Uriel Feige. Random walks with the minimum degree local rule have O(n²) cover time. SIAM J. Comput., 47(3):755-768, 2018. URL: https://doi.org/10.1137/17M1119901.
  18. Cyrus Derman. Finite state Markovian decision processes. Mathematics in Science and Engineering, Vol. 67. Academic Press, New York-London, 1970. Google Scholar
  19. Klim Efremenko and Omer Reingold. How well do random walks parallelize? In Approximation, randomization, and combinatorial optimization, volume 5687 of Lecture Notes in Comput. Sci., pages 476-489. Springer, Berlin, 2009. URL: https://doi.org/10.1007/978-3-642-03685-9_36.
  20. Robert Elsässer and Thomas Sauerwald. Tight bounds for the cover time of multiple random walks. Theoret. Comput. Sci., 412(24):2623-2641, 2011. URL: https://doi.org/10.1016/j.tcs.2010.08.010.
  21. Robert Fitzner and Remco van der Hofstad. Non-backtracking random walk. J. Stat. Phys., 150(2):264-284, 2013. URL: https://doi.org/10.1007/s10955-012-0684-6.
  22. M. R. Garey, D. S. Johnson, and L. Stockmeyer. Some simplified NP-complete graph problems. Theoret. Comput. Sci., 1(3):237-267, 1976. URL: https://doi.org/10.1016/0304-3975(76)90059-1.
  23. Agelos Georgakopoulos, John Haslegrave, Thomas Sauerwald, and John Sylvester. The Power of Two Choices for Random Walks. Preprint, 2019. URL: http://arxiv.org/abs/1911.05170.
  24. Martin Grötschel, László Lovász, and Alexander Schrijver. Geometric algorithms and combinatorial optimization, volume 2 of Algorithms and Combinatorics. Springer-Verlag, Berlin, second edition, 1993. URL: https://doi.org/10.1007/978-3-642-78240-4.
  25. John Haslegrave and Jonathan Jordan. Preferential attachment with choice. Random Structures Algorithms, 48(4):751-766, 2016. URL: https://doi.org/10.1002/rsa.20616.
  26. John Haslegrave, Thomas Sauerwald, and John Sylvester. Time Dependent Biased Random Walks. In preparation, to appear on ArXiv, 2019. Google Scholar
  27. Roger A. Horn and Charles R. Johnson. Matrix Analysis, 2nd Ed. Cambridge University Press, 2012. URL: https://doi.org/10.1017/CBO9781139020411.
  28. Satoshi Ikeda, Izumi Kubo, and Masafumi Yamashita. The hitting and cover times of random walks on finite graphs using local degree information. Theoret. Comput. Sci., 410(1):94-100, 2009. URL: https://doi.org/10.1016/j.tcs.2008.10.020.
  29. N. Karmarkar. A new polynomial-time algorithm for linear programming. Combinatorica, 4(4):373-395, 1984. URL: https://doi.org/10.1007/BF02579150.
  30. Yury Malyshkin and Elliot Paquette. The power of choice over preferential attachment. ALEA Lat. Am. J. Probab. Math. Stat., 12(2):903-915, 2015. Google Scholar
  31. Michael Mitzenmacher. The Power of Two Choices in Randomized Load Balancing. IEEE Trans. Parallel Distrib. Syst., 12(10):1094-1104, 2001. URL: https://doi.org/10.1109/71.963420.
  32. Michael Mitzenmacher, Andréa W. Richa, and Ramesh Sitaraman. The power of two random choices: a survey of techniques and results. In Handbook of randomized computing, Vol. I, II, volume 9 of Comb. Optim., pages 255-312. Kluwer Acad. Publ., Dordrecht, 2001. URL: https://doi.org/10.1007/978-1-4615-0013-1_9.
  33. Roberto I. Oliveira and Yuval Peres. Random walks on graphs: new bounds on hitting, meeting, coalescing and returning. In Marni Mishna and J. Ian Munro, editors, Proceedings of the Sixteenth Workshop on Analytic Algorithmics and Combinatorics, ANALCO 2019, San Diego, CA, USA, January 6, 2019, pages 119-126. SIAM, 2019. URL: https://doi.org/10.1137/1.9781611975505.13.
  34. Tal Orenshtein and Igor Shinkar. Greedy random walk. Combin. Probab. Comput., 23(2):269-289, 2014. URL: https://doi.org/10.1017/S0963548313000552.
  35. Oliver Riordan and Lutz Warnke. Achlioptas process phase transitions are continuous. Ann. Appl. Probab., 22(4):1450-1464, 2012. URL: https://doi.org/10.1214/11-AAP798.
  36. Joel Spencer and Nicholas Wormald. Birth control for giants. Combinatorica, 27(5):587-628, 2007. URL: https://doi.org/10.1007/s00493-007-2163-2.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact