Service interruption on Monday 11 July from 12:30 to 13:00: all the sites of the CCSD (HAL, Epiciences, SciencesConf, AureHAL) will be inaccessible (network hardware connection).
Skip to Main content Skip to Navigation
Journal articles

Comment on "Sequential Quasi-Monte Carlo Sampling"

Abstract : Gerber and Chopin combine SMC with RQMC to accelerate convergence. They apply RQMC as in the array-RQMC method discussed below, for which convergence rate theory remains thin despite impressive empirical performance. Their proof of o(N −1/2) convergence rate is a remarkable contribution. Array-RQMC simulates an array of N dependent realizations of a Markov chain, using RQMC so the distribution of the N states has low discrepancy D t with respect to its theoretical distribution, at any step t. If x t = Γ t (x t−1 , u t), where x t−1 ∼ U([0, 1)) and u t ∼ U([0, 1) d), array-RQMC approximates the (+ d)-dimensional integral E[D t ], using N RQMC points. It matches each state to a point whose first coordinates are near that point, and uses the next d coordinates for u t. The matching step is crucial. If = 1, just sort the states and points by their (increasing) first coordinate. If > 1, one can map the states x t ∈ [0, 1) → [0, 1), then proceed as for = 1. Gerber and Chopin do exactly this, using a Hilbert curve mapping. But the map [0, 1) → [0, 1) is not essential. E.g., if = 2, one can sort the states and the points in N −1/2 groups of size N −1/2 by their first coordinate, then sort each group by the second coordinate. This extends to > 2. With this multivariate sort, L'Ecuyer et al. (2009) observed an O(N −2) variance when pricing an Asian option with array-RQMC. I wonder what rate the Hilbert curve map can achieve for this example. When X ⊆ R instead of [0, 1) , Gerber and Chopin map x t → [0, 1) using a logistic transformation. The choice of transformation and its parameters may have a significant impact on the overall convergence. For the multivariate sort, no transformation is needed, it works directly in R. The Hilbert sort could also be adapted to work directly in R .
Document type :
Journal articles
Complete list of metadata

Cited literature [2 references]  Display  Hide  Download
Contributor : Bruno Tuffin Connect in order to contact the contributor
Submitted on : Tuesday, December 8, 2015 - 5:14:59 PM
Last modification on : Thursday, January 20, 2022 - 4:19:57 PM
Long-term archiving on: : Wednesday, March 9, 2016 - 3:40:42 PM


Files produced by the author(s)


  • HAL Id : hal-01240158, version 1


Pierre L'Ecuyer. Comment on "Sequential Quasi-Monte Carlo Sampling". Journal of the Royal Statistical Society: Series B, Royal Statistical Society, 2015. ⟨hal-01240158⟩



Record views


Files downloads