  We provide lower error bounds for randomized algorithms that approximate
integrals of functions depending on an unrestricted or even infinite number of
variables. More precisely, we consider the infinite-dimensional integration
problem on weighted Hilbert spaces with an underlying anchored decomposition
and arbitrary weights. We focus on randomized algorithms and the randomized
worst case error. We study two cost models for function evaluation which depend
on the number of active variables of the chosen sample points. Multilevel
algorithms behave very well with respect to the first cost model, while
changing dimension algorithms and also dimension-wise quadrature methods, which
are based on a similar idea, can take advantage of the more generous second
cost model. We prove the first non-trivial lower error bounds for randomized
algorithms in these cost models and demonstrate their quality in the case of
product weights. In particular, we show that the randomized changing dimension
algorithms provided in [L. Plaskota, G. W. Wasilkowski, J. Complexity 27
(2011), 505--518] achieve convergence rates arbitrarily close to the optimal
convergence rate.
