The discrepancy of a $[0,1]$-valued sequence $n \mapsto \alpha_n$ is the quantity $$D(N; \alpha) \stackrel{\text{def}}{=} \sup_{(a,b) \subset [0,1]} \left|\frac{\#\{1 \leq n \leq N : \alpha_n \in (a,b)\}}{N} - (b-a)\right|$$

This is of course a very well-studied concept. We typically care about the case where $\alpha$ is a so-called equidistributed sequence i.e., when $D(N; \alpha) \to 0$. Then the natural questions pertain to the rate of convergence. There are various estimates for $D(N;\alpha)$. The tightest lower bound (I believe due to W.M. Schmidt) is that $D(N; \alpha) \gtrsim \frac{\log N}{N}$, in the sense that there exist absolute constants $c,C>0$ such that (i) for every sequence $\alpha$, $\limsup_{N} \frac{D(N; \alpha)}{\frac{\log N}{N}} \geq c$ and (ii) there exists a sequence $\alpha$ with $\limsup_{N} \frac{D(N; \alpha)}{\frac{\log N}{N}} \leq C$ (an example of the latter is the van der Corput sequence).

The setting where this is typically studied is deterministic i.e., when $(\alpha_n)$ is a fixed (non-random) sequence. I would like to study this in a probabilistic setting.

Let $X=(X_i)_{i \in \mathbb{N}}$ be a sequence of independent $\text{Uniform}([0,1])$ random variables. Then it is not hard to show that $D(N; X) \to 0$ almost surely i.e., that $X$ is equidistributed almost surely. A natural question to ask (among others) is about estimating $\mathbb{E}[D(N; X)]$.

Is there any literature on this, or, more broadly, studying the discrepancy of random sequences?

  • $\begingroup$ I surely remember seeing estimates for the expected value you are asking for. I came across while I was searching some other papers and have don't have ready links. A google search would give that paper. You may add a reference request tag to this question. $\endgroup$
    – Rajesh D
    Oct 15, 2021 at 17:29

2 Answers 2


$\mathbb{E}[D(N; X)]$ is of order $N^{-1/2}$. This, and more precise information, follows from the analysis of the Kolmogorov-Smirnov test [1].
See, in particular, [2] and the references described on page 98 of the book [3]. Interesting extensions to higher dimensions are in [4].

[1] https://en.wikipedia.org/wiki/Kolmogorov%E2%80%93Smirnov_test

[2] Niederreiter, H. "Metric theorems on the distribution of sequences." In Proc. Sympos. Pure Math, vol. 24, pp. 195-212. 1973.

[3] Kuipers, L. and Niederreiter, H., 2012. Uniform distribution of sequences. Courier Corporation.

[4] Stute, Winfried. "Convergence rates for the isotrope discrepancy." The Annals of Probability (1977): 707-723.


Doing a quick search I just found this:

Probabilistic discrepancy bound for Monte Carlo point sets https://arxiv.org/pdf/1211.1058.pdf

Where they conclude on an upper bound as $D < c(q) N^{-1/2}$ with probability $q$. Are there better estimates?


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.