[EM] Quasi-Monte Carlo support in quadelect

[Forest Simmons]

Nice graphics!

On Fri, Sep 1, 2023, 4:25 PM Kristofer Munsterhjelm <km_elmet at t-online.de>
wrote:

> 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
> ----
> Election-Methods mailing list - see https://electorama.com/em for list
> info
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.electorama.com/pipermail/election-methods-electorama.com/attachments/20230904/86c8e0b8/attachment.htm>