# Discrepancy of uniformly distributed random variates

Edit: I'm not sure if this is better suited to StatsStackexchange.

I thought of this question after reading about quasi-random sequences (and quasi-random numbers) in the context of Monte Carlo integration.

## Introduction and definitions

Quasi-random numbers are different from pseudo-random numbers, because they are deterministically constructed to have **low discrepancy**.

Discrepancy is defined as follows,

Let $$x_1, x_2, \cdots x_N$$ be $$N$$ numbers in $$I=[0,1]^s$$, let $$E \subset I$$. Define a function $$A(E;N)$$ such that, it counts the number of $$n$$, $$1\leq n\leq N$$, for $$x_n \in E.$$ The discrepancy $$D_n$$ of the $$N$$ numbers in $$I$$ is then given by, \begin{align*} D_n=\sup_J \left| \frac{A(J;N)}{N}-\lambda_s(J) \right| \end{align*} Where, $$J$$ is any sub-interval of $$I$$, and $$\lambda_s(J)$$ denotes its $$s$$ dimensional Lebesgue measure.

The star discrepancy ($$D_N^*$$) is a more commonly used definition which is as follows. \begin{align*} D_N^*=\sup_{0\leq t \leq 1} \left | \frac{A([0,t); N)}{N} - \lambda_s([0,t)) \right| \end{align*} $$D_n$$ and $$D_n^*$$ are related by the following inequality \begin{align*} D_n^* \leq D_n \leq 2^s D_n^* \label{starrelation} \end{align*}

## Question

What is the discrepancy for a uniformly distributed random variate (or even pseudorandom numbers)?

Through the definition of star discrepancy it seems intuitively to me that a UD random variate probably has a high discrepancy. However I couldn't prove this, neither could I find any references online.

Update: There is a mistake in my bounty text (I misread the notation). The method described, to use the CDF of a Uniform Distribution times $$N$$ in place of $$A([0,t),N)$$ is correct and it gives the discrepancy of the uniformly distributed random variate as exactly $$0$$ for the single dimensional case. However the question to prove it for $$s$$-dimensional case is still open.

Thanks for any and all help!

• Would you mind explaining what is the $s$ in $2^s$? Sep 20, 2021 at 14:33
• The $s$ is the dimension if you are considering multidimensional case. For higher dimensions the $|J|$ can be more accurately read as the $s$ dimensional Lebesgue measure otherwise the definitions remain the same. Sep 20, 2021 at 15:45

For $$s=1$$, you can use Glivenko-Cantelli's theorem to show that $$D_N^*\to 0$$ almost surely. If $$x_1,x_2,\ldots,x_{N}$$ are i.i.d uniform on $$[0,1]^s$$ then you can also think of each coordinate of $$x_i$$'s are i.i.d uniform on $$[0,1]$$. Therefore $$D_N^* \to 0$$ in this case as well (almost surely).
• Of course, not a problem. You can also obtain rates of this convergence of $D_N^*$. I can add some references if you need such precise results. Let me know. Best Sep 21, 2021 at 16:29