Author |
Topic: Random Line Segment In Square (Read 8079 times) |
|
william wu
wu::riddles Administrator
Gender: 
Posts: 1291
|
 |
Random Line Segment In Square
« on: Mar 31st, 2003, 9:36am » |
 Quote  Modify
|
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?
|
| « Last Edit: Mar 31st, 2003, 1:42pm by william wu » |
 IP Logged |
[ wu ] : http://wuriddles.com / http://forums.wuriddles.com
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Random Line Segment In Square
« Reply #1 on: Mar 31st, 2003, 11:13am » |
Quote Modify
|
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..
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
william wu
wu::riddles Administrator
Gender:
Posts: 1291
|
|
Re: Random Line Segment In Square
« Reply #2 on: Mar 31st, 2003, 1:39pm » |
Quote Modify
|
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 = 2aleph-0. The cardinality of the set of all points in an arbitrary continuum square is also #R2 = 2aleph-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?
|
|
IP Logged |
[ wu ] : http://wuriddles.com / http://forums.wuriddles.com
|
|
|
Chronos
Full Member
Gender:
Posts: 288
|
|
Re: Random Line Segment In Square
« Reply #3 on: Mar 31st, 2003, 2:41pm » |
Quote Modify
|
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.
|
|
IP Logged |
|
|
|
Icarus
wu::riddles Moderator
Uberpuzzler
Boldly going where even angels fear to tread.
Gender:
Posts: 4863
|
|
Re: Random Line Segment In Square
« Reply #5 on: Apr 2nd, 2003, 8:15pm » |
Quote Modify
|
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.x1x2..., y = 0.y1y2..., and neither is expressed with repeating 9s (except x=1 or y=1), then (x, y) maps to the number 0.x1y1x2y2...
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 to show that there must be a one-to-one correspondence (both injective and surjective) between every element of I x I and I.
|
|
IP Logged |
"Pi goes on and on and on ...
And e is just as cursed.
I wonder: Which is larger
When their digits are reversed? " - Anonymous
|
|
|
James Fingas
Uberpuzzler
Gender:
Posts: 949
|
|
Re: Random Line Segment In Square
« Reply #6 on: Aug 5th, 2003, 1:45pm » |
Quote Modify
|
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)/n2.
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/n2. 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)/(n2-1)
p(h) = 2(n-h)/(n2-1)
So the overall probability is just this double sum:
P = sumg=0..n-1sumh=0..n-1p(g)p(h)(gcf(g,h)+1)/n2
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).
|
|
IP Logged |
Doc, I'm addicted to advice! What should I do?
|
|
|
James Fingas
Uberpuzzler
Gender:
Posts: 949
|
|
Re: Random Line Segment In Square
« Reply #7 on: Aug 6th, 2003, 10:01am » |
Quote Modify
|
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 n2 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 n2. So my probability formula should read:
p(g=0) = 1/n
p(g|g <> 0) = 2*(n-g)/n2
p(h=0) = 1/n
p(h|h <> 0) = 2*(n-h)/n2
P is still the same sum. Correcting my calculations and redoing my simulation, P(n)*n2 grows monotonically, but not entirely smoothly. Its overall growth rate appears to be logarithmic.
|
|
IP Logged |
Doc, I'm addicted to advice! What should I do?
|
|
|
SWF
Uberpuzzler
Posts: 879
|
|
Re: Random Line Segment In Square
« Reply #8 on: Aug 21st, 2003, 6:14pm » |
Quote Modify
|
By enumerating all N4 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
N6p(N)=(5N4-2N2)/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:
N6p(N)=(9N4-10N3+6N2-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...):
N6p(N)=(5N4-2N2)/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:
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.
|
| « Last Edit: Oct 21st, 2003, 9:56pm by SWF » |
IP Logged |
|
|
|
SWF
Uberpuzzler
Posts: 879
|
|
Re: Random Line Segment In Square
« Reply #9 on: Oct 21st, 2003, 10:02pm » |
Quote Modify
|
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.
|
|
IP Logged |
|
|
|
william wu
wu::riddles Administrator
Gender:
Posts: 1291
|
|
Re: Random Line Segment In Square
« Reply #10 on: Oct 22nd, 2003, 1:20am » |
Quote Modify
|
on Oct 21st, 2003, 10:02pm, 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.
|
| « Last Edit: Oct 22nd, 2003, 1:20am by william wu » |
IP Logged |
[ wu ] : http://wuriddles.com / http://forums.wuriddles.com
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Random Line Segment In Square
« Reply #11 on: Oct 22nd, 2003, 1:26am » |
Quote Modify
|
on Oct 22nd, 2003, 1:20am, 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 
Icarus' thread allready keeps track of most of them, so I think only the 'really important' threads should be at the top..
|
| « Last Edit: Oct 22nd, 2003, 1:26am by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
James Fingas
Uberpuzzler
Gender:
Posts: 949
|
|
Re: Random Line Segment In Square
« Reply #12 on: Oct 22nd, 2003, 6:56am » |
Quote Modify
|
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 is better off forgotten.
|
|
IP Logged |
Doc, I'm addicted to advice! What should I do?
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Random Line Segment In Square
« Reply #13 on: Oct 22nd, 2003, 8:04am » |
Quote Modify
|
on Oct 22nd, 2003, 6:56am, James Fingas wrote: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..)
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Earendil
Newbie
 
Gender:
Posts: 46
|
|
Re: Random Line Segment In Square
« Reply #14 on: Oct 16th, 2004, 12:54pm » |
Quote Modify
|
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] ?
|
|
IP Logged |
|
|
|
Icarus
wu::riddles Moderator
Uberpuzzler
Boldly going where even angels fear to tread.
Gender:
Posts: 4863
|
|
Re: Random Line Segment In Square
« Reply #15 on: Oct 17th, 2004, 11:30am » |
Quote Modify
|
on Oct 16th, 2004, 12:54pm, 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]2 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) ?
|
|
IP Logged |
"Pi goes on and on and on ...
And e is just as cursed.
I wonder: Which is larger
When their digits are reversed? " - Anonymous
|
|
|
Earendil
Newbie
Gender:
Posts: 46
|
|
Re: Random Line Segment In Square
« Reply #16 on: Oct 17th, 2004, 11:52am » |
Quote Modify
|
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).
|
|
IP Logged |
|
|
|
Icarus
wu::riddles Moderator
Uberpuzzler
Boldly going where even angels fear to tread.
Gender:
Posts: 4863
|
|
Re: Random Line Segment In Square
« Reply #17 on: Oct 18th, 2004, 3:19pm » |
Quote Modify
|
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).
|
|
IP Logged |
"Pi goes on and on and on ...
And e is just as cursed.
I wonder: Which is larger
When their digits are reversed? " - Anonymous
|
|
|
Earendil
Newbie
Gender:
Posts: 46
|
|
Re: Random Line Segment In Square
« Reply #18 on: Oct 24th, 2004, 9:34am » |
Quote Modify
|
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.
|
|
IP Logged |
|
|
|
KjSlag
Newbie
Posts: 4
|
|
Re: Random Line Segment In Square  ugly.GIF
« Reply #19 on: Nov 30th, 2006, 10:00pm » |
Quote Modify
|
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}
|
|
IP Logged |
 |
|
|
balakrishnan
Junior Member
Gender:
Posts: 92
|
|
Re: Random Line Segment In Square
« Reply #20 on: Jan 5th, 2007, 6:44pm » |
Quote Modify
|
Sorry
This was incorrect!
|
| « Last Edit: Jan 9th, 2007, 7:01pm by balakrishnan » |
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print