Prelegent: Aleksander Łukasiewicz

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.