Один прогін: кандидати надходять зліва направо; фаза огляду
приглушена, фаза стрибка активна, обраний виділений
Монте-Карло: частка успіху залежно від порога r для всіх r = 0 … N,
пік позначено при N/e
📖 Теорія — оптимальна зупинка
Ви співбесідуєте
N кандидатів по одному у випадковому
порядку. Після кожної співбесіди потрібно одразу вирішити: найняти
чи відхилити — відмови остаточні, повернутися не можна. Ви бачите
лише відносні ранги (знаєте, хто кращий дотепер), а не абсолютні
оцінки. Оптимальна стратегія — порогове правило: відхиліть
перших r кандидатів попри все (фаза «огляду»),
запам'ятавши кращого серед них, тоді наймайте першого пізнішого
кандидата, який перевершить цей орієнтир (фаза «стрибка»). Якщо ніхто
не перевершить — доведеться взяти останнього.
📐 Чому поріг — N/e, а успіх — 1/e
За порога
r ви виграєте саме тоді, коли найкращий
кандидат стоїть на позиції i > r, а кращий із перших
i − 1 кандидатів потрапляє у вікно огляду. Підсумовуючи
ці ймовірності, отримуємо ймовірність виграшу
P(r) = (r/N)·Σ 1/(i−1) для i = r+1 … N.
Поклавши x = r/N і взявши N → ∞, це дає
P(x) = −x·ln x, що максимізується при
x = 1/e. Тож найкращий поріг — r ≈ N/e
(близько 37% кандидатів), а відповідна ймовірність успіху —
−(1/e)·ln(1/e) = 1/e ≈ 0,368 — незалежно від N.
💡 Застосування
Та сама логіка з'являється всюди, де ви послідовно обираєте з
варіантів, до яких не можна повернутися: наймання найкращого
претендента з потоку співбесід, вибір квартири на гарячому ринку
оренди, де житло розлітається швидко, рішення, коли припинити
знайомства й осісти («правило 37% для кохання»), чи прийняття
найкращої пропозиції під час продажу низці покупців. Висновок
контрінтуїтивний: витратьте перші ~37% пошуку суто на збір
інформації, не беручи нічого, а тоді хапайте перший варіант, який
перевершує все бачене.