Минимаксный принцип Яо об алгоритмах Монте-Карло

22

PXAPDRA

minAAEcost(A,D)maxxXEcost(R,x)for all D and R.

В основном принцип Яо касается только алгоритмов Лас-Вегаса , но его можно обобщить на алгоритмы Монте-Карло следующим образом. где обозначает стоимость алгоритмов Монте-Карло, вероятность которых не .

12minAAEcost2ϵ(A,D)maxxXEcostϵ(R,x)for all DR and ϵ[0,1/2]
costϵ(,)ϵ

В оригинальной статье Яо соотношение для алгоритмов Монте-Карло дано в теореме 3 без доказательства. Любой намек на доказательство этого?

Федерико Магалланез
источник

Ответы:

6

Это просто расширенный комментарий к ответу Маркоса с использованием его записи. Я не совсем в состоянии следить за деталями его аргумента, и тот, что ниже, довольно короткий и простой.

,

Aq(A)xd(x)ϵ(A,x)=xd(x)Aq(A)ϵ(A,x)λ.

Из приведенного выше факта и неравенства Маркова вытекает .Aβ(2λ)q(A)1/2

Итак, мы получаем:

maxxAq(A)r(A,x)xd(x)Aq(A)r(A,x)=Aq(A)xd(x)r(A,x)Aβ(2λ)q(A)xd(x)r(A,x)(Aβ(2λ)q(A))minAβ(2λ)xd(x)r(A,x)12minAβ(2λ)xd(x)r(A,x)
Сашо Николов
источник
8

Я попробую это. Я собираюсь использовать оригинальную запись Яо. Таким образом, будет легче противопоставить его статью и его определения.

Пусть - конечный набор входных данных, и пусть - конечный набор детерминированных алгоритмов, которые могут не дать правильный ответ для некоторых входных данных. Пусть также если дает правильный ответ для , и противном случае. Также обозначим через количество запросов, сделанных на входе , или, что эквивалентно, глубину дерева решенийIA0ϵ(A,x)=0Axϵ(A,x)=1r(A,x)AxA

Средняя стоимость: учитывая распределение вероятности для , средняя стоимость алгоритма равна .dIAA0C(A,d)=xId(x)r(A,x)

Распределительная сложность: Пусть . Для любого распределения на входах пусть будет подмножеством заданным . Сложность распределения с ошибкой для вычислительной задачи определяется как ,λ[0,1]dβ(λ)A0β(λ)={A:AA0,xId(x)ϵ(A,x)λ}λPF1,λ(P)=maxdminAβ(λ)C(A,d)

λ -толерантность: распределение в семействе является -толерантным, если .qA0λmaxxIAA0q(A)ϵ(A,x)λ

Ожидаемая стоимость: для рандомизированного алгоритма пусть будет распределением вероятности, -толерантным к . Ожидаемая стоимость из для данного входа являются .RqλA0RxE(R,x)=AA0q(A)r(A,x)

Рандомизированная сложность: пусть . Рандомизированная сложность с ошибкой равна .λ[0,1]λF2,λ=minRmaxxIE(R,x)

Теперь мы готовы идти в бизнес. То, что мы хотим доказать, - это распределение на входах и рандомизированный алгоритм (т. Е. Распределение на )dRqA0

Минимаксный принцип Яо для алгоритмов Монте-Карло для .

maxxIE(R,x)12minAβ(2λ)C(A,d)
λ[0,1/2]

Я буду следовать подходу, данному Фичем, Мейером и Хайде, Рагде и Вигдерсоном (см. Лемму 4). Их подход не дает характеристики для алгоритмов Лас-Вегаса (только нижняя граница), но этого достаточно для наших целей. Из их доказательства легко увидеть, что для любых иA0I

Утверждение 1. .maxxIE(R,x)minAA0C(A,d)

Чтобы получить правильные цифры там, мы сделаем что-то подобное. Учитывая, что распределение вероятностей заданное рандомизированным алгоритмом является толерантным к мы получаем, что Если мы заменим семейство наqRλA0

λmaxxI{AA0q(A)ϵ(A,x)}xId(x)AA0q(a)ϵ(A,x)=AA0q(a)xId(x)ϵ(A,x)minAA0{xId(x)ϵ(A,x)}.
A0β(2λ) Мы видим, что

λmaxxI{AA0q(A)ϵ(A,x)}maxxI{Aβ(2λ)q(A)ϵ(A,x)}xId(x)Aβ(2λ)q(a)ϵ(A,x)=Aβ(2λ)q(a)xId(x)ϵ(A,x)minAβ(2λ){12xId(x)ϵ(A,x)},

где следует второе неравенство, потому что , а последнее неравенство дается определением где сумма, деленная на 2, не может быть больше, чем . Следовательно, β(2λ)A0β(2λ)λ

maxxI{AA0q(A)ϵ(A,x)}12minAβ(2λ){xId(x)ϵ(A,x)}.

Отметив, что отображается на а отображается на и п. 1 выше, теперь мы можем смело заменить функцию в вышеприведенном неравенстве на чтобы получить желаемое неравенство.ϵ{0,1}rNϵr(A,x)

Маркос Вильягра
источник
Есть ли краткое объяснение, откуда взялся фактор 2?
Робин Котари
короче говоря, это происходит от определения . Суммирование в определении, деленное на 2, не более . β(2λ)λ
Маркос Вильягра
что-то кажется мне странным. по определению, так почему мин? maxAβ(2λ)){12xId(x),ϵ(A,x)}λ
Сашо Николов
и я не понимаю последнее предложение. как вы сделали полный аргумент о а затем заменили его на ? ϵr
Сашо Николов
Что касается вашего первого вопроса, я добавил более подробную информацию.
Маркос Вильягра