English Forum Switzerland A question for the math geeks
#61
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: Phil_MCR 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.
#62
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: Phil_MCR 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 "south-pole-north-pole-chord" with very high probability).
These 2 properties are intuitively clear and they are fairly easy to prove.
#63
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: Quebecman 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 "south-pole-north-pole-chord" 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.
#64
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?
#65
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: Quebecman 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 re-phrase 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 y-axis. 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 royalty-free 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.
#66
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 end-point-of-the-needle-closest-to-the-center-of-the-disk 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$).
#67
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: Quebecman 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 end-point-of-the-needle-closest-to-the-center-of-the-disk 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?
#68
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 end-point of the needle closest to the center of the disk. Let F be the other end-point 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 = (d-l,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 end-point 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 end-point of the needle closest to the center of the disk.
#69
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: Quebecman One last comment and then I swear I stay away from this forum until Sunday! Let E be the end-point of the needle closest to the center of the disk. Let F be the other end-point 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 = (d-l,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 end-point 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 end-point 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.
#70
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?
#71
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: marton If "needle is infinitesimally thin" - how can you see where it landed?
by having infinitely good eyesight.
#72
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: Phil_MCR 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: (n-1)/(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(n-1)(1-r)r^{n-2}. 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(1-R(n)) converges in distribution to the gamma distribution with density f(x) = x e^{-x}. Cool!
#73
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 x-coordinates 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.
#74
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 end-points 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.
#75
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.
#76
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: Phil_MCR 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.
#77
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: amogles 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.
#78
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: amogles 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.
#79
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.
#80
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: MrVertigo 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 BB code is On Smilies are On [IMG] code is On HTML code is OffTrackbacks are Off Pingbacks are Off Refbacks are Off Forum Rules

 Similar Threads Thread Thread Starter Forum Replies Last Post sam ali TV/internet/telephone 6 30.09.2011 23:16 Odyssey General off-topic 8 30.11.2010 11:31 Polorise Jokes/funnies 8 14.12.2009 12:17 flavio Food and drink 25 07.12.2009 03:43 dende General off-topic 0 15.04.2008 20:12

All times are GMT +2. The time now is 09:14.

 Imprint - Contact Us - English Forum Switzerland - Archive - Top