21
$\begingroup$

The square $[0,1]^2$ is cut into some number of regions by $n$ random lines. We can chose these random lines by randomly picking a point on one of the four sides, picking another point randomly from any of the other three sides and then connecting the dots. We do this $n$ times.

What is the probability after $n$ lines that the largest region has area $1/2$ or greater?

(A follow-up question: Is the circle in the square best at avoiding random lines?)

$\endgroup$
  • $\begingroup$ To this upper bound of $0.862^n$ I can add a rather weak lower bound of $\frac1{6^n},$ this is the probability that the tilted square with vertices at the edge midpoints is in a single region. $\endgroup$ – Aaron Meyerowitz Jul 17 '17 at 21:47
  • $\begingroup$ @AaronMeyerowitz: One can also get $1/6^{n-1}$ as a lower bound by observing that this is the probability that all lines are between the same two edges. $\endgroup$ – Christian Remling Jul 17 '17 at 22:29
  • $\begingroup$ @ChristianRemling: Don't these two edges have to be opposing for your bound to hold? But the problem statement does not guarantee that condition. $\endgroup$ – David G. Stork Jul 17 '17 at 22:34
  • $\begingroup$ @MattF: Your bound cannot be very tight, as it is $>1$ for $1 \leq n \leq 4$. Moreover, we know the probability for $n=1$ is 1.0, not $1.732$, as given by your bound. $\endgroup$ – David G. Stork Jul 17 '17 at 22:42
  • 1
    $\begingroup$ Isn't the upper bound $1.0$, because all points could be on adjacent edges, so that no lines ever cut through the isosceles right triangle defined by the other two edges of the square, and hence the largest region will remain that triangle regardless of $n$? $\endgroup$ – David G. Stork Jul 18 '17 at 0:12
11
$\begingroup$

Aaron and fedja have pointed out that the problem is equivalent to finding the convex region in the plane with area $1/2$ with the highest probability that a random line does not intersect it.

The optimal convex region $\Delta$ has boundary a union of eight segments, each satisfying a differential equation from a certain one-parameter family, that hence are smooth.

Pick a corner of the square, choose coordinates so that that corner is point $(0,0)$, and consider the segment of the boundary $C$ of $\Delta$ whose tangent lines touch the two sides of the square adjacent to that point.

If we write this segment of $C$ as the graph of a decreasing function $y(x)$, then the tangent line at the point $(x,y)$ connects the points $\left(x- \frac{y}{\dot{y}},0\right)$ and $\left(0, y+ \dot{y}x \right)$ on these two sides, where $\dot{y}$ is the derivative with respect to $x$. So if we plot the region in the $a,b$ plane consisting of those $(a,b)$ such that the line connecting $(a,0)$ and $(b,0)$ does not intersect $\Delta$, the boundary of that region is the parameteric curve $\left(x- \frac{y}{\dot{y}}, y- \dot{y}x \right)$ and thus the area of the region is $$ - \int \left(x- \frac{y}{\dot{y}} \right) \frac{d}{dx} \left(y - \dot{y}x \right) dx$$

$$= - \int \left(x- \frac{y}{\dot{y}} \right) \left(\frac{dy}{x} - \ddot{y}x - \dot{y} \right) dx$$

$$= \int x \ddot{y} \left(x- \frac{y}{\dot{y}} \right) dx$$

the negative sign being because $\left(y- \dot{y}x \right)$ is a decreasing function of $x$ by convexity.

So we are optimizing $$ \int x \ddot{y} \left(x- \frac{y}{\dot{y}} \right) dx$$ subject to an upper bound on $ \int y dx$ which by Lagrange multipliers is equivalent to optimizing

$$ \int x \ddot{y} \left(x- \frac{y}{\dot{y}} \right) dx - \lambda \int y dx$$

for some $\lambda>0$.

By calculus of variations, if we set $F(y, \dot{y}, \ddot{y}) = x \ddot{y} \left(x- \frac{y}{\dot{y}} \right) - \lambda y$, then the optimal value of $y$ satisfies $$\frac{dF}{dy} - \frac{d}{dx} \left( \frac{dF}{d \dot{y}} - \frac{d}{dx} \left(\frac{dF}{d \ddot{y}} \right) \right) =0$$

