Tight Bounds for Coalescing-Branching Random Walks on Regular Graphs
Tight Bounds for Coalescing-Branching Random Walks on Regular Graphs
A Coalescing-Branching Random Walk (CoBra) is a natural extension to the standard random walk on a graph. The process starts with one pebble at an arbitrary node. In each round of the process every pebble splits into k pebbles, which are sent to k random neighbors. At the end of …