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

Nice graphics! On Fri, Sep 1, 2023, 4:25 PM Kristofer Munsterhjelm <km_elmet@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 >