Seja uma função. Queremos estimar a média de ; ou seja: .f E [ f ( n ) ] = 2 - n ∑ x ∈ { 0 , 1 } 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!)
Seja o algoritmo estimador (randomizado). Suponha que tenha acesso à caixa preta para . Denotamos isso por .E f E f
Existem duas condições:
1) tempo de funcionamento da Estimador: Existe um único polinómio de tal modo que para todos os e todos , o tempo de execução do é delimitada por .n f E f ( 1 n ) p ( n )
2) Precisão do estimador com confiança : q ( ⋅ ) n f 1 existe um único polinômio , tal que para todo e todo , temos com probabilidade de pelo menos .δ
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.
Existem tais estimadores?
Antecedentes e Motivação
Eu não mencionei minha motivação no início, pois requer muito conhecimento prévio. De qualquer forma, para os entusiastas, descrevo-o brevemente: A necessidade de tais estimadores surge no contexto de "Provas de capacidade", conforme definido no seguinte artigo:
Mihir Bellare, Oded Goldreich. Proving Computational Ability , 1992. Manuscrito não publicado.
Especificamente, na parte inferior da página 5, os autores assumiram implicitamente a existência de tais estimadores (não há menção à precisão e o tempo de execução não é definido com precisão; ainda assim, o contexto define tudo claramente).
Minha primeira tentativa foi ler " Uma amostra de amostradores - uma perspectiva computacional sobre amostragem ". Pertence a um problema muito semelhante, mas a probabilidade de erro definida é aditiva, enquanto a nossa é multiplicativa. (Eu não li completamente o artigo, talvez ele mencione o que eu preciso em algum lugar.)
EDIT (conforme solicitação de Tsuyoshi): De fato, a definição de "Provas de Habilidade Computacional" requer a existência de um "extrator de conhecimento" cujo tempo de execução (esperado) seja . Como não conhecemos , queremos estimar isso; no entanto, isso não deve alterar o tempo de execução consideravelmente: deve ser alterado para um fator polinomial. A condição de precisão tenta capturar esse requisito. E[f(n)]
fonte
Respostas:
EDIT: Isso resolve a versão do problema em que f apenas gera 0 ou 1. Mas acho que a solução pode ser adaptada para fazê-la funcionar no caso mais geral.
Talvez eu tenha entendido mal a pergunta, mas isso não parece muito difícil.
Em vez de estimar, a média, vamos pensar em estimar o número de 1s e chamar esse número k. Seja . Então a média é k / N. Você deseja estimar isso dentro de um fator multiplicativo polinomial no tempo O (N polilog (N) / k).N=2n
Eu acho que isso pode ser feito dentro de qualquer fator multiplicativo constante também. Por exemplo, digamos que você queira estimar isso dentro de um fator de 2. Portanto, a saída do algoritmo estará entre k / 2 e 2k.k′
Esboçarei um algoritmo, que deve ter o tempo de execução apropriado. Primeiro verifique se k está entre N / 2 e N. Isso é fácil, basta amostrar alguns valores aleatórios e se você tiver mais de meio segundo, então está nesse intervalo. Então você tem uma aproximação 2. Caso contrário, verifique se está entre N / 4 e N / 2. E assim por diante. Toda vez que você diminui o intervalo, é mais caro estimar se k está nesse intervalo. Mas o custo é inversamente proporcional ao tamanho do intervalo.
Por exemplo, se você estiver verificando se k está entre e , precisará fazer consultas . De qualquer forma, depois de repetir esse procedimento várias vezes, você deve obter o intervalo em que k se encontra. Digamos que k esteja entre e . Então k é aproximadamente . Então é sobre k / N. Portanto, nesta etapa, gastaríamos consultas O (k / N). Mas chegar a essa etapa exigiu q outras etapas, mas esse é apenas um fator extra de polilog (N). Portanto, o tempo total de execução é O (N polylog (N) / k), para uma aproximação de 2. 2 N / 2 q O ( 2 q ) N / 2 q 2 N / 2 q N / 2 q 2 qN/2q 2N/2q O(2q) N/2q 2N/2q N/2q 2q
(Na verdade, seria necessário amplificar o erro para obter precisão decente em cada etapa. Mas isso é apenas um fator extra de polilog.)
A razão pela qual gosto de pensar nesse processo de várias etapas é que ele destaca o processo como um palpite e verifica a precedência. Se alguém lhe que está entre e , você poderá estimar com precisão ainda melhor sabendo esse fato, no prazo prometido. Portanto, precisamos eliminar a etapa de adivinhar o . Isso é feito através da pesquisa binária em todos os intervalos possíveis desse tipo.N / 2 q 2 n / 2 q kk N/2q 2n/2q k
Para fazer isso funcionar no caso de saídas não booleanas, em vez de contar o número de 1s, basta somar os valores vistos. Vou tentar encontrar uma referência para mostrar que isso funciona rigorosamente.
fonte
Deixe denotar os valores de aplicados a uma sequência infinita de amostras aleatórias (com substituição) de . Seja o número inteiro menos positivo que para algum valor , talvez . Eu acho que o estimador deve realizar o que você deseja.f1,f2,… f {0,1}n k ∑ki=1fi≥M M M=polylog(n) M/k
Para a análise, você não pode aplicar os limites de Chernoff diretamente à variável aleatória mas há um truque para permitir que você use Chernoff de qualquer maneira. Vamos denotar a expectativa desconhecido . Encontre as constantes e (funções de ) para que, com probabilidade pelo menos , tenhamos e . Essas somas de s podem ser limitadas usando Chernoff. Segue-se que com probabilidade de pelo menos e, portanto, o estimadorμ E ( f ) k l O w K H i g h μ 1 - ô Σ k l o w i = 1 f i < H Σ k h i g h i = 1 f i > H f i k L O w < k < k h i g h 1 - δk μ E(f) klow khigh μ 1−δ ∑klowi=1fi<M ∑khighi=1fi>M fi klow<k<khigh 1−δ M/k está bem concentrado.
fonte