June 2014 - mathfun@mailman.xmission.com

Re: [math-fun] math-fun Digest, Vol 136, Issue 48
by Warren D Smith 22 Jun '14

22 Jun '14

> From: Tom Rokicki <rokicki(a)gmail.com> > Smells like B trees to me. --it is not B trees since each of my nodes has <=2 children. (May have same "smell.")

2 1

[math-fun] SCOTUS spanks patent court; abstract ideas not patentable
by Henry Baker 22 Jun '14

22 Jun '14

Hopefully, today's Supreme Court decision will have the effect of slowing down substantially the issuing of bad software patents. Simply expressing an algorithm in computer code doesn't make it patentable, unless the algorithm itself is patentable. Abstract ideas aren't patentable, so abstract ideas embedded in computer code aren't patentable. Judge Randall Rader, the ex-Chief of the patent court, already embarrassed by ethics violations, is spanked unanimously by the Supremes in today's opinion; he is leaving that court at the end of the month. http://www.supremecourt.gov/opinions/13pdf/13-298_7lh8.pdf http://www.reuters.com/article/2014/06/13/us-usa-court-ip-idUSKBN0EO2OO2014…

5 7

[math-fun] Election ideas etc
by Warren D Smith 21 Jun '14

21 Jun '14

I suggest posting your ideas on election science forum https://groups.google.com/forum/#!forum/electionscience

1 0

[math-fun] soap bubbles and gerrymandering
by Warren D Smith 21 Jun '14

21 Jun '14

if you want to know more about that see http://rangevoting.org/PuzzGerryOpt.html

1 0

[math-fun] gerrymandering maths
by Warren D Smith 21 Jun '14

21 Jun '14

Asimov: standard deviation of curvature of boundary.. limit for smooth curves approaching in "suitable sense". 0 for circle, infinite for Koch snowflake. WDS: Won't work. Consider the unit square. Approach it by using circular arcs of angle 90 degrees and radius r at the 4 corners, as r-->0+. Result: the integral of curvature^2 is 2*pi*r*(1/r)^2 = 2*pi/r --> infinity. A variant of Asimov's idea which has the advantage of not being *completely* silly, is to use the integral (along boundary) value of |curvature|. I frankly am dubious about any measure which employs derivatives -- as soon as you do that you are asking for trouble for any real world numerical purpose. And even worse (as in this case) second derivatives. But the quantity I just described can be defined somewhat without need of derivatives by taking advantage of the Gauss-Bonnet theorem. Specifically, the integral of curvature along any curve segment on which the curve is convex, equals the |difference| between final and initial angle of tangent ray, where be careful not to add the wrong multiple of 2*pi (angles being defined mod 2*pi). So as long as your curve is divisible into convex and convex-the-other-way segments, with all inflection points having a tangent line, then can compute this integral. Bad news: EVERY convex object has the SAME |curvature| integral, indicating this variant idea is still completely stupid. Baker: muttering about gas, boundaries made of rubber, minimize energy. Knight: other such mutterings. Soap bubbles got involved somewhere. WDS: actually, Baker's ideas are vaguely valid intuitions about the problem of dividing up a country into equipopulous districts while minimizing total cutlength; that is one of the 3 quality measured defined in my survey essay. The soap bubbles obey certain properties like 120-120-120 angles at junctions, each boundary is a circular arc with uniform (but different) gas pressures (population densities) on each side. Those would be theorems. However... unfortunately population densities in real world are NOT uniform, and anyhow the whole problem of optimizing the map with cutlength as quality measure, is (I proved) NP-hard. In fact I proved NP-hardness for exact optimal districting using all 3 of the quality measures recommended in my paper. As an OPEN PROBLEM: find, for one of the 3 main quality measures in my paper, a polytime districting algorithm you can prove produces a map within some constant factor of optimality (or prove no such algorithm exists if P != NP). I actually partly succeeded in this quest, in the sense I had a somewhat vague algorithm and a somewhat vague proof it approximated -- I never carried this through to completion, and this all is not discussed in my paper. The method I had in mind was very complicated, fairly high degree polynomial time, and involved some high powered computational-geometry algorithm-design ideas involving "dynamic programming" related to work by Joe Mitchell. If we assume my proof could have been made to work, the resulting algorithm and approx guarantee both would have been totally impractical.

