Lattice rules with random n achieve nearly the optimal O(n−α−1/2) error independently of the dimension

We analyze a random algorithm for numerical integration of d-variate functions from weighted Sobolev spaces with dominating mixed smoothness α ≥ 0 and product weights 1 ≥ γ1 ≥ γ2 ≥ ... > 0. The algorithm is based on rank-1 lattice rules with a random number of points n. For the case α > 1/2, we prove that the algorithm achieves almost the optimal order of convergence of O(n−α−1/2), where the implied constant is independent of d if the weights satisfy sum j=1 ∞ γj 1/α < ∞. The same rate of convergence holds for the more general case α > 0 by adding a random shift to the lattice rule with random n. This shows, in particular, that the exponent of strong tractability in the randomized setting equals 1/(α+1/2), if the weights decay fast enough. We obtain a lower bound to indicate that our results are essentially optimal.