I would add to this: suppose you give each vertex in the square lattice a uniformly random real-valued “height" in the unit interval. We now perform local greedy search that tries to minimize the height: start at a vertex, and move to the neighbor with the lowest height, until you reach a local minimum where all the neighors are higher than the current vertex. Each local minimum has a “basin of attraction”, i.e., a set of initial vertices which will lead to it if we carry out this process. The distribution of the sizes of these basins is complicated. But what is their average size? (This is rather like Veit’s second problem…) - Cris
On Nov 19, 2017, at 12:53 PM, Veit Elser <ve10@cornell.edu> wrote:
This kind of question brings up the phenomenon of probability distributions that are very hard to compute and yet have easily computed expectation values. Here are two of my favorite examples:
1. The expected number of sides of the Voronoi cells for random, homogeneously distributed points in the infinite plane.
2. The expected number of stars per constellation, in the model where stars are distributed homogeneously over an infinite plane (large sphere) and assigned to constellations (connected graphs) by the rule that each star is joined by an edge to its nearest neighbor.
-Veit
On Nov 17, 2017, at 2:08 PM, James Propp <jamespropp@gmail.com> wrote:
To get the answer, let's treat the number of vertices of the random polygon P as a sum of indicator functions, so that the expected number of vertices is the sum of the probabilities of the events associated with those indicator functions. (I'll be concise and possibly confusing here, since the style of reasoning is similar to one I've described in greater detail before.) Each of the three vertices of the first triangle contributes 1/4, since that's the probability that the vertex will fall inside the second triangle when it's translated by a random vector that makes the intersection of the two triangles nonempty (you can obtain 1/4 as the ratio of two areas). Each of the three vertices of the second triangle contributes 1/4 for the same reason. So we get six contributions of 1/4. Meanwhile, for any edge e of the first triangle and any edge e' of the second triangle not parallel to e, the probability that they'll give rise to a vertex of P is 2/4 (again obtained as a ratio of two areas), so we get six contributions of 2/4. So the expected number of vertices is 1/4+1/4+1/4+1/4+1/4+1/4+2/4+2/4+2/4+2/4+2/4+2/4 = 18/4 = 9/2.
Veit also solved the puzzle, and his solution is slicker than mine:
"The intersection has either 4 or 6 sides. The locus of translations of the down triangle that gives an intersection is the up triangle scaled by 2. Join the edge midpoints of that triangle to give a partition into 4 congruent triangles, one of which is a translate of the down triangle, the other three translates of the up (all four have the same area). If the translation belongs to one of the up partitions, the intersection has 4 sides. In the other case, the intersection has 6 sides. The expected number of sides is therefore (3/4)4 + (1/4)6."
Either way, we see that a "random" intersection of a rightside-up unit triangle with an upside-down unit triangle is a semi-enneagon! :-)
Jim
On Wed, Nov 15, 2017 at 6:08 PM, James Propp <jamespropp@gmail.com> wrote:
Nobody? ...
Maybe these puzzles are less fun than I thought. (Or maybe "Fun is fun, but enough's enough.")
I like the fact that the answer to this one isn't a whole number.
One frustrating feature of this particular puzzle is that someone with no mathematical training might guess the correct answer using bogus reasoning.
Jim
On Tue, Nov 14, 2017 at 10:13 PM, James Propp <jamespropp@gmail.com> wrote:
Here's an easier puzzle of the same kind; it's probably the one I'd present to people first now that I know about it, since the calculations are simpler:
What's the expected number of vertices in the intersection of a rightside-up equilateral triangle and an upside-down equilateral triangle of the same size, conditioned on the event that the intersection is nonempty?
(The equilaterality of the triangle is a red herring; any triangle and its rotated-by-180-degrees twin will do.)
I'll let someone else have the fun of posting a solution.
Jim Propp
On Sat, Nov 11, 2017 at 11:06 AM, James Propp <jamespropp@gmail.com> wrote:
Let H be a regular hexagon and t a translation vector, so that H+t is a translate of H. Here's one way to prove that the average number of sides in the intersection of a H with H+t, conditioned on the event that the intersection is nonempty, is 5. (Veit found a nicer way, but I'll get to that later.)
A polygon P obtained by intersecting H with H+t can have three different sorts of vertices: a vertex of H, a vertex of H+t, and the intersection of an edge of H with an edge of H+t. So we can write the expected number of vertices of P as a sum of 48 probabilities (many of which are equal to one another, by symmetry): the probability that a particular vertex v of H belongs to H+t (which we sum over the 6 vertices v of H), the probability that a particular vertex v+t of H+t belongs to H (which we sum over the 6 vertices v of H), and the probability that a particular edge e of H intersects a particular edge e'+t of H+t (summed over all 24 pairs of nonparallel edges e,e' of H). But these probabilities are all easy to interpret geometrically and thus easy to compute.
First, let's find the common denominator of these probabilities: the area of the set of vectors {t: the intersection of H and H+t is nonempty}. This is the Minkowski difference H-H, and since H is centrally symmetric, it's just 2H (up to translation). Since H is made of 6 unit equilateral triangles, 2H has area equal to 24 unit equilateral triangles. (I'll just say "area 24" from now on.)
Now, on to the numerators and the probabilities! For each vertex of H, the set of vectors t for which that vertex of H belongs to H+t is just a translate of H, with area 6; so the probability that the vertex v belongs to H+t is just the area of H divided by the area of 2H, or 6/24=1/4. We get 6 such terms, for a total of 6/4 = 3/2. Likewise, for each vertex v of H, the probability that v+t belongs to H is 3/2. Finally, consider the pairs e,e'. The set of vectors t for which e intersects e'+t is just a parallelogram, namely, the parallelogram spanned by e and e' (treated as vectors), which consists of two unit triangles; so the probability measure of the set {t: e intersects e'+t} is 2/24, or 1/12. Summing over all 24 pairs e,e', we get 24/12, or 2. Finally, we add up all the probabilities, obtaining 3/2 + 3/2 + 2 = 5 as the expected number of vertices.
Veit's proof collapses the 24 edge-meets-edge terms into a single term whose value is the constant 2! What's more, his argument can be used to show that for any centrally symmetric 2n-gon, the expected number of vertices in the intersection of the 2n-gon with a translate of itself, conditioned on the event that the intersection is nonempty, is exactly n+2. The part of his argument that I still don't understand is this: how do we know that (generically) the boundaries of the two 2n-gons intersect exactly twice?
Jim Propp
On Mon, Nov 6, 2017 at 10:07 PM, James Propp <jamespropp@gmail.com> wrote:
I wrote:
> I actually know two different proofs of the result. One follows the > approach to such problems that I learned from George Hart (see his email to > math-fun from October 18), and the other follows the approach I learned > from Warren Smith (see my email to math-fun from October 19). If you look > at their solutions to the random-slices-of-a-cube problem you might be > inspired, as I was, to see how to solve the random-intersecting-parallelog > rams-puzzle. > > George's method can also be used to prove that if you take a random > nonempty intersection of a regular hexagon with a translate of itself, the > expected number of sides is exactly 5. >
Hint: instead of counting sides, count vertices.
I'll sketch the proof tomorrow or Wednesday, if nobody beats me to it.
Anyway, two days have passed since I posted the puzzle, so I think it's > appropriate to have an unbridled conversation, with or without spoilers. >
Let me say, by way of motivation, that the "George-style" proof is really sweet. You'll feel good when you find it.
Jim
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun