  Wheeler automata were introduced in 2017 as a tool to generalize existing
indexing and compression techniques based on the Burrows-Wheeler transform.
Intuitively, an automaton is said to be Wheeler if there exists a total order
on its states reflecting the co-lexicographic order of the strings labeling the
automaton's paths; this property makes it possible to represent the automaton's
topology in a constant number of bits per transition, as well as efficiently
solving pattern matching queries on its accepted regular language. After their
introduction, Wheeler automata have been the subject of a prolific line of
research, both from the algorithmic and language-theoretic points of view. A
recurring issue faced in these studies is the lack of large datasets of Wheeler
automata on which the developed algorithms and theories could be tested. One
possible way to overcome this issue is to generate random Wheeler automata.
Motivated by this observation, in this paper we initiate the theoretical study
of random Wheeler automata, focusing on the deterministic case (Wheeler DFAs --
WDFAs). We start by extending the Erd\H{o}s-R\'enyi random graph model to
WDFAs, and proceed by providing an algorithm generating uniform WDFAs according
to this model. Our algorithm generates a uniform WDFA with $n$ states, $m$
transitions, and alphabet's cardinality $\sigma$ in $O(m)$ expected time
($O(m\log m)$ worst-case time w.h.p.) and constant working space for all
alphabets of size $\sigma \le m/\ln m$. As a by-product, we also give formulas
for the number of distinct WDFAs and obtain that $ n\sigma + (n - \sigma) \log
\sigma$ bits are necessary and sufficient to encode a WDFA with $n$ states and
alphabet of size $\sigma$, up to an additive $\Theta(n)$ term. We present an
implementation of our algorithm and show that it is extremely fast in practice,
with a throughput of over 8 million transitions per second.
