Finding the source of a random process
Consider a random diffusion of particles on a graph, started from a single site. Given only a snapshot of the history, can the starting point be determined? I will discuss the ideas and problems surrounding this question in two contexts: for random rumour spreading algorithms, and for simple random walk/Brownian motion. For rumour spread, I will present the state-of-the-art, an algorithm called adaptive diffusion, discuss its shortfalls, and suggest a path forward. For random walks, I will sketch some new results on random regular graphs and Z^d.