• C++ Programming for Financial Engineering
    Highly recommended by thousands of MFE students. Covers essential C++ topics with applications to financial engineering. Learn more Join!
    Python for Finance with Intro to Data Science
    Gain practical understanding of Python to read, understand, and write professional Python code for your first day on the job. Learn more Join!
    An Intuition-Based Options Primer for FE
    Ideal for entry level positions interviews and graduate studies, specializing in options trading arbitrage and options valuation models. Learn more Join!

Need for needles

radosr

Baruch MFE Faculty
Joined
7/18/07
Messages
640
Points
73
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?
 
Are we assuming the stick is one-dimensional, so that the needles can only lie along the length of the stick?
 
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.
 
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.
 
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}\)
 
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)}\)?
 
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.
 
I neglected to mention:

The above argument holds only if \(hn\leq 1\). If \(hn>1\), the probability is of course zero.
 
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.
 
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}\)
 
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.
 
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.
 
Back
Top