We can evaluate $$\frac{dF}{d \ddot{y}} = x^2 - \frac{xy}{\dot{y}}$$ $$\frac{d}{dx} \left(\frac{dF}{d\ddot{y}} \right)= 2x-\frac{y}{\dot{y}} - x + \frac{xy \ddot{y}}{\left(\dot{y}\right)^2}$$ $$ \frac{dF}{ d\dot{y}} =\frac{xy \ddot{y}}{\left(\dot{y}\right)^2}$$ $$ \frac{dF}{d \dot{y}} - \frac{d}{dx} \left(\frac{dF}{d \ddot{y} }\right) = \frac{y}{\dot{y}} -x $$ $$ \frac{d}{dx} \left( \frac{dF}{d \dot{y}} - \frac{d}{dx} \left(\frac{dF}{d \frac{dy^2}{dx^2}}\right) \right) = 1 - \frac{y \ddot{y}}{\left( \dot{y}\right)^2} -1$$

$$\frac{dF}{dy} = - \lambda - x \frac{\ddot{y}}{\dot{y}}$$

so the differential equation is

$$ - \lambda - x \frac{\ddot{y}}{\dot{y}} + \frac{y \ddot{y}}{\left( \dot{y}\right)^2} =0$$

or

$$ \lambda \left( \dot{y}\right)^2 +( x \dot{y} -y )\ddot{y} =0$$

If we let $t= \dot{y} \frac{x}{y}$ be the dimensionless derivative, then $\dot{y} = t\frac{y}{dx}, \ddot{y} = \frac{d}{dx}\left( t\frac{y}{x}\right)= \dot{t}\frac{y}{x} + t^2 \frac{y}{x^2} - t \frac{y}{x^2} =\frac{y}{x^2} \left( \frac{dt}{d\log x} +t^2-t\right)$

so we can write the equation (ignoring factors of $y$ or $x$) as

$$ \lambda t^2 + (t-1) \left( \frac{dt}{d\log x} + t^2-t \right) =0$$

$$\frac{dt}{d \log x} = - \lambda \frac{t^2}{t-1} + t -t^2 $$

so either we have $t$ a constant solution of $(t^2-t)(t-1) + \lambda t^2 =0$ with $y$ a constant times $x^t$ or we can express $\log x$ and $\log y$ as integrals of rational functions of $t$.

$$\log x = \int \frac{1}{ - \lambda \frac{t^2}{t-1} + t -t^2} dt$$

$$\log y = \int \frac{t}{ - \lambda \frac{t^2}{t-1} + t -t^2} dt$$

Matt F. in the comments did the integrals and found that the formulas, while explicit, are quite nasty. Perhaps this can be fixed by changing the parameter, but this seems unlikely.

It should be possible to do similar calculations for the other kind of segment, but the next step would be to calculate the different ways these segments can be stitched together, which amounts to solving an equation involving eight of these explicit solutions. That seems difficult unless the solutions are really nice - although I'm sure it can be done with the aid of a suitable computer algebra system.

$\endgroup$
  • $\begingroup$ Nice. The only "spoon of tar" I have to add is that you should be a bit careful with the calculus of variations in such problems: quite often the extrema are attained "at the boundary" (which is also quite often invisible and has to be discerned first). So, a formal proof of extremality is still due. Upvoting nevertheless :-) $\endgroup$ – fedja Jul 22 '17 at 19:54
  • $\begingroup$ @fedja Thanks! I'll think about the boundary. Ill think about enumerating all the possible boundary conditions. There's a couple I'm pretty sure I know how to rule out - straight line edges and corners. There's some that appear for certain sizes - small enough bodies will have every tangent line passing through two opposite sides, and so the parametric curve I describe hear will not appear but some other curve will. However, I think one can check if my analysis is completed that this does not occur at area 1/2. $\endgroup$ – Will Sawin Jul 22 '17 at 20:42
  • $\begingroup$ @fedja It seems likely that large enough optimal convex bodies touch the sides, but again probably not for 1/2 - in particular it can't possibly touch all the sides, unless it's a diamond, which we know is not optimal. $\endgroup$ – Will Sawin Jul 22 '17 at 20:42
  • $\begingroup$ Is there a reason to use $dy/dx$ here rather than the $\dot{y}$ notation more common in calculus of variations? That would make this easier to read. $\endgroup$ – Matt F. Jul 22 '17 at 20:44
  • $\begingroup$ @MattF. Probably not. If I return to this (such as by solving the equation for the sides of the shape) I will fix that. $\endgroup$ – Will Sawin Jul 22 '17 at 20:51
7
$\begingroup$

UPDATED AGAIN Here are some lower bounds and the results of $10^6$ random trials. The $1$-dimensional case is quite informative and is discussed at the end.

