Nierówności dla sum zmiennych losowych: perspektywa kombinatoryczna

Abstract

W rozprawie badamy oszacowania prawdopodobieństwa P (S ε I), gdzie S = X1 +• • •+Xn jest suma niezależnych lub słabo zależnych zmiennych losowych, a I jest przedziałem (ograniczonym lub nie). Rozpatrujemy trzy raczej różne problemy. Pierwszy z nich dotyczy koncentracji zmiennej losowej f(X1, • • • ,Xn), gdzie X1, • • • ,Xn są niezależnymi zmiennymi losowymi Bernoulliego z parametrem p, a funkcja f spełnia warunek Lipschitza ze względu na metrykę Hamminga. Otrzymujemy proste oszacowanie na P (f − Ef ≥ x), które w rozpatrywanym kontekście jest lepsze niż znana nierówność McDiarmida. Z uzyskanego oszacowania wyprowadzamy nierówność izoperymetryczna, która jest podobna do pewnej nierówności, uzyskanej przez Talagranda inną metoda. W drugiej części udowadniamy optymalne oszacowania z góry dla P (S ε I), gdy zmienne Xi sa niezależne, mają symetryczne rozkłady i wartości bezwzględne ograniczone przez 1. Nasze wyniki dotyczą przypadków, gdy I = [x,1) lub I = {x}. Trzeci kierunek rozprawy dotyczy liczby X kopii danego grafu G w grafie losowym G(n, p). Dla pewnych G, otrzymujemy oszacowania wykładnicze dla P (X ≥ tEX), które są optymalne z dokładnością do stałej w wykładniku.

We investigate bounds for the probability P (S ε I), where S = X1 +• • •+Xn is a sum of independent or weakly dependent random variables and I is an interval (bounded or unbounded). We consider three rather different problems. The first one is about the concentration of a random variable f (X1 , • • • , Xn ), where X1 , • • • , Xn are independent Bernoulli random variables with parameter p and function f is Lipschitz with respect to the Hamming distance. We obtain a simple bound for P (f − Ef ≥ x), which in the given setting is better than the well-known McDiarmid inequality. From our bound we derive an isoperimetric inequality which is similar to an inequality by Talagrand obtained by a different method. In the second part we obtain optimal bounds for P (S ε I), when Xi ’s are independent, symmetrically distributed and bounded in absolute value by 1. Our results cover the cases when I = [x, ∞) or I = {x}. The third direction of the thesis focuses on the number X of copies of a fixed graph G in the random graph G(n, p). For certain graphs G we obtain several exponential bounds for P (X ≥ tE X) which are optimal up the constant in the exponent.