Title of Seminar: Infosys Chandrasekharan Random Geometry Colloquium
Title of Talk: Lower tail bounds beyond Chernoff for very small deviations from the mean
Speaker: Jatin Batra, TIFR
Date: November 8, 2021
Time: 16:00:00 Hours
Venue: AG-77
Abstract: Concentration bounds for sums of independent random variables are ubiquitous in probabilistic setups. The most famous ones of these, the Chernoff-Hoeffding bounds provide guarantees of the following type: given a binomial random variable with expectation $k$, what is the probability that the variable deviates by a factor of more than $(1 + y)$ from $k$? The (nearly tight) answer is approx $\exp(-ky^2)$. However, what if we are interested in small additive deviations from the expectation $k$? In particular, what is the probability that the variable takes a value strictly less than $k$? Now, for large $k$, the Chernoff-Hoeffding bounds will give only the vacuous bound of 1. However, Jogdeo and Samuels showed in 1968 that the right answer is actually $1/2$. In this talk, I will describe this result and a helpful result of Hoeffding which shows that the worst case is the Poisson case. I will finally talk about our result from this year (with Nikhil Bansal, Majid Farhadi and Prasad Tetali) which extends the bound of Jogdeo and Samuels for the case of small deviations from $k/t$ for $t$ close to and at least 1.
Title of Talk: Lower tail bounds beyond Chernoff for very small deviations from the mean
Speaker: Jatin Batra, TIFR
Date: November 8, 2021
Time: 16:00:00 Hours
Venue: AG-77
Abstract: Concentration bounds for sums of independent random variables are ubiquitous in probabilistic setups. The most famous ones of these, the Chernoff-Hoeffding bounds provide guarantees of the following type: given a binomial random variable with expectation $k$, what is the probability that the variable deviates by a factor of more than $(1 + y)$ from $k$? The (nearly tight) answer is approx $\exp(-ky^2)$. However, what if we are interested in small additive deviations from the expectation $k$? In particular, what is the probability that the variable takes a value strictly less than $k$? Now, for large $k$, the Chernoff-Hoeffding bounds will give only the vacuous bound of 1. However, Jogdeo and Samuels showed in 1968 that the right answer is actually $1/2$. In this talk, I will describe this result and a helpful result of Hoeffding which shows that the worst case is the Poisson case. I will finally talk about our result from this year (with Nikhil Bansal, Majid Farhadi and Prasad Tetali) which extends the bound of Jogdeo and Samuels for the case of small deviations from $k/t$ for $t$ close to and at least 1.