A question of random points in a square and probability of intersection of their line segments

Question

The following is a problem from PUMaC 2007:

Take the square with vertices $(0,0)$, $(1,0)$, $(0,1)$, and $(1,1)$. Choose a random point in this square and draw the line segment from it to $(0,0)$. Choose a second random point in this square and draw the line segment from it to $(1,0)$. What is the probability that the two line segments intersect?

I tried to find the probability by taking the general point $(x,y)$ and finding the region in which the second point should lie so that the line segments intersect, however, I am stuck in this step. My idea was to find the area of the region, divide by area of the square to get probability and then double integrate wrt y and x to get probability. I have failed at this after multiple attempts, If the region is a triangle (which is erroneous) I got the answer as $3/8$ , and if I try to do the general case, I find that the integral does not converge.

(Do note, over here vertices are adjacent, not opposite)

Answer 1

Let the square be $ABCD$ and the points $P$ and $Q$.
Consider the bent lines $APC$ and $BQD$. They intersect once, so by symmetry the chance that $AP$ and $BQ$ cut is $1/4$.

Answer 2

This is basically the same solution the Stef presented in the comments, but completing the final step.

Let $A=(0,0)$ and $B=(1,0)$. Pick random points $P$ and $Q$ and draw the line $l$ through $P$ and $Q$.

There is a probability $1/2$ that $l$ intersects the line segment $AB$. One way to see this is that it intersects two of the sides of the square (ignoring the probability zero case of it passing through one of the corners), and by symmetry (the four rotations of the square), all sides are equally likely.

If $l$ intersects the line segment $AB$, the line segments $AP$ and $BQ$ will be on separate sides of the line $l$ and therefore not intersect.

If $l$ does not intersect the line segment $AB$, then the points $A$, $B$, $P$, $Q$ are the corners of a convex quadrilateral. The quadrilateral with points in order will be either $ABQP$ or $ABPQ$ depending on which of the points $P$ and $Q$ share a side of the quadrilateral with $A$ and $B$. If the quadrilateral is $ABQP$, then $AP$ and $BQ$ do not intersect; if the quadrilateral is $ABPQ$, then $AP$ and $BQ$ intersect. Since $P$ and $Q$ are picked independently, these two cases are equally likely.

So, the likelihood that $AP$ and $BQ$ intersect is $1/2\times1/2=1/4$: first that $l$ does not intersect $AB$, and then the order of $P$ and $Q$ on the convex quadrilateral.

Answer 3

Your integration method should work, but it's tedious.

I think there's a "clever" way.

Call A (0,0) and B (1,0) the two square corners. Call X and Y the two random points.

There are three possible (disjoint) events:

• (E1) := [AX] and [BY] intersect;
• (E2) := [AX] and [BY] don't intersect, but [AY] and [BX] intersect;
• (E3) := [AX] and [BY] don't intersect and [AY] and [BX] don't intersect either.

By symmetry we have $P(E1) = P(E2)$. Geometrically we can also see: $E_1 \cup E_2$ if and only if XY has slope < 1.

By symmetry P(XY has slope < 1) = P(XY has slope > 1) = 1/2.

Hence P(E_1) = P(XY has slope < 1) / 2 = 1/4.

Answer 4

This answer extends what the OP has tried.

Let $O=(0,0)$ and $P=(1,0)$, $U = (U_1,U_2)$, $V = (V_1,V_2)$ with $U_1,U_2,V_1,V_2$ iid $\mathcal U([0,1])$.

We look for $P(OU\cap PV\neq \emptyset) = E[E[1_{OU\cap PV\neq \emptyset}|U]]$. We fix a point $A=(a_1,a_2)$ in the square and we compute the conditional expectation $E[1_{OU\cap PV\neq \emptyset}|U = A]$. Since $U$ and $V$ are independent, this is the same as $P(OA\cap PV\neq \emptyset)$.

Let $I$ denote the point where the line $PA$ intersects the square. Let $\mathcal R$ denote the region of the square located "behind" the points $O,I,A$. Your mistake is in thinking that $\mathcal R$ is always a triangle. When $a_2>1-a_1$, this region has $4$ sides.

Note that the line $PA$ has equation $y= \frac{a_2}{1-a_1}(1-x)$.

Case 1: $a_2\leq 1-a_1$. The region $\mathcal R$ is a triangle with base $OI$, hence with length $\frac{a_2}{1-a_1}$, and height $a_1$, thus with area $\frac{a_1a_2}{2(1-a_1)}$.

Case 2: $a_2> 1-a_1$. The region $\mathcal R$ has 4 sides and it is more convenient to compute the area of the complement, which is the disjoint union of two triangles. One has area $\frac{1-a_1}{2a_2}$ and the other $\frac{a_2}2$.

Thus $P(OA\cap PV\neq \emptyset) = P(V\in R) = 1_{a_2\leq 1-a_1}\frac{a_1a_2}{2(1-a_1)} + 1_{a_2> 1-a_1}[1-\frac 12(\frac{1-a_1}{a_2} + a_2)]$.

Finally, the probability $P(OU\cap PV\neq \emptyset)$ is $$E\Big[1_{U_2\leq 1-U_1}\frac{U_1U_2}{2(1-U_1)} + 1_{U_2> 1-U_1}[1-\frac 12(\frac{1-U_1}{U_2} + U_2)] \Big].$$

The Mathematica command

Integrate[
 1/2*(x*y)/(1 - x), {x, y} \[Element] 
  ImplicitRegion[y <= 1 - x && 0 < x < 1 && 0 < y < 1, {x, y}]]
+ 
 Integrate[(1 - 1/2*((1 - x)/y + y)), {x, y} \[Element] 
   ImplicitRegion[y > 1 - x && 0 < x < 1 && 0 < y < 1, {x, y}]]

yields an answer of $\frac 14$.