Teoretyczne informatyka chernoff-bound

6

Czy istnieje odwrotna granica Chernoffa, która ogranicza, że prawdopodobieństwo ogona jest co najmniej tak duże. tj. jeśli X 1 , X 2 , … , X nX1,X2,…,XnX_1,X_2,\ldots,X_n są niezależnymi dwumianowymi zmiennymi losowymi, a μ = E [ ∑ n i = 1 X i ]μ=E[∑ni=1Xi]\mu=\mathbb{E}[\sum_{i=1}^n X_i] . Czy możemy zatem …

31 pr.probability chernoff-bound

1

Chernoff wyznaczył sumy ważone

Rozważ , gdzie lambda_i> 0 i Y_i są rozłożone jako normalna norma. Jakie granice koncentracji można udowodnić na X, jako funkcję (stałych) współczynników lambda_i?X=∑iλiY2iX=∑iλiYi2X = \sum_i \lambda_i Y_i^2 Jeśli wszystkie lambda_i są równe, oznacza to ograniczenie Chernoffa. Jedyny inny wynik, jaki znam, to lemat z pracy Arory i Kannana („Uczenie …

14 chernoff-bound

3

Nierówność typu Chernoffa dla niezależnych zmiennych losowych parami

Nierówności typu Chernoffa służą do wykazania, że prawdopodobieństwo, że suma niezależnych zmiennych losowych znacznie odbiega od wartości oczekiwanej, jest wykładniczo małe w wartości oczekiwanej i odchyleniu. Czy istnieje jakakolwiek nierówność typu Chernoffa dla dowolnej sumy niezależnych parami zmiennych losowych? Innymi słowy, czy istnieje wynik, który pokazuje, co następuje: prawdopodobieństwo, że …

13 derandomization pr.probability chernoff-bound

3

Rozszerzenie związane z Chernoffem

Szukam odwołania (a nie dowodu, że mogę to zrobić) do następującego rozszerzenia Chernoff. Niech bądź logiczne zmienne losowe, niekoniecznie niezależne . Zamiast tego jest zagwarantowane, że P r ( X i = 1 | C ) < p dla każdego i i każdego zdarzenia C, które zależy tylko od { …

13 reference-request pr.probability chernoff-bound

2

Suma niezależnych wykładniczych zmiennych losowych

Czy możemy udowodnić ostry wynik koncentracji na sumie niezależnych wykładniczych zmiennych losowych, tj. Niech będą niezależnymi zmiennymi losowymi takimi, że . Niech . Czy możemy udowodnić granice postaci . Wynika to bezpośrednio, jeśli użyjemy formy wariancji granic chernoffa i dlatego uważam, że jest to prawda, ale granice, które czytam, wymagają …

12 pr.probability randomness chernoff-bound

2

Nierówność typu Chernoffa dla zmiennej losowej z 3 wynikami

Załóżmy, że mamy zmienną losową, która przyjmuje wartości nienumeryczne a, b, c i chce określić ilościowo, w jaki sposób rozkład empiryczny nnnpróbki tej zmiennej odbiegają od rozkładu rzeczywistego. W tym przypadku obowiązuje następująca nierówność (z Cover & Thomas ). Twierdzenie 12.4.1 (twierdzenie Sanowa): Niech X1,X2,…,XnX1,X2,…,XnX_1, X_2, \ldots, X_n bądź tam …

9 pr.probability chernoff-bound

Pytania otagowane jako chernoff-bound