Discrete total variation under the multinomial, Part~1: expectation under the uniform null

Source abstract

We study the expectation of the discrete total variation statistic $d=\sum_{i=1}^{n-1}|X_{i+1}-X_i|$ of counts $X_1,\dots,X_n$ over $n$ ordered bins with sample size $N$, under the uniform multinomial null. In the notation used throughout the series, a reference distribution $\mathbf r$ defines $d_{\mathbf r}(x)=\|x-N\mathbf r\|_V$; here $\mathbf r=\mathbf u$ is uniform and we write simply $d$. We obtain an exact single-sum formula, a closed form in central trinomial coefficients valid for every $n\ge2$, with one-term evaluations at $n=2,4$ and a complete D-finite characterization for $n=3$. The per-edge expectation $W_N=E|X_2-X_1|$ satisfies an exact three-term recurrence, from which we derive its complete $1/N$ expansion with the $n$-independent constant $E(d^\circ/\sqrt{Nn})\to 2/\sqrtπ$ for the cyclic statistic $d^\circ=d^\circ_{\mathbf u}$, independent of the number of bins; the complementary sparse regime (fixed $N$, $n\to\infty$) is treated in a separate paper. Conditioning on a two-bin total reduces each edge to a symmetric random walk; as the subsequent parts of the series will show, this method carries the analysis to non-uniform reference laws.