Неравенство Пророка

В теории онлайн-алгоритмов и оптимальной остановки — неравенство Пророка это граница ожидаемого значения процесса принятия решений, который обрабатывает последовательность случайных входных данных из известных распределений вероятностей , относительно ожидаемого значения, которое может быть достигнуто с помощью « пророк», который заранее знает все входные данные (а не только их распределение). Эти неравенства имеют приложения в теории построения алгоритмических механизмов и математических финансах .

Один предмет

Классическое неравенство пророка, состоящее из одного элемента, было опубликовано Кренгелем и Сучестоном (1978) , приписав его точную форму DJH (Бену) Гарлингу. Речь идет о процессе, в котором последовательность случайных величин $X_{i}$ поступают из известных дистрибутивов ${\mathcal {D}}_{i}$. Когда каждый $X_{i}$ поступает, процесс принятия решения должен решить, принять его и остановить процесс или отклонить его и перейти к следующей переменной в последовательности. Значением процесса является единственная принятая переменная, если она есть, или ноль в противном случае. Можно предположить, что все переменные неотрицательны; в противном случае замена отрицательных значений нулем не изменит результат. Это может, например, моделировать финансовые ситуации, в которых переменными являются предложения купить какой-то неделимый товар по определенной цене, и продавец должен решить, какое предложение (если таковое имеется) принять. Пророк, зная всю последовательность переменных, очевидно, может выбрать наибольшую из них, достигнув значения ${\textstyle \max _{i}X_{i}}$ для любого конкретного экземпляра этого процесса и ожидаемое значение ${\textstyle \mathbb {E} [\max _{i}X_{i}]}$. Неравенство пророка утверждает существование онлайн-алгоритма для этого процесса, чье ожидаемое значение как минимум вдвое меньше, чем у пророка: ${\textstyle {\tfrac {1}{2}}\mathbb {E} [\max _{i}X_{i}]}$. Ни один алгоритм не может достичь большего ожидаемого значения для всех распределений входных данных.

Один из методов доказательства неравенства Пророка с одним элементом — использовать «пороговый алгоритм», который устанавливает параметр $\tau$ а затем принимает первую случайную величину, которая по крайней мере равна $\tau$. Если вероятность того, что этот процесс примет элемент, равна $p$, то его ожидаемое значение равно $p\tau$ плюс ожидаемое превышение над $\tau$ что выбранная переменная (если она есть). Каждая переменная $X_{i}$ будет учитываться пороговым алгоритмом с вероятностью не менее $1-p$, и если это учитывать, будет способствовать ${\textstyle \max(X_{i}-\tau ,0)}$ к избытку, поэтому в силу линейности ожидания ожидаемый избыток составляет, по крайней мере, $$\mathbb {E} {\Bigl [}\sum _{i}(1-p)\max(X_{i}-\tau ,0){\Bigr ]}\geq (1-p){\bigl (}\mathbb {E} [\max _{i}X_{i}]-\tau ).$$ Параметр $\tau$ к медиане распределения ${\textstyle \max _{i}X_{i}}$, так что $p={\tfrac {1}{2}}$и добавление $p\tau$ к этой границе ожидаемого избытка, приводит к $p\tau$ и $(1-p)(-\tau )$ члены отменяют друг друга, показывая, что для этой настройки $\tau$ пороговый алгоритм достигает ожидаемого значения не менее ${\textstyle {\tfrac {1}{2}}\mathbb {E} [\max _{i}X_{i}]}$. Другой порог, ${\textstyle \tau ={\tfrac {1}{2}}\mathbb {E} [\max _{i}X_{i}]}$, также достигает как минимум того же ожидаемого значения.

Обобщения

Известны различные обобщения одноэлементного неравенства пророка на другие онлайн-сценарии, которые также называются неравенствами пророка.

Сравнение с конкурентным анализом

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

Внешние ссылки

• Матроид Пророк Неравенства и проектирование механизмов , The Maroid Union
• Экономический взгляд на неравенство Пророка