Of Notes

Large Deviations Theory & Rate Functions

1 min read · revised 17 October 2026 · ·

Table of Contents

This is part of the topic of Probability Theory > concentration of measure > large deviations > rate functions.

We study how collecting more data (numbers), leads to changes in the average measure. In large deviation theory specifically we ask, if the ends up somewhere very far or different, how astonishing or surprising is that outcome?

Rate Functions

This is how we measure this oddity of that outcome. Say we have some average of a random process we can say if is large enough that:

To get to how this equation came to be we start with a coin which is if heads and if tails and we measure:

which for a fair coin .

But imagine outcomes such as:

The farther we deviate from the expected natural outcome the more cost we generate.

which tells us that grows with deviation from the expected result.

Rate function of a fair coin, \(I(x) = x\ln 2x + (1-x)\ln 2(1-x)\): zero at the expected \(0.5\) and rising ever faster with the deviation, so \(e^{-nI(x)}\) makes far-off averages exponentially rare.
Fig. 1. Rate function of a fair coin, : zero at the expected and rising ever faster with the deviation, so makes far-off averages exponentially rare.

Now if we know that and we plug that back into the formula we get that which is just .

With a non-zero rate function and a growing , the probability estimation diminishes exponentially.

  • NOTE: a rate function can also have two minima or more.

KL Divergence

We will often measure as the divergence of observed observations from some other distribution.

/ or Ctrl K
search; empty, it shows notes to revise and lately read
m
mark this note to revise, or unmark it
c
cover maths, proofs and solutions to test yourself
n
uncover the next covered item
y
copy this note’s org-roam link
e
copy this note as markdown, LaTeX kept as TeX
p
the next problem to work; there h hints, s shows the solution, x passes it for today
→ ← j k space
turn the page, when reading in pages
l
on the map, trace the greatest distance, then the longest path
double-click
a formula, to copy its TeX
rest on maths
bind a part of a formula and open the wheel of notes it comes from; scroll or ↑ ↓ widens it, 1–6 goes
?
this card