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 ss-dimensional sequence mm, whose elements are vectors obtained by concatenating dd-dimensional vectors from a low-discrepancy sequence qq with (s−d)(s−d)-dimensional random vectors, probabilistic upper bounds for its star discrepancy have been provided. In a paper of G. Ökten, B. Tuffin and V. Burago [G. Ökten, B. Tuffin, V. Burago, J. Complexity 22 (2006), 435–458] it was shown that for arbitrary ε>0ε>0 the difference of the star discrepancies of the first NN points of mm and qq is bounded by εε with probability at least 1−2exp(−ε2N/2)1−2exp(−ε2N/2) for NN sufficiently large. The authors did not study how large NN actually has to be and if and how this actually depends on the parameters ss and εε. In this note we derive a lower bound for NN, which significantly depends on ss and εε. Furthermore, we provide a probabilistic bound for the difference of the star discrepancies of the first NN points of mm and qq, which holds without any restrictions on NN. In this sense it improves on the bound of Ökten, Tuffin and Burago and is more helpful in practice, especially for small sample sizes NN. We compare this bound to other known bounds.