Coverage for /pythoncovmergedfiles/medio/medio/usr/local/lib/python3.8/site-packages/scipy/stats/qmc.py: 100%

1# -*- coding: utf-8 -*- 

2r""" 

3==================================================== 

4Quasi-Monte Carlo submodule (:mod:`scipy.stats.qmc`) 

5==================================================== 

6 

7.. currentmodule:: scipy.stats.qmc 

8 

9This module provides Quasi-Monte Carlo generators and associated helper 

10functions. 

11 

12 

13Quasi-Monte Carlo 

14================= 

15 

16Engines 

17------- 

18 

19.. autosummary:: 

20 :toctree: generated/ 

21 

22 QMCEngine 

23 Sobol 

24 Halton 

25 LatinHypercube 

26 PoissonDisk 

27 MultinomialQMC 

28 MultivariateNormalQMC 

29 

30Helpers 

31------- 

32 

33.. autosummary:: 

34 :toctree: generated/ 

35 

36 discrepancy 

37 update_discrepancy 

38 scale 

39 

40 

41Introduction to Quasi-Monte Carlo 

42================================= 

43 

44Quasi-Monte Carlo (QMC) methods [1]_, [2]_, [3]_ provide an 

45:math:`n \times d` array of numbers in :math:`[0,1]`. They can be used in 

46place of :math:`n` points from the :math:`U[0,1]^{d}` distribution. Compared to 

47random points, QMC points are designed to have fewer gaps and clumps. This is 

48quantified by discrepancy measures [4]_. From the Koksma-Hlawka 

49inequality [5]_ we know that low discrepancy reduces a bound on 

50integration error. Averaging a function :math:`f` over :math:`n` QMC points 

51can achieve an integration error close to :math:`O(n^{-1})` for well 

52behaved functions [2]_. 

53 

54Most QMC constructions are designed for special values of :math:`n` 

55such as powers of 2 or large primes. Changing the sample 

56size by even one can degrade their performance, even their 

57rate of convergence [6]_. For instance :math:`n=100` points may give less 

58accuracy than :math:`n=64` if the method was designed for :math:`n=2^m`. 

59 

60Some QMC constructions are extensible in :math:`n`: we can find 

61another special sample size :math:`n' > n` and often an infinite 

62sequence of increasing special sample sizes. Some QMC 

63constructions are extensible in :math:`d`: we can increase the dimension, 

64possibly to some upper bound, and typically without requiring 

65special values of :math:`d`. Some QMC methods are extensible in 

66both :math:`n` and :math:`d`. 

67 

68QMC points are deterministic. That makes it hard to estimate the accuracy of 

69integrals estimated by averages over QMC points. Randomized QMC (RQMC) [7]_ 

70points are constructed so that each point is individually :math:`U[0,1]^{d}` 

71while collectively the :math:`n` points retain their low discrepancy. 

72One can make :math:`R` independent replications of RQMC points to 

73see how stable a computation is. From :math:`R` independent values, 

74a t-test (or bootstrap t-test [8]_) then gives approximate confidence 

75intervals on the mean value. Some RQMC methods produce a 

76root mean squared error that is actually :math:`o(1/n)` and smaller than 

77the rate seen in unrandomized QMC. An intuitive explanation is 

78that the error is a sum of many small ones and random errors 

79cancel in a way that deterministic ones do not. RQMC also 

80has advantages on integrands that are singular or, for other 

81reasons, fail to be Riemann integrable. 

82 

83(R)QMC cannot beat Bahkvalov's curse of dimension (see [9]_). For 

84any random or deterministic method, there are worst case functions 

85that will give it poor performance in high dimensions. A worst 

86case function for QMC might be 0 at all n points but very 

87large elsewhere. Worst case analyses get very pessimistic 

88in high dimensions. (R)QMC can bring a great improvement over 

89MC when the functions on which it is used are not worst case. 

90For instance (R)QMC can be especially effective on integrands 

91that are well approximated by sums of functions of 

92some small number of their input variables at a time [10]_, [11]_. 

93That property is often a surprising finding about those functions. 

94 

95Also, to see an improvement over IID MC, (R)QMC requires a bit of smoothness of 

96the integrand, roughly the mixed first order derivative in each direction, 

97:math:`\partial^d f/\partial x_1 \cdots \partial x_d`, must be integral. 

98For instance, a function that is 1 inside the hypersphere and 0 outside of it 

99has infinite variation in the sense of Hardy and Krause for any dimension 

100:math:`d = 2`. 

101 

102Scrambled nets are a kind of RQMC that have some valuable robustness 

103properties [12]_. If the integrand is square integrable, they give variance 

104:math:`var_{SNET} = o(1/n)`. There is a finite upper bound on 

105:math:`var_{SNET} / var_{MC}` that holds simultaneously for every square 

106integrable integrand. Scrambled nets satisfy a strong law of large numbers 

107for :math:`f` in :math:`L^p` when :math:`p>1`. In some 

108special cases there is a central limit theorem [13]_. For smooth enough 

109integrands they can achieve RMSE nearly :math:`O(n^{-3})`. See [12]_ 

110for references about these properties. 

111 

112The main kinds of QMC methods are lattice rules [14]_ and digital 

113nets and sequences [2]_, [15]_. The theories meet up in polynomial 

114lattice rules [16]_ which can produce digital nets. Lattice rules 

115require some form of search for good constructions. For digital 

116nets there are widely used default constructions. 

117 

118The most widely used QMC methods are Sobol' sequences [17]_. 

119These are digital nets. They are extensible in both :math:`n` and :math:`d`. 

120They can be scrambled. The special sample sizes are powers 

121of 2. Another popular method are Halton sequences [18]_. 

122The constructions resemble those of digital nets. The earlier 

123dimensions have much better equidistribution properties than 

124later ones. There are essentially no special sample sizes. 

125They are not thought to be as accurate as Sobol' sequences. 

126They can be scrambled. The nets of Faure [19]_ are also widely 

127used. All dimensions are equally good, but the special sample 

128sizes grow rapidly with dimension :math:`d`. They can be scrambled. 

129The nets of Niederreiter and Xing [20]_ have the best asymptotic 

130properties but have not shown good empirical performance [21]_. 

131 

132Higher order digital nets are formed by a digit interleaving process 

133in the digits of the constructed points. They can achieve higher 

134levels of asymptotic accuracy given higher smoothness conditions on :math:`f` 

135and they can be scrambled [22]_. There is little or no empirical work 

136showing the improved rate to be attained. 

137 

138Using QMC is like using the entire period of a small random 

139number generator. The constructions are similar and so 

140therefore are the computational costs [23]_. 

141 

142(R)QMC is sometimes improved by passing the points through 

143a baker's transformation (tent function) prior to using them. 

144That function has the form :math:`1-2|x-1/2|`. As :math:`x` goes from 0 to 

1451, this function goes from 0 to 1 and then back. It is very 

146useful to produce a periodic function for lattice rules [14]_, 

147and sometimes it improves the convergence rate [24]_. 

148 

149It is not straightforward to apply QMC methods to Markov 

150chain Monte Carlo (MCMC). We can think of MCMC as using 

151:math:`n=1` point in :math:`[0,1]^{d}` for very large :math:`d`, with 

152ergodic results corresponding to :math:`d \to \infty`. One proposal is 

153in [25]_ and under strong conditions an improved rate of convergence 

154has been shown [26]_. 

155 

156Returning to Sobol' points: there are many versions depending 

157on what are called direction numbers. Those are the result of 

158searches and are tabulated. A very widely used set of direction 

159numbers come from [27]_. It is extensible in dimension up to 

160:math:`d=21201`. 

161 

162References 

163---------- 

164.. [1] Owen, Art B. "Monte Carlo Book: the Quasi-Monte Carlo parts." 2019. 

165.. [2] Niederreiter, Harald. "Random number generation and quasi-Monte Carlo 

166 methods." Society for Industrial and Applied Mathematics, 1992. 

167.. [3] Dick, Josef, Frances Y. Kuo, and Ian H. Sloan. "High-dimensional 

168 integration: the quasi-Monte Carlo way." Acta Numerica no. 22: 133, 2013. 

169.. [4] Aho, A. V., C. Aistleitner, T. Anderson, K. Appel, V. Arnol'd, N. 

170 Aronszajn, D. Asotsky et al. "W. Chen et al.(eds.), "A Panorama of 

171 Discrepancy Theory", Sringer International Publishing, 

172 Switzerland: 679, 2014. 

173.. [5] Hickernell, Fred J. "Koksma-Hlawka Inequality." Wiley StatsRef: 

174 Statistics Reference Online, 2014. 

175.. [6] Owen, Art B. "On dropping the first Sobol' point." :arxiv:`2008.08051`, 

176 2020. 

177.. [7] L'Ecuyer, Pierre, and Christiane Lemieux. "Recent advances in randomized 

178 quasi-Monte Carlo methods." In Modeling uncertainty, pp. 419-474. Springer, 

179 New York, NY, 2002. 

180.. [8] DiCiccio, Thomas J., and Bradley Efron. "Bootstrap confidence 

181 intervals." Statistical science: 189-212, 1996. 

182.. [9] Dimov, Ivan T. "Monte Carlo methods for applied scientists." World 

183 Scientific, 2008. 

184.. [10] Caflisch, Russel E., William J. Morokoff, and Art B. Owen. "Valuation 

185 of mortgage backed securities using Brownian bridges to reduce effective 

186 dimension." Journal of Computational Finance: no. 1 27-46, 1997. 

187.. [11] Sloan, Ian H., and Henryk Wozniakowski. "When are quasi-Monte Carlo 

188 algorithms efficient for high dimensional integrals?." Journal of Complexity 

189 14, no. 1 (1998): 1-33. 

190.. [12] Owen, Art B., and Daniel Rudolf, "A strong law of large numbers for 

191 scrambled net integration." SIAM Review, to appear. 

192.. [13] Loh, Wei-Liem. "On the asymptotic distribution of scrambled net 

193 quadrature." The Annals of Statistics 31, no. 4: 1282-1324, 2003. 

194.. [14] Sloan, Ian H. and S. Joe. "Lattice methods for multiple integration." 

195 Oxford University Press, 1994. 

196.. [15] Dick, Josef, and Friedrich Pillichshammer. "Digital nets and sequences: 

197 discrepancy theory and quasi-Monte Carlo integration." Cambridge University 

198 Press, 2010. 

199.. [16] Dick, Josef, F. Kuo, Friedrich Pillichshammer, and I. Sloan. 

200 "Construction algorithms for polynomial lattice rules for multivariate 

201 integration." Mathematics of computation 74, no. 252: 1895-1921, 2005. 

202.. [17] Sobol', Il'ya Meerovich. "On the distribution of points in a cube and 

203 the approximate evaluation of integrals." Zhurnal Vychislitel'noi Matematiki 

204 i Matematicheskoi Fiziki 7, no. 4: 784-802, 1967. 

205.. [18] Halton, John H. "On the efficiency of certain quasi-random sequences of 

206 points in evaluating multi-dimensional integrals." Numerische Mathematik 2, 

207 no. 1: 84-90, 1960. 

208.. [19] Faure, Henri. "Discrepance de suites associees a un systeme de 

209 numeration (en dimension s)." Acta arithmetica 41, no. 4: 337-351, 1982. 

210.. [20] Niederreiter, Harold, and Chaoping Xing. "Low-discrepancy sequences and 

211 global function fields with many rational places." Finite Fields and their 

212 applications 2, no. 3: 241-273, 1996. 

213.. [21] Hong, Hee Sun, and Fred J. Hickernell. "Algorithm 823: Implementing 

214 scrambled digital sequences." ACM Transactions on Mathematical Software 

215 (TOMS) 29, no. 2: 95-109, 2003. 

216.. [22] Dick, Josef. "Higher order scrambled digital nets achieve the optimal 

217 rate of the root mean square error for smooth integrands." The Annals of 

218 Statistics 39, no. 3: 1372-1398, 2011. 

219.. [23] Niederreiter, Harald. "Multidimensional numerical integration using 

220 pseudorandom numbers." In Stochastic Programming 84 Part I, pp. 17-38. 

221 Springer, Berlin, Heidelberg, 1986. 

222.. [24] Hickernell, Fred J. "Obtaining O (N-2+e) Convergence for Lattice 

223 Quadrature Rules." In Monte Carlo and Quasi-Monte Carlo Methods 2000, 

224 pp. 274-289. Springer, Berlin, Heidelberg, 2002. 

225.. [25] Owen, Art B., and Seth D. Tribble. "A quasi-Monte Carlo Metropolis 

226 algorithm." Proceedings of the National Academy of Sciences 102, 

227 no. 25: 8844-8849, 2005. 

228.. [26] Chen, Su. "Consistency and convergence rate of Markov chain quasi Monte 

229 Carlo with examples." PhD diss., Stanford University, 2011. 

230.. [27] Joe, Stephen, and Frances Y. Kuo. "Constructing Sobol sequences with 

231 better two-dimensional projections." SIAM Journal on Scientific Computing 

232 30, no. 5: 2635-2654, 2008. 

233 

234""" 

235from ._qmc import *