Materiały

Wszystkie zagadnienia omawiane na wykładzie są opisane w co najmniej jednej z wymienionych niżej pozycji:
  1. Michael Mitzenmacher, Eli Upfal "Metody probabilistyczne i obliczenia" (ang. "Probability and Computing")
  2. Rajeev Motwani, Prabhakar Raghavan "Randomized Algorithms"
  3. Devdatt Dubhashi, Alessandro Panconesi "Concentration of Measure for the Analysis of Randomized Algorithms"
W większości przypadków wystarczy pozycja pierwsza. W pozostałych (ze względu na słabą dostępność pozycji 2 i 3) postaramy się dostarczyć alternatywne materiały, o ile uznają to państwo za wskazane.

Co było?

To było.

Nierówność Chernoffa dla zmiennych ujemnie skorelowanych

Ze względu na to, że prezentacja tego tematu na wykładzie nie przebiegła szczególnie płynnie, oraz na to, że nie jest on omówiony w pozycji 1, pozwoliłem sobie przygotować krótki szkic dowodu.