Description:

Title: Biased random walks

Abstract: The ordinary random walk on an n-vertex graph takes at least (1 - o(1)) n log n steps in expectation to cover the graph (that is, to visit every vertex). If an agent is able to partially influence the walk (maybe by corrupting some of the underlying randomness), it is plausible that the expected cover time could be dramatically reduced. One natural model of influence is that at every step, there is some positive probability p that the agent may choose the next vertex of the walk. Addressing questions of Olesker-Taylor, Sauerwald, and Sylvester, we show that for any bounded degree graph and fixed p, the agent can always guarantee an expected cover time of n^{1 + o(1)}, and conversely, we show that if p tends to zero, then there is no strategy on any graph achieving an expected cover time of O(n). Based partially on joint work with Boris Bukh.