One way to get an exponential lower bound is to choose an area $1/2$ subset and find the chance that it remains intact after $n$ lines. A tilted square, the intact isosceles right triangle after the first line (if there is one), an optimal octagon and centered circle (in that order) give such bounds which are increasingly good. However an exponential model is not the right one to use.

  • The chance that a single line avoids the tilted square with corners $(1/2,0),(1,1/2),(1/2,1),(0,1/2)$ (of area $1/2$) is $1/6:$ With probability $1$, the point first chosen is not a corner of the original square or the tilted one. wlog it is on the left half of the bottom. Then the second point needs to be on the lower half of the right side. The chance of this is 1/6. So the chance that none of $n$ lines cut the tilted square is $$\frac1{6^{n}}.$$

  • This can be improved to $$\frac4{6^n}=\frac2{3\cdot 6^{n-1}}$$ by considering instead isosceles right triangles. The chance that the first line crosses two adjacent sides is $2/3.$ If this does happen then one of the diagonals misses this line and splits the square into two isosceles right triangles with area $1/2.$ One is cut and the other intact. For every subsequent choice the first point is outside the intact half with probability $1/2$ and the second with probability $1/3.$

  • Here is a certain octagon along with the circle with center $(\frac12,\frac12)$ and radius $\frac1{\sqrt{2\pi}}.$ enter image description here I find that the octagon above is the best of its kind. I get that the probability it stays intact is about $$(\frac{2(0.4797667)}3)^n=0.31984^n.$$ The lower left corner is at about $(0.32606,0.11670).$

  • For the octagon, and also the circle, the exact probability of a line missing it can, in principle, be found using several integrals. They are not that nice so I evaluated them numerically. The probability of a line missing the circle is about $.34470989$ hence $$0.34470989^n.$$

    Perhaps some shape of the form $t$circle+$(1-t)$octagon beats the circle. However another octagon might do even better for that process.


It is not all that hard to randomly generate lines. One need only keep track of the vertices of the one maximum area region. Then a new line either misses it or intersects two of the sides creating two new vertices and two regions.

In $10^6$ random trials it happened $4$ times that only the $20$th line left all regions with size less than $\frac12.$ Of course the first line is always OK. $187209$ times the second line was fatal, the other $812791$ it wasn't. The counts were

$$[1, 1000000], [2, 812791], [3, 580116], [4, 376623], [5, 228824], [6, 131445],$$$$ [7, 72077], [8, 38186], [9, 19805], [10, 10009], [11, 4852], [12, 2299],$$$$ [13, 1070], [14, 540], [15, 259], [16, 113], [17, 47], [18, 18], [19, 4]$$

As suggested by Emil, the correct model is possibly of the form $f(n) c^n$ for some $f(n)$ with sub-exponential growth. This is supported by the following:


Consider the similar problem in $1$-dimension:

The interval $[0,1]$ is divided into $n+1$ subintervals by $n$ random points. What is the probability that the longest subinterval has length at least $\frac12?$

It turns out that the exact answer is $\frac{n+1}{2^n}.$ It is easiest to prove the more general form: Given that the largest currently surviving interval has length $\frac12+x,$ the probability of surviving the next $n$ random points is $$\frac{n(2x-1)+1}{2^n}.$$

Given this exact result, we don't need an upper bound. But getting one helped me understand Christian's method: I claim that an upper bound, valid for all $n$ is $$N\left(\frac12+\frac1N\right)^n.$$ Fix an integer $N>2$ and consider the $N$ intervals $I_t=[\frac{t}{2N},\frac{t}{2N}+\frac{N-1}{2N}]$ with $1 \leq t \leq N.$ A subinterval $[s,s+\frac12]$ contains one of these (move each endpoint inward to the nearest $\frac{a}{2n}.$) If some interval of length $\frac12$ stays undivided, so does at least one of the $I_t.$ The chance that any particular one stays undivided by $n$ random points is $(\frac12+\frac1N)^n.$ So the chance that at least one does is less than $N\left(\frac12+\frac1N\right)^n.$ This is an upper bound on what we seek.

