A Measure-on-Graph-Valued Diffusion: A Particle System with Collisions and Its Applications

Abstract

A diffusion-taking value in probability-measures on a graph with vertex set V, ∑i∈Vxiδi is studied. The masses on each vertex satisfy the stochastic differential equation of the form dxi=∑j∈N(i)xixjdBij on the simplex, where {Bij} are independent standard Brownian motions with skew symmetry, and N(i) is the neighbour of the vertex i. A dual Markov chain on integer partitions to the Markov semigroup associated with the diffusion is used to show that the support of an extremal stationary state of the adjoint semigroup is an independent set of the graph. We also investigate the diffusion with a linear drift, which gives a killing of the dual Markov chain on a finite integer lattice. The Markov chain is used to study the unique stationary state of the diffusion, which generalizes the Dirichlet distribution. Two applications of the diffusions are discussed: analysis of an algorithm to find an independent set of a graph, and a Bayesian graph selection based on computation of probability of a sample by using coupling from the past.

Keywords

• Bayesian graph selection
• coupling from the past
• integer partition
• interacting particle system
• independent set finding
• measure-valued diffusion