[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