Limite inferior na estimativa

11

Eu gostaria de saber (relacionado a essa outra pergunta ) se os limites inferiores eram conhecidos para o seguinte problema de teste: um deles recebe acesso de consulta a uma sequência de números não negativos e , com a promessa de que ou . ε ( 0 , 1 ) Σ n k = 1 uma k = 1 Σ n k = 1 uma k1 - εana1ε(0,1)k=1nak=1k=1nak1ε

Quantas consultas (pesquisas) são suficientes e necessárias para que um algoritmo aleatório (adaptativo) faça a distinção entre os dois casos, com probabilidade de pelo menos ?2/3

Eu encontrei um post anterior que fornece um limite logarítmico (em ) para o problema relacionado de aproximar a soma, e um limite inferior que corresponde aproximadamente a esse problema para algoritmos determinísticos; mas não foi possível encontrar um resultado para o problema específico que estou considerando (em particular, algoritmos aleatórios).n


Edit: Seguindo a resposta abaixo, acho que deveria ter sido mais claro: acima (e particularmente nos assintóticos para o limite inferior), é a quantidade "principal" vista como indo para o infinito, enquanto é um (arbitrariamente pequeno) constante.εnε

Clemente C.
fonte
Eu acho que você quer dizer . k=1nak1ε
RB
De fato - consertou.
Clement C.
Bem, sem a ordem em que uma dependência de seria necessária, eu acho (com ou sem amostragem). Uma instância "ruim" (par de seqüências) seria, por exemplo, uma sequência com todos os iguais a , exceto por uma (arbitrária, aleatória) modo que é igual a (na primeira sequência) e (na segunda). Sem consultas , as duas seqüências não podem ser diferenciadas ...um k 1 - εnak jajε0Ω(n)1εn1jajε0Ω(n)
Clement C.
Presumo que o modelo de consulta permita escolher o para o qual você consulta , está certo? a kkak
Kodlu
Sim (você escolhe o ponto que deseja "divulgar").
Clement C.

Respostas:

5

Aqui estão os limites inferiores que posso mostrar. Eu conjectura de que para um fixo , o direito limite inferior é Ω ( log n ) , mas, naturalmente, eu poderia estar errado.ϵΩ(logn)

Vou usar uma sequência decrescente (apenas por conveniência). O mecanismo básico está dividindo a sequência em blocos No i th bloco não vão ser n i elementos (ou seja, Σ i n i = n ).Liniini=n

A seguir, queremos que o algoritmo seja bem-sucedido com probabilidade , para alguns parâmetros δ > 0 .1δδ>0

Primeiro limite inferior: .Ω(1ϵlog1δ)

O th bloco tem n i = 2 i - 1 os elementos, de modo que L = LG n . Definimos o valor de todos os elementos no i- ésimo bloco para ( 1 + X i ) / ( 2 n i L ) , onde X i é uma variável que é 0 ou 1 . Claramente, a soma total desta sequência é α = L i = 1 1 + Xini=2i1L=lgni(1+Xi)/(2niL)Xi01 Imagine escolher cadaXicom probabilidadeβde1e0caso contrário. Para estimarα, precisamos de uma estimativa confiável deβ. Particularmente, queremos ser capazes de distinguir a baseβ=1-4ϵe, digamos,β=1.

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

Agora, imagine amostrar dessas variáveis ​​aleatórias e deixar Z 1 , ... , Z m serem as variáveis ​​amostradas. Definições Y = Σ m i = 1 ( 1 - X i ) (nota, que estão a tomar a soma das complemento variáveis), temos μ = E [ Y ] = ( 1 - β ) m , e Chernoff desigualdade nos diz que se β = 1 - 4mZ1,,ZmY=i=1m(1Xi)μ=E[Y]=(1β)m , então μ = 4 ε m , e a probabilidade de falha é P [ Y 2 ε m ] = P [ Y ( 1 - 1 / 2 ) μ ]exp ( - μ ( 1 / 2 ) 2 / 2 ) = exp ( - ϵ m / 2 ) . Para tornar essa quantidade menor queβ=14ϵμ=4ϵm

P[Y2ϵm]=P[Y(11/2)μ]exp(μ(1/2)2/2)=exp(ϵm/2).
, precisamos de m 2δ .m2ϵln1δ

A principal observação é que a desigualdade de Chernoff é pequena (é preciso ter cuidado, porque não é correto para todos os parâmetros, mas é correto neste caso), para que você não possa fazer melhor que isso (até constantes).

Segundo limite inferior: .Ω(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)

Sariel Har-Peled
fonte
Ω(1/ϵ)β<1β1/ϵXiϵ
Sim. Se você rali quer distinguir apenas entre 1 e 1-epsilon então é claro que você não pode melhorar o limite inferior ... Eu estava pensando em tentar distinguir outras gamas ... s
Sariel Har-Peled
4

Limite inferior

Ω(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/ϵ)

Limite superior

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/ϵ))

Agora, estimaremos a soma dos valores em cada intervalo. O primeiro intervalo será tratado separadamente de todo o resto:

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

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

0.25ϵ0.25ϵ0.5ϵ11ϵ

DW
fonte
Obrigado - isso parece interessante (tanto quanto posso dizer, não é a mesma abordagem usada no artigo / discussão acima), e examinarei mais profundamente o que você escreveu. No entanto, estou procurando um limite inferior em vez de um limite superior - ou seja, quantas consultas são necessárias .
Clement C.
(Com o tempo terminando, estou concedendo a "recompensa" à resposta, no entanto - embora ainda esteja procurando uma referência para um limite inferior, se houver algum em algum lugar lá em cima.)
Clement C.
2
@ClementC., Adicionei um limite inferior, de acordo com sua solicitação.
DW
nε