ETD

• Clustering
• Loop erased random walk
• Spanning forest

Given a weighted and finite graph, an efficient way to sample spanning treesis due to Wilson, who in the 1990s introduced his famous algorithm based onloop-erased random walks. Recently, L. Avena et al. general-ized Wilson’s algorithm to spanning forests with results on the distribution ofthe roots sampled by the algorithm, showing in particular that such set is adeterminantal point process.In this thesis, we first recall the results above and then focus on the case of adiscreted-dimensional torus, so that the associated Markov process is a simplerandom walk. We provide some original results on an asymptotic description ofthe number of roots and Wilson’s algorithm total running time, that we showto be faster than the cover time for a random walk, if d≥2, as predicted byWilson himself.We then report on some known applications of random forests, including therandom generation of rectangular mazes. We explore how well this algorithmdetects a minimum spanning tree Finally we suggest forest-based method for clustering.