• 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!

random intervals

radosr

Baruch MFE Faculty
Joined
7/18/07
Messages
640
Points
73
Numbers 1, 2, ..., 2010 on the x-axis are paired up at random to form 1005 intervals. Find the probability that one of these intervals intersects all the others.
 
if im not mistaken... pairing to have an interval (a,b) intersecting all of the others means that for each (a_i, b_i) != (a,b) one has a_i < a, b_i > b.

so, (a,b) = (1005, 1006), a_i < 1005, b_i > 1006.

thus, suitable / total number of pairings:
\[\frac{1004!}{\binom{2010}{1005} \cdot 1005!}= \frac{1}{\binom{2010}{1005} \cdot 1005}\]
 
The totol number ofpossible pairs (i.e the sample set ) :> 2010C2 *2008C2 * 2006C2 ..... 4C2 * 1

If one pair has to intersect all the other intervals (I assume it is (1,2010) ), we can have 1004 other distinct pairs , this can be done in : 2008C2 * 2006C2 .... 4C2 *1

The probability is => 2008C2 * 2006C2 .... 4C2 *1 / 2010C2 *2008C2 * 2006C2 ..... 4C2 * 1 => 1/2010c2 = 2/ 2010*2009 = 1/(1005*2009)
 
The totol number ofpossible pairs (i.e the sample set ) :> 2010C2 *2008C2 * 2006C2 ..... 4C2 * 1

If one pair has to intersect all the other intervals (I assume it is (1,2010) ), we can have 1004 other distinct pairs , this can be done in : 2008C2 * 2006C2 .... 4C2 *1

The probability is => 2008C2 * 2006C2 .... 4C2 *1 / 2010C2 *2008C2 * 2006C2 ..... 4C2 * 1 => 1/2010c2 = 2/ 2010*2009 = 1/(1005*2009)
The total number of possible pairs is (2n-1)(2n-3)...3*1=(2n-1)!!
Since in each pairing there must be an interval (1,b) then if we denote by S_n the total number of pairings in case of 2n numbers, we will have S_n=(2n-1)S_(n-1), ... , S_2=3*S_1, S_1=1. After substitution, we will have S_n=(2n-1)!!
In case of your answer if 2n=4 4C2=6 but the answer is 3.
 
I remember this problem from a while back. If I recall correctly, the answer is 2/3, and it's 2/3 no matter how many numbers you're pairing.
 
As I have posted, the total number of possible pairs for 2n numbers is S_n=(2n-1)!!
Now, using the same technique, we will get the answer of 2/3 as @peterruse mentioned.
In all cases there must be an interval (a, n) or (n,b) (overall (n-1)+n=2n-1 cases). If we remove this interval, we will have the same problem for 2n-2 numbers. After adding the removed interval, the interval that intersected all the others will intersect it as well since its length must be more than n-1. There is only one case when that interval is (n+1,2n), but in this case all the other intervals will intersect both all the others and the removed interval. So we have s_n=(2n-1)*s_n-1, ... , s_3=5*s_2, s_2=2*s_1, s_1=1. ( s_2=(2*2-1)s_1= 3*s_1 won't be correct since in this case there is no number between 1 and 2. If n>2 there is always a number before n which is essential for the intersection by the interval obtained for 2n-2 numbers). After substitution we get s_n=(2n-1)(2n-3)...7*5*2=(2/3)*(2n-1)!!.
Finally, P(n)=s_n/S_n=2/3 for all n.:)
 
Back
Top