Interesting Geometry/Statistics problem

• May 10th 2011, 09:23 AM
DannyOcean
Interesting Geometry/Statistics problem
Take the Unit Circle. Let U1 and U2 be two randomly distributed points on the Unit Circle, and let L1 be the line that connects them. Let V1 and V2 be two additional randomly distributed points on the unit circle, and let L2 be the line that connects them.

What is the probability that L1 intersects L2?

I've got an idea of how this might work, but I'm not sure. You can map the Unit circle to a straight line of length 2pi, and maybe arbitrarily rotate so that U1 is at 0. Then U2 is a uniform random variable from 0 to 2pi. Is this good so far?

Then, L2 will only intersect L1 if either V1 < U2 < V2 or V2 < U2 < V1. If V1, V2 > U2 or V1, V2 < U2 then the lines will not intersect when mapped to a circle. Therefore, we need to find the P( V1, V2 > U2) + P(V1, V2 < U2). Again, does this seem correct?

That's where I'm not sure how to continue. Can anyone comment on my approach to the problem so far and where I should go from here? There's also a more general question but I can save that for later.
• May 10th 2011, 10:22 AM
SpringFan25
impressive idea.

you can get the probabilities v1 < u2 < v2 etc using convolutions, its a triple integral though (ouch! should be perfectly doable though).

alternatively, can you make a symmetry argument you for the order of v1 , v2 , u2? since they are i.i.d it seems to me that they all must have the same chance of being in the middle, ie 1/3.
• May 10th 2011, 10:51 AM
Plato
Here is another way to look at it.
The points $U_1~\&~U_2$ define two arcs of the circle.
In order for the chords to insect, $V_1$ must be on one of the arcs and $V_2$ must be on the other.

Those four points can be arranged on the circle in $3!=6$ ways.
But there are only two of the in which $V_1$ is not 'next to' $V_2~.$
• May 10th 2011, 02:12 PM
DannyOcean
Quote:

Originally Posted by Plato
Here is another way to look at it.
The points $U_1~\&~U_2$ define two arcs of the circle.
In order for the chords to insect, $V_1$ must be on one of the arcs and $V_2$ must be on the other.

Those four points can be arranged on the circle in $3!=6$ ways.
But there are only two of the in which $V_1$ is not 'next to' $V_2~.$

So basically, we're saying that every arrangement of the four points is equally likely, which makes sense, because the points are are randomly distributed on the unit circle. And because the 6 arrangements are equally likely, we simply take [arrangments that produce an intersection]/6 and get 2/6 = 1/3. Starting from U1, we would say specifically,

U1 - U2 - V1 - V2
U1 - U2 - V2 - V1
U1 - V1 - V2 - U2
U1 - V2 - V1 - U2

Would not produce any intersections and

U1 - V1 - U2 - V2
U1 - V2 - U2 - V1

Would produce intersections. Thus, 1/3. Is this correct?

If that seems good, there's a generalization which asks "What is the probability that given similar points W1 and W2 which join to make L3, that L1 passes through both L2 and L3?" And then, for some arbitrary number of Li's formed by similar points.

At that point, we could still assume that U1, U2, V1, V2, W1, W2 have 5! possible arrangements, all equally likely. We would be interested in these arrangements that look like

U1 (some combination of a V and W) U2 (combination of a V and W). By my count, there are 16 such arrangements, so the odds that L1 passes through L2 and L3 are 16/5!. Does this part look correct?

Generalizing for L2, L3, .... Li,

the total number of arrangements will be (2i-1)!. The arrangements we are looking for look like

U1 (some combination of V, W, ... i) U2 (combination of V, W, ....i)

Any idea what kind of factorial expression we could use to find this number of arrangements?
• May 10th 2011, 02:35 PM
Plato
Well I do agree with your 16 favorable arrangements.
However, I am not sure how you generalize to the n case.
Each pair points must be on different arcs determined by each other pair.
• May 10th 2011, 06:38 PM
DannyOcean
Ok, after thinking about it here's my idea. Please comment if you think this logic is good/bad/hilarious/etc.

the n case of our first line L0 (I renamed it for ease) passing through L1, L2, L3... Ln should go something like this. we need exactly one point of each line between U1 and U2 on each side, like

U1 (One V, One W, ... one point from the nth line) U2 (One V, One W, ... one point from the nth line)

Now, how many ways can we choose just which points go in the first set of parentheses? I think this is 2^n, because we can either choose V1 or V2, then either choose W1 or W2, all the way to the nth case, which is a choice of two options n times, giving me 2^n total choices.

Now that we've chosen which go in the first set of parentheses and which go in the second, how many ways can they be ordered? Well, there are n terms in each group, so that's N! for each.

So i think the total number of combinations of points that will give us L0 passing through L1, L2... Ln is (2^n)*n!*n!. The total number of ways the points can be ordered overall is (2n-1)!
• May 11th 2011, 06:15 AM
Plato
To be honest, I am not sure where your approach is going.
The bad news is that we were both wrong in the case of $n=3.$
There are 8 favorable arrangements and not 16.

After a good night’s sleep, I have found a simple way of modeling this.
I will give you the answer I found: $2^{n-1}(n-1)!$