June 2014 - mathfun@mailman.xmission.com

[math-fun] new (?) maxent characterization of gamma distribution, and random-sample generators
by Warren D Smith 07 Jun '14

07 Jun '14

Consider probability densities P(x) on the positive real half-line with given mean. The one maximizing the entropy-like functional integral P(x) * log(P(x) * x^k) dx is a general gamma distribution. I don't think I like this as much as the other maxent characterization in wikipedia, though: gamma distribution is maxent on the halfline given that E(X) and E(lnX) are specified. =========== An idea attributed to Chris Wallace for generating random normal or random exponential deviates, is as follows. RANDOM NORMAL: 1. Maintain a pool of N standard normal (mean=0, variance=1) deviates for some moderately large N such as N=256. 2. To update the pool: A. Choose a small subset among those N randomly. Most simply, choose 2 of them. B. Randomly rotate this 2-vector using a 2x2 rotation with random uniform angle in [0..2*pi), and/or random reflection in a line thru the origin of the XY plane. Other updates also are possible. For example, you might only use the 8 rotations and reflections in the dihedral group D4. Or you might choose 4, not 2, and perform a rotation/reflection in 4 dimensions, which has the advantage you can do that with quaternions and only rational operations. Indeed you can make other normals in the poll select the quaternions defining the 4D rotation for you, so you do not have to generate it yourself. RANDOM EXPONENTIAL: 1. Maintain a pool of N standard exponential (mean=1) deviates for some moderately large N such as N=256. 2. To update the pool: A. Choose a small subset among those N randomly. Most simply, choose 2 of them. B. Replace these two (X,Y) with R*S, (1-R)*S where S=X+Y and R is uniform random on (0,1). The point of these update operations is they preserve the sum of squares (for normal) or plain sum (for exponential) of the pool, while increasing entropy. As a result after a lot of updates we approach the maxent distribution with given mean (i.e. exponential) or given variance (i.e. normal). This kind of generator is extremely fast and simple. No transcendental functions are needed. Unfortunately a slight defect is that the sum of squares (or plain sum) of the entire pool remains constant. This is correctable because really, this sum should be a gamma-distributed random variable with known parameters, so every N updates you can alter the entire pool-sum (or sum of squares) by calling a gamma generator just once. If N is large this does not slow things down much. However this leads us to ask: "how do we generate random samples from gamma distributions?" ============================= Here is a gamma generator based on the same Wallace-like maxent+pool approach, and using wikipedia's maxent characterization. To generate gammas from some fixed gamma distribution (fix its parameters once and for all at start): 1. Maintain a pool of N gamma deviates for some moderately large N such as N=256. 2. To update the pool: A. Choose three (X,Y,Z) among those N randomly. B. Replace (X,Y,Z) with "random" (x,y,z) chosen to have the same sum S=X+Y+Z and same product P=X*Y*Z. Once x is known, 0<=x<=S/3, then y and z could be found by finding the two solutions of a quadratic equation. The set of these x,y,z form a closed approximately-circular-shaped curve X*Y*Z=P drawn on the subset X>0, Y>0, Z>0 of the 2-dimensional plane X+Y+Z=S and centered at X=Y=Z=S/3. One could pretend the distribution along this curve was uniform in angle and thus generate a random direction within this plane, then find the point in that direction on the curve (by solving cubic). Anyhow, it does not terribly matter how we generate a "random" point (x,y,z) on this curve -- virtually any reasonable method and any reasonable definition of random will do, because all we need is that this update be entropy-increasing. Incidentally, gammas can be used to generate betas... ================ In these maxent/pool methods, the parameters of the distribution are chosen by making the initial pool have the desired variance (for normal), mean (for exponential), and mean & mean-logarithm (for gamma).

1 0

[math-fun] Stupid Mercator map question
by Henry Baker 07 Jun '14

07 Jun '14

