Hurray, our signed mixture simulation paper has been accepted by Statistics & Computing! If Og’s readers remember my earlier post about this problem, things get surprisingly more complicated when the mixture weights can take negative values. For instance, the naïve solution consisting in first simulating from the associated mixture of positive weight components and then using an accept-reject step may prove highly inefficient since the overall probability of acceptance can get arbitrarily close to zero. Substituting to this naïve version, we construct an alternative accept-reject scheme based on pairing positive and negative components as efficiently as possible, partitioning the real line, and finding tighter upper and lower bounds on positive and negative components, respectively, towards yielding a higher acceptance rate on average. In retrospect, the problem was beyond the reach of the undergraduate students we supervised (pre-COVID) on a research internship!
Archive for inverse cdf
positive response to negative mixtures
Posted in pictures, Running with tags academic publisher, accept-reject algorithm, acceptance, acceptance probability, article, COVID-19, inverse cdf, master project, PSL Research University, publication, signed mixture, simulation, Statistics and Computing, Université Paris Dauphine, ziggurat algorithm on December 17, 2024 by xi'ansimulating a normal variate
Posted in Books, Statistics, University life with tags field-programmable gate array, FPGA, Intel, inverse cdf, lookup table, multilevel Monte Carlo, normal distribution, simulation, webinar on December 3, 2024 by xi'an
Ali–Mikhail–Haq copula, [re]simulated
Posted in Books, R, Statistics with tags Ali–Mikhail–Haq copula, bivariate cdf, copBasic, copulas, empirical cdf, inverse cdf, package, R, simulating copulas, simulation on October 13, 2024 by xi'an
When looking for a copula I could simulate from (rather than the Gaussian copula), I found an algorithm for the Ali–Mikhail–Haq copula
that was proposed by Kumar (2010) as reproduced above. But the method seriously fails in that the range of (U,V) resulting from the simulation does not even cover the (0,1)² square! Unless I made an R coding mistake (which is always a possibility).
sim=function(T=1e3,h=.5){
o=matrix(runif(2*T),T,2)
a=1-o[,1];b=1-h*(1+2*a*o[,2])+2*h^2*a^2*o[,2]
d=1+h*(2-4*a+4*a*o[,2])+h^2*(1-4*a*o[,2] +4*a^2*o[,2])
o[,2]=1-2*o[,2]*(a*h-1)^2/(b+sqrt(d))
return(o)}
There is no explanation in the paper as to why this algorithm is (not!) working, besides the inverse cdf argument—with the reference in R copBasic temporarily worrying until I checked the cdf inversion is completely numerical—, but a correct version can be derived from inverting the conditional cdf of one component, V, given the other, U. Namely, since the conditional cdf is given by
which leads to a second degree polynomial equation (in v) when solving the equation F(v|U=u) = w.
sim=function(T=1e3,h=.5){
o=matrix(runif(2*T),T,2)
v1=o[,1];w=o[,2]
d=(2*h*v1*w-1-h)^2-4*(1-w)*h*(1-h*w*v1^2)
o[,2]=-2*h*v1*w+1+h-sqrt(d))/(2*h*(1-h*w*v1^2)
return(1-o)}
And with a more likely outcome (Xed checked by comparing F(u,v) with its empirical version for several pairs (u,v)):
simulating signed mixtures
Posted in Books, pictures, R, Statistics, University life with tags accept-reject algorithm, arXiv, fundamental lemma of simulation, HAL, inverse cdf, mixtures of distributions, Monte Carlo Statistical Methods, pseudo-random generator, simulation on February 2, 2024 by xi'an
While simulating from a mixture of standard densities is relatively straightforward, when the component densities are easily simulated, to the point that many simulation methods exploit an intermediary mixture construction to speed up the production of pseudo-random samples from more challenging distributions (see Devroye, 1986), things get surprisingly more complicated when the mixture weights can take negative values. For instance, the naïve solution consisting in first simulating from the associated mixture of positive weight components and then using an accept-reject step may prove highly inefficient since the overall probability of acceptance
is the inverse of the sum of the positive weights and hence can be arbitrarily close to zero. The intuition for such inefficiency is that simulating from the positive weight components need not produce values within regions of high probability for the actual distribution
since its negative weight components may remove most of the mass under the positive weight components. In other words, the negative weight components do not have a natural latent variable interpretation and the resulting mixture can be anything, as the above graph testifies.
Julien Stoehr (Paris Dauphine) and I started investigating this interesting challenge when the Master students who had been exposed to said challenge could not dent it in any meaningful way. We have now arXived a specific algorithm that proves superior to the naïve accept-reject algorithm, but also to the numerical cdf inversion (which happens to be available in this setting). Compared with the naïve version, we construct an alternative accept-reject scheme based on pairing positive and negative components as well as possible, partitioning the real line, and finding tighter upper and lower bounds on positive and negative components, respectively, towards yielding a higher acceptance rate on average. Designing a random generator of signed mixtures with enough variability and representativity proved a challenge in itself!
combining normalizing flows and QMC
Posted in Books, Kids, Statistics with tags Arianna Rosenbluth, arXiv, Illya Sobol, importance sampling, inverse cdf, John Halton, MCM 2023, Metropolis-Hastings algorithm, mostly Monte Carlo seminar, normalizing flow, Python, quasi-Monte Carlo methods, scrambling, Sobol sequences on January 23, 2024 by xi'an
My PhD student Charly Andral [presented at the mostly Monte Carlo seminar and] arXived a new preprint yesterday, on training a normalizing flow network as an importance sampler (as in Gabrié et al.) or an independent Metropolis proposal, and exploiting its invertibility to call quasi-Monte Carlo low discrepancy sequences to boost its efficiency. (Training the flow is not covered by the paper.) This extends the recent study of He et al. (which was presented at MCM 2023 in Paris) to the normalising flow setting. In the current experiments, the randomized QMC samples are computed using the SciPy package (Roy et al. 2023), where the Sobol’ sequence is based on Joe and Kuo (2008) and on Matouˇsek (1998) for the scrambling, and where the Halton sequence is based on Owen (2017). (No pure QMC was harmed in the process!) The flows are constructed using the package FlowMC. As expected the QMC version brings a significant improvement in the quality of the Monte Carlo approximations, for equivalent computing times, with however a rapid decrease in the efficiency as the dimension of the targetted distribution increases. On the other hand, the architecture of the flow demonstrates little relevance. And the type of RQMC sequence makes a difference, the advantage apparently going to a scrambled Sobol’ sequence.
