Límite inferior al estimar

Me gustaría saber (en relación con esta otra pregunta ) si se conocen límites inferiores para el siguiente problema de prueba: a uno se le da acceso de consulta a una secuencia de números no negativos y ε ∈ ( 0 , 1 ) , con la promesa de que ∑ n k = 1 a k = 1 o ∑ n k = 1 a 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$

¿Cuántas consultas (Búsquedas de) son suficientes y necesarias para un (adaptativa) algoritmo aleatorio para distinguir entre los dos casos, con una probabilidad de al menos ?$2/3$

He encontrado una publicación anterior que proporciona un límite superior logarítmico (en ) para el problema relacionado de aproximación de la suma, y ​​un límite inferior más o menos coincidente en ese problema para algoritmos deterministas; pero no pude encontrar un resultado para el problema específico que estoy considerando (en particular, algoritmos aleatorios).$n$

---

Editar: Siguiendo la respuesta a continuación, supongo que debería haber sido más claro: en lo anterior (y particularmente en las asíntotas para el límite inferior), es la cantidad "principal" que se ve que va al infinito, mientras que ε es una (arbitrariamente pequeña ) constante.$n$$\varepsilon$

Aquí están los límites inferiores que puedo mostrar. Me conjetura de que para un fijo , el derecho límite inferior es Ω ( log n ) , pero, naturalmente, yo podría estar equivocado.$\epsilon$$\Omega( \log n)$

Voy a usar una secuencia decreciente (solo por conveniencia). El mecanismo básico es romper la secuencia en bloques En el bloque i ésimo habrá n elementos i (es decir, ∑ i n i = n ).$L$$i$$n_i$$\sum_i n_i = n$

A continuación, queremos que el algoritmo tenga éxito con probabilidad , para algún parámetro δ > 0 .$\geq 1-\delta$$\delta >0$

Primer límite inferior: .$\displaystyle \Omega\left( \frac{1}{\epsilon} \log \frac{1}{\delta} \right)$

El ésimo bloque tiene n i = 2 i - 1 elementos, entonces L = lg n . Establecemos el valor de todos los elementos en el i ésimo bloque para que sea ( 1 + X i ) / ( 2 n i L ) , donde X i es una variable que es 0 o 1 . Claramente, la suma total de esta secuencia es α = L ∑ i = 1 1 + $i$$n_i = 2^{i-1}$$L = \lg n$$i$$(1+X_i)/(2n_iL)$$X_i$$0$$1$ Imagínese elegir cadaXicon probabilidadβde ser1y0 de locontrario. Para estimarα, necesitamos una estimación confiable deβ. En particular, queremos poder distinguir la baseβ=1-4ϵy, 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$

Ahora, imagine muestrear de estas variables aleatorias y deje que Z 1 , ... , Z m sean las variables muestreadas. Configuración Y = ∑ m i = 1 ( 1 - X i ) (tenga en cuenta que estamos tomando la suma de las variables del complemento ), tenemos μ = E [ Y ] = ( 1 - β ) m , y la desigualdad de Chernoff nos dice que si β = 1 - $m$$Z_1, \ldots, Z_m$$Y = \sum_{i=1}^m (1-X_i)$$\mu = E[Y] = (1-\beta) m$ , entonces μ = 4 ε m , y la probabilidad de fallo es P [ Y ≤ 2 ε m ] = P [ Y ≤ ( 1 - 1 / 2 ) μ ] ≤ exp ( - μ ( 1 / 2 ) 2 / 2 ) = exp ( - ϵ m / 2 ) . Para hacer esta cantidad más pequeña 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).$$ , necesitamos m ≥ $\delta$ .$\displaystyle m \geq \frac{2}{\epsilon} \ln \frac{1}{\delta}$

La observación clave es que la desigualdad de Chernoff es estrecha (hay que tener cuidado, porque no es correcta para todos los parámetros, pero es correcta en este caso), por lo que no se puede hacer mejor que eso (hasta constantes).

Segundo límite 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)$

Límite 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})$

Límite 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))$

Ahora, calcularemos la suma de valores en cada rango. El primer rango se manejará por separado del 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$