Chernoff, Hoeffding, etc. bounds || @ CMU || Lecture 5c of CS Theory Toolkit

Поделиться
HTML-код
  • Опубликовано: 2 янв 2025

Комментарии • 3

  • @hanmaslin
    @hanmaslin 2 года назад

    Is there an error on the Hoeffding bound? Wikipedia has an extra factor of 2 outside the exponential.

    • @alex_xiong
      @alex_xiong Год назад

      The wiki page shows exactly the same bound Prof O'Donnell wrote: en.wikipedia.org/wiki/Chernoff_bound#Sums_of_independent_bounded_random_variables
      could you share the link to the expression you saw?

    • @hanmaslin
      @hanmaslin Год назад

      @@alex_xiong en.wikipedia.org/wiki/Hoeffding%27s_inequality
      Third expression in "Statement".