June 2012 - mathfun@mailman.xmission.com

Re: [math-fun] Gun problem
by Michael Kleber 14 Jun '12

14 Jun '12

So I coded the "combinatorial type" stuff up in Mathematica also, letting me ask it things like region["<>"] --> v[1] < v[2] region["<<>>"] --> v[2] < v[3] && 3 + v[2]/(-v[2] + v[3]) <= If[v[2] <= v[1], Infinity, (2*v[2] - 1*v[1])/(v[2] - v[1])] && 3 + v[2]/(-v[2] + v[3]) <= If[v[4] <= v[3], Infinity, (4*v[4] - 3*v[3])/(v[4] - v[3])] && v[1] < v[4] Then integrating Boole[region[type]] over the appropriate-dimensional unit cube gives me probability["<>"] --> 1/2 probability["<<>>"] --> 5/24 - Log[2] + (9/16) Log[3] probability["<><>"] --> 1/6 + Log[2] - (9/16) Log[3] So I tried the same for the simplest situation I could think of on 6 bullets: take the combinatorial type "<<<>>>", where there's only one possible time-order in which the collisions can occur, and restrict it to one linear ordering of the velocities, so I can pre-resolve all those If[]s that depend on whether some pair of bullets would eventually meet: r = Simplify[region["<<<>>>"], v[1] < v[2] < v[3] < v[4] < v[5] < v[6]] --> v[1]*(2*v[3] - 3*v[4]) <= v[2]*(v[3] - 2*v[4]) && v[3]*(v[2] + v[4]) <= 2*v[2]*v[4] && v[4]*(v[3] + v[5]) >= 2*v[3]*v[5] && v[4]*v[5] + 3*v[3]*v[6] <= 2*(v[3]*v[5] + v[4]*v[6]) && v[2]*(v[1] + 3*v[5]) <= 4*v[1]*v[5] && v[2]*(-3*v[5] + 4*v[6]) <= v[5]*v[6] Integrate[Boole[r], {v[1],0,1},{v[2],v[1],1},{v[3],v[2],1},{v[4],v[3],1},{v[5],v[4],1},{v[6],v[5],1}] The Mma computation blows up -- I just let it get to around 22GB of RAM, at which point it started swapping and brought my machine to its knees. Anyone have a better idea of how to figure out the probability that 6 bullets from David's gun all annihilate each other? --Michael -- Forewarned is worth an octopus in the bush.

1 0

[math-fun] Wilson's 1D gun problem, reply to Kleber objection.
by Warren Smith 13 Jun '12

13 Jun '12

> From: Gareth McCaughan <gareth.mccaughan(a)pobox.com> > Warren Smith wrote: > >> The bullet that annihilates the leader, follows a line segment in the >> time-space plane. >> This line segment totally separates what came before & what follows. >> The new stuff is a total restart, totally independent of all the previous >> stuff. > > Really? > > If "before" means "before the time at which that bullet is > fired" or something of the kind: the line segment doesn't > separate "before" from "after" because it's at an angle. --before/after means more precisely on one side vs other of that line. > If "before" means "on the earlier side of the line segment": > the line segment does separate "before" from "after" but > that doesn't make "before" and "after" independent, because > e.g. if the-bullet-that-annihilates-the-leader leaves at > time t then a superfast bullet at time t+1 would hit *that* > bullet, making it not annihilate the leader after all. So > conditional on that bullet actually annihilating the leader, > there are speed constraints on bullets fired shortly after > that one that weren't there at time t=0. > > Am I missing something here? --ok, you (Gareth) are correct, it is not independent because a superfast bullet "after" would not be permitted. However, intuitively speaking, it seems like this kind of lack of independence only helps my argument, not hurts it. So the proof seems no longer to be a proof, I agree, but the "flaw" in the proof at least *seems* to only be helping the proof... i.e. it does not (or hardly at all) diminish my faith that my answer is correct. Further, perhaps this intuition can be made rigorous? Modify Wilson's problem so that the permitted velocity range is not [0,1] but rather [0,X] for some positive constant X, or allow X to be an increasing function of time trapped in [0,1]. Obviously this with X constant is an equivalent problem (just rescale time) and with X varying in trapped-monotone-increasing manner as defined, it seems to me all previous arguments still work. Now in my proof, Gareth's complaint basically causes us to have the [0,X] version of the problem for various X with 0<X<1 during period after each "reset" where X increases back toward 1. This would seem only to make my argument more true?

2 1

[math-fun] clock of nines
by Stuart Anderson 13 Jun '12

13 Jun '12

saw this on facebook https://fbcdn-sphotos-a.akamaihd.net/hphotos-ak-prn1/551099_429862577048001… there is a problem, what's the best fix? and how to generalise for all digits?

4 3

[math-fun] Wilson's 1D gun problem, reply to Kleber objection.
by Warren Smith 12 Jun '12

12 Jun '12

>> CASE A: > *IF* we knew that probability-sum approached infinity, or more precisely > that > the total number of leader-replacements -->infinity almost surely > (which follows from its expectation being infinite), > then we'd know every leader gets replaced > eventually, hence could deduce that the ultimate speed of the rightmost guy > does NOT tend to 1, since no matter how far you go into the future, > there are moments > when the current leader is killed whereupon the situation is sort of > wholy reset. >Michael Kleber: I don't believe that's correct. It could be the case that we expect the rightmost bullet to get replaced infinitely often, and also that the probability distribution of the speed of successive rightmost bullets tends to be weighted more and more heavily towards 1. --WDS: The bullet that annihilates the leader, follows a line segment in the time-space plane. This line segment totally separates what came before & what follows. The new stuff is a total restart, totally independent of all the previous stuff. Hence the new speed probability distribution from then on, is the same as the old one starting at time=0. >Kleber: That is, I don't see any reason to believe that the PDF(velocity of bullet fired at time 10^3 that turns out to be rightmost) is the same as PDF(velocity of bullet fired at time 10^6 that turns out to be rightmost). >(I talked about this a little in my first (excessively long) mail on the subject.) --well, hopefully you now DO see a reason to believe a version of this.

2 1

[math-fun] reverse-engineering biased Galton boards
by James Propp 12 Jun '12

12 Jun '12

