Return to JUNTO

JUNTO Practice: Probability, Intersecting Intervals

Discussed on July 14, 2020.

From "Twenty problems in probability":

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?

Please provide an answer and a justification.

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[0] <= rbound)
                | (lbound <= inv[1] <= 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


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[0] <= I[1].min(axis=0),
        I[1] >= I[0].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[0]
        right_end = ordered_interval[1]
        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))