# Unbiased spanning-tree generation

Recently I’ve done some micro-tests with spanning-trees in my spare time inspired by some talks I had with my good friend ditiem.

The video below is my implementation of Wilson’s algorithm.

Spanning-trees can be visualized as classic mazes, which are always pretty to look at (bonus: rainbow floodfill). But let’s forget about the maze itself. To me the majestuous beauty of this algorithm lies in the fact that it is *fully unbiased*:

- If the random numbers involved are uniformly distributed, it generates an also
*uniformly distributed random sample*in the*space of all possible 2D-filling spanning-trees*. *i.e.,*if the algorithm is called an infinite amount of times,*all*possible such mazes will be generated with*equal likelihood*.

**Unbiasedness** for the win.

Some interesting remarks could be made about how to optimize the generation time stochastically. Let’s save that discussion for another time…