[EM] Quasi-Monte Carlo support in quadelect

Kristofer Munsterhjelm km_elmet at t-online.de
Fri Sep 1 16:23:21 PDT 2023


On a completely different subject, I've added quasi-Monte Carlo support 
to quadelect's Yee diagram drawing module, and it seems to be making 
quite a difference.

Here's an example with a particular nonmontone method (not recommended 
for practical use).

Ordinary MC, 2000 voters: 
https://munsterhjelm.no/km/elections/quasi_monte_carlo_yee/monte_carlo_2000.png

QMC, 200 voters: 
https://munsterhjelm.no/km/elections/quasi_monte_carlo_yee/quasi_mc_200.png

QMC, 2000 voters: 
https://munsterhjelm.no/km/elections/quasi_monte_carlo_yee/quasi_mc_2000.png

QMC, 8000 voters: 
https://munsterhjelm.no/km/elections/quasi_monte_carlo_yee/quasi_mc_8000.png

The 200 voters QMC picture looks roughly similar to the 2000 voters MC 
one. "Just" a 10x improvement doesn't sound like much, but if QMC 
converges as 1/n and MC at 1/sqrt(n), then it'll only get better at 
higher vote counts.

There's another oops: it turns out Warren implemented something kind of 
similar to a low discrepancy Gaussian sampling for his Yee code. 
(Basically he picks regularly spaced angles around a circle, and 
distance from center randomly.) So that explains why IEVS was getting so 
much sharper images than say, Brian Olson's code. But IEVS is limited to 
200x200, and it more or less tops out at ~10k voters due to his 
progressive sampling code; any noise still present at 10k voters remains 
even at 65k.

Quadelect is still 11x slower than IEVS per voter, so there's definitely 
room for more general optimization. But having implemented QMC should 
make it easier to adapt it to other domains like strategy resistance 
calculations.

-km


More information about the Election-Methods mailing list