Оценка среднего за полиномиальное время

Пусть . Мы хотим оценить среднее значение , то есть: .f E [ f ( n ) ] = 2 - n ∑ x ∈ { 0 , 1 } n f ( x $f \colon \lbrace 0,1 \rbrace ^ n \to (2^{-n},1]$$f$$\mathbb{E}[f(n)]=2^{-n}\sum_{x\in \lbrace 0,1 \rbrace ^ n}f(x)$

NOTE: In the OP, the range of f was [0,1]. I changed this a bit for technical reasons. (This should simplify the problem; if not, forget it!)

Пусть - (рандомизированный) алгоритм оценки. Предположим, что имеет черный ящик доступа к . Обозначим это через .E F E $E$$E$$f$$E^f$

Есть два условия:

1) Время выполнения оценщика: существует один многочлен такой, что для всех и всех время выполнения ограничено .n f E f ( 1 n ) p ( n $p(\cdot)$$n$$f$$E^f(1^n)$$\frac{p(n)}{\mathbb{E}[f(n)]}$

2) Точность оценки с уверенностью :$\delta$ существует один многочлен , такой что для всех и всех мы имеем с вероятностью не менее .$q(\cdot)$$n$$f$${1 \over {q(n)}} < \frac{E^f(1^n)}{\mathbb{E}[f(n)]} < q(n)$$\delta$

NOTE: The confidence δ was not in the OP. The parameter δ is in (0,1), and may depend on n. For instance, it may be 1-1/2^n.

Существуют ли такие оценки?

Фон и мотивация

Я не упомянул свою мотивацию в начале, так как она требует большого количества базовых знаний. В любом случае, для энтузиастов, я кратко опишу это: необходимость в таких оценщиках возникает в контексте «Доказательств способностей», как определено в следующей статье:

Михир Белларе, Одед Голдрайх. Доказательство вычислительной способности , 1992. Неопубликованная рукопись.

В частности, в нижней части страницы 5 авторы неявно предположили существование таких оценщиков (здесь нет упоминания о точности, и время выполнения точно не определено; все же контекст четко определяет все).

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

РЕДАКТИРОВАТЬ (согласно запросу Цуёси): На самом деле, определение «Доказательства вычислительной способности» требует существования «экстрактора знаний», чье (ожидаемое) время выполнения равно . Поскольку мы не знаем , мы хотим оценить его; все же это не должно значительно изменить время выполнения: оно должно изменить его до полиномиального множителя. Условие точности пытается охватить такое требование. E[f(n)$p(n) \over E[f(n)]$$E[f(n)]$

РЕДАКТИРОВАТЬ: Это решает версию проблемы, где f выводит только 0 или 1. Но я думаю, что решение может быть адаптировано, чтобы оно работало для более общего случая.

Может быть, я неправильно понял вопрос, но это не выглядит слишком сложно.

Вместо оценки среднего, давайте подумаем об оценке числа 1 и назовем это число k. Пусть . Таким образом, среднее значение к / ш. Вы хотите оценить это в полиномиальном мультипликативном множителе за время O (N polylog (N) / k).$N = 2^n$

Я думаю, что это можно сделать с точностью до любого постоянного мультипликативного фактора. Например, предположим, что вы хотите оценить это с точностью до коэффициента 2. Таким образом, выходной сигнал алгоритма будет между k / 2 и 2k.$k'$

Я нарисую алгоритм, который должен иметь соответствующее время выполнения. Сначала проверьте, находится ли k между N / 2 и N. Это легко, просто выберите несколько случайных значений, и если вы получите больше половины 1 с, то это в этом интервале. Итак, у вас есть 2-приближение. Если нет, то проверьте, находится ли он между N / 4 и N / 2. И так далее. Каждый раз, когда вы делаете интервал меньшим, более затратно оценивать, находится ли k в этом диапазоне. Но стоимость обратно пропорциональна тому, насколько мал интервал.

Например, если вы проверяете, находится ли k между и 2 N / 2 q , то вам нужно выполнить около O ( 2 q ) запросов. В любом случае, после повторения этой процедуры достаточно времени, вы должны получить интервал, в котором лежит k. Скажем, k лежит между N / 2 q и 2 N / 2 q . Тогда k примерно N / 2 q . Итак, 2 $N/2^q$$2N/2^q$$O(2^q)$$N/2^q$$2N/2^q$$N/2^q$$2^q$о к / ш. Таким образом, на этом этапе мы бы потратили O (k / N) запросов. Но для перехода к этому шагу потребовалось q других шагов, но это всего лишь дополнительный множитель (N). Таким образом, общее время работы O (N polylog (N) / k) для 2-приближения.

(Фактически нужно было бы усиливать ошибки, чтобы получить приличную точность на каждом шаге. Но это только дополнительный фактор полилога.)

Причина, по которой мне нравится думать об этом в этом многоступенчатом процессе, заключается в том, что он выделяет этот процесс как предположение и проверяет предварительное условие. Если кто-то сказал вам, что находится между N / 2 q и 2 n / 2 q , то вы можете оценить его с еще большей точностью, зная этот факт, в течение обещанного периода времени. Таким образом, нам нужно исключить шаг, чтобы дать предположение для k . Это делается с помощью бинарного поиска по всем возможным интервалам этого типа.$k$$N/2^q$$2n/2^q$$k$

Чтобы это работало для случая небулевых выходных данных, вместо подсчета числа 1, просто сложите полученные значения. Я постараюсь найти ссылку, чтобы показать, что это работает строго.

Пусть обозначают значения f, примененные к бесконечной последовательности случайных выборок (с заменой) из { 0 , 1 } n . Пусть K будет наименьшее положительное целое число , такое , что Σ K я = 1 е я ≥ М при некотором значении М , может быть , М = р о л у л о г ( п ) . Я бы догадался, что оценщик M $f_1,f_2,\ldots$$f$$\{0,1\}^n$$k$$\sum_{i=1}^k f_i \ge M$$M$$M=polylog(n)$$M / k$ должен выполнить то, что вы хотите.

Для анализа вы не можете применить границы Черноффа непосредственно к случайной переменной но есть прием, позволяющий вам использовать Черноффа в любом случае. Обозначим через μ неизвестное ожидание E ( f ) . Найти константы k l o w и k h i g h (функции от µ ) так, чтобы с вероятностью не менее 1 - δ мы имели ∑ k l o w i = 1 f i < M и ∑ k $k$$\mu$$E(f)$$k_{low}$$k_{high}$$\mu$$1 - \delta$$\sum_{i=1}^{k_{low}} f_i < M$. Эти суммыеяс может быть ограниченапомощью Чернова. Отсюда следует, чтоklow<k<khighс вероятностью не менее1-δи, следовательно, оценкаM/kхорошо сконцентрирована.$\sum_{i=1}^{k_{high}} f_i > M$$f_i$$k_{low} < k < k_{high}$$1-\delta$$M/k$