Chernoff-Hoeffding Inequality and Applications

Abstract

When dealing with modern big data sets, a very common theme is reducing the set through a random process. These generally work by making "many simple estimates" of the full data set, and then judging them as a whole. Perhaps magically, these "many simple estimates" can provide a very accurate and small representation of the large data set. The key tool in showing how many of these simple estimates are needed for a fixed accuracy trade-off is the Chernoff-Hoeffding inequality[Che52,Hoe63]. This document provides a simple form of this bound, and two examples of its use.

Expository document hopefully at the level of an advanced undergrad or beginning graduate student. The update corrects a missing bound on a parameter in one form of the main theorem

Cited by in corpus (8)

• Capacity Results for Binary Fading Interference Channels with Delayed CSIT
• Communication Through Collisions: Opportunistic Utilization of Past Receptions
• Topological Content Delivery with Feedback and Random Receiver Cache
• Online Semi-Supervised Concept Drift Detection with Density Estimation
• Explicit Explore, Exploit, or Escape ($E^4$): near-optimal safety-constrained reinforcement learning in polynomial time
• MeanShift++: Extremely Fast Mode-Seeking With Applications to Segmentation and Object Tracking
• Runtime Performances of Randomized Search Heuristics for the Dynamic Weighted Vertex Cover Problem
• Rank-Regret Minimization