# Estimates on the discrepancy of random sequences

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?

• 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. Oct 15, 2021 at 17:29

$$\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].

[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?