Exact spatial model probabilities?
On 25.01.2022 06:06, Forest Simmons wrote:
Thanks Ted and Daniel. Very interesting!
In the early 70's we did our minuteman missile simulations on a room
size mainframe IBM 360/65 computer with FORTRAN code, double precision
arithmetic ... punched cards interface.... and all. We got one
turnaround per night.... night because the Top Secret runs had to be
totally isolated from the daytime use of the computer. In 1974 our group
got ahold of a couple of the mini-computers that were just coming out
... TTY "ticker tape" interface at first then (unreliable, but more
convenient) floppy discs. Very slow, single precision, but interactive
BASIC for the spine of the simulation. We employed pseudo-double
precision for the numerical integration, and modified BASIC so we could
call on assembled bottle-neck subroutines, etc.
It's things like these that makes me think that current computers are
capable of vastly more than they're currently being used for. Computers
with less than 1M of RAM could be used to calculate missile
trajectories, run industrial process control, etc. We now have 16G or more.
Of course, I know that part of the reason is that programmer time is now
the most scarce resource. The programs that are developed now (mostly
user-facing stuff) are much slower than they need to be in part because
it would take too much time and effort to optimize down to the bare metal.
-km
On Tue, Jan 25, 2022 at 9:40 AM Kristofer Munsterhjelm
km_elmet@t-online.de wrote:
It's things like these that makes me think that current computers are
capable of vastly more than they're currently being used for. Computers
with less than 1M of RAM could be used to calculate missile
trajectories, run industrial process control, etc. We now have 16G or more.
Of course, I know that part of the reason is that programmer time is now
the most scarce resource. The programs that are developed now (mostly
user-facing stuff) are much slower than they need to be in part because
it would take too much time and effort to optimize down to the bare metal.
If you aren't familiar with Wirth's law, you probably should be:
https://en.wikipedia.org/wiki/Wirth%27s_law
In short: "software is getting slower more rapidly than hardware is
becoming faster"
I'm reasonably sure that the reason why my browser slows down
(whenever that does) is because the website that I've browsed to is
doing the following:
20% Bitcoin mining
20% farmed out virtual machines running jobs for the website I've browsed to
20% bloated A/B testing framework deciding which order to put the
graphics on the screen in
20% other unnecessary Javascript bloat in the name of "usability"
(usability for the programmer of the website; not for me)
20% functionality that MAY be useful on the webpage (or perhaps if I
click on the correct three things to make the gamble pay off)
Ever since I seen video codecs implemented in Javascript, after (many
years before) being surrounded by codec engineers who had me convinced
that the work that they did was much too complicated for my little
brain, and best left to rocket surgeons like them, AND when I saw my
state-of-the-art computer in 1997 being slowed to a crawl with 10 fps
video in a postage-stamp-sized window using one of these
state-of-the-art codecs, I've come to realize Zoom calls are not
rocket surgery. It also makes me wonder what else Zoom is doing in
the background when my Zoom call stutters. :-)
Speaking of video calls, I'm planning on holding my video call at 2pm
PST today here:
https://whereby.com/robla
...and I'm planning to stick around until 4pm PST.
2pm PST is three hours away from the coming "top of the hour". I may
be a bit late because I'm planning to go to a Center for Election
Science event which slightly overlaps:
https://electionscience.org/events/brokencongressionalprimaries/
The electionscience.org event will probably be over by 2:30pm PST, and
you should be able to join my whereby.com call before I get there and
potentially talk to some of my friends who know nothing about
electoral reform. You may even be able to convince one of them that
electoral reform is an important topic.
Sorry for the tangent. Carry on!
Rob
To paraphrase Dickens ... they were the good old days ... and the bad old
days!
Daniel's idea reminds me of Robert B-J's comment about Heaviside and
Dirac functions. Dirac unit impulse functions are approximated by
Gaussians with infinitesimal variance in the Theory of Distributions. And
every Probability distribution is a convolution of itself with a Dirac
delta ... which is useful because Laplace transforms turn convolution
products into algebraic products.
Electrical engineers are used to approximating all kinds of input signals
with sums of standard functions ... impulse, step, ramp, sinusoids,
Gaussians, that have well known Laplace and Fourier Transforms.
How useful it is to be able to go back and forth between the time and
frequency domains! Even in quantum mechanics ... the more compact the
support of a wave function, the more spread out its Fourier transform, and
vice-versa. That's the wave mechanical basis of the uncertainty principle.
A convenient way to get the mean, variance, and higher moments of a
probability distribution (think voter distribution) is by finding the
Taylor/MacLauren coefficients of the Laplace or Fourier transforms of the
distribution functions.
[Fourier and Laplace transforms differ by a 90 degree rotation in the
complex frequency domain.So what I say for one also goes for the other
without needing to mention it every time.]
My wife needs the phone ... more later..
W
El mar., 25 de ene. de 2022 9:40 a. m., Kristofer Munsterhjelm <
km_elmet@t-online.de> escribió:
On 25.01.2022 06:06, Forest Simmons wrote:
Thanks Ted and Daniel. Very interesting!
In the early 70's we did our minuteman missile simulations on a room
size mainframe IBM 360/65 computer with FORTRAN code, double precision
arithmetic ... punched cards interface.... and all. We got one
turnaround per night.... night because the Top Secret runs had to be
totally isolated from the daytime use of the computer. In 1974 our group
got ahold of a couple of the mini-computers that were just coming out
... TTY "ticker tape" interface at first then (unreliable, but more
convenient) floppy discs. Very slow, single precision, but interactive
BASIC for the spine of the simulation. We employed pseudo-double
precision for the numerical integration, and modified BASIC so we could
call on assembled bottle-neck subroutines, etc.
It's things like these that makes me think that current computers are
capable of vastly more than they're currently being used for. Computers
with less than 1M of RAM could be used to calculate missile
trajectories, run industrial process control, etc. We now have 16G or more.
Of course, I know that part of the reason is that programmer time is now
the most scarce resource. The programs that are developed now (mostly
user-facing stuff) are much slower than they need to be in part because
it would take too much time and effort to optimize down to the bare metal.
-km
So we can approximate voter distributions with sums, products,
convolutions, etc of standard library distributions. And then get the mean,
variance, and other moments via MacLauren series coefficients ...AND vice
versa ... if we know the desired moments, we can construct the MacLauren
series for the transform of the distribution function, and then inverse
trans form back to the desired distribution function. Classically this was
called. "The problem of the moments."
The biggest difficulty was dealing with divergent or slowly convergent
MacLauren series ... the solution was to use continued fraction expansions
or other Pade approximants to get convergence. Nowadays numerical inversion
of these transforms is much more practical than it was in those days.
Of course all of this is trivial in one dimension ... but not in two or
three dimensions.
At least an answer to Colin's question about the proper or central
mathematical setting for voting methods is starting to take shape.
(She's taking off again on a long errand of mercy with the phone ... so
more later)
El mar., 25 de ene. de 2022 12:10 p. m., Forest Simmons <
forest.simmons21@gmail.com> escribió:
To paraphrase Dickens ... they were the good old days ... and the bad old
days!
Daniel's idea reminds me of Robert B-J's comment about Heaviside and
Dirac functions. Dirac unit impulse functions are approximated by
Gaussians with infinitesimal variance in the Theory of Distributions. And
every Probability distribution is a convolution of itself with a Dirac
delta ... which is useful because Laplace transforms turn convolution
products into algebraic products.
Electrical engineers are used to approximating all kinds of input signals
with sums of standard functions ... impulse, step, ramp, sinusoids,
Gaussians, that have well known Laplace and Fourier Transforms.
How useful it is to be able to go back and forth between the time and
frequency domains! Even in quantum mechanics ... the more compact the
support of a wave function, the more spread out its Fourier transform, and
vice-versa. That's the wave mechanical basis of the uncertainty principle.
A convenient way to get the mean, variance, and higher moments of a
probability distribution (think voter distribution) is by finding the
Taylor/MacLauren coefficients of the Laplace or Fourier transforms of the
distribution functions.
[Fourier and Laplace transforms differ by a 90 degree rotation in the
complex frequency domain.So what I say for one also goes for the other
without needing to mention it every time.]
My wife needs the phone ... more later..
W
El mar., 25 de ene. de 2022 9:40 a. m., Kristofer Munsterhjelm <
km_elmet@t-online.de> escribió:
On 25.01.2022 06:06, Forest Simmons wrote:
Thanks Ted and Daniel. Very interesting!
In the early 70's we did our minuteman missile simulations on a room
size mainframe IBM 360/65 computer with FORTRAN code, double precision
arithmetic ... punched cards interface.... and all. We got one
turnaround per night.... night because the Top Secret runs had to be
totally isolated from the daytime use of the computer. In 1974 our group
got ahold of a couple of the mini-computers that were just coming out
... TTY "ticker tape" interface at first then (unreliable, but more
convenient) floppy discs. Very slow, single precision, but interactive
BASIC for the spine of the simulation. We employed pseudo-double
precision for the numerical integration, and modified BASIC so we could
call on assembled bottle-neck subroutines, etc.
It's things like these that makes me think that current computers are
capable of vastly more than they're currently being used for. Computers
with less than 1M of RAM could be used to calculate missile
trajectories, run industrial process control, etc. We now have 16G or
more.
Of course, I know that part of the reason is that programmer time is now
the most scarce resource. The programs that are developed now (mostly
user-facing stuff) are much slower than they need to be in part because
it would take too much time and effort to optimize down to the bare metal.
-km
On 25.01.2022 22:09, Forest Simmons wrote:
So we can approximate voter distributions with sums, products,
convolutions, etc of standard library distributions. And then get the
mean, variance, and other moments via MacLauren series coefficients
...AND vice versa ... if we know the desired moments, we can construct
the MacLauren series for the transform of the distribution function, and
then inverse trans form back to the desired distribution function.
Classically this was called. "The problem of the moments."
The biggest difficulty was dealing with divergent or slowly convergent
MacLauren series ... the solution was to use continued fraction
expansions or other Pade approximants to get convergence. Nowadays
numerical inversion of these transforms is much more practical than it
was in those days.
Of course all of this is trivial in one dimension ... but not in two or
three dimensions.
At least an answer to Colin's question about the proper or central
mathematical setting for voting methods is starting to take shape.
I have been investigating the problem a bit myself. I was thinking that
the best case is to have a black box numerical integration method where
we evaluate the function to be integrated at a number of points and then
get a reasonable approximation.
Well, it turns out that even getting the exact volume of a convex
polytope is hard. https://mathoverflow.net/questions/979
So even in this idealized case, there would be trouble, unless Voronoi
cells have some additional structure that make calculating the volume
easy (unlike convex polytopes in full generality).
I did implement an approximation algorithm called billiard sampling for
quadelect for a different problem, but this is only approximate. I would
also guess that, like most MIPs and NP-complete problems, this problem
can be determined in practical time for low dimensions. However, the
autodiff of the whole solver would be horrible: you'd have a number of
step functions and attendant exploding or vanishing gradients (and
slowdown having to take both paths). So the numerical differentiation
method couldn't use derivatives; or the derivatives would also have to
be found in some clever fashion.
Perhaps the better approach is to use MC or quasi MC. Or meet in the
middle somehow, e.g. let f(A>B>C, A.x, A.y, B.x, B.y, C.x, C.y) be the
fraction of voters who vote A>B>C when the candidates are at the given
coordinates; then use billiard sampling to determine f, and sample using
MC or a perturbed over the coordinates. This could perhaps be more
accurate than using MC for both picking the candidate locations and
counting voter proportions.
-km
On Tue, Jan 25, 2022 at 12:37 PM Rob Lanphier roblan@gmail.com wrote:
If you aren't familiar with Wirth's law, you probably should be:
https://en.wikipedia.org/wiki/Wirth%27s_law
In short: "software is getting slower more rapidly than hardware is
becoming faster"
There was a time when computer science was the domain of mathematics
departments. Today, computer science is the mass market STEM degree. I
attended a friend's graduation a long time ago, and I remember being struck
by the fact that there were as many computer science graduates as all other
science degrees put together. At the end of the day, there is a large
market for mediocre programmers who never need to do anything more complex
than write a glorified database front-end.
Ever since I seen video codecs implemented in Javascript,
weep
--
Dr. Daniel Carrera
Postdoctoral Research Associate
Iowa State University
On Tue, Jan 25, 2022 at 3:26 PM Kristofer Munsterhjelm km_elmet@t-online.de
wrote:
Perhaps the better approach is to use MC or quasi MC. Or meet in the
middle somehow, e.g. let f(A>B>C, A.x, A.y, B.x, B.y, C.x, C.y) be the
fraction of voters who vote A>B>C when the candidates are at the given
coordinates; then use billiard sampling to determine f, and sample using
MC or a perturbed over the coordinates. This could perhaps be more
accurate than using MC for both picking the candidate locations and
counting voter proportions.
I'm not familiar with billiard sampling. Is this it?
https://www.sciencedirect.com/science/article/pii/S037722171400280X
I have an idea that might be very naive, but here it goes. The problem is
hard in part because you want to compute f(A>B>C) for every permutation of
candidates. You could make a quicksort-like algorithm to iteratively
partition the space:
-
Start with a population of V voters and C candidates spread in some
N-dimensional space. -
Select any two candidates {A,B}. Partition the voters based on whether
they are in the A>B camp or the A<B camp. Now you have two disjoint groups.
Partition each group based on where they fall on the {A,C} contest.
Partition those based on where they fall on the {B,C} debate, and so on.
The total number of operations is V*C^2 which... can be a lot if V is
large. But it might not be too bad if the alternative way of computing the
volume of 1 set of preferences costs more than doing a simple {A,B}
comparison V times. There might be some clever geometrical tricks to
quickly classify some of the voters, but I can't think of any right now
that is obviously faster.
Cheers,
Dr. Daniel Carrera
Postdoctoral Research Associate
Iowa State University
On Tue, Jan 25, 2022 at 5:10 PM Daniel Carrera dcarrera@gmail.com wrote:
The total number of operations is V*C^2 which... can be a lot if V is
large. But it might not be too bad if the alternative way of computing the
volume of 1 set of preferences costs more than doing a simple {A,B}
comparison V times. There might be some clever geometrical tricks to
quickly classify some of the voters, but I can't think of any right now
that is obviously faster.
To expand a little bit: If you have C candidates you have C! possible
orderings. Whereas the partitioning idea only requires C^2 candidate pairs
{A,B}. Perhaps a dumb {A,B} comparison performed V times is cheaper than a
clever volume-finding algorithm performed C! times.
--
Dr. Daniel Carrera
Postdoctoral Research Associate
Iowa State University
I'm thinking ergodic theory.... here's a relevant quote from the wikipedia
article:
The concepts of ergodicity https://en.m.wikipedia.org/wiki/Ergodicity and
the ergodic hypothesis https://en.m.wikipedia.org/wiki/Ergodic_hypothesis are
central to applications of ergodic theory. The underlying idea is that for
certain systems the time average of their properties is equal to the
average over the entire space.
We have the force field, and I proposed using it to find sinks as possibly
stable equilibria positions ... local minima of the electo-potential V.
All we have to do is add some inertia to the test point and set it in
motion. Then keep track of the time average, and we have a space average
for the basin to which the particle is limited by its initial energy.
El mar., 25 de ene. de 2022 3:20 p. m., Daniel Carrera dcarrera@gmail.com
escribió:
On Tue, Jan 25, 2022 at 5:10 PM Daniel Carrera dcarrera@gmail.com wrote:
The total number of operations is V*C^2 which... can be a lot if V is
large. But it might not be too bad if the alternative way of computing the
volume of 1 set of preferences costs more than doing a simple {A,B}
comparison V times. There might be some clever geometrical tricks to
quickly classify some of the voters, but I can't think of any right now
that is obviously faster.
To expand a little bit: If you have C candidates you have C! possible
orderings. Whereas the partitioning idea only requires C^2 candidate pairs
{A,B}. Perhaps a dumb {A,B} comparison performed V times is cheaper than a
clever volume-finding algorithm performed C! times.
--
Dr. Daniel Carrera
Postdoctoral Research Associate
Iowa State University
On Tue, Jan 25, 2022 at 8:52 PM Forest Simmons forest.simmons21@gmail.com
wrote:
We have the force field, and I proposed using it to find sinks as possibly
stable equilibria positions ... local minima of the electo-potential V.
All we have to do is add some inertia to the test point and set it in
motion. Then keep track of the time average, and we have a space average
for the basin to which the particle is limited by its initial energy.
What you are saying sounds similar to how Hamiltonian Monte Carlo sees a
probability distribution as a potential and traces orbits about that
potential to efficiently sample from it. However, I must confess that I
haven't quite understood how you would turn the problem Kristofer wants to
solve into a potential V. But if you can express the problem in the
language that HMC can understand, there are popular tools used by
statisticians (e.g. the Stan language) that have HMC (and the
closely related and very fast No U-Turn Sampler) already implemented.
https://en.wikipedia.org/wiki/Hamiltonian_Monte_Carlo
Cheers,
Dr. Daniel Carrera
Postdoctoral Research Associate
Iowa State University