wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> easy >> Random Chord Intersection
        
(Message started by: william wu on Dec 15^th, 2004, 8:51pm)

Title: Random Chord Intersection
Post by william wu on Dec 15^th, 2004, 8:51pm

RANDOM CHORD INTERSECTION

Two chords are drawn at random on a circle. What is the probability that these chords intersect?

Source: Piyush Shanker

Note 1: A "random chord" is generated in the following intuitive way: Draw two points uniformly at random over the circumference of the circle. Then connect those two points.

Note 2: There is a clever way to solve this very quickly, without evaluating any integrals.

======================
Harder variants (added 7:05 PM 12/18/2004)

- Compute the probability distribution of the number of chord intersections when three chords are dropped.

- What about N chords?

Title: Re: Random Chord Intersection
Post by Noke Lieu on Dec 15^th, 2004, 10:40pm

Going to have a stab... probability isn't my strong point. Probably. Accordingly, I reckon that if I set off in the right direction, not going to be able to wrap it up.

Assuming- not sure what difference it makes- that the chords are distinct. Oh that goes for points too.
[hide]

Two points on the circle. Cut into two arcs... 2[pi]r(a) and 2[pi](a-1).

For the chords to NOT intersect... need the next two points on the same arc.

[/hide]
That makes me think of this (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi?board=riddles_easy;action=display;num=1090592289)

Poop. Run out of steam- and time. ...

Title: Re: Random Chord Intersection
Post by Grimbal on Dec 16^th, 2004, 12:20am

[hide]Basically, you take 4 points on the circle and you pair them. With 4 points, there are 3 ways to pair them, only one of them with an intersection. So the probability is 1/3.[/hide]

Title: Re: Random Chord Intersection
Post by Noke Lieu on Dec 16^th, 2004, 3:40pm

DAMN IT!
That's how I started... I figured it wasn't enough. Oh well.

Title: Re: Random Chord Intersection
Post by Sir Col on Dec 16^th, 2004, 4:48pm

As I couldn't think of an approach as clever as Grimbal's, I ignored note 2 and solved it (inelegantly) by integration...

Between any two points on a circle there are two arcs; call them s1 and s2. Let P(point in s1)=p and P(point in s2)=q=1-p.

For a given p, P(two chords intersect)=2p(1-p)=2p-2p².

As we are dealing with a uniform distribution, we integrate 2p-2p² between 0 and 1 to give, P(intersection)=1/3.

I suppose a challenging extension would be to explore the probability of three random chords intersecting; that is, none, two, or three. Even harder, if X represents the number of points of intersection, find P(X=r), where r=0,1,2,3.

Title: Re: Random Chord Intersection
Post by william wu on Dec 18^th, 2004, 6:56pm

In case anyone is unclear about the slick solution, the following picture I made should clear it up. In the diagram below, we have a circle with four points A, B, C, and D randomly placed along the circumference:

http://www.ocf.berkeley.edu/~wwu/images/riddles/randomChordIntersection.png

These points represent the endpoints of the two chords, and due to the facts that 1) the points are distributed uniformly at random, and 2) we have circular symmetry, the actual positions do not matter. All that matters is which endpoints belong to which chords.

Without loss of generality, let's assume point A is an endpoint for the first chord. Then we will have an intersection only if the other endpoint of this first chord is point C. So the probability of intersection is 1/3.

====

Using the same geometrical inspirations as above, but with six points on the circumference, I tried Sir Col's challenge. This problem was quite a bit harder since there were many more cases. I broke it up into the following scenarios:
::[hide]
0) 0 intersections
1a) 1 intersection, given that the first chord is not intersected
1b) 1 intersection, given that the first chord is intersected
2) 2 intersections
3) 3 intersections
[/hide]::
Also, I used the 1/3 result from the original problem many times. In the end, I computed the following answers (hidden; highlight the area below with your mouse to reveal):
::[hide]
Pr(X = 0) = 1/3
Pr(X = 1) = 2/5
Pr(X = 2) = 1/5
Pr(X = 3) = 1/15
[/hide]::
The distribution sums to 1 (a good check), and it agrees with a MATLAB simulation I wrote, so it's right ;) You can adjust "numChords" in the code below to simulate the problem for higher numbers of chords -- but don't go too high or you'll be sorry. The simulation unwraps the circle into a unit interval, draws pairs of points uniformly at random, and then uses the observation that two chords intersect iff exactly one of the endpoints of a chord lies in the interval spanned by the endpoints of the other chord.

Code:

