Author 
Topic: Random Line Segment In Square (Read 7499 times) 

william wu
wu::riddles Administrator
Gender:
Posts: 1291


Random Line Segment In Square
« on: Mar 31^{st}, 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 31^{st}, 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: 13651


Re: Random Line Segment In Square
« Reply #1 on: Mar 31^{st}, 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 31^{st}, 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 = 2^{aleph0}. The cardinality of the set of all points in an arbitrary continuum square is also #R^{2} = 2^{aleph0}. (I got these facts from http://www.ii.com/math/ch/#cardinals .) However, what would be an example onetoone 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 31^{st}, 2003, 2:41pm » 
Quote Modify

Quote:However, what would be an example onetoone 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 lowerdimensional subspace of a higherdimensional 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 2^{nd}, 2003, 8:15pm » 
Quote Modify

Because of the 0.999... = 1.000... phenomenon, interlacing the decimals on the coordinates is not quite onetoone. 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_{1}x_{2}..., y = 0.y_{1}y_{2}..., and neither is expressed with repeating 9s (except x=1 or y=1), then (x, y) maps to the number 0.x_{1}y_{1}x_{2}y_{2}... This defines an injection of I x I into I, (injection means that it is onetoone: 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 SchroederBernstein Theorem to show that there must be a onetoone 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 5^{th}, 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)/n^{2}. 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(ac),abs(bd)). So our analysis depends only on the relative sizes of ac and bd. Note that we will have to calculate the probabilities that we will get various distances. From now on, I will define: g = abs(ac) h = abs(bd) 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 randomlychosen point lies on the line would thus be 2/n^{2}. 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 g1 and one less way to get a distance g+1. There is one way to get a distance g=n1. The sum of all these probabilities is [(n)(n1)]/2 p(g) = 2(ng)/(n^{2}1) p(h) = 2(nh)/(n^{2}1) So the overall probability is just this double sum: P = sum_{g=0..n1}sum_{h=0..n1}p(g)p(h)(gcf(g,h)+1)/n^{2} 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 6^{th}, 2003, 10:01am » 
Quote Modify

My apologiesI 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^{2} ordered ways of choosing two grid columns, there are exactly n that give g=0. There are 2n2 that give g=1, 2n4 that give g=2, ... and 2 ways that give g=n1. Adding these up, we get n^{2}. So my probability formula should read: p(g=0) = 1/n p(gg <> 0) = 2*(ng)/n^{2} p(h=0) = 1/n p(hh <> 0) = 2*(nh)/n^{2} P is still the same sum. Correcting my calculations and redoing my simulation, P(n)*n^{2} 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 21^{st}, 2003, 6:14pm » 
Quote Modify

By enumerating all N^{4} 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^{6}p(N)=(5N^{4}2N^{2})/3+4[sum][sum](Ng)*(Nh)*gcf(g,h) where the summations are for g and h=1 to N1, 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,a1)=1, and gcf(1,a)=1. For example using gcf(a,a)=a and assuming gcf() is 1 everywhere else gives the approximation: N^{6}p(N)=(9N^{4}10N^{3}+6N^{2}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 onequarter 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]=(11/2[sup2])*(11/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 (Ng)*(Nh) in the summation above that have both g and h multiples of Q. If F=floor((N1)/Q) this average is given by ([sum][sum](Ni*Q)*(Nj*Q))/F[sup2] where the sums are for i and j=1 to F. Approximating F by ((N1)/Q0.5) allows the summations to be evaluated as: A(Q)=(N[sup2]+2*NN*Q+1+Q[sup2]/4Q)/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*(N1)[sup2]*[sum]A(Q)*Q/Q[sup2]*6/[pi][sup2] summing over Q=1 to N1. This sum can be evaluated using 1+1/2+1/3+1/4+...+1/(N1) [approx] ln(N1)+[gamma] ([gamma]=Euler's constant [approx] 0.5772156...): N^{6}p(N)=(5N^{4}2N^{2})/3+6*(N1)[sup2]/[pi][sup2]*((N+1)[sup2]*(ln((N1)+[gamma])7*N[sup2]/8N/81) 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 21^{st}, 2003, 9:56pm by SWF » 
IP Logged 



SWF
Uberpuzzler
Posts: 879


Re: Random Line Segment In Square
« Reply #9 on: Oct 21^{st}, 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(N1)+[gamma] term is only there to convert the harmonic series into a standard calculator function. If ln(N1)+[gamma] is left as H(N1) (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 22^{nd}, 2003, 1:20am » 
Quote Modify

on Oct 21^{st}, 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 22^{nd}, 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: 13651


Re: Random Line Segment In Square
« Reply #11 on: Oct 22^{nd}, 2003, 1:26am » 
Quote Modify

on Oct 22^{nd}, 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 22^{nd}, 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 22^{nd}, 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: 13651


Re: Random Line Segment In Square
« Reply #13 on: Oct 22^{nd}, 2003, 8:04am » 
Quote Modify

on Oct 22^{nd}, 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 16^{th}, 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 17^{th}, 2004, 11:30am » 
Quote Modify

on Oct 16^{th}, 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 17^{th}, 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 18^{th}, 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 24^{th}, 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 30^{th}, 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 5^{th}, 2007, 6:44pm » 
Quote Modify

Sorry This was incorrect!

« Last Edit: Jan 9^{th}, 2007, 7:01pm by balakrishnan » 
IP Logged 



