§ 13.4. Выбор с отбрасыванием

Задача, рассматривавшаяся в § 13.2 и 13.3, весьма специфична в тгом отношении, что единственной информацией, которую статистик получает в результате осмотра предмета, является его ранг среди всех уже просмотренных предметов. Тем самым предполагается, что в начале процесса осмотра статистик ничего не знает об общем уровне обследуемых им произведений искусства. Таким образом, даже если статистик осознает чрезвычайную красоту и совершенство первого из них, то он должен считать равновероятным высокое и низкое качество этого произведения среди всех осматриваемых. В задачах, к которым мы сейчас перейдем, статистик располагает значительно более обширной информацией. Мы предположим, что каждому просмотренному предмету статистик сразу по осмотре может приписать численную полезность и самое важное, что статистику известно распределение этих полезностей во всей большой совокупности, предметов из которой могут рассматриваться как выборка.

Более точно, предположим, что последовательная повторная выборка из распределения на вещественной прямой с известной и конечным средним значением. Допустим, что для числа производимых наблюдений задана верхняя граница На шаге процесса выбора после наблюдения значений статистик может либо Остановиться, получив выигрыш либо продолжать выбор, наблюдая Он заведомо должен остановиться с выигрышем, равным последнему наблюдению если не остановился нигде ранее. Как обычно, обозначим через случайное число наблюдений, проводимых при некотором заданном правиле остановки. Задача состоит в отыскании правила остановки, максимизирующего средний выигрыш Это задача выбора с отбрасыванием, поскольку здесь, как и в задаче из § 13.2 и 13.3, если статистик решил не останавливаться на некотором наблюдении, то он «отбрасывает» его и уже не сможет позже принять это значение в качестве выигрыша.

На всяком шаге процесса выбора после того, как сделано хотя бы одно наблюдение, состояние статистика задается значением х последнего наблюдения и числом наблюдений, оставшихся да момента обязательного прекращения выбора. При обозначим через средний выигрыш от использования оптимальной процедуры при этих условиях. Итак, после наблюдения значений средний выигрыш, отвечающий оптимальной процедуре, равен Так как статистик обязан остановиться и принять значение последнего из отведенных ему наблюдений в качестве выигрыша, в случае если он не остановился раньше, то при

Далее, для обозначим через максимальный средний выигрыш, который может быть получен, когда осталось провести наблюдений, причем хотя бы одно из них обязательна проводится до окончания выбора. Так как рассматриваемая задача есть задача выбора с отбрасыванием из известного распределения, то средний выигрыш от проведения хотя бы одного наблюдения и последующего оптимального продолжения есть постоянная, зависящая лишь от числа оставшихся наблюдений и не зависящая от значений уже проведенных наблюдений. После одного дальнейшего наблюдения X средний выигрыш от продолжения оптимального на оставшихся шагах есть Поэтому средний выигрыш равен

При средний выигрыш от использования оптимальной процедуры должен быть равен максимуму двух выигрышей: выигрыша х от остановки и среднего выигрыша от продолжения. Таким образом,

Так как то функции и числа можно найти последовательно из соотношений (1) и (2). Поскольку более наблюдений провести нельзя, а хотя бы одно наблюдение должно быть сделано, средний выигрыш от оптимальной процедуры равен Если в начале процесса выбора статистик может получить выигрыш без всяких наблюдений, то средний выигрыш от оптимальной процедуры равен

Пусть теперь преобразование определенное формулой (9) § 11.8. Оно существует в силу предположения о конечности среднего Можно показать (упр. 5), что преобразование обладает следующим свойством:

Из (1) и (2) видно, что при

Согласно (1), Следовательно, последовательность может быть найдена с помощью рекуррентного соотношения (4). Так как число наблюдений не может превосходить то, согласно оптимальной процедуре надо продолжать наблюдения, если наблюденное значение надо окончить выборг если Средний выигрыш при такой процедуре равен

Некоторые примеры представлены ниже в упр. 6—9.

Аналогичные задачи рассматривали Гилберт и Мостеллер (1966), Гутмэн (1960) и Мозер (1956), а также Кэли (1875) боле чем на 80 лет раньше всех других.