{ "cells": [ { "cell_type": "markdown", "metadata": {}, "source": [ "# Inequalities" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## General-purpose Inequalities\n", "\n", "### The Arithmetic-Geometric Mean Inequality\n", "Let $\\{ a_j \\}_{j=1}^n$ and $\\{q_j\\}_{j=1}^n$ be sets of nonnegative numbers with\n", "$\\sum_j q_j = 1$.\n", "Then\n", "$$\n", " \\prod_{j=1}^n a_j^{q_j} < \\sum_{j=1}^n q_j a_j.\n", "$$\n", "\n", "### Rearrangements\n", "\n", "Let $x \\equiv (x_j)_{j=1}^n \\in {\\mathbb R}^n$.\n", "The _decreasing rearrangement_ of $x$, denoted $x^*$, has the same multiset of \n", "component values as $x$, but ordered so that\n", "$$\n", "x_1^* \\ge x_2^* \\ge \\cdots \\ge x_n^*.\n", "$$\n", "\n", "The _increasing rearrangmement_ of $x$, denoted $x_*$, has the same multiset of component\n", "values as $x$, but ordered so that\n", "$$\n", "x_{*1} \\le x_{*2} \\le \\cdots \\le x_{*n}.\n", "$$\n", "\n", "#### The Rearrangement Inequality for two vectors\n", "Suppose $x \\in \\mathbb{R}^n$ and $y \\in \\mathbb{R}^n$.\n", "Let $x \\cdot y \\equiv \\sum_{j=1}^n x_j y_j$.\n", "Then \n", "$$\n", " x^* \\cdot y_* \\le x \\cdot y \\le x^* \\cdot y^*.\n", "$$\n", "\n", "\n", "#### The Rearrangement Inequality for three vectors\n", "[To do]" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Probability Inequalities\n", "This section follows Lugosi (2006) closely.\n", "\n", "### The tail-sum formula\n", "If $X$ is a nonnegative real-valued random variable,\n", "$$ \n", " {\\mathbb E} X = \\int_0^\\infty {\\mathbb{P}} \\{X \\ge x\\} dx\n", "$$\n", "\n", "### Jensen's Inequality\n", "If $\\phi$ is a convex function from ${\\mathcal X}$ to $\\mathbb{R}$, then $\\phi({\\mathbb E} X) \\le {\\mathbb E} \\phi(X)$.\n", "\n", "\n", "\n", "### Markov's, Chebychev's, and related inequalities\n", "From the tail-sum formula,\n", "$$\n", " {\\mathbb E} X \\ge \\int_0^t {\\mathbb{P}} \\{X \\ge x\\} dx \\ge t {\\mathbb{P}} \\{X \\ge t \\}\n", "$$\n", "so\n", "$$\n", " {\\mathbb{P}} \\{ X \\ge t \\} \\le \\frac{{\\mathbb E} X}{t}.\n", "$$\n", "This is _Markov's Inequality_.\n", "\n", "Moreover, for any strictly monotonic function $f$ and nonnegative $X$,\n", "$$ \n", " {\\mathbb{P}} \\{ X \\ge t \\} = {\\mathbb{P}} \\{ f(X) \\ge f(t) \\} \\le \\frac{{\\mathbb E} f(X)}{f(t)}.\n", "$$\n", "In particular, for any real-valued $X$ and real $q > 0$,\n", "$| X - {\\mathbb E} X |$ is a nonnegative\n", "random variable and $f(x) = x^q$ is strictly monotonic, so \n", "$$\n", " {\\mathbb{P}} \\{| X - {\\mathbb E} X | \\ge t \\} = {\\mathbb{P}} \\{ | X - {\\mathbb E} X |^q \\ge t^q \\} \\le\n", " \\frac{{\\mathbb E} | X - {\\mathbb E} X |^q}{t^q}.\n", "$$\n", "This is the _Generalized Markov Inequality_.\n", "\n", "_Chebychev's Inequality_ is a special case:\n", "$$ \n", " {\\mathbb{P}} \\{ | X - {\\mathbb E} X |^2 \\ge t^2 \\} \\le\n", " \\frac{{\\mathbb E} | X - {\\mathbb E} X |^2}{t^2}\n", " = \\frac{{\\mbox{Var}} X}{t^2}.\n", "$$\n", "\n", "### Chernoff bounds\n", "If $X$ has a moment generating function (if ${\\mathbb{E}} e^{sX}$ exists for $s \\in [-a, a]$\n", "for some $a > 0$), we can apply the generalized Markov Inequality with $f(x) = e^{sx}$ for positive $s$:\n", "$$\n", " {\\mathbb{P}} \\{ X \\ge t \\} = {\\mathbb{P}} \\{ e^{sX} \\ge e^{st} \\} \\le \\frac{{\\mathbb E} e^{sX}}{e^{st}}\n", "$$\n", "for all $s \\in [-a, a]$.\n", "For any particular $X$, one can optimize this over $s$:\n", "$$\n", " {\\mathbb{P}} \\{ X \\ge t \\} = {\\mathbb{P}} \\{ e^{sX} \\ge e^{st} \\} \\le \\inf_{s \\in [-a, a]}\n", " \\frac{{\\mathbb E} e^{sX}}{e^{st}}.\n", "$$\n", "\n", "\n", "\n", "### Hoeffding's Inequality\n", "Let $\\{ X_j \\}_{j=1}^n$ be independent, and define \n", "$S_n \\equiv \\sum_{j=1}^n X_j$.\n", "Then, applying the Chernoff bound gives\n", "$$\n", " {\\mathbb{P}} \\{ S_n - {\\mathbb E} S_n \\ge t \\} \\le e^{-st} {\\mathbb E} e^{sS_n} =\n", " e^{-st} \\prod_{j=1}^n e^{s(X_j - E X_j)}.\n", "$$\n", "Hoeffding bounds the moment generating function for a bounded random variable\n", "$X$:\n", "If $a \\le X \\le b$ with probability 1, then\n", "$$\n", " {\\mathbb E} e^{sX} \\le e^{s^2 (b-a)^2/8},\n", "$$\n", "from which follows _Hoeffding's tail bound_:\n", "\n", "If $\\{X_j\\}_{j=1}^n$ are independent and ${\\mathbb{P}} \\{a_j \\le X_j \\le b_j\\} = 1$,\n", "then\n", "$$ \n", " {\\mathbb{P}} \\{ S_n - {\\mathbb E} S_n \\ge t \\} \\le e^{-2t^2/\\sum_{j=1}^n (b_j - a_j)^2}\n", "$$ \n", "and\n", "$$ \n", " {\\mathbb{P}} \\{ S_n - {\\mathbb E} S_n \\le -t \\} \\le e^{-2t^2/\\sum_{j=1}^n (b_j - a_j)^2}\n", "$$ \n", "\n", "### Hoeffding's Other Inequality\n", "Suppose $f$ is a convex, continuous, real function and ${\\mathcal X}$ is a finite set.\n", "Let $\\{X_j \\}_{j=1}^n$ be a simple random sample from ${\\mathcal X}$ and\n", "let $\\{Y_j \\}_{j=1}^n$ be an iid uniform random sample (with replacement) from ${\\mathcal X}$.\n", "Then\n", "$$ \n", " {\\mathbb E} f \\left ( \\sum_{j=1}^n X_j \\right ) \\le {\\mathbb E} f \\left ( \\sum_{j=1}^n Y_j \\right ).\n", "$$\n", "\n", "### Bernstein's Inequality\n", "\n", "Suppose $\\{X_j \\}_{j=1}^n$ are independent with ${\\mathbb E} X_j = 0$ for all $j$,\n", "${\\mathbb{P}} \\{ | X_j | \\le c\\} = 1$,\n", "$\\sigma_j^2 = {\\mathbb E} X_j^2$ and $\\sigma = \\frac{1}{n} \\sum_{j=1}^n \\sigma_j^2$.\n", "Then for any $\\epsilon > 0$,\n", "$$\n", " {\\mathbb{P}} \\{ S_n/n > \\epsilon \\} \\le e^{-n \\epsilon^2 / 2(\\sigma^2 + c\\epsilon/3)}.\n", "$$" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "collapsed": true }, "outputs": [], "source": [] } ], "metadata": { "anaconda-cloud": {}, "kernelspec": { "display_name": "Python 3", "language": "python", "name": "python3" }, "language_info": { "codemirror_mode": { "name": "ipython", "version": 3 }, "file_extension": ".py", "mimetype": "text/x-python", "name": "python", "nbconvert_exporter": "python", "pygments_lexer": "ipython3", "version": "3.6.1" } }, "nbformat": 4, "nbformat_minor": 1 }