# Probabilistic Bounds -- A Primer

DevFeed: [Probabilistic Bounds -- A Primer](<https://devfeed.tech/articles/probabilistic-bounds-a-primer-40312.md>)

Original publisher: [Read original article](<https://www.jeremykun.com/2013/04/15/probabilistic-bounds-a-primer/>)

Published: 2013-04-15T11:14:32Z

Content type: tutorial

Language: en

Sources: [Jeremy Kun](<https://devfeed.tech/sources/jeremy-kun.md>)

Topics: [Algorithms, Complexity](<https://devfeed.tech/topics/algorithms-complexity.md>), [math](<https://devfeed.tech/topics/math.md>), [Learning](<https://devfeed.tech/topics/learning.md>), [Streaming](<https://devfeed.tech/topics/streaming.md>)

Tags: [algorithm](<https://devfeed.tech/tags/algorithm.md>), [algorithms](<https://devfeed.tech/tags/algorithms.md>), [chebyshev](<https://devfeed.tech/tags/chebyshev.md>), [chernoff](<https://devfeed.tech/tags/chernoff.md>), [chernoff-bound](<https://devfeed.tech/tags/chernoff-bound.md>), [inequality](<https://devfeed.tech/tags/inequality.md>), [learning-theory](<https://devfeed.tech/tags/learning-theory.md>), [machine-learning](<https://devfeed.tech/tags/machine-learning.md>), [markov](<https://devfeed.tech/tags/markov.md>), [mathematics](<https://devfeed.tech/tags/mathematics.md>), [probabilistic](<https://devfeed.tech/tags/probabilistic.md>), [probabilistic-method](<https://devfeed.tech/tags/probabilistic-method.md>), [probability-theory](<https://devfeed.tech/tags/probability-theory.md>), [random-variables](<https://devfeed.tech/tags/random-variables.md>), [streaming](<https://devfeed.tech/tags/streaming.md>), [streaming-algorithms](<https://devfeed.tech/tags/streaming-algorithms.md>), [variance](<https://devfeed.tech/tags/variance.md>)

## AI overview

This tutorial introduces probabilistic bounds used in algorithm analysis, machine learning theory, randomized algorithms, and streaming algorithms. It focuses on the Chernoff bound and presents simpler bounds from Markov's and Chebyshev's inequalities, including short proofs.

## Source excerpt

Probabilistic arguments are a key tool for the analysis of algorithms in machine learning theory and probability theory. They also assume a prominent role in the analysis of randomized and streaming algorithms, where one imposes a restriction on the amount of storage space an algorithm is allowed to use for its computations (usually sublinear in the size of the input). While a whole host of probabilistic arguments are used, one theorem in particular (or family of theorems) is ubiquitous: the Chernoff bound.