1 0

[math-fun] personal worst
by Bill Gosper 21 Jun '14

21 Jun '14

Today (at NeilB's) I was testing a nine-variable theta-fn conjecture: In[531]:=Det[%519/.SetPrecision[ Join[{s -> RandomChoice[Range[4]]}, {q -> RandomReal[.999]*E^(I*RandomReal[2*\[Pi]])}, Thread[{t, u, v, w, x, y, z} -> RandomComplex[{-6 - 9*I, 9 + 6*I}, 7]]], 99]] Out[531]= 1.7947822160078335895630499053244455396741527880586403925848897324738*10^2147 - 2.480887366402951261629114856034958605850308048123481310444081443215*10^2147 I (Should be 0.) This had to be the worst conjecture I ever made. But it seemed so plausible. Without a shred of optimism, I upped 99 to 1999. And never saw another positive exponent. --rwg

1 0

[math-fun] gerrymandering via constrained corruption?
by Warren D Smith 20 Jun '14

20 Jun '14

> From: Allan Wechsler <acwacw(a)gmail.com> > I am wondering what Warren would think of a slightly different approach. > Rather than legislate a process that arrives at a reasonable district map, > why not legislate a constraint on such maps, letting the legislators be as > corrupt as they want within those constraints? I think some very simple > constraints would go a long way in placing a ceiling on the amount of > possible corruption. For example: > > A. All districts should be the intersection with the state of a convex > region. > > B. All districts should be the intersection with the state of a > latitude-longitude rectangle. > > It is true that these schemes permit maps to be marred with a few long, > thin regions, but the amount of possible horror is greatly reduced. --well, sure. I think some such constraint, but then be as corrupt about gerrymandering as you want subject to that constraint... would be better than now (i.e, unconstrained corruption) but worse than something that actually removes the intentional bias from the picture, like (my) splitline algorithm. One could go on... e.g. in the USA, in many states, the elections are supervised by somebody with hire+fire power over everybody in the system, who by design, is the single most biased person in the entire state, e.g. in the 2000 presidential election, Bush-Cheney campaign chair K.Harris was the Florida secretary of state in charge of elections (crucial state). In Ohio 2004, Bush-Cheney campaign chair K.Blackwell was the Ohio SOS, ditto. It is kind of like when Obama recently appointed, as head of the FCC, a reasonable candidate for "the single most biased person in the entire country" i.e. cable/telco lobbyist Tom Wheeler, who appears to be about to destroy "net neutrality" then return to a rich future life as a continued lobbyist. Point is... aside from the danger of getting me started with ranting... the problem is the intentional bias. In the USA, similarly, districts are most commonly drawn by the top 10 most biased people that exist in that entire state. It isn't just bad. It is maximally bad. And election predictability over the 1995-2005 decade in the USA was over 98%, see http://www.rangevoting.org/NonVoters.html for proof, meaning USA has, to a good approximation, 96% rigged and 4% democratic elections, plus with that 4% sliver in turn being near maximally lame in the sense we have 2-party domination and the ultra-bad plurality voting system. It's a hell of a way to run the world. And I've been trying to save the world via the rangevoting.org website I am the main creator of -- all help by others appreciated! -- but I am highly unequal to the challenge and getting more and more cynical and burned out. The splnoff group "center for election science" (I was first president, but they've got rid of me) electology.org hopefully will outperform rangevoting.org but that remains to be seen, there's reasons for major pessimism and minor optimism.

1 0

Re: [math-fun] Spirography
by Steve Witham 20 Jun '14

20 Jun '14

