  
18.11.2011, 12:02
 Newbie 1st class   Join Date: Sep 2011 Location: Zurich
Posts: 12
Groaned at 0 Times in 0 Posts
Thanked 6 Times in 4 Posts
  Re: A question for the math geeks  Quote:      thanks. but i guess the probability will depend on the ratio of l and r. if l=r, then the all the needles will touch as they will have to cross the centre point.      Yes of course, it should be 'easy' to get the curve  range of l versus probability of crossing the line.
In the matter of fact this current measured probability in fact is 0 < l <= r/2.

18.11.2011, 12:12
 Member   Join Date: May 2011 Location: Lausanne
Posts: 145
Groaned at 2 Times in 2 Posts
Thanked 60 Times in 36 Posts
  Re: A question for the math geeks  Quote:      thanks. but i guess the probability will depend on the ratio of l and r. if l=r, then the all the needles will touch as they will have to cross the centre point.      Perhaps you meant "if l = 2r".
Yes, the desired probability is a function of the ration q = l/r, say P(q).
Here q can be anything between 0 and 2. It is clear that
\lim_{q \to 0} P(q) = 0 (a very short needle will almost certainly not intersect the forbidden line segment connecting south pole and north pole).
And I think that what you are saying is this:
\lim_{q \to 2} P(q) = 1 (a very long needle, i.e. a needle of length l nearly equal to the diameter of the circle 2r, will intersect the "southpolenorthpolechord" with very high probability).
These 2 properties are intuitively clear and they are fairly easy to prove.

18.11.2011, 12:29
  Forum Legend   Join Date: Oct 2009 Location: Basel
Posts: 14,750
Groaned at 284 Times in 189 Posts
Thanked 18,639 Times in 7,827 Posts
  Re: A question for the math geeks  Quote:      Perhaps you meant "if l = 2r".
Yes, the desired probability is a function of the ration q = l/r, say P(q).
Here q can be anything between 0 and 2. It is clear that
\lim_{q \to 0} P(q) = 0 (a very short needle will almost certainly not intersect the forbidden line segment connecting south pole and north pole).
And I think that what you are saying is this:
\lim_{q \to 2} P(q) = 1 (a very long needle, i.e. a needle of length l nearly equal to the diameter of the circle 2r, will intersect the "southpolenorthpolechord" with very high probability).
These 2 properties are intuitively clear and they are fairly easy to prove.      thanks. yes, i meant 2r. i had intended the original question to be for l <=2r but forgot that r was radius and not diameter.
agree on both limits, they are as expected.

18.11.2011, 13:11
 Member   Join Date: May 2011 Location: Lausanne
Posts: 145
Groaned at 2 Times in 2 Posts
Thanked 60 Times in 36 Posts
  Re: A question for the math geeks
Phil MCR,
Here is a clever idea (but I am not sure it is of any help).
From now on, let's assume that r = 1 (disk of radius 1) and that 0 < l < 2 (a needle of length less than 2, so that it is possible to fit it inside the disk). Let's write P(l) for the probability that the needle will intersect the naughty chord, i.e. the line segment connecting south pole and north pole.
Let's exploit the symmetry a bit.
The naughty chord could be replaced by any other chord going through the center of the disk and the answer would be the same. Alright, here is my idea: we place the needle at random, as before, and THEN we choose the naughty chord at random, with an orientation having uniform distribution (e.g., we choose a \theta with uniform distribution on the interval (\pi/2, \pi/2] and our naughty chord is the line segment joining the point (\cos(\theta), \sin(\theta)) and the point (\cos(\theta), \sin(\theta))). Now we can say something intelligent about the probability P(l):
P(l) = E[S]/\pi
where S is the "length" of the shadow of the needle on the circle when the only light around is a light located at the center of the disk.
Isn't that cute?

18.11.2011, 13:23
  Forum Legend   Join Date: Oct 2009 Location: Basel
Posts: 14,750
Groaned at 284 Times in 189 Posts
Thanked 18,639 Times in 7,827 Posts
  Re: A question for the math geeks  Quote:      Phil MCR,
