WIAS Preprint No. 1881, (2013)

On some random forests with determinantal roots


  • Avena, Luca
  • Gaudillière, Alexandre

2010 Mathematics Subject Classification

  • 05C81 60J20 15A15 4215A18 05C85


  • finite networks, spanning forests, determinantal processes, random sets, hitting times, local equilibria, Wilson's algorithm, random partitions, coalescence and fragmentation




Consider a finite weighted oriented graph. We study a probability measure on the set of spanning rooted oriented forests on the graph. We prove that the set of roots sampled from this measure is a determinantal process, characterized by a possibly non-symmetric kernel with complex eigenvalues. We then derive several results relating this measure to the Markov process associated with the starting graph, to the spectrum of its generator and to hitting times of subsets of the graph. In particular, the mean hitting time of the set of roots turns out to be independent of the starting point, conditioning or not to a given number of roots. Wilson's algorithm provides a way to sample this measure and, in absence of complex eigenvalues of the generator, we explain how to get samples with a number of roots approximating a prescribed integer. We also exploit the properties of this measure to give some probabilistic insight into the proof of an algebraic result due to Micchelli and Willoughby [13]. Further, we present two different related coalescence and fragmentation processes.

Download Documents