Yes, I know this question is 400 years old, but what is the shape of the image of a great circle on a Mercator projection map? I've seen it described as "sinusoid" shaped, but that can't be right, can it? (Yes, we've all seen those satellite location maps on TV, and they look pretty sinusoidal, but are they really?) I'm not trying to measure lengths or angles, but am simply interested in the mathematical shapes of these great circle on the flat Mercator map. I'm also not interested in the images of non-great circles.

7 11

[math-fun] Apple introduces new "swift" programming language
by Warren D Smith 06 Jun '14

06 Jun '14

http://swift-lang.org/main/

2 1

[math-fun] Einstein gravity, like fluid dynamics, can exhibit "turbulence"?
by Warren D Smith 06 Jun '14

06 Jun '14

or so it is claimed in this paper: Huan Yang, Aaron Zimmerman, Luis Lehner: Turbulent black holes http://arxiv.org/abs/1402.4859 However: 1. "turbulence" of the sort I am used to, features energy flowing from lower spatial frequencies into higher ones. This is the opposite. They don't care. 2. it is well known that the Kerr "spinning black hole" metric is unique, stationary, and perturbations to it die out exponentially. They claim precisely such an isolated black hole is "turbulent." So how can such a scenario be claimed "turbulent?" More like "boring, and proven to be so, for many years now." (They do not cite the uniqueness theorems.) So I don't understand them. My initial guess would be: this is overhyped baloney and they are desperately trying to take some incredibly minor and unimportant result, and act like it is important. But feel free to correct me.

1 0

[math-fun] Shortest Euler path (driving a car) through all US states except Alaska & Hawaii
by Thane Plambeck 05 Jun '14

05 Jun '14

I thought this was interesting...a Google map allegedly showing how to drive a car through the lower 48 USA states, visiting each state [at least? exactly?] once and minimizing the total distance travelled. http://goo.gl/maps/90i0Y -- Thane Plambeck tplambeck(a)gmail.com http://counterwave.com/

3 4

[math-fun] approximate partition formula
by rcs＠xmission.com 05 Jun '14

05 Jun '14

I always have trouble recalling the formula for the number of partitions of N. Here's a simple approximation: partition(N) ~= 13^sqrt(N) / 7N Rich

4 3

[math-fun] Atropa Belladonna
by Fred Lunnon 05 Jun '14

05 Jun '14

How to destroy any ability at chess which you may previously have enjoyed. Playing from the centre of an infinite open board --- Q1. Prove that Every point has some knight-move neighbour at smaller knight-move distance from the origin if and only if Every point has some knight-move neighbour at greater knight-move distance from the origin. Q2. Prove(!) that there is just a single shortest knight path from (0,0) to (2r,r) taking distance r steps. Q3. Denote e(x, y) the number of shortest knight paths from (0,0) to (x,y) . Prove that e(1999999999, 3) = e(1500000000, 1499999998) . Fred Lunnon

4 21

[math-fun] Finding numbers represented by indefinite binary quadratic forms
by Neil Sloane 05 Jun '14

05 Jun '14

Does anyone have a program for doing the following: Given an indefinite binary quadratic form ax^2+bxy+cy^2 (with discriminant b^2-4ac>0 and not a square) and a positive or negative number n, decide if ax^2+bxy+cy^2 = n has a solution. (If n = p is a prime, one can use the PARI command qfbsolve(Qfb(a,b,c),p) ) Neil

5 5

Re: [math-fun] algebraic geometry query
by Dan Asimov 04 Jun '14

04 Jun '14

[I sent this 1.5 hours ago, but through some glitch it still hasn't shown up in my Inbox.] CORRECTION: Where I wrote "In R^n, let W be a compact connected (n-1)-dimensional submanifold with connected boundary M = bd(W)," the correct dimension of W should be n (not n-1), as corrected below. Also, the affiliation mentioned is no longer current. --Dan ----- Hmm, Why wouldn't C^0 (just continuous) work. In R^n, let W be a compact connected n-dimensional submanifold with connected boundary M = bd(W). Claim: ------ If a continuous function f: W -> R^1 (= the reals) for which 0 lies in f(W) but not in f(M), then f must have an absolute extremum in int(W) = W - M. Proof à la Latto: ----------------- Since f is continuous on the compact set W, it must have both an absolute minimum and an absolute maximum on W. Since f is nonzero on the connected set M, f must take M into either (0,oo) or (-oo,0). If the former, f must have a local minimum in int(W); if the latter f must have a local maximum in int(W). [ ] Corollary: ---------- If f is also differentiable on int(W), then it has a critical point there (since any local extremum x of a function differentiable in a neighborhood of x must have a critical point at x). -----

2 7

Re: [math-fun] Shortest Euler path (driving a car) through all US states except Alaska & Hawaii
by Henry Baker 04 Jun '14

04 Jun '14

I believe that what you have described is the "Travelling Salesman Problem", not the Euler problem. TSP is the Fedex/UPS/Amazon(?) delivery problem. Euler problem is easily solveable (whether possible), TSP is NP-hard. https://en.wikipedia.org/wiki/Travelling_salesman_problem https://en.wikipedia.org/wiki/Seven_Bridges_of_K%C3%B6nigsberg BTW, I've never seen a mathematical characterization of what I call the "bicycle touring problem": the problem of riding for N miles on the most pleasant roads possible without repeats (or without significant repeats). The focus is on _links_, not _nodes_, and we want to maximize the pleasantness of the total trip, or perhaps minimize the maximum unpleasantness of the worst link. The BTP may be closer to the Euler problem than the TSP. At 11:36 AM 6/4/2014, Thane Plambeck wrote: >I thought this was interesting...a Google map allegedly showing how to >drive a car through the lower 48 USA states, visiting each state [at least? >exactly?] once and minimizing the total distance travelled. > >http://goo.gl/maps/90i0Y > >-- >Thane Plambeck >tplambeck(a)gmail.com >http://counterwave.com/

2 1