%RANDOMCHORDINTERSECTION Uses simulation to determine the distribution of
%number of intersections when chords are dropped uniformly at random onto a
%circle. - William Wu 6:41 PM 12/18/2004
clear; clc; close all;
numChords = 3;
numTrials = 100000;
numIntersections = zeros(1,numTrials);
maxIntersections = nchoosek(numChords,2);
for k=1:numTrials
chords = rand(numChords,2);
chords = sort(chords')'; % second column has higher values
idx = nchoosek(1:numChords,2);
for m=1:maxIntersections
numIntersections(k) = numIntersections(k) + ...
overlapCheck( chords(idx(m,1),:),chords(idx(m,2),:) );
end
end
[N,X] = hist(numIntersections,0:maxIntersections);
bar(X,N/numTrials); grid on;
title(sprintf('empirical distribution with %d chords and %d trials',numChords,numTrials));
fprintf(1,'empirical distribution: %s\n',num2str(N/numTrials));

function overlapFlag = overlapCheck(a,b)
% a(1) is within the bounds of b, and a(2) is outside bounds
x = (b(1)<a(1))&(a(1)< b(2))&(b(2) < a(2));
% or, a(2) is within the bounds of b, and a(1) is outside bounds
y = (b(1)<a(2))&(a(2)< b(2))&(b(1) > a(1));
overlapFlag = (x | y);

Title: Re: Random Chord Intersection
Post by Sir Col on Dec 19^th, 2004, 3:52am

I've spent quite a bit of time on this and I don't think that there is a general solution for the number of intersections. I have, however, derived a formula for the probability of no intersections with r chords...

For r chords there will be n=2r points on the circle.
Given the first chord is connected to one of these points there are (n-1) other end points it can connect to.
The end point of the "second" chord can connect to (n-3) other points.
Similarly the other chords will be able to connect to (n-5), (n-7), ..., 5, 3, 1 other end points.

Therefore, the number of ways of drawing r chords, R, is given by,
R = (n-1)(n-3)...5*3*1 = (2r-1)(2r-3)..*3*1 = (2r)!/(r!*2^r)

The hard part is finding the number of ways that no chords can intersect. After a little investigating I found an amazing connection with Catalan numbers.

Imagine that the n points are numbers sequentially 1 to n around the circumference of the circle.

If one of the chords is (1,3), then the chord connected to 2 must intersect (1,3). So there must be an even number of points between each pair of connected points, but even this does not guarantee.

I then was reminded of a similar investigation. I'm not sure what it is called, so I shall call it the "bracket string" problem: given r pairs of brackets (one left and one right), how many bracket strings can we form?

For example,
r=1: () [)( is not considered a bracket string]
r=2: ()(), (())
r=3: ()()(), ()(()), (())(), (()()), ((()))

The number of solutions are given by the rth Catalan number: C=(2r)!/((r+1)!r!). More importantly, it can be seen that if the left and right brackets represent end points of a chord, the number of solutions to this problem is equivalent to the number of solutions to the number of non-intersecting chords.

Hence P(X_r=0) = C/R = [(2r)!/((r+1)!r!)]/[(2r)!/(r!*2^r)] = 2^r/(r+1)!, where X_r is the number of intersections for r chords.

For example, P(X₁=0)=1, P(X₂=0)=2/3, P(X₃=0)=1/3, P(X₄=0)=2/15.

Obviously the complement of this gives the probability that there is at least one intersection, but given the complexity of the derivation for this particular case, I doubt we're going to find a general solution for each of the separate probabilities.

Title: Re: Random Chord Intersection
Post by william wu on Dec 19^th, 2004, 4:10pm

That's a nice observation Sir Col. I don't feel certain though about whether a general solution is not possible for n chords ... I was hoping for a recursive expression.

It's interesting to note that the parenthetical analogy seems to break down when counting a nonzero number of intersections. For instance, consider the string

(()())

which can be interpreted as the following for 0 intersections:

( () () )

or the following for one intersection:

( ()() )

or the following for two intersections:

( ()() )

Here is some more empirical data for higher chord values; the true answers would round to some nice rationals:

===
4 chords:

0.13374
0.26962
0.26681
0.18711
0.09545
0.03731
0.00996

http://www.ocf.berkeley.edu/~wwu/images/riddles/four_chords.png

empirical average: 1.9980
theoretical mean: 2

===
5 chords:

0.04484
0.12675
0.1907
0.20846
0.17365
0.12194
0.07316
0.03806
0.01566
0.00553
0.00125

http://www.ocf.berkeley.edu/~wwu/images/riddles/five_chords.png

empirical average = 3.3308
theoretical mean = 10/3

===
6 chords:
0.01235
0.04757
0.09709
0.13683
0.1578
0.15587
0.13212
0.10195
0.06926
0.04402
0.02527
0.01175
0.00548
0.00191
0.00066
7e-005

http://www.ocf.berkeley.edu/~wwu/images/riddles/six_chords.png

empirical mean: 5.0023
empirical variance: 6.0224
theoretical mean: 5

Note the nice shapes. I believe the asymptotic distribution is Gaussian. For N chords, we can express the number of intersections as the sum of C(N,2) indicator random variables, each taking on the value of 1 if a particular pair of chords intersects (which occurs with probability 1/3). These indicator variables are not independent. However, in the limit when we have many chords, they are almost independent. From CLT we know that the sum of K iid random variables is Gaussian with mean K[mu] and variance K[sigma]². There are also some more precise variants of the CLT specifically for weakly dependent random variables.

Title: Re: Random Chord Intersection
Post by Sir Col on Dec 19^th, 2004, 5:18pm

Using your experimental results and the formula I derived for the number of ways we can connect r chords: R = (2r)!/(r!*2^r), we can obtain an estimate of frequencies/theoretical probabilities.

I've included a spreadsheet with a summary of the calculations. For example, when r=4, we obtain:
P(X=0)=14/105
P(X=1)=28/105
P(X=2)=28/105
P(X=3)=20/105
P(X=4)=10/105
P(X=5)=4/105
P(X=6)=1/105

The numerators for P(X=0) are the Catalan numbers: 1, 2, 5, 14, 42, 132, ..., but maybe someone else can recognise the other numerators? Beware though, as you can see that the expected frequencies become less reliable as r increases. It estimated P(X=0)=128/10395 for r=6, when it should be 132/10395.