# JUNTO Practice: Probability, Intersecting Intervals

Discussed on July 14, 2020.

Choose two random numbers from [0,1] and let them be the endpoints of a random interval. Repeat this n times. What is the probability that there is an interval which intersects all others?

## Solutions

Click to see:

### Oscar Martinez

``````import numpy as np

def get_intervals(n=1):
return np.random.uniform(size=(n, 2))

def check_for_super_intersector_naive(intervals):
# the interval will contain an endpoint from all other intervals
for interval in intervals:
lbound = interval.min()
rbound = interval.max()
super_intersector = np.all(
np.apply_along_axis(
lambda inv: (lbound <= inv <= rbound)
| (lbound <= inv <= rbound),
axis=1,
arr=intervals,
)
)
if super_intersector:
return True
return False

def check_for_super_intersector(intervals):
# the interval will contain an endpoint from all other intervals
for interval in intervals:
lbound = interval.min()
rbound = interval.max()
super_intersector = np.all(
np.any(
(intervals >= lbound)
& (intervals <= rbound),
axis=1,
)
)
if super_intersector:
return True
return False

def simulate(n, simulations):
return np.mean(
[
check_for_super_intersector_naive(
get_intervals(n)
)
for _ in range(simulations)
]
)

def simulate_1(n, simulations):
sim_sums = 0
return np.mean(
[
check_for_super_intersector(get_intervals(n))
for _ in range(simulations)
]
)

if __name__ == "__main__":
print(f"N=5: {simulate_1(5,10000)}")
print(f"N=10: {simulate_1(10,10000)}")
print(f"N=20: {simulate_1(20,10000)}")
``````

### John Lekberg

I believe that the probability that there is an interval which intersects all others is

• 1 for n = 1.
• 2/3 for n > 1.

I wrote a Python function to sample the random boolean variable "there is an interval which intersects all others."

``````import numpy as np

def random_interval_IAO(*, n_I, n_sample):
"""
n_I -- number of intervals. (E.g. 10.)
n_sample -- number of samples to take (E.g. 10_000.)
"""
I = np.random.uniform(0, 1, (2, n_I, n_sample))
I.sort(axis=0)
covers_all = np.logical_and(
I <= I.min(axis=0),
I >= I.max(axis=0),
)
return covers_all.any(axis=0)
``````

Then I wrote a Python function to generate a table of probabilities:

``````def table_avg_interval_IAO(*, n_I_range, n_sample):
print("n_I  Prob.")
print("---  -----")
for n_I in n_I_range:
sample = random_interval_IAO(
n_I=n_I, n_sample=n_sample
)
print(f"{n_I:3}  {sample.mean():5.0%}")

table_avg_interval_IAO(
n_I_range=range(1, 16), n_sample=1_000_000
)
``````
``````n_I  Prob.
---  -----
1   100%
2    67%
3    67%
4    67%
5    67%
6    67%
7    67%
8    67%
9    67%
10    67%
11    67%
12    67%
13    67%
14    67%
15    67%
``````

### Daniel Bassett

The solution is 0.67 or 2/3. I found this by running a simulation that generated 100 intervals and tested whether they were intersected by another interval.

``````from random import random

def generate_intervals(n):
# create empty list to store intervals
interval_list = [0 for i in range(n)]
i = 0

while i < len(interval_list):
# generate random numbers, order them in a tuple & store in list
first_number = random()
second_number = random()
unordered_interval = [first_number, second_number]
ordered_interval = sorted(unordered_interval)
left_end = ordered_interval
right_end = ordered_interval
interval = tuple([left_end, right_end])
interval_list[i] = interval
i += 1

for x, y in interval_list:
# copy interval list and generate empty boolean list
new_list = interval_list[:]
span_values = []
# clip each tuple from the list & compare to see if it is intersected
# by another tuple, store results as boolean in a list
new_list.remove((x, y))
for i, j in new_list:
if y < i or x > j:
span_values.append(False)
break
else:
span_values.append(True)
# if each tuple is intersected by another, return 'True'
if all(span_values):
return True
return False

# store these results in an overall boolean list to give us the total probability
def simulation(trials, n):
result_list = []
for i in range(trials):
result_list.append(generate_intervals(n))
return sum(result_list) / len(result_list)

# print three different size trials to show the results converging to the actual
# probability
print(simulation(100, 100))
print(simulation(1000, 100))
print(simulation(10000, 100))
``````