Here is a clever idea (but I am not sure it is of any help).
From now on, let's assume that r = 1 (disk of radius 1) and that 0 < l < 2 (a needle of length less than 2, so that it is possible to fit it inside the disk). Let's write P(l) for the probability that the needle will intersect the naughty chord, i.e. the line segment connecting south pole and north pole.
Let's exploit the symmetry a bit.
The naughty chord could be replaced by any other chord going through the center of the disk and the answer would be the same. Alright, here is my idea: we place the needle at random, as before, and THEN we choose the naughty chord at random, with an orientation having uniform distribution (e.g., we choose a \theta with uniform distribution on the interval (\pi/2, \pi/2] and our naughty chord is the line segment joining the point (\cos(\theta), \sin(\theta)) and the point (\cos(\theta), \sin(\theta))). Now we can say something intelligent about the probability P(l):
P(l) = E[S]/\pi
where S is the "length" of the shadow of the needle on the circle when the only light around is a light located at the center of the disk.
Isn't that cute?      hmm. that is pretty elegant. maybe a way to rephrase would be to calculate the expected angle \phi, subtended by the two end points of the needle to the centre of the disk. then presumably the probability of intersection would be related to that expected angle. e.g. E[\phi]/\pi
but i'm not sure it really simplifies the problem since i think it will still be necessary to examine the separate cases of the annulus area and the central strip.
but going with this:
so needle is thrown, we orient the circle so that the closest point of the needle and centre of the circle lies on the horizontal axis. the needle is at angle \theta to the yaxis. the closest point is distance 'd' from the centre. then i think the angle \phi subtended by the end points of the needle to the centre should be:
Tan (\phi) = { (d + l sin(\theta) ) / (l cos(\theta) ) }
__________________
By replying to this post, you hereby grant Phil_MCR a royaltyfree license to use, in any way, anything posted by you on the internet. If you do not accept, stop using EF and delete your account.
Last edited by Phil_MCR; 18.11.2011 at 13:42.

18.11.2011, 15:06
 Member   Join Date: May 2011 Location: Lausanne
Posts: 145
Groaned at 2 Times in 2 Posts
Thanked 60 Times in 36 Posts
  Re: A question for the math geeks
Yes.
Your $\phi$ and my $S$ are the same thing (since I am assuming $r = 1$). I just thought that my description was more poetic.
I agree that, interesting as it may be, this way of looking at the problem does not make the problem trivial.
I agree with your suggestion regarding $\phi$ but I would condition on the distance $D$ between the center of the needle and the center of the disk instead of your distance $d$ between the endpointoftheneedleclosesttothecenterofthedisk and the center of the disk. Reason: with your suggestion, the distribution of the angle $\theta$ is complicated whereas with my suggestion, the orientation of the needle is still uniform (except when the center of the needle is within $l/2$ of the boundary of the disk).
This is all very interesting but, eventhough I am paid to do this kind of work, I have to return to the papers that I am currently working on (which, incidently, involve random points in ${\mathbb R}^n$).

18.11.2011, 15:09
  Forum Legend   Join Date: Oct 2009 Location: Basel
Posts: 14,750
Groaned at 284 Times in 189 Posts
Thanked 18,639 Times in 7,827 Posts
  Re: A question for the math geeks  Quote:      Yes.
Your $\phi$ and my $S$ are the same thing (since I am assuming $r = 1$). I just thought that my description was more poetic.
I agree that, interesting as it may be, this way of looking at the problem does not make the problem trivial.
I agree with your suggestion regarding $\phi$ but I would condition on the distance $D$ between the center of the needle and the center of the disk instead of your distance $d$ between the endpointoftheneedleclosesttothecenterofthedisk and the center of the disk. Reason: with your suggestion, the distribution of the angle $\theta$ is complicated whereas with my suggestion, the orientation of the needle is still uniform (except when the center of the needle is within $l/2$ of the boundary of the disk).
This is all very interesting but, eventhough I am paid to do this kind of work, I have to return to the papers that I am currently working on (which, incidently, involve random points in ${\mathbb R}^n$).      thanks. maybe i'm missing something, but i thought my distribution should also be uniform (ok, still need to take boundary effects, but that is true of both cases).
don't you have students you can give this to for homework? 
18.11.2011, 15:35
 Member   Join Date: May 2011 Location: Lausanne
Posts: 145
Groaned at 2 Times in 2 Posts
Thanked 60 Times in 36 Posts
  Re: A question for the math geeks
One last comment and then I swear I stay away from this forum until Sunday!
Let E be the endpoint of the needle closest to the center of the disk. Let F be the other endpoint of the needle. Let d be, as in your previous post, the distance between E and the center of the disk. Let's assume that E is on the positive real axis (i.e. on the segment connecting the point (0,0) and the point (1,0)). Thus E = (d,0). Let \theta \in (\pi, \pi] be, as in your post, the angle between the needle and the vertical line through E. Thus \theta = 0 if F is straight above E, i.e. F = (d,l)), \theta = \pi/2 if F is straight to the right E, i.e. if F = (d+l,0), \theta = \pi/2 if F is straight to the left of E, i.e., F = (dl,0), and \theta = \pi (or \pi) if F is straight below E, i.e. F = (d,l). I say that even if we condition on E being away from (1,0), so that there is no boundary effect, \theta can't be uniformly distributed on the interval (\pi/2, \pi/2] simply because this would violate the condition that E is the endpoint of the needle closest to the center of the disk. For example, suppose l = 1/5 and E = (2/5, 0). If \theta were close to \pi/2, then F would be close to the point (1/5,0). But this would violate the fact that E is the endpoint of the needle closest to the center of the disk.

