

Title: Random Line Segment In Square Post by william wu on Mar 31^{st}, 2003, 9:36am 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^{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? 

Title: Re: Random Line Segment In Square Post by Chronos on Mar 31^{st}, 2003, 2:41pm Quote:
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. 

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:
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 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 (http://www.ocf.berkeley.edu/~wwu/cgibin/yabb/YaBB.cgi?board=wanted;action=display;num=1034370401) to show that there must be a onetoone 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^{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). 

Title: Re: Random Line Segment In Square Post by James Fingas on Aug 6^{th}, 2003, 10:01am 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. 

Title: Re: Random Line Segment In Square Post by SWF on Aug 21^{st}, 2003, 6:14pm 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: 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:
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. 

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:
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:
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/cgibin/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:
(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:
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) ? 

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! 

Powered by YaBB 1 Gold  SP 1.4! Forum software copyright © 20002004 Yet another Bulletin Board 