Go Back   English Forum Switzerland > Off-Topic > Off-Topic > General off-topic  
Reply
 
Thread Tools Display Modes
  #61  
Old 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
jurem has no particular reputation at present
Re: A question for the math geeks

Quote:
View Post
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.
Reply With Quote
  #62  
Old 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
Quebecman is considered knowledgeableQuebecman is considered knowledgeableQuebecman is considered knowledgeable
Re: A question for the math geeks

Quote:
View Post
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.
Reply With Quote
  #63  
Old 18.11.2011, 12:29
Phil_MCR's Avatar
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
Phil_MCR has a reputation beyond reputePhil_MCR has a reputation beyond reputePhil_MCR has a reputation beyond reputePhil_MCR has a reputation beyond reputePhil_MCR has a reputation beyond reputePhil_MCR has a reputation beyond repute
Re: A question for the math geeks

Quote:
View Post
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.
Reply With Quote
  #64  
Old 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
Quebecman is considered knowledgeableQuebecman is considered knowledgeableQuebecman is considered knowledgeable
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?
Reply With Quote
  #65  
Old 18.11.2011, 13:23
Phil_MCR's Avatar
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
Phil_MCR has a reputation beyond reputePhil_MCR has a reputation beyond reputePhil_MCR has a reputation beyond reputePhil_MCR has a reputation beyond reputePhil_MCR has a reputation beyond reputePhil_MCR has a reputation beyond repute
Re: A question for the math geeks

Quote:
View Post
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.
Reply With Quote
  #66  
Old 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
Quebecman is considered knowledgeableQuebecman is considered knowledgeableQuebecman is considered knowledgeable
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$).
Reply With Quote
  #67  
Old 18.11.2011, 15:09
Phil_MCR's Avatar
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
Phil_MCR has a reputation beyond reputePhil_MCR has a reputation beyond reputePhil_MCR has a reputation beyond reputePhil_MCR has a reputation beyond reputePhil_MCR has a reputation beyond reputePhil_MCR has a reputation beyond repute
Re: A question for the math geeks

Quote:
View Post
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?
Reply With Quote
  #68  
Old 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
Quebecman is considered knowledgeableQuebecman is considered knowledgeableQuebecman is considered knowledgeable
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.
Reply With Quote
  #69  
Old 18.11.2011, 15:43
Phil_MCR's Avatar
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
Phil_MCR has a reputation beyond reputePhil_MCR has a reputation beyond reputePhil_MCR has a reputation beyond reputePhil_MCR has a reputation beyond reputePhil_MCR has a reputation beyond reputePhil_MCR has a reputation beyond repute
Re: A question for the math geeks

Quote:
View Post
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.
Reply With Quote
  #70  
Old 18.11.2011, 15:55
marton's Avatar
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
marton has a reputation beyond reputemarton has a reputation beyond reputemarton has a reputation beyond reputemarton has a reputation beyond reputemarton has a reputation beyond reputemarton has a reputation beyond repute
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?
Reply With Quote
  #71  
Old 19.11.2011, 02:24
Phil_MCR's Avatar
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
Phil_MCR has a reputation beyond reputePhil_MCR has a reputation beyond reputePhil_MCR has a reputation beyond reputePhil_MCR has a reputation beyond reputePhil_MCR has a reputation beyond reputePhil_MCR has a reputation beyond repute
Re: A question for the math geeks

Quote:
View Post
If "needle is infinitesimally thin" - how can you see where it landed?
by having infinitely good eyesight.
Reply With Quote
  #72  
Old 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
Quebecman is considered knowledgeableQuebecman is considered knowledgeableQuebecman is considered knowledgeable
Re: A question for the math geeks

Quote:
View Post
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!
Reply With Quote
  #73  
Old 20.11.2011, 19:09
FrankZappa's Avatar
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
FrankZappa has a reputation beyond reputeFrankZappa has a reputation beyond reputeFrankZappa has a reputation beyond reputeFrankZappa has a reputation beyond reputeFrankZappa has a reputation beyond reputeFrankZappa has a reputation beyond repute
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.
Reply With Quote
  #74  
Old 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
Quebecman is considered knowledgeableQuebecman is considered knowledgeableQuebecman is considered knowledgeable
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.
Reply With Quote
  #75  
Old 24.11.2011, 01:38
Phil_MCR's Avatar
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
Phil_MCR has a reputation beyond reputePhil_MCR has a reputation beyond reputePhil_MCR has a reputation beyond reputePhil_MCR has a reputation beyond reputePhil_MCR has a reputation beyond reputePhil_MCR has a reputation beyond repute
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.
Reply With Quote
  #76  
Old 24.11.2011, 15:23
amogles's Avatar
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
amogles has a reputation beyond reputeamogles has a reputation beyond reputeamogles has a reputation beyond reputeamogles has a reputation beyond reputeamogles has a reputation beyond reputeamogles has a reputation beyond repute
Re: A question for the math geeks

Quote:
View Post
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.
Reply With Quote
  #77  
Old 24.11.2011, 15:58
MrVertigo's Avatar
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
MrVertigo has a reputation beyond reputeMrVertigo has a reputation beyond reputeMrVertigo has a reputation beyond reputeMrVertigo has a reputation beyond reputeMrVertigo has a reputation beyond reputeMrVertigo has a reputation beyond repute
Re: A question for the math geeks

Quote:
View Post
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.
Reply With Quote
  #78  
Old 24.11.2011, 16:09
Phil_MCR's Avatar
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
Phil_MCR has a reputation beyond reputePhil_MCR has a reputation beyond reputePhil_MCR has a reputation beyond reputePhil_MCR has a reputation beyond reputePhil_MCR has a reputation beyond reputePhil_MCR has a reputation beyond repute
Re: A question for the math geeks

Quote:
View Post
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.
Reply With Quote
  #79  
Old 24.11.2011, 19:50
MrVertigo's Avatar
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
MrVertigo has a reputation beyond reputeMrVertigo has a reputation beyond reputeMrVertigo has a reputation beyond reputeMrVertigo has a reputation beyond reputeMrVertigo has a reputation beyond reputeMrVertigo has a reputation beyond repute
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.
Reply With Quote
  #80  
Old 24.11.2011, 21:21
FrankZappa's Avatar
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
FrankZappa has a reputation beyond reputeFrankZappa has a reputation beyond reputeFrankZappa has a reputation beyond reputeFrankZappa has a reputation beyond reputeFrankZappa has a reputation beyond reputeFrankZappa has a reputation beyond repute
Re: A question for the math geeks

Quote:
View Post
yup agree. The simulation should only be used to confirm/invalidate the analytical solution.
Lots of real world problems don't have analytical solutions.
Reply With Quote
Reply




Currently Active Users Viewing This Thread: 1 (0 members and 1 guests)
 
Thread Tools
Display Modes

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 Off
Trackbacks are Off
Pingbacks are Off
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
iPhone geeks, this ones for you sam ali TV/internet/telephone 6 30.09.2011 23:16
Gadgets for Geeks! Odyssey General off-topic 8 30.11.2010 11:31
Show me your geeks Polorise Jokes/funnies 8 14.12.2009 12:17
For the real geeks about coffee flavio Food and drink 25 07.12.2009 03:43
About geeks dende General off-topic 0 15.04.2008 20:12


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


Powered by vBulletin® Version 3.8.4
Copyright ©2000 - 2022, Jelsoft Enterprises Ltd.
LinkBacks Enabled by vBSEO 3.1.0