The drunkard walk is a game where two players have $a$ and $b$ dollars, respectively, and they play a series of fair games (both risking one dollar in each game) until one of them goes broke.

My question is: has this been considered on a graph? More precisely, we are given a (finite, connected) simple graph, and every vertex has a positive integer assigned to it. Each round we pick an edge uniformly at random, and toss a fair coin to decide which vertex gives the other one dollar. The game is played until someone goes broke.

(I have reasonably good estimates for the expected runtime if the graph is a cycle.)



Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.