18.11.2011, 15:43
  Forum Legend   Join Date: Oct 2009 Location: Basel
Posts: 14,750
Groaned at 284 Times in 189 Posts
Thanked 18,639 Times in 7,827 Posts
  Re: A question for the math geeks  Quote:      One last comment and then I swear I stay away from this forum until Sunday!
Let E be the endpoint of the needle closest to the center of the disk. Let F be the other endpoint of the needle. Let d be, as in your previous post, the distance between E and the center of the disk. Let's assume that E is on the positive real axis (i.e. on the segment connecting the point (0,0) and the point (1,0)). Thus E = (d,0). Let \theta \in (\pi, \pi] be, as in your post, the angle between the needle and the vertical line through E. Thus \theta = 0 if F is straight above E, i.e. F = (d,l)), \theta = \pi/2 if F is straight to the right E, i.e. if F = (d+l,0), \theta = \pi/2 if F is straight to the left of E, i.e., F = (dl,0), and \theta = \pi (or \pi) if F is straight below E, i.e. F = (d,l). I say that even if we condition on E being away from (1,0), so that there is no boundary effect, \theta can't be uniformly distributed on the interval (\pi/2, \pi/2] simply because this would violate the condition that E is the endpoint of the needle closest to the center of the disk. For example, suppose l = 1/5 and E = (2/5, 0). If \theta were close to \pi/2, then F would be close to the point (1/5,0). But this would violate the fact that E is the endpoint of the needle closest to the center of the disk.      ok. i see your point, but the 'closest endpoint' isn't really a condition as such and is merely a convenience to help visualise. if we say instead 'an' endpoint, the trigonometry should still work out.

18.11.2011, 15:55
  Forum Legend   Join Date: May 2008 Location: Kt. Zürich
Posts: 11,616
Groaned at 578 Times in 487 Posts
Thanked 20,883 Times in 10,968 Posts
  Re: A question for the math geeks  Quote:     Is the point at which I'm supposed to ask "Are the lines and needle infinitesimally thin?"
Are you Charles Darke, or is Charles Darke you?      If "needle is infinitesimally thin"  how can you see where it landed?

19.11.2011, 02:24
  Forum Legend   Join Date: Oct 2009 Location: Basel
Posts: 14,750
Groaned at 284 Times in 189 Posts
Thanked 18,639 Times in 7,827 Posts
  Re: A question for the math geeks  Quote:      If "needle is infinitesimally thin"  how can you see where it landed?      by having infinitely good eyesight.

20.11.2011, 13:14
 Member   Join Date: May 2011 Location: Lausanne
Posts: 145
Groaned at 2 Times in 2 Posts
Thanked 60 Times in 36 Posts
  Re: A question for the math geeks  Quote:      Take the interval of real numbers [0,100].
From this interval, n different numbers are picked randomly, where n>1.
What is the expected difference between the largest and smallest number picked for a given value of n? (assume uniform distribution, where required)
Happy to hear an answer for the case n=2, as well as the more general case for arbitrary integer values of n>1.      Phil MCR,
Some people have given the correct answer to your original question: (n1)/(n+1). There are different ways to get this answer. In particular, you can compute the density of R(n), the "range" of your sample of size n, i.e., R(n) = M(n)  m(n), where M(n) is the maximum of your n observations and m(n) is the minimum. Once you have that density, you compute the expectation. You can also compute the standard deviation or anything else you want about R(n). It is easy to show that the density of R(n) is simply n(n1)(1r)r^{n2}. But if all you need is E[R(n)], there is no need to find the density of R(n). You can use E[R(n)] = E[M(n)]  E[m(n)]. The densities of M(n) and m(n) are easier to obtain than the density of R(n). Finally, as others have observed, there is a nice intuitive interpretation: the n points divide the interval into n+1 pieces. The lengths of these n+1 pieces all have the same distribution, thus they all have the same expectation 1/(n+1).
You can also show that n(1R(n)) converges in distribution to the gamma distribution with density f(x) = x e^{x}. Cool!

20.11.2011, 19:09
  Forum Veteran   Join Date: Feb 2008 Location: France, near Geneva
Posts: 865
Groaned at 8 Times in 7 Posts
Thanked 2,777 Times in 728 Posts
  Re: A question for the math geeks
