CEBA Talk: Tight Probability Bounds with Pairwise Independence

Every Friday at Moscow time (21:00 AEST / 12:00 BST) Center conducts research seminars online. More about it here: Title: Tight Probability Bounds with Pairwise Independence Speaker: Karthik Natarajan (Professor, Singapore University of Technology and Design) Abstract: While some useful probability bounds for the sum of n pairwise independent Bernoulli random variables exceeding an integer k have been proposed in the literature, none of these bounds are tight in general. In this work, we provide results towards finding tight probability bounds for this class of problems. Firstly, when k=1, the tightest upper bound on the probability of the union of n pairwise independent events is provided in closed form. Secondly, for general k, new upper bounds are derived exploiting ordering of probabilities. Time permitting, I will try to discuss some of the current research directions that we are pursuing in this area.