Pruebas que exponen una estructura más profunda.

35

La prueba estándar del límite de Chernoff (del libro de texto de Algoritmos Aleatorios ) utiliza la desigualdad de Markov y las funciones generadoras de momentos, con un poco de expansión de Taylor. Nada demasiado difícil, pero algo mecánico.

Pero hay otras pruebas vinculadas a Chernoff que exponen la estructura más profunda que impulsa el resultado. Por ejemplo, hay una versión teórica de la información que se aplica a través del método de tipos, ejemplificado en este artículo de Impagliazzo y Kabanets , así como en esta breve publicación de Sanjoy Dasgupta . Estas últimas pruebas son más "intuitivas" ya que proporcionan una generalización del resultado estándar, además de explicar de dónde provienen los términos divertidos en el exponente (es una divergencia KL).

¿Cuáles son buenos ejemplos de tales cosas? Para ser más concreto, aquí están las reglas:

La declaración debe ser razonablemente conocida (el tipo de cosas que se enseñarían en algún tipo de clase de posgrado)

Debe haber una prueba "estándar" disponible en los libros de texto o material de referencia estándar que se enseñe "comúnmente"

Debería haber una prueba alternativa que no sea tan conocida, que NO se enseñe comúnmente y que pruebe una declaración más general o vincule la declaración a una estructura matemática más profunda.

Comenzaré con dos ejemplos.

El chernoff atado
- prueba de "libro de texto": desigualdad de Markov, funciones generadoras de momentos, expansión de Taylor (MR)
- Prueba poco común y perspicaz: método de tipos, exponente de cola que involucra divergencia KL
El lema de Schwartz-Zippel
- Prueba de "libro de texto": caso base que implica un polinomio univariado. Inducción sobre el número de variables.
- Prueba "poco común": argumento geométrico a través de Dana Moshkovitz (y Per Vognsen )

Un ejemplo por respuesta por favor.

ps No estoy necesariamente insinuando que se debe enseñar la prueba poco común : una prueba directa a menudo es más fácil para los estudiantes. Pero en el sentido de que "las pruebas nos ayudan a entender", estas pruebas alternativas son muy útiles.

big-list proofs Suresh Venkat
fuente

23

No estoy seguro de que esto sea exactamente lo que está buscando, ya que he visto la prueba "poco común" en los libros de texto, pero: el tiempo O (n log n) está limitado para la clasificación rápida.

Prueba de "libro de texto": establezca una relación de recurrencia aleatoria, pruebe por inducción que tiene la solución deseada.
Prueba "poco común": encuentre una fórmula simple para la probabilidad de que se comparen dos elementos (es solo 2 / (d + 1) donde d es la diferencia entre sus rangos en el orden ordenado), y use linealidad de expectativa y series armónicas para calcular el número esperado de pares que se comparan.

La prueba del libro de texto requiere una visión menos creativa, pero la prueba poco común introduce una técnica que es muy útil en otros análisis de algoritmos, por ejemplo, para algoritmos incrementales aleatorios en geometría computacional.

David Eppstein
fuente

3

Creo que esto funciona. Es un buen ejemplo. tienes razón en que la prueba 'poco común' también está en los libros de texto, pero aún así no es tan común.

Suresh Venkat

1

He estado enseñando a estudiantes universitarios esa prueba "poco común" durante más de una década.

Jeffε

No sé lo que otros piensan de eso; pero Jon Bentley ha realizado un análisis de tiempo de ejecución muy elegante para el tiempo de ejecución esperado de clasificación rápida en el texto Beautiful Code. También puede acceder a su video sobre el mismo tema <a href=" youtube.com/watch?v=aMnn0Jq0J-E"> aquí </ a >. Estoy bastante seguro de que este es "el análisis del libro" del tiempo de ejecución esperado de quicksort

Akash Kumar

19

uno de la complejidad, la prueba de que BPP está en . La prueba del libro de texto se debe a Lautemann, simplemente escriba la expresión y demuestre que funciona con un argumento probabilístico simple. La prueba poco común: adivina una función difícil ( para adivinar, para verificar la dureza) y conéctala al generador Nisan-Wigderson. $\Sigma_2^p$ $\exists\forall$ $\exists$ $\forall$

Lance Fortnow
fuente

Además de eso, la prueba de Lautemann simplifica enormemente la prueba de Sipser (1983), que Sipser atribuye a Gacs.

MS Dousti

1

¿Hay alguna referencia para la prueba "poco común", o es folklore?

MS Dousti

2

La prueba está en el documento de Nisan-Wigderson.

Lance Fortnow

2

Es una "prueba poco común", pero ¿cuál es el "nuevo entendimiento" de esta prueba? Creo que la prueba de Lautemann es más esclarecedora. ¿Me estoy perdiendo de algo?

V Vinay el

13

Todos sabemos que para Bernoulli debería comportarse como un gaussiano con desviación estándar , ¿verdad? ¡Entonces, demostrémoslo relacionándonos directamente con los gaussianos! Tomando un número entero, $\sum_i a_iX_i$ $\pm 1$ $X_i$ $\sigma = \|a\|_2$ $t \ge 2$

