wu :: forums - Print Page


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

        riddles >> hard >> Random Line Segment In Square
        
(Message started by: william wu on Mar 31^st, 2003, 9:36am)

Title: Random Line Segment In Square
Post by william wu on Mar 31^st, 2003, 9:36am

Two points in a square are selected uniformly at random. Draw a line segment connecting those two points. Now a third point in the square is chosen uniformly at random. What is the probability that the third point falls on the drawn line segment?

Note: A colleague tipped me off to this problem from an exam, baffled because the professor said the answer is not 0. I also think it should be 0. If anyone can enlighten us on why it would be otherwise, your efforts will be very appreciated.

Revised:

Two points on an N x N grid are selected uniformly at random. Draw a line segment connecting those two points. Now a third point in the grid is chosen uniformly at random. What is the probability that the third point falls on the drawn line segment?

Title: Re: Random Line Segment In Square
Post by towr on Mar 31^st, 2003, 11:13am

if it's a real square, rather than a grid, I would have to go with 0 as well..
There's only an infinite number of points on a line segment, while there are infinite^2 points on a square..

Title: Re: Random Line Segment In Square
Post by william wu on Mar 31^st, 2003, 1:39pm

The answer has got to be zero. I think the question was probably not worded properly to me -- the square is most likely a grid. Now the question is more interesting. I have reworded it above.

On another note, the cardinality of the set of all points in an arbitrary continuous line segment is #R = 2^aleph-0. The cardinality of the set of all points in an arbitrary continuum square is also #R² = 2^aleph-0. (I got these facts from http://www.ii.com/math/ch/#cardinals .) However, what would be an example one-to-one mapping between a line segment and a square?

Title: Re: Random Line Segment In Square
Post by Chronos on Mar 31^st, 2003, 2:41pm

Quote:

However, what would be an example one-to-one mapping between a line segment and a square?

You take the decimal representations of the two coordinates, and interlace them. For instance, the point x=0.574964106... , y=0.418906840... would map to the point x=0.547148996046170460....

So cardinality won't help, but measure will. A lower-dimensional subspace of a higher-dimensional space will have measure zero.

But I'm not sure how to proceed for the grid case.

Title: Re: Random Line Segment In Square
Post by william wu on Apr 2^nd, 2003, 4:15am

on 03/31/03 at 14:41:33, Chronos wrote:

You take the decimal representations of the two coordinates, and interlace them.

That's neat. Thanks.

Title: Re: Random Line Segment In Square
Post by Icarus on Apr 2^nd, 2003, 8:15pm

Because of the 0.999... = 1.000... phenomenon, interlacing the decimals on the coordinates is not quite one-to-one. For instance, the numbers 83/198 and 101/198 are both mapped to the point (1/2, 1/9).

Let I = [0, 1] = {x | 0 <= x <= 1}. Define a map from I x I --> I by interlacing decimals: If x = 0.x₁x₂..., y = 0.y₁y₂..., and neither is expressed with repeating 9s (except x=1 or y=1), then (x, y) maps to the number 0.x₁y₁x₂y₂...

This defines an injection of I x I into I, (injection means that it is one-to-one: if (a, b) and (x, y) are mapped to the same number, then a=x, and b=y), but it is not surjective. That is, there are some numbers in I which are not matched to any (x, y) in I x I (83/198 is one of these numbers, as this mapping is defined to take (1/2, 1/9) to 101/198 ).

An injection from I into I x I is easy to define: x --> (x, 0).

Now you apply the Schroeder-Bernstein Theorem (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi?board=wanted;action=display;num=1034370401) to show that there must be a one-to-one correspondence (both injective and surjective) between every element of I x I and I.

Title: Re: Random Line Segment In Square
Post by James Fingas on Aug 5^th, 2003, 1:45pm

Here are a few thoughts for the grid case:

Given two endpoints (a,b) and (c,d), then the probability that a randomly chosen point on the nxn grid will be on the line segment (a,b)-(c,d) is equal to (# of grid points on the line segment)/n².

There are a few simplifications we can make: for any (a,b) and (c,d), the number of grid points on the line is the same as the number of grid points on the line segment (0,0)-(abs(a-c),abs(b-d)). So our analysis depends only on the relative sizes of a-c and b-d. Note that we will have to calculate the probabilities that we will get various distances. From now on, I will define:

g = abs(a-c)
h = abs(b-d)

Now if g and h are relatively prime, then there are only two points on the line (0,0)-(g,h). The probability that a randomly-chosen point lies on the line would thus be 2/n². If g and h are not relatively prime, then there are gcf(g,h)+1 points on the line (which also happens to work when g and h are relatively prime).

The probabilities for various g and h are independent. For each distance g there is one more way to get a distance g-1 and one less way to get a distance g+1. There is one way to get a distance g=n-1. The sum of all these probabilities is [(n)(n-1)]/2

p(g) = 2(n-g)/(n²-1)
p(h) = 2(n-h)/(n²-1)

So the overall probability is just this double sum:

P = sum_g=0..n-1sum_h=0..n-1p(g)p(h)(gcf(g,h)+1)/n²

Now this probably works out to something a little simpler...

After calculating some values for this sequence, it doesn't look any less complicated. Getting rid of the n^2 tern gives us a monotonically increasing sequence, that goes up at about O(ln(n)), but not exactly (starts off growing quickly, then gets slower, then faster again).

Title: Re: Random Line Segment In Square
Post by James Fingas on Aug 6^th, 2003, 10:01am

My apologies--I neglected the g=0 and h=0 cases in my analysis.

Since g and h are independent, I will only consider g here. Out of the n² ordered ways of choosing two grid columns, there are exactly n that give g=0. There are 2n-2 that give g=1, 2n-4 that give g=2, ... and 2 ways that give g=n-1. Adding these up, we get n². So my probability formula should read:

p(g=0) = 1/n
p(g|g <> 0) = 2*(n-g)/n²
p(h=0) = 1/n
p(h|h <> 0) = 2*(n-h)/n²

P is still the same sum. Correcting my calculations and redoing my simulation, P(n)*n² grows monotonically, but not entirely smoothly. Its overall growth rate appears to be logarithmic.

Title: Re: Random Line Segment In Square
Post by SWF on Aug 21^st, 2003, 6:14pm

By enumerating all N⁴ possible endpoints for the line, I come up with the same thing as James Fingas, but was able to simplify the result. The "1+" in the summations and the cases when g=0 or h=0 can be summed exactly. If p(N) is the probability, then
N⁶p(N)=(5N⁴-2N²)/3+4[sum][sum](N-g)*(N-h)*gcf(g,h)
where the summations are for g and h=1 to N-1, and the gcf(g,h) function means greatest common factor of g and h. Further simplifcation can be done using facts such as gcf(a,a)=a, gcf(a,a-1)=1, and gcf(1,a)=1. For example using gcf(a,a)=a and assuming gcf() is 1 everywhere else gives the approximation:
N⁶p(N)=(9N⁴-10N³+6N²-2N)/3
This is correct for N=1, 2, 3, and 4 but quickly deviates from the exact solution.

I found a good approximation (accurate to within one-quarter of one percent for N>13), but first needed to estimate probability of two numbers being relatively prime. Given two random integers from 1 to M, then for large M, the probability they are relatively prime approaches 6/[pi][sup2]=(1-1/2[sup2])*(1-1/3[sup2])*(1-/5[sup2])*... In that continued product, the first term is probability they are not both multiples of 2, second term is probability they are both not multiples of 3, ... (for each prime number up to [sqrt]M).

For an integer Q<N, find the average value of all the (N-g)*(N-h) in the summation above that have both g and h multiples of Q. If F=floor((N-1)/Q) this average is given by ([sum][sum](N-i*Q)*(N-j*Q))/F[sup2] where the sums are for i and j=1 to F. Approximating F by ((N-1)/Q-0.5) allows the summations to be evaluated as:
A(Q)=(N[sup2]+2*N-N*Q+1+Q[sup2]/4-Q)/4.
This average includes terms that are multiples of Q (i.e. gcf[ne]Q), so it is only an approximation.

For each value of Q, the number of terms in the summation that have gcf=Q, is approximately equal to 6/[pi][sup2]/Q[sup2]. This is because there is 1/Q chance of g being a multiple of Q, 1/Q chance of h being a multiple of Q, and 6/[pi][sup2] chance of g/Q and h/Q being relatively prime. The summation in the first equation above can therefore be approximated by: 4*(N-1)[sup2]*[sum]A(Q)*Q/Q[sup2]*6/[pi][sup2] summing over Q=1 to N-1. This sum can be evaluated using 1+1/2+1/3+1/4+...+1/(N-1) [approx] ln(N-1)+[gamma] ([gamma]=Euler's constant [approx] 0.5772156...):
N⁶p(N)=(5N⁴-2N²)/3+6*(N-1)[sup2]/[pi][sup2]*((N+1)[sup2]*(ln((N-1)+[gamma])-7*N[sup2]/8-N/8-1)
or using towr's formula maker:

http://www.ai.rug.nl/~towr/PHP/FORMULA/formula.php?id=59

I compared to exact value from N=1 to 6000 and this formula gives p(N) to within 0.25% for N>13, but is not as good for small N (especially N=1). For very large N, p(N) approaches 6/[pi][sup2]*ln(N)/N[sup2].

Edited Oct. 21 to fix typos in the first paragraph.

Title: Re: Random Line Segment In Square
Post by SWF on Oct 21^st, 2003, 10:02pm

Although nobody has commented in 2 months, this thread must have gained importance for William, because it is now locked at the top of the forum. Since it has high priority, I will respond to the Icarus' comment from the unsolved hard problems thread:

Quote:

Is a formula for smaller N feasible?

The previous post gave an approximation which is exact for N=1, 2, 3, and 4, and it can be further improved by using less drastic assumptions about gcf(g,h) (for that approximation it was assumed to be 1 unless g=h).

In addition to being within 0.3% for N>13, the final equation in last post is within 3% for N>4, but does not work at N=1 because of the ln(0). The ln(N-1)+[gamma] term is only there to convert the harmonic series into a standard calculator function. If ln(N-1)+[gamma] is left as H(N-1) (H(0)=0; H(1)=1; H(2)=1+1/2; H(3)=1+1/2+1/3;...), then that formula is within 1 percent for all N>3.

Title: Re: Random Line Segment In Square
Post by william wu on Oct 22^nd, 2003, 1:20am

on 10/21/03 at 22:02:04, SWF wrote:

Although nobody has commented in 2 months, this thread must have gained importance for William, because it is now locked at the top of the forum.

Actually I just did that because it's an unsolved problem, not that I feel particularly passionate about it ... I was sifting through some threads and happened upon this one, and thought perhaps the unsolved threads should all be at the top (what do you think moderators?). But I was too lazy to do this for all the threads with unresolved matters.

Title: Re: Random Line Segment In Square
Post by towr on Oct 22^nd, 2003, 1:26am

on 10/22/03 at 01:20:03, william wu wrote:

and thought perhaps the unsolved threads should all be at the top (what do you think moderators?).

I think that would mean I have to go to the second page to see new puzzles :P
Icarus' thread allready keeps track of most of them, so I think only the 'really important' threads should be at the top..

Title: Re: Random Line Segment In Square
Post by James Fingas on Oct 22^nd, 2003, 6:56am

I agree with towr on this one, and I'd like to add that at some point we should be able to forget about these problems even if they're unsolved. Of course, Icarus has his list, so there's no danger of us actually forgetting.

For instance, this puzzle (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi?board=riddles_hard;action=display;num=1030722128) is better off forgotten.

Title: Re: Random Line Segment In Square
Post by towr on Oct 22^nd, 2003, 8:04am

on 10/22/03 at 06:56:29, James Fingas wrote:

For instance, this puzzle (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi?board=riddles_hard;action=display;num=1030722128) is better off forgotten.

Yes, let's link to the puzzles we should all forget, that will make it a lot easier ;)
(though I suppose not mentioning it just entices people to look for the puzzles better left buried..)

Title: Re: Random Line Segment In Square
Post by Earendil on Oct 16^th, 2004, 12:54pm

Something similar to this problem that, perhaps could be more interesting would be to ask: What is the measure of Lebesgue of the line f(x) = x , x [in] [0,1] on R² ? and on [0,0] x [1,1] ?

Title: Re: Random Line Segment In Square
Post by Icarus on Oct 17^th, 2004, 11:30am

on 10/16/04 at 12:54:05, Earendil wrote:

Something similar to this problem that, perhaps could be more interesting would be to ask: What is the measure of Lebesgue of the line f(x) = x , x [in] [0,1] on R² ? and on [0,0] x [1,1] ?

The Lesbegue measure of any line in [bbr]² is zero. Restricting to a square doesn't change that. This is why the original version of the problem, which William has struck through, had an uninteresting "0" for its answer.

Also, what do you mean by [0,0] x [1,1]? Is this not just the point (0,1) ?

Title: Re: Random Line Segment In Square
Post by Earendil on Oct 17^th, 2004, 11:52am

Ops... I guess I meant [0,1] x [0,1]. And, yes, it is obvious that the Lebesgue measure is 0, but not that obvious to prove it (even though, not really challenging).

Title: Re: Random Line Segment In Square
Post by Icarus on Oct 18^th, 2004, 3:19pm

For segments in the square, it is not hard to prove at all. Such a line segment has length [le] [surd]2. Consider the rectangle obtained by translating the segment [delta]/2 to the left and right. The area (or, if you prefer, measure) of the rectangle is [le] [delta][surd]2. Since the original segment is contained in the rectangle, it's area is also [le] [delta][surd]2. Since [delta] is arbitrary, the area of the line segment must be zero.

For rays and lines, you have a sightly harder problem because of the infinite extent, but it only takes a slight modification of the same argument to show they have zero area as well (a sequence of rectangles whose areas decrease geometrically is one approach).

Title: Re: Random Line Segment In Square
Post by Earendil on Oct 24^th, 2004, 9:34am

Or, perhaps, there is an enumerable infinite number of squares necessary to contain a line. Since a line in a square has measure 0, the line must also have it.

Title: Re: Random Line Segment In Square
Post by KjSlag on Nov 30^th, 2006, 10:00pm

I solved the following values for N using Mathematica and an equation (a picture of it is attached) composed of 6 summations... Although my equation technically does answer the question, it's very ugly and a more simple equation would be much more interesting :-/

N=1: 0
N=2: 0
N=3: 16/189
N=4: 33/448
N=5: 912/14375
N=6: 31/612
N=7: 4944/112847
N=8: 579/15872
N=9: 1808/57591
N=10: 834/30625
N=11: 41952/1742279
N=12: 287/13632
N=13: 90432/4769687
N=14: 15759/931588
N=15: 57376/3763125

in decimal:
{0, 0, 0.0846561, 0.0736607, 0.0634435, 0.0506536, 0.0438115, 0.0364793, 0.0313938, 0.0272327, 0.0240788, 0.0210534, 0.0189597, 0.0169163, 0.0152469}

Title: Re: Random Line Segment In Square
Post by balakrishnan on Jan 5^th, 2007, 6:44pm

Sorry
This was incorrect!