I'm back to see if anyone solved the needle problem  nothing...
So I'm busy with R, learning as I go.
What is clear to me:
1) l/D is the only parameter (we all agree)
2) Using the angle is not very helpful, IMHO.
My circle has centre (0,0) and goes from 1 to 1 on both axes. I'm generating random points in the circle and creating lines by joining random pairs. So they have random lengths, less than D. It is clear that half of these lines will pass through the vertical diameter. (Say the first is on the left ... then it is 50/50 that the second one is on the right and the line crosses the diameter). It will be easy to see if a pair of points defines a crossing line: the xcoordinates must have different sign, so to cross, X1 x X2 has to be negative.
After doing stats on a large enough number of lines, I should get the probabilities for all l/D in one shot ... I think . Elegant, it ain't.
All suggestions more than welcome.

20.11.2011, 21:03
 Member   Join Date: May 2011 Location: Lausanne
Posts: 145
Groaned at 2 Times in 2 Posts
Thanked 60 Times in 36 Posts
  Re: A question for the math geeks
FrankZappa,
Indeed, R is the way to go.
But I don't see how your approach is going to help with the original problem.
Let's take the unit disk centered at (0,0).
Fix L < 2, the length of the needle (lowercase l looks too much like a "one" on my computer screen). Here is the program I would write in order to estimate the desired probability:
Set the "counters" N and M both equal to zero.
Repeat the following 1,000,000 times:
 Choose a point, say (X,Y), at random with uniform distribution on the unit disk. (That point will be the center of the needle).
 Choose an angle theta with uniform distribution between pi/2 and +pi/2. (That will be the orientation of the needle with respect to the horizontal).
 Draw the needle. In other words, compute the coordinates of the endpoints of the needle: A = (X+L cos(theta), Y + L sin(theta)) and B = (X  L cos(theta), Y  L sin(theta)).
 Set N = N + 1 if the points A and B are both inside the unit disk.
 Set M = M + 1 if the points A and B are both inside the unit disk AND if they are on opposite sides of the central vertical line.
The estimate of the desired probability is M/N.
This estimate will be quite good if N is sufficiently large.
Note that if L is small not too big (i.e. not too close to 2), then N will be large but if L is close to 2, then N might be somewhat small and the estimate might be not so good.

24.11.2011, 01:38
  Forum Legend   Join Date: Oct 2009 Location: Basel
Posts: 14,750
Groaned at 284 Times in 189 Posts
Thanked 18,639 Times in 7,827 Posts
  Re: A question for the math geeks
Anyone familiar with programming ATI GPUs? I wonder if it could be used to simulate random needle throws? I figure it could be a good way to learn GPU programming even if the speed isn't required.

24.11.2011, 15:23
  Forum Legend   Join Date: Mar 2008 Location: Zurich
Posts: 12,361
Groaned at 340 Times in 276 Posts
Thanked 26,264 Times in 11,001 Posts
  Re: A question for the math geeks  Quote:      Anyone familiar with programming ATI GPUs? I wonder if it could be used to simulate random needle throws? I figure it could be a good way to learn GPU programming even if the speed isn't required.      Solving this type of problem by any brute force simulation is cheap. The art is in analytical solutions.

24.11.2011, 15:58
  Forum Legend   Join Date: Feb 2010 Location: CH
Posts: 3,200
Groaned at 86 Times in 70 Posts
Thanked 5,788 Times in 2,254 Posts
  Re: A question for the math geeks  Quote:      Solving this type of problem by any brute force simulation is cheap. The art is in analytical solutions.      yup agree. The simulation should only be used to confirm/invalidate the analytical solution.

24.11.2011, 16:09
  Forum Legend   Join Date: Oct 2009 Location: Basel
Posts: 14,750
Groaned at 284 Times in 189 Posts
Thanked 18,639 Times in 7,827 Posts
  Re: A question for the math geeks  Quote:      Solving this type of problem by any brute force simulation is cheap. The art is in analytical solutions.      you can't solve it by brute force simulation. 
24.11.2011, 19:50
  Forum Legend   Join Date: Feb 2010 Location: CH
Posts: 3,200
Groaned at 86 Times in 70 Posts
Thanked 5,788 Times in 2,254 Posts
  Re: A question for the math geeks
Didn't have the time nor the courage yet to tackle the needle/circle problem.
Maybe starting with a square instead of a circle is simpler in a first step, then try to extend it to circle. The square case should be somehow related to the Buffon needle problem. 
24.11.2011, 21:21
  Forum Veteran   Join Date: Feb 2008 Location: France, near Geneva
Posts: 865
Groaned at 8 Times in 7 Posts
Thanked 2,777 Times in 728 Posts
  Re: A question for the math geeks  Quote:      yup agree. The simulation should only be used to confirm/invalidate the analytical solution.      Lots of real world problems don't have analytical solutions.

Currently Active Users Viewing This Thread: 1 (0 members and 1 guests)   Thread Tools   Display Modes  Linear Mode 
Posting Rules
 You may not post new threads You may not post replies You may not post attachments You may not edit your posts HTML code is Off    All times are GMT +2. The time now is 09:14.  