В теории вероятностей , проблема Роббинса в оптимальной остановки , названный в честь Герберта Robbins , иногда называют четвертой задачи секретаря или проблемы минимизации ожидаемого ранга с полной информацией. Его формулировка такова.
Пусть X 1 , ..., X n - независимые одинаково распределенные случайные величины , однородные на [0, 1]. Мы наблюдаем X k последовательно и должны остановиться ровно на одном из них. Отзыв предыдущих наблюдений не допускается. Какое правило остановки минимизирует ожидаемый ранг выбранного наблюдения и каково его соответствующее значение?
Общее решение этой проблемы ожидаемого ранга с полной информацией неизвестно. Основная трудность состоит в том, что проблема полностью зависит от истории, то есть оптимальное правило зависит на каждом этапе от всех предыдущих значений, а не только от более простой достаточной статистики этих. Известны только границы для предельного значения v при стремлении n к бесконечности, а именно 1.908 < v <2.329. Известно, что есть возможности улучшить нижнюю границу путем дальнейших вычислений для усеченной версии задачи. До сих пор не известно, как улучшить верхнюю границу, вытекающую из подкласса пороговых правил без памяти.
Важность [ править ]
Одним из мотивов изучения проблемы Роббинса является то, что с ее решением будут решены все классические (четыре) задачи секретаря . Но главная причина состоит в том, чтобы понять, как справиться с полной исторической зависимостью в (обманчиво простой) проблеме. На Международной конференции Ester's Book в Израиле (2006) проблема Роббинса была соответственно названа одной из четырех наиболее важных проблем в области оптимальной остановки и последовательного анализа .
История [ править ]
Герберт Роббинс представил описанную выше проблему на Международной конференции по поиску и отбору в реальном времени в Амхерсте в 1990 году. Он завершил свое выступление словами: « Я хотел бы, чтобы эта проблема была решена, прежде чем я умру» . Ученые, работающие в области оптимальной остановки, с тех пор назвали эту проблему проблемой Роббинса .
Ссылки [ править ]
- Чоу, Ю.С.; Moriguti, S .; Роббинс, H .; Сэмюэлс, С.М. (1964). «Оптимальный выбор на основе относительного ранга». Израильский математический журнал . 2 (2): 81–90. DOI : 10.1007 / bf02759948 .
- «Минимизация ожидаемого ранга с помощью полной информации», Ф. Томас Брюсс и Томас С. Фергюсон , Журнал прикладной вероятности, том 30 , № 1 (1993), стр. 616–626
- Полупророки и проблема Роббинса минимизации ожидаемого ранга, Ф. Т. Брюсс и Т. С. Фергюсон, Лекционные заметки Springer в томе 1 статистики в честь Дж. М. Гани, (1996), стр. 1–17
- «Проблема секретаря; минимизация ожидаемого ранга с помощью iid случайных величин», Д. Ассаф и Э. Самуэль-Кан, Adv. Прил. Вероятность. Том 28 , (1996), стр. 828–852 Кат.Инист.
- "Что известно о проблеме Роббинса?" Ф. Томас Брюсс , Журнал прикладной вероятности, том 42 , № 1 (2005), стр. 108–120 Евклид
- «Подход с непрерывным временем к проблеме Роббинса минимизации ожидаемого ранга», Ф. Томас Брюсс и Ив Каоимхин Свон, Журнал прикладной вероятности, том 46, № 1, 1–18, (2009).
