В сети есть несколько статей, в которых обсуждается следующий вопрос, который якобы возник во время интервью с Google.

Если вероятность увидеть машину на трассе за 30 минут составляет 0,95, какова вероятность увидеть машину на трассе через 10 минут? (предполагаем постоянную вероятность дефолта)

Это вопрос, чтобы проверить мои навыки вероятности - что, если математика мне не друг, а программирование?

Вероятность 10-минутного интервала должна быть в диапазоне от 0 до 1, я знаю по крайней мере столько же. И я могу смоделировать событие Бернулли с вероятностью p¹⁰, используя единый генератор случайных чисел: success = rand() < p¹⁰.

Затем я могу отслеживать дорогу в течение трех независимых 10-минутных интервалов с заданной вероятностью p¹⁰, чтобы проверить, вижу ли я машину. Если я отслеживаю сразу несколько дорог, я могу оценить вероятность p³⁰ 30-минутного интервала на основе 10-минутных интервалов с фиксированным значением p¹⁰.

Итак, я могу найти p³⁰ для заданного значения p¹⁰, но как мне найти p¹⁰ для желаемого значения p³⁰ =. 95? Ответ - метод деления пополам. Это своего рода бинарный поиск по непрерывным данным.

Начните поиск с интервалом [0, 1] и установите p¹⁰ = .5
Если p³⁰ ›.95, выполните поиск по [0, .5]
If p³⁰‹ .95 , поиск по [.5, 1]

Через мгновение выясняется, что вероятность для 30-минутного интервала составляет около 63%. А кто сказал, что математика нужна для решения сложных задач ?!

Https://github.com/coells/100days

Https://notebooks.azure.com/coells/libraries/100days

алгоритм

def solve_question(trials):
    # range to search in
    probability_range = np.array([0., 1.])
    while True:
        # prob. to see car in 10 minutes
        probability_10min = probability_range.mean()
        
        # simulate three 10-minute intervals
        events = np.random.rand(trials, 3) < probability_10min
        events = np.sum(events, axis=1) > 0
        # prob. to see car in 30 minutes
        probability_30min = np.mean(events)
        if abs(probability_30min - .95) < 1e-4:
            return probability_10min
        # bisection
        i = 0 if probability_30min < .95 else 1
        probability_range[i] = probability_10min

бегать

> solve_question(10**6)
0.6318359375