On probabilistic results for the discrepancy of a hybrid-Monte Carlo sequence
In many applications it has been observed that hybrid-Monte Carlo sequences perform better than Monte Carlo and quasi-Monte Carlo sequences, especially in difficult problems. For a mixed s-dimensional sequence m, whose elements are vectors obtained by concatenating d-dimensional vectors from a low-discrepancy sequence q with (s - d)-dimensional random vectors, probabilistic upper bounds for its star discrepancy have been provided. In a paper of G. Okten, B. Tuffin and V. Burago [G. Okten, B. Tuffin, V. Burago, J. Complexity 22 (2006), 435-458] it was shown that for arbitrary epsilon > 0 the difference of the star discrepancies of the first N points of m and q is bounded by F with probability at least 1 - 2exp(-epsilon(2) N/2) for N sufficiently large. The authors did not study how large N actually has to be and if and how this actually depends on the parameters s and F. In this note we derive a lower bound for N, which significantly depends on s and epsilon. Furthermore, we provide a probabilistic bound for the difference of the star discrepancies of the first N points of m and q, which holds without any restrictions on N. In this sense it improves on the bound of Okten, Tuffin and Burago and is more helpful in practice, especially for small sample sizes N. We compare this bound to other known bounds. (C) 2009 Elsevier Inc. All rights reserved.
monte carlo low-discrepancy sequences star discrepancy probabilistic bounds quasi monte-carlo padding mixed sequences hybrid methods