Discrete total variation under the multinomial, Part~1: expectation under the uniform null
Abstract
We study the expectation of the discrete total variation statistic d=∑i=1n−1|Xi+1−Xi| of counts X1,…,Xn over n ordered bins with sample size N, under the uniform multinomial null. In the notation used throughout the series, a reference distribution r defines dr(x)=|x−Nr|V; here r=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≥2, with one-term evaluations at n=2,4 and a complete D-finite characterization for n=3. The per-edge expectation WN=E|X2−X1| satisfies an exact three-term recurrence, from which we derive its complete 1/N expansion with the n-independent constant E(d∘/√(Nn))→ 2/√π for the cyclic statistic d∘=d∘u, independent of the number of bins; the complementary sparse regime (fixed N, n→∞) 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.
Related
- Discrete total variation under the multinomial, Part 3: expectation under a general distribution
- Discrete total variation under the multinomial, Part 2: variance under the uniform null
- A total variation threshold for the first coordinates of uniform parking functions via Lorentzian polynomials
- Bridging persistence of discrete and continuous 1D maps: Total variation, permutation equivalence, and diagonal affine transformations
- Uniform convergence of canonical discrete uniformization on equilateral approximations
BibTeX
@misc{banic2026discrete,
title = {{Discrete total variation under the multinomial, Part~1: expectation under the uniform null}},
author = {N. Banić and N. Elezović},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.13366},
eprint = {2610.13366},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.13366},
}
RIS
TY - UNPB
TI - Discrete total variation under the multinomial, Part~1: expectation under the uniform null
AU - N. Banić
AU - N. Elezović
PY - 2026
DA - 2026/10/09
PB - arXiv
DO - 10.48550/arxiv.2610.13366
UR - https://arxiv.org/abs/2610.13366
AB - We study the expectation of the discrete total variation statistic d=∑_i=1^n−1|X_i+1−X_i| of counts X_1,…,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 r defines d_r(x)=|x−Nr|_V; here r=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≥2, 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^∘/√(Nn))→ 2/√π for the cyclic statistic d^∘=d^∘_u, independent of the number of bins; the complementary sparse regime (fixed N, n→∞) 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.
ER -