Re: [math-fun] More random polygons: fun puzzle

On Fri, Nov 24, 2017 at 4:38 PM Allan Wechsler <acwacw@gmail.com> wrote:

> I did the arithmetic all wrong. I think I got the linear coefficient right,
> but the quadratic one is certainly less than 20. Perhaps I will do a more
> careful census over the weekend, especially if anybody else on list shows
> any sign of understanding what I'm doing and being interested :)
>
> On Fri, Nov 24, 2017 at 2:30 PM, Allan Wechsler <acwacw@gmail.com> wrote:
>
> > The quadratic coefficient is 20, corresponding to three new shapes, two
> > pentagons and a hexagon. One pentagonal type has an area of 11/8; the
> other
> > pentagon (equivalent, I believe, to baseball's home plate) and the
> hexagon
> > both have areas of 3/2.
> >
> > On Fri, Nov 24, 2017 at 2:17 PM, Allan Wechsler <acwacw@gmail.com>
> wrote:
> >
> >> Harking back to Veit's problem, I once tried making inroads on a
> >> closely-related discrete problem. Suppose the randomly-chosen centers
> are
> >> confined to lattice-points, each point populated with probability p.
> What
> >> does a typical Voronoi cell look like, and how does this vary with p? I
> >> adopt the convention that q = 1-p.
> >>
> >> At p=1, all the cells are just squares. As p falls from 1, some of the
> >> cells, with a probability of 4q, become pentagons of area 1.25. The
> >> expected area of the cells thus has a Taylor series in q that starts 1
> + q
> >> + ... At some point I calculated the quadratic and cubic coefficients of
> >> this series, considering more-and-more-elaborate cell shapes, but I
> don't
> >> remember the results.
> >>
> >> On Fri, Nov 24, 2017 at 12:28 PM, Cris Moore <moore@santafe.edu> wrote:
> >>
> >>>
> >>> 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
> >>>
> >>>
> >>> _______________________________________________
> >>> 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
>