Suppose we want to create a biased (n-1)-level Galton board so that the distribution of the balls at the bottom will be governed by some specific probability vector (p_1,p_2,...,p_n). This is a massively underdetermined problem; there are lots of ways to choose biases at the n(n-1)/2 junctions so as to generate this distribution at the nth level. But suppose we have the additional goal of minimizing the effect that slight perturbations of the biases will have. Is there a unique best choice of biases, and if so, what is it? Here we're dealing with a map from R^{n(n-1)/2} to R^n, so it's not clear to me what the right way to measure sensitivity to perturbations is. But I suspect that this problem has a nice canonical answer if one chooses some natural way to measure sensitivity. Example: Take n=3, with (p_1,p_2,p_3) = (1/3,1/3,1/3). Let the bias at the top of the Galton board be q:1-q, and let the biases at the second level be r:1-r and s:1-s. We want (*) qr=1/3, q(1-r)+(1-q)s=1/3, and (1-q)(1-s)=1/3. This has a one-parameter family of solutions r=1/(3q) and s=1-1/(3-3q) (but we won't actually use this fact explicitly in the analysis appearing below). Suppose we have such a solution q,r,s. Now consider the perturbed solution q',r',s' with q'=q+x, r'=r+y, s'=s+z. The difference between the perturbed vector (q'r',q'(1-r')+(1-q')s',(1-q')(1-s')) and the vector (1/3,1/3,1/3), up to first order, is v(x,y,z) := (rx+qy,(1-r-s)x-qy+(1-q)z,(s-1)x+(q-1)z). If we now replace x,y,z by independent Gaussian random variables X,Y,Z with mean 0 and variance 1, we find that the expected squared magnitude of v(X,Y,Z) is r^2+q^2+(1-r-s)^2+q^2+(1-q)^2+(s-1)^2+(q-1)^2, which equals (**) 4-4q-2r-4s+4q^2+2r^2+2s^2+2rs. If instead of variance 1 we use variance epsilon, that just multiplies the expected squared magnitude of d(X,Y,Z) by a factor of epsilon. So it's natural to try to minimize the expression (**) subject to the constraints (*). Use Lagrange multipliers L, M, N: Setting the partial derivatives of 4-4q-2r-4s+4q^2+2r^2+2s^2+2rs with respect to q, r, s, L, M, and N equal to 0, we obtain six equations, three of which are (*) and three of which are L(r) + M(1-r-s) + N(s-1) = -4+8q L(q) - M(q) = -2+4r+2s M(1-q) - N(1-q) = -4+2r+4s When Maple solves this system, it gives only one solution with q, r, and s positive, namely (q,r,s) = (1/2,2/3,1/3). I'm betting that more generally there's some unique way to minimize sensitivity to error, and that the biases that minimize sensitivity to error are rational functions of p_1,...,p_n. Any ideas, anyone? I'm open to other candidate definitions of what it means to minimize sensitivity; I just picked the one that seemed most natural to me. Jim Propp

1 0

[math-fun] Provably Winning Go games at high handicap
by Warren Smith 12 Jun '12

12 Jun '12

Perhaps relevant (but I doubt it) is this. Gunnar Farneback has been testing how many handicap stones a "random player" needs to win versus a sensible go-playing program. I'm not sure of his precise definition of "random player," but he provides a program so there is one. Gnugo ~=~ random+(20 to 22) stones; the strongest program GF's tried ~=~ random+(29-to-32); these all are on a 9x9 board. Assuming scaleup linearly with area, the strongest programs versus a random player on a 19x19 board would play even if random were given about 134 handicap stones.

1 0

[math-fun] Lester Hill and Error Correcting Codes
by Victor Miller 12 Jun '12

12 Jun '12

This looks interesting (Hill was the guy who invented the Hill cipher): http://wdjoyner.wordpress.com/2012/06/11/lester-hill-and-error-detecting-co… Victor

1 0

Re: [math-fun] Provably Winning Go games at high handicap
by John Tromp 12 Jun '12

12 Jun '12

dear Warren, > Play "go" on an NxN grid (usual is N=19). In "H-handicap" go, the second player > (white) generously passes his first H turns, before starting to play. > For example, > some pro could easily give me handicap H=9 and still destroy me. > > PUZZLE: for the smallest H that you can, formulate a strategy such that > the first player can assure a win, even against a perfect opponent. In this configuration . . . . . . . . . @ . . . . . . . . . . . . . . . . . . @ . . . . . . . . . . . . . . . . . . @ . . . . . . . . . . . . . . . . . . @ . . . . . . . . . . . . . . . . . . @ . . . . . . . . . . . . . . . . . . @ . . . . . . . . . . . . . . . . . . @ . . . . . . . . . . . . . . . . . . @ . . . . . . . . . . . . . . . . . . @ . . . . . . . . . @ @ @ @ @ @ @ @ @ . @ @ @ @ @ @ @ @ @ . . . . . . . . . @ . . . . . . . . . . . . . . . . . . @ . . . . . . . . . . . . . . . . . . @ . . . . . . . . . . . . . . . . . . @ . . . . . . . . . . . . . . . . . . @ . . . . . . . . . . . . . . . . . . @ . . . . . . . . . . . . . . . . . . @ . . . . . . . . . . . . . . . . . . @ . . . . . . . . . . . . . . . . . . @ . . . . . . . . . with white to move, Black can be assured of having the first move in 2 quadrants. Playing on a (3,3) point denies white to chance to survive in that corner (even with white playing first on (3,3), life is questionable). Any of the top go programs should be able to attest to that, but turning that into a formal proof is still a big challenge; black has to play enough stones to deny white enough eye space, and connect them to his central chains, which are easily made unconditionally alive. regards, -John

2 1

[math-fun] Wilson's 1D gun problem -- now solved(?)
by Warren Smith 11 Jun '12

11 Jun '12

Michael Kleber: So to bring things back closer to David's original question, these constructions prove that the probability of the current rightmost bullet getting replaced eventually is nonzero. Can anyone prove that that probability is 1? Or might there be some configuration of bullets in which we expect the current rightmost bullet to survive forever? --Warren Smith: well, the trouble is, the probability certainly is nonzero and my construction as slightly corrected by Wechler shows that. But it might be that the sum of all replacement probabilities over all states in the whole infinite future, i.e. the expected total number of replacements, is 0.001... But now this argument occurs to me: CASE A: *IF* we knew that probability-sum approached infinity, or more precisely that the total number of leader-replacements -->infinity almost surely (which follows from its expectation being infinite), then we'd know every leader gets replaced eventually, hence could deduce that the ultimate speed of the rightmost guy does NOT tend to 1, since no matter how far you go into the future, there are moments when the current leader is killed whereupon the situation is sort of wholy reset. This also shows the position of the rightmost is NOT asymptotic to t. CASE B: On the other hand, if we know the total number of leader-replacements stays finite almost surely, then it seems to me we'd also know that the rightmost guy's speed does not tend to 1, but rather to some V<1 which after some amount of time just stays constant forever after. Then the leader position is asymptotic to V*t, not t. CASE C: With some probability P (0<P<1) the number of replacements is infinite, but with probability 1-P it stays finite. Then it seems to me you can argue using a mixture of the A and B arguments. CONCLUSION: So this three-pronged argument seems to me to settle Wilson's question: Does the leader-speed tend to 1 with time t? Does his position asymptote to t? Answers: "no" and "no." However, this ultimately seemed a little too easy, so maybe I screwed up; certainly I've left the details kind of loose. Assuming I did not screw up, and this really is that easy, then actually this "easy" argument might be generalizable to have pretty wide applicability to proving way more stuff, and it'd be nice to figure out what that is.

3 2

Re: [math-fun] Wilson's 1D gun problem
by Michael Kleber 11 Jun '12

11 Jun '12

> > But I think he is right. I think a simpler proof is the next n shots > all use exactly > the maximum allowed speed. This kills the previous n bullets assuming > none used exactly max speed. Then the next M-n shots all are arranged > to annihilate in chronologically-successive pairs. > No, that's not correct: some of the n currently-living bullets may annihilate each other before these speed=1 (or 1-e) bullets reach them. But as I said before, there is certainly *some* number of bullets you can fire which will make this plan work. --Michael -- Forewarned is worth an octopus in the bush.

2 2