Need for needles

[radosr]

You are given a stick of length 1 and a supply of n identical needles of length h. Drop the n needles at random on the stick, subject to the following "needle discipline": needles should fit entirely within the stick (they cannot stick out). What is the probability that no two needles overlap?

 

[pruse]

Are we assuming the stick is one-dimensional, so that the needles can only lie along the length of the stick?

 

[Tom Maloney]

Are we assuming the stick is one-dimensional, so that the needles can only lie along the length of the stick?

I'm guessing so, otherwise probability would definitely vary as a function of thickness. And then the definition of overlap should include "cross", where the needles are not necessarily parallel.

 

[radosr]

Yes, that is the correct assumption. The stick is just an interval (0,1). Needles are small intervals of length h, that are somewhere inside.

 

[pruse]

Dropping the needles so that they all fall within the stick is equivalent to randomly picking \(n\) numbers (the left endpoints) each uniformly and independently drawn from \([0,1-h]\). Under this interpretation, the volume of the sample space is \((1-h)^n\). The volume of the region where the first needle is to the left of the second is to the left of the third ... is to the left of the \(n\)-th, is given by \(\int_0^{1-nh}\int_{x_1+h}^{1-(n-1)h}\cdots\int_{x_{n-1}+h}^{1-h}1dx_ndx_{n-1}\cdots dx_1\), which comes out to \(\frac{(1-nh)^n}{n!}\). To account for the ordering we need to multiply this by \(n!\). The probability we want is then \(\frac{(1-nh)^n}{(1-h)^n}\)

 

[bigbadwolf]

Dropping the needles so that they all fall within the stick is equivalent to randomly picking \(n\) numbers (the left endpoints) each uniformly and independently drawn from \([0,1-h]\). Under this interpretation, the volume of the sample space is \((1-h)^n\). The volume of the region where the first needle is to the left of the second is to the left of the third ... is to the left of the \(n\)-th, is given by \(\int_0^{1-nh}\int_{x_1+h}^{1-(n-1)h}\cdots\int_{x_{n-1}+h}^{1-h}1dx_ndx_{n-1}\cdots dx_1\), which comes out to \(\frac{(1-nh)^n}{n!}\). To account for the ordering we need to multiply this by \(n!\). The probability we want is then \(\frac{(1-nh)^n}{(1-h)^n}\)

Not sure but to avoid overlap, should not the second iterated integral be \(int_{x_1+h}^{1-nh-(x_1+h)}\)?

 

[pruse]

Not sure but to avoid overlap, should not the second iterated integral be \(int_{x_1+h}^{1-nh-(x_1+h)}\)?

No. The lower bound of \(x_1+h\) is enough: the second left endpoint has to be at least \(h\) units ahead of the first left endpoint.

 

[pruse]

I neglected to mention:

The above argument holds only if \(hn\leq 1\). If \(hn>1\), the probability is of course zero.

 

[bigbadwolf]

No. The lower bound of \(x_1+h\) is enough: the second left endpoint has to be at least \(h\)units ahead of the first left endpoint.

Right you are.

 

[Ergodic]

http://xkcd.com/356/

 

[pruse]

http://xkcd.com/356/

Hahaaa

 

[radosr]

I got just (1-nh)^n, but I could be wrong...

 

[pruse]

When n=1, the probability of no overlap should be 1.

 

[Ohad]

When n=1, the probability of overlap should be 1.

Ninja edit, I accidentally did the 1-P of the question

 

[pruse]

I meant to say the probability of *no* overlap.

 

[radosr]

When n=1, the probability of no overlap should be 1.

For n=1, the probability is 1-h, since the needle still has to fit into the interval.

 

[pruse]

For it to be 1-h, we'd have to assume that either the sample space of left endpoints is the entire interval or the sample space of right endpoints is. but then the other endpoint can be off the stick, yet there's no reason to distinguish between right and left.

The way I understand it, the question is asking for the conditional probability of no overlap, given that all needles land completely on the stick.

 

[pratikpoddar]

I think it should be
\(\int_0^{1-nh}\int_{x_1+h}^{1-nh}\cdots\int_{x_{n-1}+h}^{1-nh}1dx_ndx_{n-1}\cdots dx_1\)

Right?

Dropping the needles so that they all fall within the stick is equivalent to randomly picking \(n\) numbers (the left endpoints) each uniformly and independently drawn from \([0,1-h]\). Under this interpretation, the volume of the sample space is \((1-h)^n\). The volume of the region where the first needle is to the left of the second is to the left of the third ... is to the left of the \(n\)-th, is given by \(\int_0^{1-nh}\int_{x_1+h}^{1-(n-1)h}\cdots\int_{x_{n-1}+h}^{1-h}1dx_ndx_{n-1}\cdots dx_1\), which comes out to \(\frac{(1-nh)^n}{n!}\). To account for the ordering we need to multiply this by \(n!\). The probability we want is then \(\frac{(1-nh)^n}{(1-h)^n}\)

 

[pruse]

I think it should be
\(\int_0^{1-nh}\int_{x_1+h}^{1-nh}\cdots\int_{x_{n-1}+h}^{1-nh}1dx_ndx_{n-1}\cdots dx_1\)

Right?

Nope. Because if any left endpoints of the earlier needles are too far to the right, there's no room to place later needles with no overlap.

 

[pratikpoddar]

Right. Thanks. I was expecting that would mean that the integrals to the further right should be zero. But that is not the case. Thanks.