2
$\begingroup$

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!

$\endgroup$
2
  • $\begingroup$ Would you mind explaining what is the $s$ in $2^s$? $\endgroup$ Sep 20, 2021 at 14:33
  • $\begingroup$ 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. $\endgroup$ Sep 20, 2021 at 15:45

1 Answer 1

4
+50
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ +1 I think this is the closest to an answer for the multidimensional case, I'll leave the bounty open for a few days incase there's any other answers. $\endgroup$ Sep 21, 2021 at 15:55
  • 1
    $\begingroup$ 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 $\endgroup$ Sep 21, 2021 at 16:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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