IIC2283 / DAA-2022-2

Repositorio con material asociado al curso IIC2283 - Diseño y Análisis de Algoritmos para el año 2022
37 stars 5 forks source link

[I2] Demostración Lema de Schwartz-Zippel #27

Open Ignaciomendezp opened 2 years ago

Ignaciomendezp commented 2 years ago

Hola! Revisando lo PPTs no me quedó muy claro esta diapositiva. En primer lugar, me parece que faltan signos "=" entre cada línea, lo que confunde un poco. En segundo lugar, no me queda claro qué es lo que se hace a partir de la primera flecha indicada, ni de donde sale el signo "<="

Muchas gracias de antemano!

CleanShot 2022-10-29 at 16 02 25@2x

BFFV commented 2 years ago

Hola!

1) Respecto a los signos =, creo que no falta ninguno. Lo que pasa es que se descompone la probabilidad inicial usando el teorema de Probabilidades Totales, por lo que queda la suma de 2 multiplicaciones de probabilidades (fíjate en los símbolos de multiplicación .). Por lo tanto, el único signo = que aparece afuera de las probabilidades es el primero, y después pasa al tiro al <= (el otro signo = aparece al final de todo al llegar al resultado).

2) El signo <= sale porque al tener 2 probabilidades multiplicándose, si te quedas sólo con una de ellas eso siempre será mayor o igual que tener las 2 multiplicadas, dado que a lo más toman valor 1. Entonces, lo que se hace en ese paso es quedarse con sólo un término de cada multiplicación, quedando la suma de 2 probabilidades. Después, esa suma permite acotar todo de forma conveniente con los resultados de las slides anteriores.

Espero haber aclarado tus dudas, saludos!

Ignaciomendezp commented 2 years ago

Muchas gracias! Quedo mucho mas claro 🙌🏻