> Date: Mon, 16 Jun 2014 11:54:40 -0400 [in issue 29] > From: James Propp <jamespropp(a)gmail.com> > > Has anyone designed a mechanism that permits the spirographer to focus on > circumferential force? The knockoff product I have, has holes in both parts, suitable for pushing pins through, so in theory you only have to push on the pen tip. Rather than a wax tray the first thing I'd think of would be corrugated cardboard & the second, cork. > I'm imagining something like a latchable/unlatchable zipper. That's a fascinating idea in itself. It could be used in funicular railways, for instance. Although the zipper tooth design is asymmetrical, I have a coat that unzips from both ends. --Steve

7 7

Re: [math-fun] secretary problem
by Paul R. Pudaite 20 Jun '14

20 Jun '14

Andy Latto wrote: > Suppose we take n independent samples from a normal distribution > (let's fix the distrubution as having mean 0 and variance 1). As n > increases, what happens to the expected value of (largest sample - 2nd > largest sample)? > > How sensitive is this answer to the normality of the distribution? > What do we need to know about the distribution to conclude that as n > increases, this difference will behave the way it does for a normal > distribution? Let {X[i], i = 1 to n} be a set of n independent identically distributed random variables. For each i, the cumulative distribution function is F(x) = Prob[X[i] <= x], and (assuming F(x) is differentiable) the probability density function is f(x) = F'(x). Let X and Y be, respectively, the largest and second largest numbers in this set. Then the joint probability density function of X and Y is: f(x,y) = n(n-1) f(x) f(y) F(y)^(n-2) for x >= y = 0 for x < y E[X-Y] = C n Integral(F(x)^(n-1) - F(x)^n, all x) My calculus is rusty so I'm pretty sure I lost a constant factor somewhere! ... When the random variables are normally distributed my Monte Carlo estimates agreed with this formula using C = Sqrt(2 Pi). For the normal distribution, the formula E[X-Y] = K / (log(n)^q) works pretty well for q just above 1/2. But E[X-Y] actually shrinks a bit more slowly than the right hand side. Paul

1 0

[math-fun] secretary problem: "harmonic strategy" conjecturally approximately optimal
by Warren D Smith 20 Jun '14

20 Jun '14

So here's one possible algorithm for the problem I'll call the "harmonic strategy." (There are N candidates in all, you see them in random order, and have to make a decision to hire one immediately after you see them, or they are gone forever. Incidentally, there is a wikipedia article on "Secretary Problem" and it says it was originally called "fiancee problem."). HARMONIC STRATEGY: Let C be a suitable constant 0<C<1. For k=1,2,3,... If less than C*N/k candidates remain unexamined, and the last one you saw had rank<=k among all those so far seen ("rank" counting 1,2,... from the best), then hire. For brevity let f(k) = 1/k - 1/(k+1) = 1/((k+1)*k). It seems to me that the expected rank R of the one you hire with this strategy (among all N candidates) will obey R = order 1 with probability P[1] of order 1, order k (1<k<N) with probability P[k] of order (1 - (1-k/N)^(f(k)*N)) * (1-P[k-1]), (1+N)/2 with whatever probability is left over. If we note that for large N that (1-k/N)^(f(k)*N) = exp(-k*f(k)) = exp(-1/(k+1)) = 1-1/(k+1) approximately, then we see the the probability that R=order k, is about 1/(k+1) fraction of whatever probability is left over from all the preceding k. Since SUM 1/k = infinity (harmonic series diverges) logarithmically we see PRODUCT (1-1/k) = 0 ("harmonic product") in fact it telescopes so the exact value of Product[ 1-1/k from k=2..N ] = 1/N, indicating that the "leftover probability" should become of order 1/N at most, for large N. That is good because it means the final term contributes at most O(1) to the expectation value of R. Now in fact you can see that every time k doubles the (1-P[k-1]) approximately halves, which means P[k] behaves like 1/k^2 for large k. Hence performing the sum to find the expectation value of R we conclude: CLAIM: Expect(R) = O(logN). So this has been an admittedly sketchy proof that Expect(R) = O(logN) is assured by the harmonic strategy. I conjecture the harmonic strategy is optimal to within a constant factor, i.e. that no matter what strategy is employed, Expect(R) will always be at least of order logN. -- Warren D. Smith http://RangeVoting.org <-- add your endorsement (by clicking "endorse" as 1st step)

1 1