В теории вероятностей проблему оптимальной остановки Роббинса , названную в честь Герберта Роббинса , иногда называют проблемой четвертого секретаря или проблемой минимизации ожидаемого ранга при полной информации. Его утверждение состоит в следующем.
Пусть X1 ,..., Xn — независимые, одинаково распределенные случайные величины , равномерные на [0, 1] . Мы наблюдаем X k последовательно и должны остановиться ровно на одном из них. Воспоминание о предыдущих наблюдениях не допускается. Какое правило остановки минимизирует ожидаемый ранг выбранного наблюдения и каково его соответствующее значение?
Общее решение этой проблемы ожидаемого ранга полной информации неизвестно. Основная трудность состоит в том, что задача полностью зависит от истории, т. е. оптимальное правило на каждом этапе зависит от всех предшествующих значений, а не только от их более простых достаточных статистик. Известны только границы предельного значения v при стремлении n к бесконечности, а именно 1,908 < v < 2,329. Известно, что есть возможность улучшить нижнюю границу путем дальнейших вычислений для усеченной версии задачи. До сих пор неизвестно, как улучшить верхнюю границу, вытекающую из подкласса пороговых правил без памяти.
Одной из причин изучения проблемы Роббинса является то, что при ее решении будут решены все классические (четыре) задачи о секретарях . Но основная причина заключается в том, чтобы понять, как справиться с полной зависимостью от истории в (обманчиво простой) задаче. На международной конференции Ester's Book в Израиле (2006 г.) проблема Роббинса соответственно была названа одной из четырех наиболее важных проблем в области оптимальной остановки и последовательного анализа .
Герберт Роббинс представил описанную выше проблему на Международной конференции по поиску и селекции в реальном времени в Амхерсте в 1990 году. Он завершил свое выступление словами: « Я хотел бы, чтобы эта проблема была решена до того, как я умру» . С тех пор ученые, работающие в области оптимальной остановки, назвали эту проблему проблемой Роббинса .