Я хотел бы знать ( в связи с этим другой вопрос ) , если нижние оценки были известны следующие задачи тестирования: один получает доступ запроса к последовательности неотрицательных чисел п ≥ ⋯ ≥ 1 и & epsi ; ∈ ( 0 , 1 ) с обещанием, что либо k n k = 1 a k = 1, либо ∑ n k = 1 a k ≤ 1 - ε .
Сколько запросы (Lookups) достаточны и необходимы для (адаптивного) рандомизированного алгоритма различения между этими двумя случаями, с вероятностью по крайней мере ?
Я нашел предыдущий пост, который дает логарифмическую (по ) верхнюю границу для связанной задачи аппроксимации суммы и приблизительно совпадающую нижнюю границу этой проблемы для детерминированных алгоритмов; но не смог найти результат для конкретной проблемы, которую я рассматриваю (в частности, рандомизированные алгоритмы).
Изменить: После ответа ниже, я думаю, я должен был быть более ясным: в приведенном выше (и особенно в асимптотике для нижней границы), является «основной» величиной, рассматриваемой как уходящая в бесконечность, в то время как ε является (сколь угодно малым ) постоянная
Ответы:
Вот нижние границы, которые я могу показать. Я предполагаю, что для фиксированного правая нижняя граница Ω ( log n ) , но, естественно, я могу ошибаться.ϵ Ω(logn)
Я собираюсь использовать уменьшающуюся последовательность (просто для удобства). Основной механизм разбивает последовательность на блоков. В я - м блоке там будут п I элементов (т.е. Е I п я = п ).L i ni ∑ini=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 + Xi ni=2i−1 L=lgn i (1+Xi)/(2niL) Xi 0 1
Представьте себе, что каждыйXi выбираетсяс вероятностьюβравной1и0 впротивном случае. Для оценкиαнам нужна надежная оценкаβ. В частности, мы хотим уметь различать основаниеβ=1-4ϵи, скажем,β=1.
Теперь представьте выборку этих случайных величин, и пусть Z 1 , … , Z m будут выборочными переменными. Настройки Y = ∑ m i = 1 ( 1 - X i ) (обратите внимание, что мы берем сумму переменных дополнения ), мы имеем μ = E [ Y ] = ( 1 - β ) m , и неравенство Чернова говорит нам что если β = 1 - 4m Z1,…,Zm Y=∑mi=1(1−Xi) μ=E[Y]=(1−β)m , то μ = 4 ε м , а вероятность неудачи
Р [ Y ≤ 2 ε т ] = Р [ Y ≤ ( 1 - 1 / 2 ) μ ] ≤ ехр ( - μ ( 1 / 2 ) 2 / 2 ) = exp ( - ϵ м / 2 ) .
Чтобы сделать это количество меньше, чемβ=1−4ϵ μ=4ϵm
Ключевое наблюдение состоит в том, что неравенство Чернова является жестким (нужно быть осторожным, потому что оно не корректно для всех параметров, но в данном случае оно корректно), поэтому вы не можете добиться большего успеха (вплоть до констант).
Вторая нижняя граница: .Ω(logn/loglogn)
источник
Нижняя граница
Теперь построим новую последовательность , изменив один элемент из указанной последовательности путем вычитания ϵa′1,…,a′n ϵ a′1=a1 a′2=a2 a′i=ai−ϵ a′1+⋯+a′n=1−ϵ
Верхняя граница
Теперь мы оценим сумму значений в каждом диапазоне. Первый диапазон будет обрабатываться отдельно от всех остальных:
источник