On some random forests with determinantal roots

Abstract

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.