You are not logged in | log in

Wydział Matematyki, Informatyki i Mechaniki Uniwersytetu Warszawskiego

  • Skala szarości
  • Wysoki kontrast
  • Negatyw
  • Podkreślenie linków
  • Reset

Aktualności — Wydarzenia

Sem. Probability

 

Macierzowo-ekspanderowa nierówność Chernoffa


Prelegent: Aleksander Łukasiewicz

2019-06-13 12:15

Opowiem o wybranych wynikach z pracy A. Garga, Y. T. Lee, Z. Songa i N. Srivastavy „A Matrix Expander Chernoff Bound” z 2018r. Nierówności typu Chernoffa znajdują szerokie zastosowanie w analizie algorytmów probabilistycznych. W najbardziej podstawowej formie, nierówność Chernoffa pokazuje mocną koncentrację wokół średniej dla sumy prób Bernoulliego. Znanych jest wiele innych wersji, np. oszacowanie dla sumy niezależnych zmiennych o wartościach macierzowych, czy też oszacowanie dla zmiennych skalarnych, pochodzących ze spaceru po grafie skończonym. Autorzy pracy zajmują się fuzją tych dwóch wspomnianych nierówności, wykazując naturalną koncentrację dla zmiennych losowych o wartościach macierzowych, pochodzących ze spaceru losowego po grafie nieskierowanym. W tym celu, aby pokonać problem braku niezależności, wyprowadzają nową nierówność typu Goldena-Tomphsona.