\begin{array}{rcl} E [{(\sum_{i} a_{i} X_{i})}^{t}] & = & \sum_{i_{1}, \dots, i_{t}} (\prod_{j = 1}^{t} a_{i_{j}}) E [\prod_{j = 1}^{t} X_{i_{j}}] \\ \leq & \sum_{i_{1}, \dots, i_{t}} (\prod_{j = 1}^{t} | a_{i_{j}} |) E [\prod_{j = 1}^{t} X_{i_{j}}] \\ = & \sum_{\begin{matrix} i_{1} < \dots < i_{m} \\ r_{1}, \dots, r_{m} \\ \sum_{j} r_{j} = t \\ \forall j r_{j} > 0 \end{matrix}} (\binom{t}{r_{1}, \dots, r_{m}}) (\prod_{j = 1}^{m} | a_{i_{j}} |^{r_{j}}) (\prod_{j = 1}^{m} E [X_{i_{j}}^{r_{j}}]) \end{array}

$\begin{eqnarray*} \mathbf{E}\left[\left(\sum_i a_iX_i\right)^t\right] &=& \sum_{i_1,\ldots,i_t} \left(\prod_{j=1}^t a_{i_j}\right) \mathbf{E}\left[\prod_{j=1}^t X_{i_j}\right]\\ &\le& \sum_{i_1,\ldots,i_t} \left(\prod_{j=1}^t |a_{i_j}|\right) \mathbf{E}\left[\prod_{j=1}^t X_{i_j}\right]\\ &=& \sum_{\substack{i_1<\ldots< i_m\\ r_1,\ldots,r_m\\ \sum_j r_j = t\\ \forall j\ r_j > 0}} \binom{t}{r_1,\ldots,r_m}\left(\prod_{j=1}^m |a_{i_j}|^{r_j}\right)\left(\prod_{j=1}^m \mathbf{E}[X_{i_j}^{r_j}]\right) \end{eqnarray*}$

Ahora, veamos la suma anterior a la derecha. En cualquier sumando, algunos son impares, lo que hace que la expectativa sea , o todos son pares, por lo que es . Imagina reemplazar todos los con Gaussian . Entonces estaríamos en un escenario similar: impar daría , y todos los pares harían al producto al menos . Entonces, el caso gaussiano, término por término, domina el caso de Bernoulli. Así, $r_j$ $0$ $1$ $X_i$ $G_i$ $r_j$ $0$ $r_j$ $1$

E [{(\sum_{i} a_{i} X_{i})}^{t}] \leq E [{(\sum_{i} | a_{i} | G_{i})}^{t}]

$\mathbf{E}\left[\left(\sum_i a_iX_i\right)^t\right] \le \mathbf{E}\left[\left(\sum_i |a_i|G_i\right)^t\right]$

Pero, por -estabilidad del gaussiano, es en sí un gaussiano con desviación estándar , ¡así que conocemos sus momentos! Por lo tanto, nuestro momento está limitado por (Aproximadamente ); Esto se conoce como la desigualdad de Khintchine. Luego, $2$ $\sum_i |a_i| G_i$ $\|a\|_2$ $t$ $\|a\|_2^t \cdot t! / (2^{t/2} \cdot (t/2)!)$ $\|a\|_2^tt^{t/2}$

P r [| \sum_{i} a_{i} X_{i} | > λ] < 2^{O (t)} \cdot λ^{- t} \cdot ‖ a ‖_{2}^{t} t^{t / 2}

$\mathbf{Pr}\left[\left|\sum_i a_iX_i\right| > \lambda\right] < 2^{O(t)}\cdot \lambda^{-t}\cdot \|a\|_2^t t^{t/2}$ Establezca para una constante suficientemente grande y obtienes la cola gaussiana . Escuché por primera vez esta prueba de la desigualdad de Khintchine cuando chateé con Daniel Kane, pero probablemente haya una referencia más antigua. Observe que la prueba también deja en claro qué nivel de independencia entre los necesita para obtener varios límites de cola.

t = λ^{2} / (C \cdot ‖ a ‖_{2}^{2})

$t = \lambda^2 / (C\cdot \|a\|_2^2)$

C

$C$

e x p (- Ω (λ^{2} / ‖ a ‖_{2}^{2}))

$\mathrm{exp}(-\Omega(\lambda^2 / \|a\|_2^2))$

X_{i}

$X_i$

Jelani Nelson
fuente

6

Minc conjeturó y Brégman demostró que si es una matriz 0-1 con 1 en la fila , entonces el permanente de es como máximo Hay una pequeña prueba en el libro de texto de Alon y Spencer, El Método Probabilístico , pero podría decirse que la prueba del "libro" es la prueba de Jaikumar Radhakrishnan usando entropía ( J. Combin. Theory Ser. A 77 (1997), 161-164). No es del todo obvio a partir de la declaración del resultado que el concepto de entropía se encuentra aquí debajo de la superficie. $A$ $r_i$ $i$ $A$

\prod_{i} (r_{i}!)^{1 / r_{i}} .

$\prod_i (r_i!)^{1/r_i}.$

Timothy Chow
fuente

Pruebas que exponen una estructura más profunda.

Respuestas: