Limite inferior na estimativa

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 k ≤ 1 - $a_n \geq \dots\geq a_1$$\varepsilon \in (0,1)$$\sum_{k=1}^n a_k = 1$$\sum_{k=1}^n a_k \leq 1-\varepsilon$

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$$\varepsilon$

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.$\epsilon$$\Omega( \log n)$

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 ).$L$$i$$n_i$$\sum_i n_i = n$

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

Primeiro limite inferior: .$\displaystyle \Omega\left( \frac{1}{\epsilon} \log \frac{1}{\delta} \right)$

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 + $i$$n_i = 2^{i-1}$$L = \lg n$$i$$(1+X_i)/(2n_iL)$$X_i$$0$$1$ 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.

$$\alpha = \sum_{i=1}^L \frac{1+X_i}{2n_i L} = \frac{1}{2} + \frac{1}{2L}\left(\sum_{i=1}^L X_i \right).$$ $X_i$$\beta$$1$$0$$\alpha$$\beta$$\beta = 1-4\epsilon$$\beta=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 - $m$$Z_1, \ldots, Z_m$$Y = \sum_{i=1}^m (1-X_i)$$\mu = E[Y] = (1-\beta) 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$\beta =1-4\epsilon$$\mu = 4\epsilon m$

$$P\left[ Y \leq 2\epsilon m \right] = P\left[ Y \leq (1-1/2) \mu \right] \leq \exp \left( -\mu (1/2)^2 / 2 \right) = \exp \left( -\epsilon m / 2 \right).$$ , precisamos de m ≥ $\delta$ .$\displaystyle m \geq \frac{2}{\epsilon} \ln \frac{1}{\delta}$

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: .$\Omega( \log n / \log \log n)$

$i$$n_i = L^i$$L = \Theta( \log n / \log \log n)$$i$$\alpha_i = \Bigl(1/L\Bigr)/n_i$$1$

$j$$\alpha_{j-1} = L \alpha_j$$\alpha_j$$j$$1/L$$1$$2$

$L$

$p=1/2$$1$$L/8$$1/8$$L/8$

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

---

$\Omega(1/\epsilon^2)$

Limite inferior

$\Omega(1/\sqrt{\epsilon})$

$a_1,\dots,a_n$$\epsilon,2\epsilon,3\epsilon,4\epsilon,\dots$$n$$a_1+\dots+a_n = 1$$n \approx 1/\sqrt{2\epsilon}$

$a'_1,\dots,a'_n$$\epsilon$$a'_1=a_1$$a'_2=a_2$$a'_i = a_i - \epsilon$$a'_1 + \dots + a'_n = 1-\epsilon$

$a_1,\dots,a_n$$a'_1,\dots,a'_n$$i$$\Omega(n)$$n \approx 1/\sqrt{2\epsilon}$$\Omega(1/\sqrt{\epsilon})$

Limite superior

$O(\lg(n/\epsilon) [\lg n + 1 / \epsilon^2])$

$[0,1]$

$$[0,1] = [0,0.25\epsilon/n] \cup (0.25\epsilon/n,0.5\epsilon/n] \cup (0.5\epsilon/n,\epsilon/n] \cup (\epsilon/n,2\epsilon/n] \cup (2\epsilon/n,4\epsilon/n] \cup \dots \cup (\ldots,1].$$

$a_i$$a_i$$a_i$$[\ell,u]$$i,j$$a_i,\dots,a_j \in [\ell,u]$$O(\lg(n/\epsilon))$

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

• $[0,0.25\epsilon/n)$$0$$m \times 0.25\epsilon/n$$m$$m \le n$$0.25 \epsilon$

• $\delta$$O(1/\delta^2)$$2 \times$$\delta = 0.25 \epsilon$

$0.25 \epsilon$$0.25 \epsilon$$\le 0.5 \epsilon$$1$$1-\epsilon$