A sample space

$\Omega$ is a set of outcomes

$\Omega = {a_1, a_2, … }$ with associated probabilities

$P(a_1), …$ . Each time we sample from

$\Omega$ we recieve an outcome

$V(\Omega)$ . After

$k$ trials let

$G_k = \sum_{i=1}^k V(\Omega)$ .

Example

Let's say there's a lottery that either wins you $60, $1010, or nothing at all. It costs $10 to enter, so the net outcomes would be

$\Omega = \{ -10, 50, 1000 \}$ , let's say with probabilities

$P(-10)=90\%$ ,

$P(50)=9.9\%$ , and

$P(1000)=0.1\%$ .

After

$k$ trials, what are the odds that we won't loss money? That we'll make or lose more than

$$1000$ ? To answer these questions, we'll be finding upper bounds on probabilities of the form

$P(G_k \geq Z)$ .

Deriving

The expected value of each trial is

$\mathbb{E}[V(\Omega)] = \sum_{a \in \Omega} a \cdot P(a)$ We'll introduce an auxiliary variable,

$t > 0$ , to modify the value of each outcome,

$\mathbb{E}[e^{t\cdot V(\Omega)}] = \sum_{a \in \Omega} e^{a\cdot t} \cdot P(a)$ We'll leave the value of

$t$ floating for now and resolve it towards the end of the post. We now show

$\begin{align} \mathbb{E}[e^{t \cdot G_K}] &= \mathbb{E}[e^{t \sum_{i=1}^k V(\Omega)}] \\ &= \prod_{i=1}^k \mathbb{E}[e^{t \cdot V(\Omega)}] && \text{ because trials are independent} \\ &= \Big( \mathbb{E}[e^{t \cdot V(\Omega) } ] \Big)^{k} \\ &= \Big(\sum_{a \in \Omega} e^{a\cdot t} \cdot P(a) \Big)^{k} \end{align}$

Bounding the probability on the upper tail,

$G_k \geq Z$ ,

$\begin{align} P(G_k \geq Z) &= P(e^{t G_k} \geq e^{t Z}) && \text{ by monotonicity} \\ &\leq \frac{\mathbb{E}[e^{t G_k}]}{e^{t Z}} && \text{ by Markov's inequality} \\ &= \frac{\Big(\sum_{a \in \Omega} e^{a\cdot t} \cdot P(a) \Big)^{k}}{e^{t Z}} \end{align}$

To evaluate the bound we'll pick a

$t > 0$ that minimizes the RHS. Because it's convex, we can numerically find

$t$ using a binary search type algorithm,

	const optimizer = (boundFn) => (lottery, k, z) => {
	let t = 1e-10;
	let step = 1;
	let value = Infinity;
	while(Math.abs(step) > 1e-10){
	const proposal = t + step;
	if(proposal <= 0){ step *= -0.5; continue; }
	const prop_val = boundFn(lottery, k, z, proposal);
	if(prop_val < value){
	t = proposal;
	value = prop_val;
	} else {
	step *= step<0? -0.5 : -1;
	}
	}
	return value;
	}


	/**
	* @param {Array} lottery - An array of pairs, eg [[value, probability], ...]
	* @param {integer} k - Number of trials
	* @param {number} z - The x-axis of the tail
	* @return {number} An upper bound
	* @example
	* upperTail([[-5, 0.65], [5, 0.34], [95, 0.01]], 100, 0)
	*/
	const upperTail = optimizer((lottery, k, z, t) =>
	Math.pow(lottery.reduce((acc, [a, p]) => acc + (p * Math.exp(a*t)), 0), k)
	/ Math.exp(t * z));

view raw chernoffUpperBound.js hosted with ❤ by GitHub

Empirical Evaluation

Revisiting the example, if we buy

$k$ tickets, what are the odds we won't lose money,

$P(G_k \geq 0)$ ? This may be somewhat difficult to answer, and so we'll ask for an upper bound on this probability. We plot the derived bound alongside probabilities found by monte carlo simulation,

Deriving Chernoff Bounds

Definitions

Example

Deriving

Empirical Evaluation

Won't lose money

We'll make at least $1000

We won't lose more than $1000

Final Thoughts