$\endgroup$
  • 2
    $\begingroup$ Getting the sharp exponential asymptotics for (very) large $n$ is the usual game of finding the convex region of area $1/2$ in the unit square such that the "missing probability" is the largest. The circle you mentioned is not a very bad competitor in this game but, most likely, still slightly suboptimal. It would, probably, be the true answer if we had another circle instead of the outer square. $\endgroup$ – fedja Jul 18 '17 at 14:08
  • 1
    $\begingroup$ I think one could in principle relate the area of a convex area given by functions $y_1(x), y_2(x)$ to the probability of not hitting it with a random line by working out where the tangent lines hit the surrounding square and integrating. But it's very messy because one has to distinguish various cases depending on which sides exactly the tangent lines hit. $\endgroup$ – Christian Remling Jul 19 '17 at 3:00
  • 1
    $\begingroup$ As mentioned by fedja, and partly explained in Christian Remling’s answer, the probability is $(c+o(1))^n$, where $c$ is the probability of being missed by a random line for a convex region of area $1/2$ that maximizes $c$. By eyeballing the picture, it should be clear that $c$ cannot be much higher than what the centered disk gives (i.e., 0.3447). It is certainly nowhere near 0.56. $\endgroup$ – Emil Jeřábek supports Monica Jul 21 '17 at 17:26
  • 2
    $\begingroup$ I don’t think the problem is in the data, but in the interpretation. The argument suggests the answer is not really of the form $a\cdot c^n$, but rather $f(n)c^n$ for some unbounded (even if subexponential) function $f$. So trying to fit it to something of the form $a\cdot c^n$ will not be very accurate, and it will overestimate the base of the exponential. Put in other way, if $p(n)$ is the probability, then $\frac1n\log p(n)$ will converge to $c$ from above, and potentially rather slowly. You only have a few datapoints, so the estimate is likely unreliable. ... $\endgroup$ – Emil Jeřábek supports Monica Jul 21 '17 at 20:48
  • 3
    $\begingroup$ It is easy to see, though, that the truly optimal region has neither straight lines nor corners. If you extend a straight line out to a round region a distance $\epsilon$, the area increases by a factor linear in $\epsilon$ whereas any lines that now hit the body that didn't before must have both endpoints in region of size $O(\epsilon)$, so the loss there is $O(\epsilon^2)$. With a corner, it's the same but opposite - cutting off the corner by epsilon loses $O(\epsilon^2)$ and gains something linear in $\epsilon$. $\endgroup$ – Will Sawin Jul 22 '17 at 9:24
6
$\begingroup$

Thinking of numbers on a clock-face, say that one of these lines is:

  • an 8-2 slash iff it goes from $(0,L)$ to $(1,R)$ with $0<L<3/7<4/7<R<1$.
  • an 11-5 slash iff it goes from $(T,1)$ to $(B,0)$ with $0<T<3/7<4/7<B<1$.

enter image description here

Each of these figures shows an 8-2 slash (in red), an 11-5 slash (in blue), and the acceptable ranges for endpoints (in green).

An 8-2 slash and an 11-5 slash together divide the square into pieces of area at most 227/455, which is less than 1/2, and which is the case shown in the second figure. So the probability that $n$ lines leave an unbroken region of area greater than 1/2 is at most

$$P(\text{no 8-2 slashes}) + P(\text{no 11-5 slashes}) - P(\text{no 8-2 slashes & no 11-5 slashes}).$$

Now consider the probability of an 8-2 slash. The probability that a randomly chosen line goes from the top to the bottom is $1/6$. The probability that such a line is an 8-2 slash is $(3/7)^2$, so the overall probability of an 8-2 slash is $3/98$. This is the same as the probability of an 11-5 slash.

Thus the probability of an unbroken region of area greater than 1/2 is at most $$\left(1-\frac{3}{98}\right)^n + \left(1-\frac{3}{98}\right)^n - \left(1-\frac{6}{98}\right)^n = 2\left(\frac{95}{98}\right)^n - \left(\frac{92}{98}\right)^n .$$

This is enough to establish an exponential upper bound.

$\endgroup$
6
$\begingroup$

A crude, but easy to prove (given fedja's comment to Aaron's answer) upper bound is $(2/3+\epsilon)^n$ for all $\epsilon>0$ and for large $n$.

This follows by just observing that if we fix any point on the boundary and connect it to one or two arcs whose combined length is more than $2/3$ of the remaining three sides, the area covered is always $>1/2$. So for any convex area $|A|\ge 1/2$ whatsoever, the probability of not hitting $A$ with a random line is $p_A\le 2/3$.

