June 2012 - mathfun@mailman.xmission.com

Re: [math-fun] reverse-engineering biased Galton boards
by Dan Asimov 19 Jun '12

19 Jun '12

Denote by p(i,j) the TP from (i,j) to (i+1,j), and let's set q(i,j) = 1-p(i,j) as the TP from (i,j) to (i,j+1). I seem to have showed that, given all the target probabilities T(i,j) > 0, then all the transition probabilities (TP's) are uniquely determined (UD). This holds with the conditions that I) T(i,j) > 0 for all i,j >= 0. II) For all k, T(0,k) + T(1,k-1) + . . . + T(k,0) = 1 (implicit in the statement of the problem). Proof: For k >= 0, let L_k denote all points of form (j,k) or (k,j), for j >= k. All points in the first quadrant are the disjoint union of all the (L-shaped) sets L_k. Then: * Clearly all the TP's on L_0 are UD. Hence the TP's along each edge that's emanating from and perpendicular to L_0 are also UD. * Inductively assume all the TP's that are below and/or to the left of L_k have been determined. * Then all the TP's that lie along L_k are UD. Then, so are the TP's emanating from and perpendicular to L_k are also UD. Q.E.D. by induction. ((( Example: Suppose all TP's along L_0 have been UD, and (by subtracting from 1) also the emanating perpendicular TP's as well. Now to find, say, the TP p(1,1) (from (1,1) to (1,2)) we just note that (since there are only 2 points from which a random walk can go to (1,2) in 1 step) we have: T(1,2) = T(0,2)*q(0,2) + T(1,1)*p(1,1). And so p(1,1) = (T(1,2) - T(0,2)*q(0,2)) / T(1,1) as long as T(1,1) > 0 (condition I). This method will lead to all TP's along L_1 being UD. Now suppose we want to find a TP emanating from and perpendicular to L_1, like q(1,3). We already know the *other* TP emanating from (1,3), namely p(1,3), and so q(1,3) is UD via q(1,3) = 1 - p(1,3). ))) The TP's are clearly *not* UD if the Q(i,j) have enough 0's among them. But I think in that case all the TP's going to point (i,j) with Q(i,j) > 0 *are* UD, so the TP's that are non-UD would seem to be irrelevant. --Dan ________________________________________________________________________________________ It goes without saying that .

1 0

[math-fun] Proof(?) that black can always win 19x19 go with 25 handicap stones
by Warren Smith 19 Jun '12

19 Jun '12

1 0

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

18 Jun '12

Here's a (hopefully clearer) statement of the question. Consider a random walk on ZxZ that starts at (0,0) and progresses n-1 steps upward and rightward, ending at some vertex (i,j) with i,j non-negative integers summing to n-1, such that p_{i,j} is the probability that a walker at (i,j) will go to (i+1,j) (and 1-p_{i,j} is the probability that a walker at (i,j) will go to (i,j+1)). Thus the path taken in the first n-1 steps is determined by all the p_{i,j}'s with i,j non-negative integers with sum no greater than n-2. Suppose we want to choose those n(n-1)/2 probabilities p_{i,j} so that the probability of the walker being at (n-k,k-1) is some specified number p_k (1 leq k leq 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 after n steps. 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. What I actually want is not necessarily the most noise-insensitive way of biasing the junctions, but a reasonably noise-insensitive way of biasing the junctions that is also easy to compute and mathematically natural. (Yes, "natural" is even more vague than "noise-insensitive".) When I posted the problem I thought that minimizing noise-sensitivity would lead to a nice way of biasing the junctions, but now I'm not so sure, since I've done some more analysis of my original idea about how to measure noise-sensitivity, and it leads to nasty algebraic expressions (e.g., polynomial equations that can't be solved in terms of radicals). Jim Propp

3 3

[math-fun] fun with incircles & excircles
by Henry Baker 18 Jun '12

18 Jun '12

[Error *** below fixed.] I imagine that this is probably well-known by Euler/Gauss/..., but here goes anyway: If you take the incenter and the centers of the 3 excircles as four complex points, and then form a quartic polynomial with complex coefficients that has these 4 points as _roots_, you can compute the coefficients of this polynomial using only rational operations on the coordinates of the 3 vertices of the triangle. In other words, you never need to compute the perimeter itself, which seems to require 3 square roots, nor do you have to compute the lengths of any of the sides (by themselves). Here are the 4 incenters/excenters, where a,b,c are the side lengths, and A,B,C are the coordinates of the vertices; A,B,C are complex numbers. I0:(a*A+b*B+c*C)/(a+b+c); this is the incenter Ib:(a*A-b*B+c*C)/(a-b+c); this is the excenter on the b side Ic:(a*A+b*B-c*C)/(a+b-c); this is the excenter on the c side Ia:(-a*A+b*B+c*C)/(-a+b+c); this is the excenter on the a side If you take the _centroid_ of these 4 in/excenters, you get the _circumcenter_ of the original triangle(!). If you form the polynomial (w-I0)(w-Ia)(w-Ib)(w-Ic) and clear fractions, a,b,c will only appear as a^2,b^2,c^2,a^4,b^4,c^4. Since the square of the side length for a can be computed as (C-B)(C-B)', we don't need any sqrt's to form the equation. Of course, to solve this quartic equation, we will then compute at least one square root. Of course, we could always utilize Newton with an initial guess of the original triangle's centroid/median. Since the roots are known to be well separated -- by the triangle sides themselves ! -- such a Newton iteration should be well-behaved. I believe that a 4th degree polynomial in Q(i)[w] is the lowest degree that has any of these centers as roots. In other words, once you extend the field to contain one of them, you get the other 3 "for free". Note that the coefficient of the cubic term of this (monic) quartic is minus *** 4x *** the centroid of the roots, and hence minus *** 4x *** the circumcenter of the original triangle.

2 1

[math-fun] fun with incircles & excircles
by Henry Baker 17 Jun '12

17 Jun '12

I imagine that this is probably well-known by Euler/Gauss/..., but here goes anyway: If you take the incenter and the centers of the 3 excircles as four complex points, and then form a quartic polynomial with complex coefficients that has these 4 points as _roots_, you can compute the coefficients of this polynomial using only rational operations on the coordinates of the 3 vertices of the triangle. In other words, you never need to compute the perimeter itself, which seems to require 3 square roots, nor do you have to compute the lengths of any of the sides (by themselves). Here are the 4 incenters/excenters, where a,b,c are the side lengths, and A,B,C are the coordinates of the vertices; A,B,C are complex numbers. I0:(a*A+b*B+c*C)/(a+b+c); this is the incenter Ib:(a*A-b*B+c*C)/(a-b+c); this is the excenter on the b side Ic:(a*A+b*B-c*C)/(a+b-c); this is the excenter on the c side Ia:(-a*A+b*B+c*C)/(-a+b+c); this is the excenter on the a side If you take the _centroid_ of these 4 in/excenters, you get the _circumcenter_ of the original triangle(!). If you form the polynomial (w-I0)(w-Ia)(w-Ib)(w-Ic) and clear fractions, a,b,c will only appear as a^2,b^2,c^2,a^4,b^4,c^4. Since the square of the side length for a can be computed as (C-B)(C-B)', we don't need any sqrt's to form the equation. Of course, to solve this quartic equation, we will then compute at least one square root. Of course, we could always utilize Newton with an initial guess of the original triangle's centroid/median. Since the roots are known to be well separated -- by the triangle sides themselves ! -- such a Newton iteration should be well-behaved. I believe that a 4th degree polynomial in Q(i)[w] is the lowest degree that has any of these centers as roots. In other words, once you extend the field to contain one of them, you get the other 3 "for free". Note that the coefficient of the cubic term of this (monic) quartic is minus the centroid of the roots, and hence minus the circumcenter of the original triangle.

1 0

Re: [math-fun] Gun problem
by Dan Asimov 17 Jun '12

17 Jun '12

Yes, I love Feller's book: < http://www.amazon.com/Introduction-Probability-Theory-Applications-Edition/… >. It contains many fascinating facts in addition to the arcsine law Thane alludes to in his essay. For example, in the symmetric random walk on Z^n starting from the origin (2n equally likely ways to step), the probability of returning to the origin is 1. If n = 1 or 2, that is. For n >= 3 that probability is < 1. Another one I liked regards the probability that n people's birthdays will cluster within some time interval of a given size (that may run from one year to the next): Take this to be the probability P(n, theta) that n points independently uniformly distributed on the circle will all lie within some arc of angle theta. What I found amazing is that for fixed n, P(n, theta) is a continuous but not everywhere differentiable function of theta. --Dan Thane wrote: << Here's a little meditation on Feller (and his being dead) that I wrote in 1999 < http://www.kothreat.com/1999.06.26.htm > >> ________________________________________________________________________________________ It goes without saying that .

1 0

[math-fun] Chessboards and Wilson's Theorem
by Adam P. Goucher 17 Jun '12

17 Jun '12

Consider a p*p chessboard, and place an arrangement of p non- attacking rooks on it. There are clearly p! ways in which this can be done. If we interpret the chessboard instead as a torus, and let translations of the board be considered equivalent, then there are fewer unique arrangements. Out of the pÂ² symmetries, 1 (the identity) fixes p! arrangements; 2(p-1) (vertical/horizontal translations) fix no arrangements; and the remaining (p-1)Â² each fix p arrangements. Hence, there are [p!+p(p-1)Â²]/pÂ² = [(p-1)!+(p-1)Â²]/p unique arrangements, up to toroidal translations of the board, by Burnside's Lemma. This must be an integer, so (p-1)! is congruent to -1 modulo p. QED. Sincerely, Adam P. Goucher

3 2

Re: [math-fun] Gun problem
by Dan Asimov 17 Jun '12

17 Jun '12

Say with Michael K. that v[n] denotes the velocity of the farthest bullet right after time n. The simplest discretization of the problem, a la Jim, may be this version: Instead of the velocities being chosen from the uniform distribution on [0,1], let them be chosen from the set {1,2,3,...,K} with each having probability 1/K. This may shed light on the original problem. ----- If the answer to the original question is Yes, (*) v[n] -> 1 as n -> oo (with probability 1), then it may be easier to first show that (**) lim sup {v[1],v[2],v[3],...,v[n],...} = 1 (with probability 1). Or, maybe (**) is true and (*) isn't. ((( If I had to guess, I'd say that (*) is probably not true, because the fastest bullets are not necessarily the ones that go farthest, but are often the ones that annihilate soonest. ))) --Dan David wrote: << A gun sits on a line. Every second, the gun shoots a bullet to the right at a random constant speed between 0 and 1. If two bullets collide they annihilate. It's probability 0, but if more than two bullets collide, the slowest bullets annihilate in pairs. Can we expect the speed of the furthest bullet to approach 1 over time? >> ________________________________________________________________________________________ It goes without saying that .

2 1

Re: [math-fun] News of the Tautological
by Dan Asimov 16 Jun '12

16 Jun '12

The article states: << The research team found that fifth graders' understanding of fractions and division predicted high school students' knowledge of algebra and overall math achievement, even after statistically controlling for parents' education and income and for the children's own age, gender, I.Q., reading comprehension, working memory, and knowledge of whole number addition, subtraction and multiplication >> It's kind of interesting that they controlled for a number of other potentially confounding factors, including skill (?) in simple arithmetic. But it is so hard to make accurate causal inferences. Anyone know what the state of the art in this is? --Dan Fred wrote: << Some comments about this article indicate ominously the traditional confusion between correlation and causation. No doubt some well-intentioned official will now become hell-bent on drilling children in long-division, on the entirely unsubstantiated assumption that this will improve their mathematics. One despairs ... Rich mentioned: << "Knowledge of Fractions and Long Division Predicts Long-Term Math Success" http://www.sciencedaily.com/releases/2012/06/120615114057.htm based on a CMU press release about the paper >> >> ________________________________________________________________________________________ It goes without saying that .

1 0

[math-fun] News of the Tautological
by rcs＠xmission.com 16 Jun '12

16 Jun '12

"Knowledge of Fractions and Long Division Predicts Long-Term Math Success" http://www.sciencedaily.com/releases/2012/06/120615114057.htm based on a CMU press release about the paper R. S. Siegler, G. J. Duncan, P. E. Davis-Kean, K. Duckworth, A. Claessens, M. Engel, M. I. Susperreguy, M. Chen. Early Predictors of High School Mathematics Achievement. Psychological Science, 2012; DOI: 10.1177/0956797612440101 Rich

2 1