OpenTURNS
Quasi Monte Carlo¶
Let us note
.
The goal is to estimate the following probability:
.
The goal is to estimate the following probability:(1)¶
Quasi-Monte Carlo is a technique which approximates the integral
(1) using low discrepancy sequences
instead of randomly generated
sequences, as follows:
instead of randomly generated
sequences, as follows:
In general, the integral of a function 
on
![\Delta = [0,1]^s](data:image/svg+xml;base64,PD94bWwgdmVyc2lvbj0nMS4wJyBlbmNvZGluZz0nVVRGLTgnPz4KPCEtLSBUaGlzIGZpbGUgd2FzIGdlbmVyYXRlZCBieSBkdmlzdmdtIDMuMyAtLT4KPHN2ZyB2ZXJzaW9uPScxLjEnIHhtbG5zPSdodHRwOi8vd3d3LnczLm9yZy8yMDAwL3N2ZycgeG1sbnM6eGxpbms9J2h0dHA6Ly93d3cudzMub3JnLzE5OTkveGxpbmsnIHdpZHRoPSc1Mi44NzA2NzRwdCcgaGVpZ2h0PScxMS45NTUxNjhwdCcgdmlld0JveD0nMCAtOC45NjYzNzYgNTIuODcwNjc0IDExLjk1NTE2OCc+CjxkZWZzPgo8cGF0aCBpZD0nZzAtMTE1JyBkPSdNMy4yMTE5NTUtMi45OTY3NjJDMy4wMjg2NDMtMi45NjQ4ODIgMi44NjEyNy0yLjgyMTQyIDIuODYxMjctMi42MjIxNjdDMi44NjEyNy0yLjQ3ODcwNSAyLjk1NjkxMi0yLjM3NTA5MyAzLjEzMjI1NC0yLjM3NTA5M0MzLjI1MTgwNi0yLjM3NTA5MyAzLjQ5ODg3OS0yLjQ2Mjc2NSAzLjQ5ODg3OS0yLjgyMTQyQzMuNDk4ODc5LTMuMzE1NTY3IDIuOTgwODIyLTMuNTE0ODE5IDIuNDg2Njc1LTMuNTE0ODE5QzEuNDE4NjgtMy41MTQ4MTkgMS4wODM5MzUtMi43NTc2NTkgMS4wODM5MzUtMi4zNTExODNDMS4wODM5MzUtMi4yNzE0ODIgMS4wODM5MzUtMS45ODQ1NTggMS4zNzg4MjktMS43NjEzOTVDMS41NjIxNDItMS42MTc5MzMgMS42OTc2MzQtMS41OTQwMjIgMi4xMTIwOC0xLjUxNDMyMUMyLjM5MTAzNC0xLjQ1ODUzMSAyLjg0NTMzLTEuMzc4ODI5IDIuODQ1MzMtLjk2NDM4NEMyLjg0NTMzLS43NTcxNjEgMi42OTM4OTgtLjQ5NDE0NyAyLjQ3MDczNS0uMzQyNzE1QzIuMTc1ODQxLS4xNTE0MzIgMS43ODUzMDUtLjE0MzQ2MiAxLjY1Nzc4My0uMTQzNDYyQzEuNDY2NTAxLS4xNDM0NjIgLjkyNDUzMy0uMTc1MzQyIC43MjUyOC0uNDk0MTQ3QzEuMTMxNzU2LS41MTAwODcgMS4xODc1NDctLjgzNjg2MiAxLjE4NzU0Ny0uOTMyNTAzQzEuMTg3NTQ3LTEuMTcxNjA2IC45NzIzNTQtMS4yMjczOTcgLjg3NjcxMi0xLjIyNzM5N0MuNzQ5MTkxLTEuMjI3Mzk3IC40MjI0MTYtMS4xMzE3NTYgLjQyMjQxNi0uNjkzNEMuNDIyNDE2LS4yMjMxNjMgLjkxNjU2MyAuMDc5NzAxIDEuNjU3NzgzIC4wNzk3MDFDMy4wNDQ1ODMgLjA3OTcwMSAzLjMzOTQ3Ny0uOTAwNjIzIDMuMzM5NDc3LTEuMjM1MzY3QzMuMzM5NDc3LTEuOTUyNjc3IDIuNTU4NDA2LTIuMTA0MTEgMi4yNjM1MTItMi4xNTk5QzEuODgwOTQ2LTIuMjMxNjMxIDEuNTcwMTEyLTIuMjg3NDIyIDEuNTcwMTEyLTIuNjIyMTY3QzEuNTcwMTEyLTIuNzY1NjI5IDEuNzA1NjA0LTMuMjkxNjU2IDIuNDc4NzA1LTMuMjkxNjU2QzIuNzgxNTY5LTMuMjkxNjU2IDMuMDkyNDAzLTMuMjAzOTg1IDMuMjExOTU1LTIuOTk2NzYyWicvPgo8cGF0aCBpZD0nZzEtNTknIGQ9J00yLjMzMTI1OCAuMDQ3ODIxQzIuMzMxMjU4LS42NDU1NzkgMi4xMDQxMS0xLjE1OTY1MSAxLjYxMzk0OC0xLjE1OTY1MUMxLjIzMTM4Mi0xLjE1OTY1MSAxLjA0MDEtLjg0ODgxNyAxLjA0MDEtLjU4NTgwM1MxLjIxOTQyNyAwIDEuNjI1OTAzIDBDMS43ODEzMiAwIDEuOTEyODI3LS4wNDc4MjEgMi4wMjA0MjMtLjE1NTQxN0MyLjA0NDMzNC0uMTc5MzI4IDIuMDU2Mjg5LS4xNzkzMjggMi4wNjgyNDQtLjE3OTMyOEMyLjA5MjE1NC0uMTc5MzI4IDIuMDkyMTU0LS4wMTE5NTUgMi4wOTIxNTQgLjA0NzgyMUMyLjA5MjE1NCAuNDQyMzQxIDIuMDIwNDIzIDEuMjE5NDI3IDEuMzI3MDI0IDEuOTk2NTEzQzEuMTk1NTE3IDIuMTM5OTc1IDEuMTk1NTE3IDIuMTYzODg1IDEuMTk1NTE3IDIuMTg3Nzk2QzEuMTk1NTE3IDIuMjQ3NTcyIDEuMjU1MjkzIDIuMzA3MzQ3IDEuMzE1MDY4IDIuMzA3MzQ3QzEuNDEwNzEgMi4zMDczNDcgMi4zMzEyNTggMS40MjI2NjUgMi4zMzEyNTggLjA0NzgyMVonLz4KPHBhdGggaWQ9J2cyLTEnIGQ9J001LjE1MjY3Ny04LjMyMDc5N0M1LjA2ODk5MS04LjQ4ODE2OSA1LjA0NTA4MS04LjUzNTk5IDQuODc3NzA5LTguNTM1OTlDNC42OTgzODEtOC41MzU5OSA0LjY3NDQ3MS04LjQ4ODE2OSA0LjU5MDc4NS04LjMyMDc5N0wuNTk3NzU4LS4yMzkxMDNDLjU3Mzg0OC0uMjAzMjM4IC41NDk5MzgtLjEzMTUwNyAuNTQ5OTM4LS4wODM2ODZDLjU0OTkzOC0uMDExOTU1IC41NjE4OTMgMCAuODAwOTk2IDBIOC45NDI0NjZDOS4xODE1NjkgMCA5LjE5MzUyNC0uMDExOTU1IDkuMTkzNTI0LS4wODM2ODZDOS4xOTM1MjQtLjEzMTUwNyA5LjE2OTYxNC0uMjAzMjM4IDkuMTQ1NzA0LS4yMzkxMDNMNS4xNTI2NzctOC4zMjA3OTdaTTQuNTA3MDk4LTcuNDM2MTE1TDcuNzcwODU5LS44MjQ5MDdIMS4yNTUyOTNMNC41MDcwOTgtNy40MzYxMTVaJy8+CjxwYXRoIGlkPSdnMi00OCcgZD0nTTUuMzU1OTE1LTMuODI1NjU0QzUuMzU1OTE1LTQuODE3OTMzIDUuMjk2MTM5LTUuNzg2MzAxIDQuODY1NzUzLTYuNjk0ODk0QzQuMzc1NTkyLTcuNjg3MTczIDMuNTE0ODE5LTcuOTUwMTg3IDIuOTI5MDE2LTcuOTUwMTg3QzIuMjM1NjE2LTcuOTUwMTg3IDEuMzg2OC03LjYwMzQ4NyAuOTQ0NDU4LTYuNjExMjA4Qy42MDk3MTQtNS44NTgwMzIgLjQ5MDE2Mi01LjExNjgxMiAuNDkwMTYyLTMuODI1NjU0Qy40OTAxNjItMi42NjYwMDIgLjU3Mzg0OC0xLjc5MzI3NSAxLjAwNDIzNC0uOTQ0NDU4QzEuNDcwNDg2LS4wMzU4NjYgMi4yOTUzOTIgLjI1MTA1OSAyLjkxNzA2MSAuMjUxMDU5QzMuOTU3MTYxIC4yNTEwNTkgNC41NTQ5MTktLjM3MDYxIDQuOTAxNjE5LTEuMDY0MDFDNS4zMzIwMDUtMS45NjA2NDggNS4zNTU5MTUtMy4xMzIyNTQgNS4zNTU5MTUtMy44MjU2NTRaTTIuOTE3MDYxIC4wMTE5NTVDMi41MzQ0OTYgLjAxMTk1NSAxLjc1NzQxLS4yMDMyMzggMS41MzAyNjItMS41MDYzNTFDMS4zOTg3NTUtMi4yMjM2NjEgMS4zOTg3NTUtMy4xMzIyNTQgMS4zOTg3NTUtMy45NjkxMTZDMS4zOTg3NTUtNC45NDk0NCAxLjM5ODc1NS01LjgzNDEyMiAxLjU5MDAzNy02LjUzOTQ3N0MxLjc5MzI3NS03LjM0MDQ3MyAyLjQwMjk4OS03LjcxMTA4MyAyLjkxNzA2MS03LjcxMTA4M0MzLjM3MTM1Ny03LjcxMTA4MyA0LjA2NDc1Ny03LjQzNjExNSA0LjI5MTkwNS02LjQwNzk3QzQuNDQ3MzIzLTUuNzI2NTI2IDQuNDQ3MzIzLTQuNzgyMDY3IDQuNDQ3MzIzLTMuOTY5MTE2QzQuNDQ3MzIzLTMuMTY4MTIgNC40NDczMjMtMi4yNTk1MjcgNC4zMTU4MTYtMS41MzAyNjJDNC4wODg2NjctLjIxNTE5MyAzLjMzNTQ5MiAuMDExOTU1IDIuOTE3MDYxIC4wMTE5NTVaJy8+CjxwYXRoIGlkPSdnMi00OScgZD0nTTMuNDQzMDg4LTcuNjYzMjYzQzMuNDQzMDg4LTcuOTM4MjMyIDMuNDQzMDg4LTcuOTUwMTg3IDMuMjAzOTg1LTcuOTUwMTg3QzIuOTE3MDYxLTcuNjI3Mzk3IDIuMzE5MzAzLTcuMTg1MDU2IDEuMDg3OTItNy4xODUwNTZWLTYuODM4MzU2QzEuMzYyODg5LTYuODM4MzU2IDEuOTYwNjQ4LTYuODM4MzU2IDIuNjE4MTgyLTcuMTQ5MTkxVi0uOTIwNTQ4QzIuNjE4MTgyLS40OTAxNjIgMi41ODIzMTYtLjM0NjcgMS41MzAyNjItLjM0NjdIMS4xNTk2NTFWMEMxLjQ4MjQ0MS0uMDIzOTEgMi42NDIwOTItLjAyMzkxIDMuMDM2NjEzLS4wMjM5MVM0LjU3ODgyOS0uMDIzOTEgNC45MDE2MTkgMFYtLjM0NjdINC41MzEwMDlDMy40Nzg5NTQtLjM0NjcgMy40NDMwODgtLjQ5MDE2MiAzLjQ0MzA4OC0uOTIwNTQ4Vi03LjY2MzI2M1onLz4KPHBhdGggaWQ9J2cyLTYxJyBkPSdNOC4wNjk3MzgtMy44NzM0NzRDOC4yMzcxMTEtMy44NzM0NzQgOC40NTIzMDQtMy44NzM0NzQgOC40NTIzMDQtNC4wODg2NjdDOC40NTIzMDQtNC4zMTU4MTYgOC4yNDkwNjYtNC4zMTU4MTYgOC4wNjk3MzgtNC4zMTU4MTZIMS4wMjgxNDRDLjg2MDc3Mi00LjMxNTgxNiAuNjQ1NTc5LTQuMzE1ODE2IC42NDU1NzktNC4xMDA2MjNDLjY0NTU3OS0zLjg3MzQ3NCAuODQ4ODE3LTMuODczNDc0IDEuMDI4MTQ0LTMuODczNDc0SDguMDY5NzM4Wk04LjA2OTczOC0xLjY0OTgxM0M4LjIzNzExMS0xLjY0OTgxMyA4LjQ1MjMwNC0xLjY0OTgxMyA4LjQ1MjMwNC0xLjg2NTAwNkM4LjQ1MjMwNC0yLjA5MjE1NCA4LjI0OTA2Ni0yLjA5MjE1NCA4LjA2OTczOC0yLjA5MjE1NEgxLjAyODE0NEMuODYwNzcyLTIuMDkyMTU0IC42NDU1NzktMi4wOTIxNTQgLjY0NTU3OS0xLjg3Njk2MUMuNjQ1NTc5LTEuNjQ5ODEzIC44NDg4MTctMS42NDk4MTMgMS4wMjgxNDQtMS42NDk4MTNIOC4wNjk3MzhaJy8+CjxwYXRoIGlkPSdnMi05MScgZD0nTTIuOTg4NzkyIDIuOTg4NzkyVjIuNTQ2NDUxSDEuODI5MTQxVi04LjUyNDAzNUgyLjk4ODc5MlYtOC45NjYzNzZIMS4zODY4VjIuOTg4NzkySDIuOTg4NzkyWicvPgo8cGF0aCBpZD0nZzItOTMnIGQ9J00xLjg1MzA1MS04Ljk2NjM3NkguMjUxMDU5Vi04LjUyNDAzNUgxLjQxMDcxVjIuNTQ2NDUxSC4yNTEwNTlWMi45ODg3OTJIMS44NTMwNTFWLTguOTY2Mzc2WicvPgo8L2RlZnM+CjxnIGlkPSdwYWdlMSc+Cjx1c2UgeD0nMCcgeT0nMCcgeGxpbms6aHJlZj0nI2cyLTEnLz4KPHVzZSB4PScxMy4wNzU4MTMnIHk9JzAnIHhsaW5rOmhyZWY9JyNnMi02MScvPgo8dXNlIHg9JzI1LjUwMTI5NCcgeT0nMCcgeGxpbms6aHJlZj0nI2cyLTkxJy8+Cjx1c2UgeD0nMjguNzUyOTU1JyB5PScwJyB4bGluazpocmVmPScjZzItNDgnLz4KPHVzZSB4PSczNC42MDU5NDUnIHk9JzAnIHhsaW5rOmhyZWY9JyNnMS01OScvPgo8dXNlIHg9JzM5Ljg1MDEwNCcgeT0nMCcgeGxpbms6aHJlZj0nI2cyLTQ5Jy8+Cjx1c2UgeD0nNDUuNzAzMDk1JyB5PScwJyB4bGluazpocmVmPScjZzItOTMnLz4KPHVzZSB4PSc0OC45NTQ3NTYnIHk9Jy00LjMzODQzNycgeGxpbms6aHJlZj0nI2cwLTExNScvPgo8L2c+Cjwvc3ZnPgo8IS0tIERFUFRIPTQgLS0+)
can be approximated by using some low
discrepancy sequence 
as
follows:
on
can be approximated by using some low
discrepancy sequence as
follows:
The low discrepancy sequence is generated on 
according to
the Lebesgue measure then may be transformed to any measure 
thanks to the inverse CDF technique in order to approximate the integral
:
As the sequence is not randomly generated, we can not use the Central Limit Theorem in order to control the quality of the approximation. This quality is given by the Koksma-Hlawka inequality that we recall here :
where 
is the discrepancy of
the sequence .
For Halton, Inverse Halton and Sobol sequences, we have :
Thus, asymptotically the error converges in
, instead of
for traditional Monte Carlo.
The convergence rate depends on the dimension 
so one must
have 
.
, instead of
for traditional Monte Carlo.
The convergence rate depends on the dimension so one must
have .