Один прогін: кандидати надходять зліва направо; фаза огляду приглушена, фаза стрибка активна, обраний виділений
Монте-Карло: частка успіху залежно від порога 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% пошуку суто на збір інформації, не беручи нічого, а тоді хапайте перший варіант, який перевершує все бачене.