[EM] Spatial models -- Polytopes vs Sampling

[Daniel Carrera]

So I implemented my proposed "voter mass function" based on integrating
"voter density" across a polytope. I have run some benchmarks on a sample
2D polytope (small dimension, but relevant to real elections). I
implemented regular Monte Carlo (MC) integration, as well as the Quasi
Monte Carlo (QMC) suggested by Kristofer. The QMC method was done with both
a Halton and a Sobol sequence. The voter density function is a
Gaussian distribution. Here are my results:


1) The Halton sequence is apparently very expensive to generate. Most of
the cost of QMC is spent just generating the sequence apparently. Despite
this absurdity, it still manages to match MC in terms of cost for a given
level of accuracy. QMC/Halton can match the accuracy of MC for much lower N
(number of points) and that roughly compensates for the lack of speed.

Target Relative Error: < 1e-3

QMC/Sobol:    N = 2^12 --- time = 0.000520s
QMC/Halton:   N = 2^13 --- time = 0.000671s
Regular MC:   N = 2^20 --- time = 0.081216s

2) The Sobol sequence has about the same accuracy as Halton (slightly
better in this example), but it is just as fast as regular MC (slightly
faster). The overall result is impressive; especially at higher accuracy.

QMC/Sobol:    N = 2^24 --- time = 1.96s --- error = 1e-6
QMC/Halton:   N = 2^24 --- time = 31.1s --- error = 2e-6
Regular MC:   N = 2^24 --- time = 1.89s --- error = 2e-4

I'll still try to find some sort of quadrature rule that can be faster and
more exact, but I'm finding the subject difficult to understand. My
baseline expectation is that I'll just stick to QMC/Sobol.

Cheers,
-- 
Dr. Daniel Carrera
Postdoctoral Research Associate
Iowa State University
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.electorama.com/pipermail/election-methods-electorama.com/attachments/20220202/89ec1a9d/attachment-0001.html>