On the Periodicity of Random Walks in Dynamic Networks

We investigate random walks in graphs whose edges change over time as a function of the current probability distribution of the walk. We show that such systems can be chaotic and can exhibit “hyper-torpid” mixing. Our main result is that, if each graph is strongly connected, then the dynamics is asymptotically periodic almost surely.