The Inverse of the Star-Discrepancy Problem and the Generation of Pseudo-Random Numbers

详细信息    查看全文

• 作者：Josef Dick (15)
  Friedrich Pillichshammer (16)
  
• 刊名：Lecture Notes in Computer Science
• 出版年：2014
• 出版时间：2014
• 年：2014
• 卷：1
• 期：1
• 页码：173-184
• 全文大小：238 KB
• 参考文献：1. Aistleitner, C.: Covering numbers, dyadic chaining and discrepancy. J. Complex. 27, 531-40 (2011) CrossRef
  2. Aistleitner, C.: Tractability results for the weighted star-discrepancy. J. Complex. 30, 381-91 (2014) CrossRef
  3. Aistleitner, C., Hofer, M.: Probabilistic discrepancy bound for Monte Carlo point sets. Math. Comput. 83, 1373-381 (2014) CrossRef
  4. Aistleitner, C., Weimar, M.: Probabilistic star discrepancy bounds for double infinite random matrices. In: Dick, J., Kuo, F.Y., Peters, G.W., Sloan, I.H. (eds.) Monte Carlo and quasi-Monte Carlo methods 2012. Springer, Berlin (2013)
  5. Bilyk, D., Lacey, M.T., Vagharshakyan, A.: On the small ball inequality in all dimensions. J. Funct. Anal. 254, 2470-502 (2008) CrossRef
  6. Chen, S., Dick, J., Owen, A.B.: Consistency of Markov chain quasi-Monte Carlo on continuous state spaces. Ann. Stat. 39, 673-01 (2011) CrossRef
  7. Dick, J.: Numerical integration of H?lder continuous, absolutely convergent Fourier, Fourier cosine, and Walsh series. J. Approx. Theory 183, 14-0 (2014) CrossRef
  8. Dick, J., Hinrichs, A., Pillichshammer, F.: Proof techniques in quasi-Monte Carlo theory. J. Complexity (2014) (Submitted)
  9. Dick, J., Leobacher, G., Pillichshammer, F.: Construction algorithms for digital nets with low weighted star-discrepancy. SIAM J. Numer. Anal. 43, 76-5 (2005) CrossRef
  10. Dick, J., Niederreiter, H., Pillichshammer, F.: Weighted star-discrepancy of digital nets in prime bases. In: Talay, D., Niederreiter, H. (eds.) Monte Carlo and Quasi-Monte Carlo Methods 2004. Springer, Berlin (2006)
  11. Dick, J., Pillichshammer, F.: Digital Nets and Sequences - Discrepancy Theory and Quasi-Monte Carlo Integration. Cambridge University Press, Cambridge (2010) CrossRef
  12. Dick, J., Pillichshammer, F.: The weighted star discrepancy of Korobov’s \(p\) -sets. Proc. Amer. Math. Soc. (2014) (Submitted)
  13. Doerr, B.: A lower bound for the discrepancy of a random point set. J. Complex. 30, 16-0 (2014) CrossRef
  14. Doerr, B., Gnewuch, M.: Construction of low-discrepancy point sets of small size by bracketing covers and dependent randomized rounding. In: Keller, A., Heinrich, S., Niederreiter, H. (eds.) Monte Carlo and Quasi-Monte Carlo Methods 2006, pp. 299-12. Springer, Berlin (2007)
  15. Doerr, B., Gnewuch, M., Srivastav, A.: Bounds and constructions for the star-discrepancy via \(\delta \) -covers. J. Complex. 21, 691-09 (2005) CrossRef
  16. Doerr, B., Gnewuch, M., Kritzer, P., Pillichshammer, F.: Component-by-component construction of low-discrepancy point sets of small size. Monte Carlo Methods Appl. 14, 129-49 (2008) CrossRef
  17. Doerr, B., Gnewuch, M., Wahlstr?m, M.: Algorithmic construction of low-discrepancy point sets via dependent randomized rounding. J. Complex. 26, 490-07 (2010) CrossRef
  18. Gnewuch, M., Wahlstr?m, M., Winzen, C.: A n
• 作者单位：Josef Dick (15)
  Friedrich Pillichshammer (16)
  
  15. School of Mathematics and Statistics, The University of New South Wales, Sydney, NSW, Australia
  16. Department of Financial Mathematics, Johannes Kepler University, Linz, Austria
  
• ISSN：1611-3349

文摘

The inverse of the star-discrepancy problem asks for point sets \(P_{N,s}\) of size \(N\) in the \(s\) -dimensional unit cube \([0,1]^s\) whose star-discrepancy \(D_N^*(P_{N,s})\) satisfies $$D_N^*(P_{N,s}) \le C \sqrt{s/N},$$ where \(C> 0\) is a constant independent of \(N\) and \(s\) . The first existence results in this direction were shown by Heinrich, Novak, Wasilkowski, and Wo?niakowski in 2001, and a number of improvements have been shown since then. Until now only proofs that such point sets exist are known. Since such point sets would be useful in applications, the big open problem is to find explicit constructions of suitable point sets \(P_{N,s}\) . We review the current state of the art on this problem and point out some connections to pseudo-random number generators.