Excursion counts in a random Eulerian circuit on a complete graph

Definitions and mathematical statement

For $n\ge2$, let $D_n$ be the directed complete graph with one arc $(u,v)$ for each pair of distinct vertices and no loops. It has $M=n(n-1)$ arcs. Choose a distinguished vertex $o$, and take a uniformly random Eulerian tour in the convention of ordered arc sequences starting at $o$, ending at $o$, and traversing each arc exactly once.

Let $0=t_0<t_1<\cdots<t_{n-1}=M$ be its successive visit times to $o$. The excursion lengths, measured in arcs, are $t_j-t_{j-1}$, and define \[ N_i=\sum_{j=1}^{n-1}\mathbf1_{\{t_j-t_{j-1}=i\}}. \] Thus $\sum_iN_i=n-1$ and $\sum_i iN_i=n(n-1)$. The source asks whether \[ \mathbb E[N_i]\sim e^{-i/n} \] as $n\to\infty$, in the intended range of excursion lengths.

The range is not provided. Fixed $i$, $i/n\to x>0$, and uniform estimates over growing intervals are distinct asymptotic assertions. For instance, a scaling formulation for $i_n/n\to x>0$ would ask $\mathbb E[N_{i_n}]\to e^{-x}$, but it is not selected as the only intended version. With the arc-length convention and no loops, $N_1=0$; therefore the displayed asymptotic cannot be asserted for every fixed positive integer $i$. The source must specify the length convention and admissible regime. The rooting/uniform-circuit convention also needs confirmation from the original.

The summary reports this exponential excursion-count prediction unproved and says related Le Jan and McKay--Robinson literature did not answer it in the accessed review. It supplies no exact resolution. The source's open presentation and later review are attributions, not an independently verified current status.

Short English statement

In a uniform Eulerian tour of the bidirected complete graph, is the expected number of excursions of a given length approximately $e^{-i/n}$? The definition is made explicit, but the source omits the length-scaling range and must exclude incompatible short-length cases under the usual arc convention.

Sources

• Local registry: data/unsolvedmath/problems.json, permanent UnsolvedMath ID $9700015$, source code catalogue entry; supplied statement, background, and research summary, updated 2026-08-06.
• David Aldous, Open problems, "Random Eulerian Circuits", example (a), maintained index: https://www.stat.berkeley.edu/~aldous/Research/OP/index.html. Supplied HTML text with linked-primary-PDF text accessed 2026-07-29; the index is reported to have 23 active problem pages.
• Le Jan, arXiv:1405.2879, and early McKay--Robinson work on complete-graph Eulerian circuits are cited by the summary as related, without full publication details or a proof of this excursion estimate.