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

Pamela E. Harris, Erik Insko, Florian Lehner

Research output: Working paperPreprint

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 $\Delta \geq \delta$. 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.
Original languageEnglish
Publication statusPublished - 26 Aug 2022

Keywords

  • math.PR
  • math.CO
  • 05C05, 05C81

Fingerprint

Dive into the research topics of 'Tipsy cop and tipsy robber: collisions of biased random walks on graphs'. Together they form a unique fingerprint.

Cite this