id: 01936097
dt: j
an: 01936097
au: Hickernell, Fred J.
ti: The mean square discrepancy of randomized nets.
so: ACM Trans. Model. Comput. Simul. 6, No. 4, 274-296 (1996).
py: 1996
pu: Association for Computing Machinery (ACM), New York
la: EN
cc: I.6.8 G.1.4 G.3
ut: algorithms; performance; theory
ci: 
li: doi:10.1145/240896.240909
ab: Summary: \BeginparOne popular family of low dicrepancy sets is the ({\it t,
    m, s})-nets. Recently a randomization of these nets that preserves
    their net property has been introduced. In this article a formula for
    the mean square {\it L}$^{2}$-discrepancy of ({\it 0, m, s})-nets in
    base {\it b} is derived. This formula has a computational complexity of
    only O(s log({\it N}) + s$^{2}$) for large {\it N} or s, where {\it N =
    b$^{m}$} is the number of points. Moreover, the root mean square {\it
    L}$^{2}$-discrepancy of ({\it 0, m, s})-nets is show to be O({\it
    N}$^{-1}$[log(N)]$^{(s-1)/2}$) as {\it N} tends to infinity, the same
    asymptotic order as the known lower bound for the {\it
    L}$^{2}$-discrepancy of an arbitrary set.\Endpar (Provider: ACM)
    Review: \Beginpar \SGMPbeginExtract \BeginparMultidimensional integrals
    over the \( S\) -dimensional unit cube can be approximated by the
    sample mean of the integral evaluated on a point set, \( P\) , with \(
    N\) points. The quadrature error depends in part on how uniformly the
    points in \( P\) are distributed on the unit cube. A good set \( P\)
    for quadrature is one that has a small discrepancy, \(
    D{\left\LeftPost{par}P\right\RightPost{par}}\) , where discrepancy is
    defined as a measure of the spread of the points in \( P\) .\Endpar
    \BeginparSeveral deterministic sets have been found that have smaller
    discrepancies than simple random points. These sets are often called
    quasi-random points. Much effort has been directed towards finding
    quasi-random sequences that have asymptotically small \( {\cal
    L}^{\infty }\) -star discrepancies as \( N\) tends to infinity. The \(
    {\left\LeftPost{par}t,m,s\right\RightPost{par}}\) -nets are one
    example. Calculating the \( {\cal L}^{\infty }\) -star discrepancy of a
    particular set is impractical because it requires \(
    O{\left\LeftPost{par}N^{5}\right\RightPost{par}}\) operations. By
    comparison, the \( {\cal L}^{2}\) -star discrepancy is easier to
    compute, requiring only \(
    O{\left\LeftPost{par}N^{2}\right\RightPost{par}}\) operations using a
    naive algorithm, or \( O{\left\LeftPost{par}N\SGMPlim{r}\log \SGMPdolim
    ^{5} N\right\RightPost{par}}\) operations using a more sophisticated
    algorithm.\Endpar \BeginparRecently, a randomization of \(
    {\left\LeftPost{par}t,m,s\right\RightPost{par}}\) -nets was proposed
    that preserves their net properties. The aim is to obtain probabilistic
    quadrature error estimates in a similar manner as one would for simple
    Monte Carlo quadrature. In this paper, a formula for the mean square \(
    {\cal L}^{2}\) -discrepancy of randomized \(
    {\left\LeftPost{par}0,m,s\right\RightPost{par}}\) -nets is derived that
    requires only \( O{\left\LeftPost{par}s\log
    N+s^{2}\right\RightPost{par}} \) mathematical operations as \( N\) , \(
    s\) , or both tend to infinity. The \( {\cal L}^{2}\) -discrepancy for
    these randomized nets is shown to decay like \(
    O{\left\LeftPost{par}N^{-1}{\left\LeftPost{par}\log
    N\right\RightPost{par}}^{%
    {\left\LeftPost{par}s-1\right\RightPost{par}}/2}\right\RightPost{par}}
    \) for large \( N\) , the same asymptotic order as the known lower
    bound for the \( {\cal L}^{2}\) -discrepancy of an arbitrary
    set.\Endpar \Beginpar{—}{\it From the Introduction}\Endpar
    \SGMPendExtract \Endpar \BeginparThe paper consists primarily of
    mathematical derivations of the expected value of the square of the
    discrepancy, under various assumptions, as well as asymptotic
    derivations. The paper is highly mathematical and is readable only by
    mathematicians with a background in probability theory. It is well
    structured and, for those readers, should not be difficult to
    follow.\Endpar \BeginparThe results should be applicable by people
    working in the fields of numerical quadrature and differentiation and
    Monte Carlo simulation, even if they cannot follow the
    derivations.\Endpar (Provider: ACM)
rv: