Tipsy cop and tipsy robber: collisions of biased random walks on graphs

DOI10.1016/J.TCS.2024.114512arXiv2208.12829MaRDI QIDQ6128705FDOQ6128705

Authors: Pamela E. Harris, Erik Insko, Florian Lehner 

Publication date: 16 April 2024

Published in: Theoretical Computer Science (Search for Journal in Brave)

Abstract: We study collisions of two interacting random walks, where one of the walks has a bias to create collisions, and the other one has a bias to avoid them. This can be seen as a variant of the well-studied cop and robber game in which both of the players get to employ their respective strategies on some (random) proportion of their moves, and move randomly otherwise. We study different sensible strategies for both players on the infinite grid $mathbb{Z}^2$ and on certain families of infinite trees obtained by attaching a $delta$-regular tree to every vertex of a $Delta$-regular tree, where $Deltageqdelta$. Our results show that the best possible cop strategy on the grid is very sensitive to change, and the best possible robber strategy on trees not only depends on the tree the game is played on, but also on the proportion of random moves by either player. We conclude with some directions for further study.

Full work available at URL: https://arxiv.org/abs/2208.12829

Recommendations

• Chasing a drunk robber in many classes of graphs
• Some remarks on cops and drunk robbers
• Cops and invisible robbers: the cost of drunkenness
• Capturing the drunk robber on a graph
• scientific article; zbMATH DE number 5241699

zbMATH Keywords

random walksinfinite graphpursuit-evasion game

Mathematics Subject Classification ID

Theory of computing (68Qxx)

This page was built for publication: Tipsy cop and tipsy robber: collisions of biased random walks on graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6128705)