Excursion Lengths in a Uniform Eulerian Circuit of the Complete Graph: Aldous's Conjecture Holds if and only if i = o(n^(3/2))

Let N_i be the number of excursions of length i from a fixed vertex in a uniformly random Eulerian circuit of the complete graph K_n in which every edge is replaced by two opposite arcs. Aldous and Yu (Open Problems in Mathematics, 2014) stated as the natural conjecture that E N_i is asymptotic to exp(-i/n). We prove that for every fixed K, uniformly in 2 <= i <= K n^(3/2), E N_i = exp(-i/n - i^2/(2n^3))(1 + O(n^(-1/2) log n)), and that E N_i exp(i/n) tends to zero when i/n^(3/2) tends to infinity. Consequently E N_i is asymptotic to exp(-i/n) if and only if i = o(n^(3/2)). This range contains fixed i, the scale i proportional to n and essentially all excursions, and the length of a uniformly chosen excursion, divided by n, converges in distribution to the standard exponential law. At the scale i proportional to y n^(3/2) the ratio E N_i/exp(-i/n) tends to exp(-y^2/2), so the conjecture read literally for all i is false. The proof combines the uniform-spanning-tree construction of a uniform Eulerian circuit (the BEST theorem, in the form used by Kandel, Matias, Unger and Winkler), a hazard representation of the first excursion, and a convexity bound. Exact computations for n <= 6 and Monte Carlo simulations up to n = 6400 agree with the results.