Macierzowo-ekspanderowa nierówność Chernoffa

Speaker(s)

Aleksander Łukasiewicz

Affiliation

Uniwersytet Wrocławski

Date

June 13, 2019, 12:15 p.m.

Room

room 3260

Seminar

Seminar of Probability Group

---

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.

---