Discrepancy of uniformly distributed random variates

monte carloprobabilityrandom variables

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!

Best Answer

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).

Related Question