For a given $\delta>0$, we can find finitely many sets $A_1,\ldots , A_N$ (convex polygons, let's say), $|A_j|\ge 1/2-\delta$, such that every convex $|A|\ge 1/2$ contains an $A_j$. (This seems intuitively clear, but to be perfectly honest, I didn't think very hard about this; it's similar in spirit to compact subsets being a compact space themselves with respect to Hausdorff distance.)

As discussed above, the probability of a random line not intersecting $A_j$ is $\le 2/3+\epsilon$, so the claim follows.

$\endgroup$
  • 1
    $\begingroup$ This confuses me. Aaron provided a lower bound; how does the comment give an upper bound? I also don't understand "the area covered" without more explanation. $\endgroup$ – Matt F. Jul 19 '17 at 12:26
  • 2
    $\begingroup$ @MattF.: The structure of the argument is: (1) For a fixed area $|A|\ge 1/2$, the probability that this area will be left intact by $n$ random lines is $\le (2/3)^n$ (this is immediate; in fact, even with one endpoint $a$ fixed, at most $2/3$ of the lines through $a$ will not intersect $A$); (2) by a compactness argument, the prob we're interested in is $\lesssim (2/3+\epsilon)^n$ also, for any given $\epsilon>0$. $\endgroup$ – Christian Remling Jul 19 '17 at 17:47
  • $\begingroup$ That's nice. So would it be correct to say that for each positive $\epsilon$ there is an $N$ so that $N(\frac23+\epsilon)^n$ is an upper bound valid for all $n?$ $\endgroup$ – Aaron Meyerowitz Jul 22 '17 at 6:53
  • $\begingroup$ @AaronMeyerowitz: Yes, that's right, that's exactly what this shows. $\endgroup$ – Christian Remling Jul 22 '17 at 16:03
6
$\begingroup$

This is really a comment to ChristianRemling that requires a figure, so please don't down-vote it.


If "all lines connect the same two adjacent edges" (as you write), then the probability a region of area greater than $1/2$ survives is always 1.0, as illustrated by this figure:

enter image description here

Note that every tight bound (for the full problem with arbitrary edge connections) should yield for $n=1$ that the probability is $1.0$. (Several proposed answers do not have that value.) The lowest lower bound for $n=2$ is clearly $0$, as it is possible the two lines split the area into regions each having area less than $1/2$.


Some background information: What is the average size of the largest remaining region after the first cut?

One of the sides is chosen for the first point, and (without loss of generality) we rotate the figure so that this is at the bottom. Call the position of its end $x_1$. There are three remaining sides, each chosen with probability $1/3$. The point on one adjacent side (see left figure) is at $x_2$ and the area of the largest portion is $1 - x_1 x_2/2$. (The calculations for the other adjacent side are the equivalent.) The opposite side (see right figure) creates two areas, and we choose the largest. The expected area of the largest surviving region is thus:

${1 \over 3} \int\limits_{x_1=0}^1 \int\limits_{x_2=0}^1 (1 - x_1 x_2/2)\ dx_1\ dx_2 \\ + {1 \over 3} \int\limits_{x_1=0}^1 \int\limits_{x_2=0}^1 (1 - x_1 x_2/2)\ dx_1\ dx_2 \\ + {1 \over 3} \int\limits_{x_1=0}^1 \int\limits_{x_2=0}^1 \max({1 \over 2} |x_2-x_1| + x_1, 1 - {1 \over 2} |x_2-x_1| + x_1)\ dx_1 dx_2 \\ = {1 \over 3}{7 \over 8} + {1 \over 3}{7 \over 8} + {1 \over 3}{2 \over 3} = {29 \over 36}$.

enter image description here

Now one might make the very oversimplified assumption that the shapes of such regions on successive cuts are independent (they are not!) and compute the expected "surviving" largest area by intersection areas, then compute the probability this area is greater than $1/2$ as a function of $n$.

$\endgroup$
  • $\begingroup$ @ChristianRemling: I agree. That's why I was so confused by your explicit statement "all lines connect the same two adjacent edges." What did you mean by "same two adjacent edges"? $\endgroup$ – David G. Stork Jul 18 '17 at 23:29
  • $\begingroup$ But your formula does not correspond to what I drew in my figure (as I wrote). What corresponds to my figure is $p_n = 1.0$ for all $n$, not your answer of $1/6^{n-1}$. $\endgroup$ – David G. Stork Jul 18 '17 at 23:39
  • 4
    $\begingroup$ The probability that the first line connects some two adjacent sides is $\frac23.$ For each subsequent line, the probability that it connects those same two adjacent sides is $\frac16.$ So with probability $\frac23(\frac16)^{n-1}$ an isosceles right triangle is empty and for THAT REASON the largest intact region has area over $\frac12.$ $\endgroup$ – Aaron Meyerowitz Jul 19 '17 at 8:25
  • $\begingroup$ Will you change "the lower bound" to "one lower bound"? $\endgroup$ – Matt F. Jul 19 '17 at 13:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.