<div dir="ltr"><div dir="ltr"><div class="gmail_default" style="font-family:trebuchet ms,sans-serif;font-size:small"><br></div></div><br><div class="gmail_quote"><div dir="ltr" class="gmail_attr">On Mon, Jan 31, 2022 at 3:32 PM Kristofer Munsterhjelm <<a href="mailto:km_elmet@t-online.de">km_elmet@t-online.de</a>> wrote:<br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex">> I don't yet know whether computing volumes is actually faster than<br>
> method (1) for comparable accuracy. But if it is, then my method (3)<br>
> could be the best of both worlds:<br>
> <br>
> - The superior speed vs accuracy trade-off geometry (2).<br>
> - The flexibility and realism of a dedicated voter-density function (1).<br>
<br>
I'd imagine it would depend on how easy it is to do high dimensional<br>
Gaussian integration. There may be more efficient methods than ordinary<br>
MC (e.g. quasi-MC,<br>
<a href="https://web.maths.unsw.edu.au/~josefdick/preprints/DKS2013_Acta_Num_Version.pdf" rel="noreferrer" target="_blank">https://web.maths.unsw.edu.au/~josefdick/preprints/DKS2013_Acta_Num_Version.pdf</a>)<br>
or there may be special-case Gaussian integrals over simplices, and then<br>
the polytope can be decomposed to simplices (like the approach for<br>
determining the exact area) and the Gaussian integral applied to them.<br></blockquote><div><br></div><div><br></div><div class="gmail_default" style="font-family:"trebuchet ms",sans-serif;font-size:small">So I started reading up on quasi-MC. I haven't done this before so my initial thoughts might be incorrect, but I think I've found two things:</div><div class="gmail_default" style="font-family:"trebuchet ms",sans-serif;font-size:small"><br></div><div class="gmail_default" style="font-family:"trebuchet ms",sans-serif;font-size:small">1) It looks easy to do. There are libraries (e.g. scipy.stats.qmc) that just give you a sequence of numbers that you can use as a drop-in replacement for your random number generator in your MC integrator.</div><div class="gmail_default" style="font-family:"trebuchet ms",sans-serif;font-size:small"><br></div><div class="gmail_default" style="font-family:"trebuchet ms",sans-serif;font-size:small">2) But I see a lot of warnings saying that QMC constructions are designed for special values of n, like powers of 2 or large primes, and if I sub-sample or pick the wrong number of points I might ruin all their properties. This is potentially a huge issue because integrating over the polytope consists of throwing away all the points that aren't inside the polytope.</div><div class="gmail_default" style="font-family:"trebuchet ms",sans-serif;font-size:small"><br></div><div class="gmail_default" style="font-family:"trebuchet ms",sans-serif;font-size:small">Right now I'm just hoping that one of the QMC number generators is more forgiving. Sobol seems to be the worst offender, while the Halton sequence looks like it might be more forgiving:</div><div class="gmail_default" style="font-family:"trebuchet ms",sans-serif;font-size:small"><br></div><div class="gmail_default" style="font-family:"trebuchet ms",sans-serif;font-size:small"><a href="https://docs.scipy.org/doc/scipy/reference/reference/generated/scipy.stats.qmc.Halton.html#scipy.stats.qmc.Halton">https://docs.scipy.org/doc/scipy/reference/reference/generated/scipy.stats.qmc.Halton.html#scipy.stats.qmc.Halton</a><br></div><div class="gmail_default" style="font-family:"trebuchet ms",sans-serif;font-size:small"><br></div><div class="gmail_default" style="font-family:"trebuchet ms",sans-serif;font-size:small">The doc says:</div><div class="gmail_default" style="font-family:"trebuchet ms",sans-serif;font-size:small"><br></div><div class="gmail_default" style="font-family:"trebuchet ms",sans-serif;font-size:small">-------------</div><div class="gmail_default" style="font-family:"trebuchet ms",sans-serif;font-size:small">Alternatively, you can skip some points like `sampler.fast_forward(5)` ...<br></div><div class="gmail_default" style="font-family:"trebuchet ms",sans-serif;font-size:small"><div class="gmail_default">-------------</div><br class="gmail-Apple-interchange-newline"></div><div class="gmail_default" style="font-family:"trebuchet ms",sans-serif;font-size:small">Presumably that means that the Halton sequence isn't very finicky about exactly which points get included in the integral. As luck would have it, the Halton sequence is apparently superior for "low-dimensional" problems N <= 6 (Morokoff & Caflisch 1995), which is the dimensionality I most care about anyway. Honestly, the N=2 and N=3 problem is the most interesting for real world elections.</div><div class="gmail_default" style="font-family:"trebuchet ms",sans-serif;font-size:small"><br></div><div class="gmail_default" style="font-family:"trebuchet ms",sans-serif;font-size:small">Cheers,</div></div>-- <br><div dir="ltr" class="gmail_signature"><div dir="ltr"><div><div dir="ltr"><div dir="ltr"><div dir="ltr"><div dir="ltr"><div dir="ltr"><div dir="ltr"><div dir="ltr"><font face="trebuchet ms, sans-serif">Dr. Daniel Carrera</font></div><div dir="ltr"><font face="trebuchet ms, sans-serif">Postdoctoral Research Associate</font></div><div><font face="trebuchet ms, sans-serif">Iowa State University</font></div></div></div></div></div></div></div></div></div></div></div>