On probabilistic results for the discrepancy of a hybrid-Monte Carlo sequence
On probabilistic results for the discrepancy of a hybrid-Monte Carlo sequence
复制标题
关于混合蒙特卡罗序列差异的概率结果
DOI：
10.1016/j.jco.2009.02.009
复制
发表时间：
2009
期刊：
影响因子：
--
通讯作者：
M. Gnewuch
中科院分区：
文献类型：
--
作者：
M. Gnewuch
在许多应用中，已经观察到混合蒙特卡罗序列比蒙特卡罗和准蒙特卡罗序列表现得更好，特别是在困难的问题中。对于混合的S维序列m，其元素是由低偏差序列q的d维向量与(S−d)维随机向量串联得到的向量，给出了它的星差的概率上界。在G.Okten，B.Tuffin和V.Burago的一篇论文[G.Okten，B.Tuffin，V.Burago，J.Complex 22(2006)，435-458]中，证明了对于任意ε>；0，m和q的前N个点的星差之差的差有界于ε，当N足够大时，概率至少为1−2exp(−ε2N/2)。作者没有研究N到底有多大，以及这实际上是否以及如何取决于S和ε的参数。在这篇注记中，我们得到了N的一个下界，它在很大程度上取决于S和ε。此外，我们还给出了m和q的前N个点的星差之差的一个概率界，该界在没有对N的任何限制的情况下成立。从这个意义上说，它改进了Ökten、Tuffin和Burago的界，并且在实践中更有帮助，特别是对于小样本数N。
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. Ö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 the difference of the star discrepancies of the first N points of m and q is bounded by ε with probability at least 1−2exp(−ε2N/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 ε. In this note we derive a lower bound for N, which significantly depends on s and ε. 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 Ökten, Tuffin and Burago and is more helpful in practice, especially for small sample sizes N. We compare this bound to other known bounds.