Нижняя граница оценки

11

Я хотел бы знать ( в связи с этим другой вопрос ) , если нижние оценки были известны следующие задачи тестирования: один получает доступ запроса к последовательности неотрицательных чисел п1 и & epsi ; ( 0 , 1 ) с обещанием, что либо k n k = 1 a k = 1, либо n k = 1 a k1 - ε .ana1ε(0,1)k=1nak=1k=1nak1ε

Сколько запросы (Lookups) достаточны и необходимы для (адаптивного) рандомизированного алгоритма различения между этими двумя случаями, с вероятностью по крайней мере ?2/3

Я нашел предыдущий пост, который дает логарифмическую (по ) верхнюю границу для связанной задачи аппроксимации суммы и приблизительно совпадающую нижнюю границу этой проблемы для детерминированных алгоритмов; но не смог найти результат для конкретной проблемы, которую я рассматриваю (в частности, рандомизированные алгоритмы).n


Изменить: После ответа ниже, я думаю, я должен был быть более ясным: в приведенном выше (и особенно в асимптотике для нижней границы), является «основной» величиной, рассматриваемой как уходящая в бесконечность, в то время как ε является (сколь угодно малым ) постояннаяnε

Климент С.
источник
Я предполагаю, что вы имеете в виду . k=1nak1ε
РБ
Действительно - это исправлено.
Климент С.
Ну, без порядка зависимость от была бы необходима, я считаю (с или без выборки). А «плохой» экземпляр (пара последовательностей) были бы, например , последовательность со всеми в K «ы, равной 1 - еnak , за исключением одного (произвольного, случайного)jтакого, чтоajлибо равноε(в первой последовательности), либо0(во второй). БезΩ(n)запросов две последовательности не могут быть разделены ...1εn1jajε0Ω(n)
Клемент С.
Я предполагаю , что запрос модель позволяет выбрать , для которого вы запрашиваете в K , правильно ли это? kak
Кодлу
Да (вы можете выбрать любую точку, которую хотите «раскрыть»).
Климент С.

Ответы:

5

Вот нижние границы, которые я могу показать. Я предполагаю, что для фиксированного правая нижняя граница Ω ( log n ) , но, естественно, я могу ошибаться.ϵΩ(logn)

Я собираюсь использовать уменьшающуюся последовательность (просто для удобства). Основной механизм разбивает последовательность на блоков. В я - м блоке там будут п I элементов (т.е. Е I п я = п ).Liniini=n

Далее мы хотим, чтобы алгоритм работал с вероятностью для некоторого параметра δ > 0 .1δδ>0

Первая нижняя граница: .Ω(1ϵlog1δ)

й блок имеет п я = 2 я - 1 элементов, так что L = Л.Г. п . Мы устанавливаем значение всех элементов в i- м блоке равным ( 1 + X i ) / ( 2 n i L ) , где X i - это переменная, равная 0 или 1 . Ясно, что общая сумма этой последовательности равна α = L i = 1 1 + Xini=2i1L=lgni(1+Xi)/(2niL)Xi01 Представьте себе, что каждыйXi выбираетсяс вероятностьюβравной1и0 впротивном случае. Для оценкиαнам нужна надежная оценкаβ. В частности, мы хотим уметь различать основаниеβ=1-4ϵи, скажем,β=1.

α=i=1L1+Xi2niL=12+12L(i=1LXi).
Xiβ10αββ=14ϵβ=1

Теперь представьте выборку этих случайных величин, и пусть Z 1 , , Z m будут выборочными переменными. Настройки Y = m i = 1 ( 1 - X i ) (обратите внимание, что мы берем сумму переменных дополнения ), мы имеем μ = E [ Y ] = ( 1 - β ) m , и неравенство Чернова говорит нам что если β = 1 - 4mZ1,,ZmY=i=1m(1Xi)μ=E[Y]=(1β)m , то μ = 4 ε м , а вероятность неудачи Р [ Y 2 ε т ] = Р [ Y ( 1 - 1 / 2 ) μ ]ехр ( - μ ( 1 / 2 ) 2 / 2 ) = exp ( - ϵ м / 2 ) . Чтобы сделать это количество меньше, чемβ=14ϵμ=4ϵm

P[Y2ϵm]=P[Y(11/2)μ]exp(μ(1/2)2/2)=exp(ϵm/2).
, нам нужно m 2δ .m2ϵln1δ

Ключевое наблюдение состоит в том, что неравенство Чернова является жестким (нужно быть осторожным, потому что оно не корректно для всех параметров, но в данном случае оно корректно), поэтому вы не можете добиться большего успеха (вплоть до констант).

Вторая нижняя граница: .Ω(logn/loglogn)

ini=LiL=Θ(logn/loglogn)iαi=(1/L)/ni1

jαj1=Lαjαjj1/L12

L

p=1/21L/81/8L/8

(1p)(7/8)>7/16>1/3.

Ω(1/ϵ2)

Сариэль Хар-Пелед
источник
Ω(1/ϵ)β<1β1/ϵXiϵ
Да уж. Если вы хотите провести различие только между 1 и 1-эпсилоном, то, конечно, вы не можете улучшить нижнюю границу ... Я думал о попытке различить другие диапазоны ... s
Сариэль Хар-Пелед
4

Нижняя граница

Ω(1/ϵ)

a1,,anϵ,2ϵ,3ϵ,4ϵ,na1++an=1n1/2ϵ

Теперь построим новую последовательность , изменив один элемент из указанной последовательности путем вычитания ϵa1,,anϵa1=a1a2=a2ai=aiϵa1++an=1ϵ

a1,,ana1,,aniΩ(n)n1/2ϵΩ(1/ϵ)

Верхняя граница

O(lg(n/ϵ)[lgn+1/ϵ2])

[0,1]

[0,1]=[0,0.25ϵ/n](0.25ϵ/n,0.5ϵ/n](0.5ϵ/n,ϵ/n](ϵ/n,2ϵ/n](2ϵ/n,4ϵ/n](,1].

aiaiai[,u]i,jai,,aj[,u]O(lg(n/ϵ))

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

  • [0,0.25ϵ/n)0m×0.25ϵ/nmmn0.25ϵ

  • δO(1/δ2)2×δ=0.25ϵ

0.25ϵ0.25ϵ0.5ϵ11ϵ

DW
источник
Спасибо - это выглядит интересно (насколько я могу судить, это не тот же подход, который использовался в статье / обсуждении, связанном выше), и я более подробно рассмотрю то, что вы написали. Тем не менее, я ищу нижнюю границу, а не верхнюю границу - то есть, сколько запросов необходимо .
Клемент С.
(Поскольку время истекло, я тем не менее присуждаю «награду» за ответ - хотя я все еще ищу ссылку на нижнюю границу, если она где-то там есть).
Клемент С.
2
@ClementC., Я добавил нижнюю границу для вашего запроса.
DW
nε