Para m=15, ¿qué número entero mínimo de aristas de corte garantiza la media?
Redondea hacia arriba 15/2.
Existe un corte entero con tamaño al menos esa media.
Debe tener8 o más, así que la garantía entera es 8.
Cinco indicadores tienen probabilidad 1/3 cada uno. Calcula la esperanza de su suma.
Suma probabilidades.
La suma de cinco indicadores tiene esperanza igual a la suma de sus probabilidades.
No se necesita independencia para esta linealidad.
Dos eventos tienen probabilidad 1/4 y 1/8. Calcula la cota de unión.
Suma.
La cota de unión suma las dos probabilidades.
La cota es 3/8, sin exigir independencia.
Prueba que un grafo tiene un corte de tamaño al menos m/2.
Usa una partición aleatoria y esperanza.
Asignamos a cada vértice un color independiente y equiprobable entre dos.
Cada arista sin bucle cruza entre colores con probabilidad1/2; la esperanza del tamaño es m/2.
El máximo es al menos la media, así que algún corte alcanza al menos m/2 aristas.
Explica por qué dos indicadores pueden ser dependientes y aun así sumar sus esperanzas.
La esperanza es lineal por definición.
Por definición y linealidad de la integral o suma, E[X+Y]=E[X]+E[Y] cuando las esperanzas están bien definidas.
La dependencia no introduce términos cruzados en una suma de esperanzas.
Sí afecta a productos y varianzas, por eso no se trasladan sus requisitos a esta identidad.