On a flat table, there is drawn a circle with radius r. A line is drawn through the circle running exactly north/south and passes directly through the centre of the circle.
A thin needle of length l, where 0<l<=r is thrown randomly onto the circle. if any part of the needle is outside the circle, it is picked up and re-thrown until it lies entirely on or within the circle.
What is the probability that the needle touches the line?
Second part of the question:
n>0 identical needles are thrown in the same manner onto the circle. a heavy cylinder then is pressed onto the needles so that they are pressed into a flat plane.
let T be the number of different needles that touch or cross. for example, if 3 needles are thrown and needles 1 and 2 land in exactly the same way and the third lies across both 1 and 2, then T=3: 1 touches 2, 1 touches 3, 2 touches 3.
what is the expected value of T for a given value of n, l and r?
doesn't it depend on the position and strength of the magnet?
yeah, the only people who use FORTRAN are those that have to or those that don't know any better.
used quite a lot in science because many scientific routines/libraries/algorithms are already written and are very well optimised.
now. who's got an answer on the circle/needle problem?
Even the big reliable FORTRAN codes (ODEPACK, MINPACK) are being made accessible from modern languages, like Python and R, so there's less and less need to learn it.
That needle/circle problem looks tough, even the 1st part. I might try a Monte Carlo simulation, but an analytical answer (if it exists) is way out of my reach (I tried). Any other offers?
Even the big reliable FORTRAN codes (ODEPACK, MINPACK) are being made accessible from modern languages, like Python and R, so there's less and less need to learn it.
That needle/circle problem looks tough, even the 1st part. I might try a Monte Carlo simulation, but an analytical answer (if it exists) is way out of my reach (I tried). Any other offers?
I can't be arsed to the maths now but my gut feeling is that the problem gets a lot simpler if you pick the right coordinate system.
On a flat table, there is drawn a circle with radius r. A line is drawn through the circle running exactly north/south and passes directly through the centre of the circle.
A thin needle of length l, where 0<l<=r is thrown randomly onto the circle. if any part of the needle is outside the circle, it is picked up and re-thrown until it lies entirely on or within the circle.
What is the probability that the needle touches the line?
Second part of the question:
n>0 identical needles are thrown in the same manner onto the circle. a heavy cylinder then is pressed onto the needles so that they are pressed into a flat plane.
let T be the number of different needles that touch or cross. for example, if 3 needles are thrown and needles 1 and 2 land in exactly the same way and the third lies across both 1 and 2, then T=3: 1 touches 2, 1 touches 3, 2 touches 3.
what is the expected value of T for a given value of n, l and r?
Your first question seems a bit hard due to the boundary effect. The following modification would probably be much easier. Instead of landing the needle as you suggested, land it as follows: pick a point A with uniform distribution on the disk of radius r. Then choose a direction at random and draw a needle of length l in the choosen direction and with center at A. For this modified version of your first question, it is not too hard to compute the probability that the needle crosses the line segment joining the north pole and the south pole.
I am not sure if I understand the definition of T in your second question. Did you mean T = the sum of all X(i,j), with 0 < i < j < n+1, where X(i,j) = 1 if needle #i and needle #j touch or cross and X(i,j) = 0 if they do not? If that is the case, then clearly the expected value of T is simply E[T] = n(n-1)/2 p*, where p* is the probability that needle #1 and needle #2 touch or cross. It remains only to compute p*.
Your first question seems a bit hard due to the boundary effect. The following modification would probably be much easier. Instead of landing the needle as you suggested, land it as follows: pick a point A with uniform distribution on the disk of radius r. Then choose a direction at random and draw a needle of length l in the choosen direction and with center at A. For this modified version of your first question, it is not too hard to compute the probability that the needle crosses the line segment joining the north pole and the south pole.
I am not sure if I understand the definition of T in your second question. Did you mean T = the sum of all X(i,j), with 0 < i < j < n+1, where X(i,j) = 1 if needle #i and needle #j touch or cross and X(i,j) = 0 if they do not? If that is the case, then clearly the expected value of T is simply E[T] = n(n-1)/2 p*, where p* is the probability that needle #1 and needle #2 touch or cross. It remains only to compute p*.
I love this stuff...
yes, the boundaries make it bit more complicated. your simplified version makes it easier and perhaps that should be the first step. though there are still some boundary issues (the strip of points within distance l of the central line).
i was pondering this puzzle again on the train home from the viadukt.
the original version is not so much more difficult, you just have to include a special calculation for the annulus of points distance 'l' from the circle edge and also the intersection of the annulus and strip.
Dear Phil MCR,
About Problem 1:
Perhaps you are underestimating the complexity of the boundary issues. Suppose that I see where the needle has landed and I give you the following information: the needle is in a horizontal position! Given that information, what are the possible locations for the center of the needle? The answer is not "the disk minus the annulus of width l/2 near the edge of the disk". Assuming we are talking about the disk of radius r centered at the origin, we can see that if the needle has landed with an east-west orientation, then near the point (-r,0) (or (r,0)), the center of the needle has to be at least a distance l/2 from the boundary whereas near the north pole (0,r) (or the south pole (0,-r)), the center of the needle can be at a distance less than l/2 from the boundary (with the whole needle still completely within the disk).
About Problem 2:
I assume that you agree with my comment to the effect that
E[T] = n(n-1)/2 times p*
where p* is the probability that 2 needles (chosen at random, independently of one another, using the same scheme as in Problem 1) will intersect.
I think that p* is very difficult to compute, again because of the bizarre boundary condition effect.
A much simpler version of Problem 2 (yet still very hard): replace the needles by little circles of diameter l. Then the new p*, let's call it p', is the probability that the two small circles will have a non-empty intersection. In other words, p' is the probability that two points (the centers of the 2 small circles) chosen at random, independently of each other, on the disk of radius r' = r-l/2 (we want the small circles to be completely inside the big one; note that here the boundary issues are much simpler) will be within a distance l of each other. Being able to compute p' is equivalent to being able to compute the distribution of the distance between 2 points chosen at random (uniformly, independently) inside a disk of radius r'. We can scale down: take r' = 1.
So here is a simple problem: Choose 2 points (independently and uniformly) on the unit disk. Find the distribution of the distance between these 2 points. It is a well-studied (and somewhat difficult) problem. Lots of papers have been published on the n-dimensional (hypersphere) version of that problem. I really need a cup of coffee...
Dear Phil MCR,
About Problem 1:
Perhaps you are underestimating the complexity of the boundary issues. Suppose that I see where the needle has landed and I give you the following information: the needle is in a horizontal position! Given that information, what are the possible locations for the center of the needle? The answer is not "the disk minus the annulus of width l/2 near the edge of the disk". Assuming we are talking about the disk of radius r centered at the origin, we can see that if the needle has landed with an east-west orientation, then near the point (-r,0) (or (r,0)), the center of the needle has to be at least a distance l/2 from the boundary whereas near the north pole (0,r) (or the south pole (0,-r)), the center of the needle can be at a distance less than l/2 from the boundary (with the whole needle still completely within the disk).
that's correct. at the moment, i'm looking to solve for the special case where r>2l. this creates a few special regions:
- strip of points within distance l of the central line
- annulus of points within distance l of the circumference
i model the needle, by taking a random point p within the disc and then assuming one end of the needles is at this point. then assume the needle lies at an angle \theta.
if the needle falls within the two half-discs created by excluding the special regions, then it cannot cross the line.
if you take now the annulus excluding the bits near the north and south:
first taking the point on the circumference, you can see that \theta is contrained within an angle defined by where the other end of the needle touches the circle above and below. as you move the point from the circumference to the inner edge of the annulus, the angle increases until it is 2*\pi radians. therefore, we can get a simple expression for the probability that the needle lies within the disc assuming one end falls within this part of the annulus.
__________________
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.
Problem 1:
Let's try to throw them few into the circle... let's say 1000 independent randomly generated and just count them
I've written one Matlab model which could of course still be buggy - but just to throw a bone and to start chewing.
My answer would be that about 26-28% needles would touch/cross the line. I've included also the lines of the circle here.
I'm attaching one image and Matlab files and try to count it yourself
Now let's go back to work...
thanks. but i guess the probability will depend on the ratio of l and r. if l=2r, then the all the needles will touch as they will have to cross the centre point.
EDIT: i see what you did, you randomized needle lengths, whereas i had meant that the needles would be a fixed length l and so the probability should be a function of l and r.
Linear Mode
