Restricted permutations and random (0,1)-matrices in the symmetric simple exclusion process in discrete time over graphs

Motivations to study exclusion processes in general and exclusion processes over graphs in particular are manifold. In physics, exclusion processes are simple models that provide nontrivial results on a number of basic issues, such as the relaxation dynamics of a gas or fluid towards the thermodynamic equilibrium. They are also relevant in the modeling of interacting processes such as queueing systems, traffic, signaling in radio and computer networks, and rumour and epidemics spreading in social networks. Moreover, exclusion processes are natural generalizations of the single random walk problem. The mathematics of random walks on graphs and groups has been an active field of investigation for at least four decades by now, having led to many developments in pure and applied probability, statistics, combinatorics, group theory, and harmonic analysis. In this work we describe the dynamics of the symmetric simple exclusion process in discrete time over simple graphs by means of suitably restricted permutations over the labels of the vertices of the graphs. Straightforward Monte Carlo and sequential importance sampling algorithms for sampling restricted permutations inspired by the related problem of computing permanents are implemented and compared. We illustrate the formalism by estimating the relaxation times of the symmetric simple exclusion process in discrete time over Newman-Watts small-world networks.