# One Hundred Probability and Statistics Inequalities

CNP Slagle

##  1 Introduction

In 2012, the author compiled a subset of the following inequalities for a
researcher in randomized algorithms. One might think of said inequalities as a
very quick reference, with access to primary and secondary resources listed
either within the section or alongside the inequality of interest. In the
intervening years, some of the original sources and their respective links
have vanished, leading the author to consider a companion document with proofs
for select inequalities within this list. Though the author would refute the
completeness of this collection for more advanced researchers, he nonetheless
believes it may serve some interest. It is important

##  2 Basic Probability and Measure Theory Inequalities

The relations to follow include axioms within the probabilistic framework,
along with a few of the basic inferences derived therefrom. See [1] for a
wonderful introduction. Given events (sets) $A$, $B$, and countable
$\\{A_{n}\\}_{n=1}^{\infty}$,

  1. 1.

$\mathbb{P}[A]\geq 0$

  2. 2.

$\mathbb{P}[A]\leq 1$

  3. 3.

If $A\subset B$, then $\mathbb{P}[A]\leq\mathbb{P}[B]$

  4. 4.

If $A\subset B$, then $\mathbb{P}[B]\leq\mathbb{P}[A^{c}]$

  5. 5.

(Boole)
$\mathbb{P}[\cup_{n=1}^{\infty}A_{n}]\leq\sum_{n=1}^{\infty}\mathbb{P}[A_{n}]$

  6. 6.

$\mathbb{P}[\cup_{n=1}^{\infty}A_{n}]\geq\sup\\{\mathbb{P}[A_{n}]|n=1,2,\dots\\}$

  7. 7.

$\mathbb{P}[\cap_{n=1}^{\infty}A_{n}]\leq\inf\\{\mathbb{P}[A_{n}]|n=1,2,\dots\\}$

  8. 8.

$\mathbb{P}[A\cap B]\leq\min\\{\mathbb{P}[A],\mathbb{P}[B]\\}$

  9. 9.

(Bonferroni) $\mathbb{P}[A\cap B]\geq\mathbb{P}[A]+\mathbb{P}[B]-1$

  10. 10.

(Bonferroni General)
$\mathbb{P}[\cap_{i=1}^{n}]\geq\sum_{i=1}^{n}\mathbb{P}[A_{i}]-(n-1)$

  11. 11.

$\mathbb{P}[A|B]\geq\mathbb{P}[A\cap B]$

  12. 12.

(Karlin Ost) Define $P_{1}=\sum_{i=1}^{n}\mathbb{P}[A_{i}]$,
$P_{2}=\sum_{1\leq i<j\leq n}\mathbb{P}[A_{i}\cap A_{j}]$, $P_{3}=\sum_{1\leq
i<j<k\leq n}\mathbb{P}[A_{i}\cap A_{j}\cap
A_{k}]$,…,$P_{n}=\mathbb{P}[A_{1}\cap\dots\cap A_{n}]$. Then for
$i=1,\dots,n$,

$P_{1}-P_{2}+P_{3}-\dots\pm
P_{i-1}\geq\mathbb{P}\left[\cup_{i=1}^{n}A_{i}\right]\geq
P_{1}-P_{2}+P_{3}-\dots\mp P_{i}.$ (1)

##  3 Power Means [1]

Define the pth power mean of a finite set of positive numbers $S$ to be

$PM(S,p)=\sqrt[p]{\sum_{s\in S}{\frac{{s}^{p}}{|S|}}}$ (2)

Notice that the arithmetic mean and harmonic mean of the set $S$ are simply
$A_{M}(S)=PM(S,1)$ and $H_{M}(S)=PM(S,-1)$, respectively. Less clear is that
the geometric mean $G_{M}(S)=\sqrt[|S|]{\prod_{s\in S}s}={\lim\limits_{p\to
0}}PM(S,p)$, the maximum $\max(S)={\lim\limits_{p\to\infty}}PM(S,p)$, and the
minimum $\min(S)={\lim\limits_{p\to-\infty}}PM(S,p)$. So, we have

  1. 1.

$PM(S,p_{0})\leq PM(S,p_{1})$ for $p_{0}\leq p_{1}$

  2. 2.

$H_{M}(S)\leq G_{M}(S)\leq A_{M}(S)$

##  4 Expectations and Variances I

The following inequalities range from elementary to moderate complexity, all
available in [1]. Let $X$ and $Y$ be random variables. If an inequality
includes a function $f$ of a random variable $X$, assume that the expectation
$\mathbb{E}f(X)$ exists.

  1. 1.

If $g(X)\leq h(X)$, then $\mathbb{E}g(X)\leq\mathbb{E}h(X)$.

  2. 2.

If $a\leq g(X)\leq b$, then $a\leq\mathbb{E}g(X)\leq b$.

  3. 3.

(Hölder) If $p,q$ satisfy ${{1}\over{p}}+{{1}\over{q}}=1$, then
$|\mathbb{E}XY|\leq\mathbb{E}|XY|\leq(\mathbb{E}|X|^{p})^{\frac{1}{p}}(\mathbb{E}|Y|^{q})^{{1}\over{q}}$

  4. 4.

(Jensen) For a convex function $g$, If $X\geq Y$, then $\mathbb{E}g(X)\geq
g(EX)$.

  5. 5.

(Cauchy-Schwartz)
$|\mathbb{E}XY|\leq\mathbb{E}|XY|\leq\sqrt{(\mathbb{E}|X|^{2})(\mathbb{E}|Y|^{2})}$

  6. 6.

$Var(X)\geq 0$

  7. 7.

$Cov^{2}(X,Y)\leq Var(X)Var(Y)$

  8. 8.

(Hölder Special Case) For $p>1$,
$\mathbb{E}|X|\leq\sqrt[p]{\mathbb{E}|X|^{p}}$

  9. 9.

(Liapounov) For $s>r>1$,
$\sqrt[r]{\mathbb{E}|X|^{r}}\leq\sqrt[s]{\mathbb{E}|X|^{s}}$

  10. 10.

(Minkowski) For $p\geq 1$,
$\sqrt[p]{\mathbb{E}|X+Y|^{p}}\leq\sqrt[p]{E|X|^{p}}+\sqrt[p]{E|Y|^{p}}$

  11. 11.

(Triangle) As a special case of Minkowski’s inequality, $\mathbb{E}|X+Y|\leq
E|X|+E|Y|$.

  12. 12.

If $g$ is nondecreasing and $h$ is nonincreasing, then
$\mathbb{E}(g(X)h(X))\leq(Eg(X))(Eh(X))$.

  13. 13.

If $g$ and $h$ are both nondecreasing or both nonincreasing, then
$\mathbb{E}(g(X)h(X))\geq(Eg(X))(Eh(X))$.

  14. 14.

(Cramér-Rao) Suppose $X_{1},\dots,X_{n}$ is a sample with joint pdf
$f(\mathbf{x}|\theta)$ and $W(\mathbf{X})$ is any estimator of $\theta$ such
that
${{d}\over{d\theta}}E_{\theta}W(\mathbf{X})=\int_{\chi}{{\partial}\over{\partial\theta}}[W(\mathbf{x})]f(\mathbf{x}|\theta)d\mathbf{x}$
and $Var_{\theta}(W(\mathbf{X}))<\infty$. Then

$Var_{\theta}(W(\mathbf{X}))\geq{{({{d}\over{d\theta}}E_{\theta}W(\mathbf{X}))^{2}}\over{E_{\theta}\left[\left({{\partial}\over{\partial\theta}}\log(f(\mathbf{x}|\theta))\right)^{2}\right]}}.$
(3)

  15. 15.

(Cramér-Rao IID) Suppose $X_{1},\dots,X_{n}$ is a sample iid with marginal pdf
$f(x|\theta)$ and $W(\mathbf{X})$ is any estimator of $\theta$ such that
${{d}\over{d\theta}}E_{\theta}W(\mathbf{X})=\int_{\chi}{{\partial}\over{\partial\theta}}[W(\mathbf{x})]f(\mathbf{x}|\theta)d\mathbf{x}$
and $Var_{\theta}(W(\mathbf{X}))<\infty$. Then

$Var_{\theta}(W(\mathbf{X}))\geq{{({{d}\over{d\theta}}E_{\theta}W(\mathbf{X}))^{2}}\over{nE_{\theta}\left[\left({{\partial}\over{\partial\theta}}\log(f(x|\theta))\right)^{2}\right]}}.$
(4)

  16. 16.

(Rao-Blackwell) Let $U$ be an unbiased estimator of $\tau(\theta)$, and let
$T$ be a sufficient statistic for $\theta$. Define $\phi(T)=E(U|T)$. Then
$\mathbb{E}\phi(T)=\tau(\theta)$, and

$Var_{\theta}\phi(T)\leq Var_{\theta}W\text{ for all }\theta.$ (5)

##  5 Expectations and Variances II

  1. 1.

(Han [2]) Let $X_{1},\dots,X_{n}$ be independent discrete random variables.
Let $H(X_{\pi_{1}},\dots,X_{\pi_{k}})$ be the joint entropy of a subset of the
$\\{X_{i}\\}$. Then

$H(X_{1},\dots,X_{n})\leq\sum_{i=1}^{n}H(X_{1},\dots,X_{i-1},X_{i+1},\dots,X_{n}).$
(6)

  2. 2.

[2] Let $X_{1},\dots,X_{n}$ be independent random variables. Let
$g:Domain(X_{1},\dots,X_{n})\to\mathbb{R}$ be Lesbegue measurable, and
$Z=g(X_{1},\dots,X_{n})$. Then

$Var(Z)\leq\sum_{i=1}^{n}E[(Z-E(Z|X_{1},\dots,X_{i-1},X_{i+1},\dots,X_{n})^{2}].$
(7)

  3. 3.

(Efron-Stein [2]) Let $X_{1},\dots,X_{n}$ be independent random variables. Let
$g:Domain(X_{1},\dots,X_{n})\to\mathbb{R}$ be Lesbegue measurable, and
$Z=g(X_{1},\dots,X_{n})$. Let $Y_{1},\dots,Y_{n}$ be an independent copy of
$X_{1},\dots,X_{n}$, and let $Z_{i}=g(X_{1},\dots,Y_{i},\dots,X_{n})$. Then

$Var(Z)\leq\sum_{i=1}^{n}E[(Z-Z_{i})^{2}].$ (8)

  4. 4.

(Logarithmic Sobolev [2]) Let $X_{1},\dots,X_{n}$ be independent random
variables. Let
$g_{i}:Domain(X_{1},\dots,X_{i-1},X_{i+1},\dots,X_{n})\to\mathbb{R}$ be
Lesbegue measurable, $Z_{i}=g_{i}(X_{1},\dots,X_{i-1},X_{i+1},\dots,X_{n})$,
$g:Domain(X_{1},\dots,X_{n})\to\mathbb{R}$ be Lesbegue measurable, and
$Z=g(X_{1},\dots,X_{n})$. Let $\psi(t)=e^{t}-t-1$ and $s>0$. Then

$sE(Ze^{sZ})-E(e^{sZ})\log[E(e^{sZ})]\leq\sum_{i=1}^{n}E[e^{sZ}\psi(-s(Z-Z_{i}))].$
(9)

  5. 5.

(Symmetrized Logarithmic Sobolev [2]) Let $X_{1},\dots,X_{n}$ be independent
random variables. Let
$g:Domain(X_{1},\dots,X_{n})\to\mathbb{R}$ be Lesbegue measurable, and
$Z=g(X_{1},\dots,X_{n})$. Let $Y_{1},\dots,Y_{n}$ be an independent copy of
$X_{1},\dots,X_{n}$, and let $Z_{i}=g(X_{1},\dots,Y_{i},\dots,X_{n})$. Let
$\psi(t)=e^{t}-t-1$ and $s>0$. Then

$sE(Ze^{sZ})-E(e^{sZ})\log[E(e^{sZ})]]\leq\sum_{i=1}^{n}E[e^{sZ}\psi(-s(Z-Z_{i}))].$
(10)

  6. 6.

[3] Suppose $\\{X_{n}\\}$ is a sequence of random variables such that for all
$n$, $X_{n}\geq 0$, and for all $\epsilon>0$, there exist $c_{1}>0$ and
$c_{2}>e^{-1}$ such that $\mathbb{P}[X_{n}>\epsilon]\leq
c_{1}e^{-c_{2}n\epsilon^{2}}$. Then

$\mathbb{E}X_{n}\leq\sqrt{{1+\log(c_{1})}\over{nc_{2}}}.$ (11)

  7. 7.

(Ledoux-Talagrand Contraction [4]) Suppose $X_{i},\dots,X_{n}$ are iid
Rademacher variables
($\mathbb{P}[X_{i}=1]=\mathbb{P}[X_{i}=-1]={{1}\over{2}}$). Suppose
$f:\mathbb{R}^{+}\to\mathbb{R}^{+}$ be convex and increasing, and
$\phi_{i}:\mathbb{R}\to\mathbb{R}$ be Lipschitz with constant $L$ for
$i=1,\dots,n$. Then for $T\subset\mathbb{R}^{n}$,

$Ef\left({{1}\over{2}}\sup_{\mathbf{t}\in
T}\left|\sum_{i=1}^{n}X_{i}\phi_{i}(t_{i})\right|\right)\leq
Ef\left(L\sup_{\mathbf{t}\in T}\left|\sum_{i=1}^{n}X_{i}t_{i}\right|\right)$
(12)

  8. 8.

(Bhatia-Davis [5]) If a univariate probability distribution $F$ has minimum
$m$, maximum $M$, and mean $\mu$, then for any $X$ following $F$,
$Var(X)\leq(M-\mu)(\mu-m)$.

  9. 9.

(Popoviciu [6]) If a univariate probability distribution $F$ has minimum $m$
and maximum $M$, then for any $X$ following $F$, $Var(X)\leq{1\over
4}(M-m)^{2}$.

  10. 10.

(Chapman-Robbins [7]) Suppose $\mathbf{X}$ is a random variable in
$\mathbb{R}^{k}$ with an unknown parameter $\theta$. If $\delta(\mathbf{X})$
is an unbiased estimator for $\tau(\theta)$, then

$Var(\delta(\mathbf{X}))\geq\sup_{\Delta}{{[\tau(\theta+\Delta)-\tau(\theta)]^{2}}\over{E_{\theta}\left[{{p(\mathbf{X}.\theta+\Delta)}\over{p(\mathbf{X},\theta)}}-1\right]^{2}}}.$
(13)

  11. 11.

(Entropy Power [8]) Define the entropy of $X$ to be
$\mathbb{H}\left((\right)X)=-\mathbb{E}\log f_{X}(X)$, where $f_{X}(x)$ is the
pdf or pmf of $X$. Define the entropy power of $X$ to be $N(X)={{1}\over{2\pi
e}}e^{{2\over n}h(X)}$. Then for random variables $X$ and $Y$, we have
$N(X+Y)\geq N(X)+N(Y)$.

  12. 12.

(Marcinkiewicz Zygmund [9]) Let $X_{1},\dots,X_{n}$ be independent random
variables with common support such that $\mathbb{E}X_{i}=0$ and
$\mathbb{E}X_{i}^{p}<\infty$ for all $p\geq 1$. Then there exist constants
$A(p)$ and $B(p)$, dependent only on $p$, such that

$A(p)E\left(\sum_{i=1}^{n}|X_{i}|^{2}\right)^{p\over 2}\leq
E\left(\sum_{i=1}^{n}|X_{i}|\right)^{p}\leq
B(p)E\left(\sum_{i=1}^{n}|X_{i}|^{2}\right)^{p\over 2}.$ (14)

  13. 13.

(Khintchine [10]) Let $X_{1},\dots,X_{n}$ be iid Rademacher random variables.
Then for any $\lambda_{1},\dots,\lambda_{n}\in\mathbb{C}$ and $p>0$, there
exist constants $A(p)$ and $B(p)$, dependent only on $p$, such that

$A(p)\left(\sum_{i=1}^{n}|\lambda_{i}|^{2}\right)^{1\over
2}\leq\left(E\left(\sum_{i=1}^{n}|\lambda_{i}X_{i}|\right)^{p}\right)^{1\over
p}\leq B(p)\left(\sum_{i=1}^{n}|\lambda_{i}|^{2}\right)^{1\over 2}.$ (15)

  14. 14.

(Rosenthal I [11]) Let $X_{1},\dots,X_{n}$ be independent nonnegative random
variables such that $\mathbb{E}X_{i}^{p}<\infty$ for a fixed $p\geq 1$,
$i=1,\dots,n$. Then there exist constants $A(p)$ and $B(p)$ dependent only on
$p$ such that

$\begin{array}[]{rl}A(p)\max\left\\{\sum_{i=1}^{n}EX_{i}^{p},\left(\sum_{i=1}^{n}EX_{i}\right)^{p}\right\\}\leq&\left(\sum_{i=1}^{n}EX_{i}\right)^{p}\\\
\\\
\leq&B(p)\max\left\\{\sum_{i=1}^{n}EX_{i}^{p},\left(\sum_{i=1}^{n}EX_{i}\right)^{p}\right\\}.\end{array}$
(16)

  15. 15.

(Rosenthal II) Let $X_{1},\dots,X_{n}$ be independent random variables such
that $\mathbb{E}X_{i}=0$ and $\mathbb{E}X_{i}^{p}<\infty$ for a fixed $p\geq
1$, $i=1,\dots,n$. Then there exist constants $A(p)$ and $B(p)$ dependent only
on $p$ such that

$\begin{array}[]{rl}A(p)\max\left\\{\sum_{i=1}^{n}E|X_{i}|^{p},\left(\sum_{i=1}^{n}EX_{i}^{2}\right)^{p\over
2}\right\\}&\leq\left|\sum_{i=1}^{n}EX_{i}\right|^{p}\\\ \\\ &\leq
B(p)\max\left\\{\sum_{i=1}^{n}E|X_{i}|^{p},\left(\sum_{i=1}^{n}EX_{i}^{2}\right)^{p\over
2}\right\\}.\end{array}$ (17)

  16. 16.

(Papadatos [12]) Let $X_{(1)},\dots,X_{(n)}$ be the order statistics of iid
random variables $X_{1},\dots,X_{n}$ with variance $\sigma^{2}$. Define
$G(x)=I_{x}(k,n+1-k)$ and
$\sigma_{n}^{2}(k)=\sup_{0<x<1}\left[{{G(x)(1-G(x))}\over{x(1-x)}}\right]$.
Then

$Var(X_{(k)})\leq\sigma_{n}^{2}(k)\sigma^{2}.$ (18)

  17. 17.

(Hürlimann Upper n–r [13]) Let $X_{(1)},\dots,X_{(n)}$ be the order statistics
of iid random variables $X_{1},\dots,X_{n}$. Define $\bar{X}={1\over
n}\sum_{i=1}^{n}X_{i}$, and the biased observed variance $S^{2}={1\over
n}\sum_{i=1}^{n}(X_{i}-\bar{X})^{2}$. Then for $r=0,\dots,n-1$, the average of
the upper n-r order statistics satisfies

${1\over{n-r}}\sum_{i=r+1}^{n}X_{(i)}\leq\bar{X}+S\sqrt{{r}\over{n-r}}.$ (19)

  18. 18.

(Hürlimann Average Excess [13]) Let $X_{(1)},\dots,X_{(n)}$ be the order
statistics of iid random variables $X_{1},\dots,X_{n}$. Define
$\bar{X}={1\over n}\sum_{i=1}^{n}X_{i}$, and the biased observed variance
$S^{2}={1\over n}\sum_{i=1}^{n}(X_{i}-\bar{X})^{2}$. Then for $r=0,\dots,n-1$,
the average excess of the upper $n-r$ order statistics conditioned on the
$r$th order statistic satisfies

${1\over{n-r}}\sum_{i=r+1}^{n}(X_{(i)}-X_{(r)})\leq
S{{n}\over{\sqrt{r(n-r)}}}.$ (20)

  19. 19.

(Hürlimann Stop-Loss Excess [13]) Let $X_{(1)},\dots,X_{(n)}$ be the order
statistics of iid random variables $X_{1},\dots,X_{n}$. Define
$\bar{X}={1\over n}\sum_{i=1}^{n}X_{i}$, and the biased observed variance
$S^{2}={1\over n}\sum_{i=1}^{n}(X_{i}-\bar{X})^{2}$. Define the rth stop-loss
statistics to be $SL(d_{r})=\sum_{i=1}^{n}(X_{(i)}-(n-r)d_{r})$ for
$d_{r}\in[X_{(r)},X_{(r+1)}]$. Then for $r=0,\dots,n-1$,

$SL(d_{r})\leq(n-r)\left[\bar{X}-d_{r}+S\sqrt{r\over{n-r}}\right].$ (21)

##  6 Concentration Inequalities

We may apply concentration inequalities to bound probabilities, often for
sequences of random variables. Such inequalities bound tail probabilities,
though the applicability and accuracy of such depends highly upon the local
and asymptotic behavior of the random variables of interest. Let $X$ be a
random variable.

###  6.1 Elementary to Moderate Concentration

  1. 1.

(Markov[1]) Suppose $X\geq 0$, and $\mathbb{E}[X]>0$. Then $\mathbb{P}(X\geq
t)\leq\frac{\mathbb{E}[X]}{t}$ for all $t>0$.

  2. 2.

(Chebychev [1]) For $t>0$, $\mathbb{P}[|X-EX|\geq
t]\leq{{Var(X)}\over{t^{2}}}$.

  3. 3.

($g$-Markov) Let $X\geq 0$, $\mathbb{E}[X]>0$. Then for increasing
$g:\mathbb{R}^{+}_{0}\to\mathbb{R}^{+}$,

$\mathbb{P}(X\geq t)\leq\frac{\mathbb{E}[g(X)]}{g(t)}.$ (22)

  4. 4.

(Normal I, Mill [1][14]) For $Z$ a standard normal, $\mathbb{P}[|Z|\geq
t]\leq\sqrt{{2}\over{\pi}}{e^{-t^{2}/2}\over{t}}$.

  5. 5.

(Normal II [1]) For $Z$ a standard normal, $\mathbb{P}[|Z|\geq
t]\geq\sqrt{{2}\over{\pi}}e^{-t^{2}/2}{t\over{1+t^{2}}}$.

  6. 6.

(Chernoff I [1][15]) Let $M_{X}(t)$,$-h\leq t\leq h$ be the moment-generating
function of $X$. Then $\mathbb{P}[X>a]\leq e^{-at}M_{X}(t)$, $-h\leq t\leq h$.

  7. 7.

(Chernoff II [1][15]) Let $M_{X}(t)$,$-h\leq t\leq h$ be the moment-generating
function of $X$. Then $\mathbb{P}[X\leq a]\leq e^{-at}M_{X}(t)$, $-h\leq t\leq
0$.

  8. 8.

(Chernoff Sum I [1]) Let $X_{1},\dots,X_{n}$ be iid, $X=\sum_{i=1}^{n}X_{i}$,
and $M_{X}(t)$,$-h\leq t\leq h$ be the moment-generating function of $X_{1}$.
. Then $\mathbb{P}[S>a]\leq e^{-at}[M_{X}(t)]^{n}$ for $0\leq t\leq h$.

  9. 9.

(Chernoff Sum II [1]) Let $X_{1},\dots,X_{n}$ be iid, $X=\sum_{i=1}^{n}X_{i}$,
and $M_{X}(t)$,$-h\leq t\leq h$ be the moment-generating function of $X_{1}$.
Then $\mathbb{P}[S\leq a]\leq e^{-at}[M_{X}(t)]^{n}$ for $-h\leq t\leq 0$.

  10. 10.

(Chernoff Mean [1]) Let $X_{1},\dots,X_{n}$ be iid, $\epsilon>0$,
$\bar{X_{n}}=\sum_{i=1}^{n}X_{i}$, $M_{U}(t)$, $-h_{U}\leq t\leq h_{U}$ be the
moment-generating function of $U=X_{1}-EX_{1}-\epsilon$, and $M_{V}(t)$,
$-h_{V}\leq t\leq h_{V}$ be the moment-generating function of
$V=-X_{1}+EX_{1}-\epsilon$. Then there exist for some $0<t_{U}\leq h_{U}$ and
$-h_{V}\leq t_{V}<0$ 111Such a $t_{U}$ and $t_{V}$ exist since $\mathbb{E}U<0$
and $\mathbb{E}V<0$, guaranteeing that $M_{U}$ and $M_{V}$ are decreasing in a
neighborhood of zero. such that

$\mathbb{P}[|\bar{X_{n}}-EX_{1}|>\epsilon]\leq 2c^{n},\\\ \text{ where
}c=\max\\{M_{U}(t_{U}),M_{V}(t_{V})\\}\in(0,1).$ (23)

###  6.2 Randomized Algorithms

See [15] for an introduction into randomized algorithms, whence we infer the
following inequalities.

  1. 1.

(Chernoff Poisson Trials I) Let $X_{i}$ be $n$ independent Poisson trials
222Each $X_{i}$ is a Bernoulli$(p_{i})$.. Let $X=\sum_{i=1}^{n}X_{i}$. Then
for $\delta>0$,

$\mathbb{P}[X\geq(1+\delta)EX]<\left({{e^{\delta}}\over{(1+\delta)^{1+\delta}}}\right)^{EX}.$
(24)

  2. 2.

(Chernoff Poisson Trials II) Let $X_{i}$ be $n$ independent Poisson trials.
Let $X=\sum_{i=1}^{n}X_{i}$. Then for $0<\delta\leq 1$,

$\mathbb{P}[X\geq(1+\delta)EX]<e^{-(EX)\delta^{2}/3}.$ (25)

  3. 3.

(Chernoff Poisson Trials III) Let $X_{i}$ be $n$ independent Poisson trials.
Let $X=\sum_{i=1}^{n}X_{i}$. Then for $R\geq gEX$,

$\mathbb{P}[X\geq R]<2^{-R}.$ (26)

  4. 4.

(Chernoff Poisson Trials IV) Let $X_{i}$ be $n$ independent Poisson trials.
Let $X=\sum_{i=1}^{n}X_{i}$. Then for $0<\delta<1$,

$\mathbb{P}[X\leq(1-\delta)EX]<\left({{e^{-\delta}}\over{(1-\delta)^{1-\delta}}}\right)^{EX}.$
(27)

  5. 5.

(Chernoff Poisson Trials V) Let $X_{i}$ be $n$ independent Poisson trials. Let
$X=\sum_{i=1}^{n}X_{i}$. Then for $0<\delta<1$,

$\mathbb{P}[X\leq(1-\delta)EX]<e^{-\delta^{2}EX/2}.$ (28)

  6. 6.

(Chernoff Rademacher I) Suppose $X_{1},\dots,X_{n}$ be iid such that
$\mathbb{P}[X_{i}=1]=\mathbb{P}[X_{i}=-1]={{1}\over{2}}$. If
$X=\sum_{i=1}^{n}X_{i}$ and $a>0$, then $\mathbb{P}[X\geq a]\leq
e^{{-a^{2}}\over{2n}}$.

  7. 7.

(Chernoff Rademacher II) Suppose $X_{1},\dots,X_{n}$ be iid such that
$\mathbb{P}[X_{i}=1]=\mathbb{P}[X_{i}=-1]={{1}\over{2}}$. If
$X=\sum_{i=1}^{n}X_{i}$ and $a>0$, then $\mathbb{P}[|X|\geq a]\leq
2e^{{-a^{2}}\over{2n}}$.

  8. 8.

(Chernoff Bernoulli I) Suppose $X_{1},\dots,X_{n}$ be iid
Bernoulli$\left({1\over 2}\right)$. If $X=\sum_{i=1}^{n}X_{i}$ and
$0<a<{n\over 2}$, then $\mathbb{P}\left[X\leq{n\over 2}-a\right]\leq
2e^{{-2a^{2}}\over{n}}$.

  9. 9.

(Chernoff Bernoulli II) Suppose $X_{1},\dots,X_{n}$ be iid
Bernoulli$\left({1\over 2}\right)$. If $X=\sum_{i=1}^{n}X_{i}$ and
$0<\delta<1$, then $\mathbb{P}\left[X\leq{n\over 2}(1-\delta)\right]\leq
2e^{{-n\delta^{2}}\over{2}}$.

  10. 10.

(Chernoff Bernoulli III) Suppose $X_{1},\dots,X_{n}$ be iid
Bernoulli$\left({1\over 2}\right)$. If $X=\sum_{i=1}^{n}X_{i}$ and $a>0$, then
$\mathbb{P}\left[X\geq{n\over 2}+a\right]\leq 2e^{{-2a^{2}}\over{n}}$.

  11. 11.

(Chernoff Bernoulli IV) Suppose $X_{1},\dots,X_{n}$ be iid
Bernoulli$\left({1\over 2}\right)$. If $X=\sum_{i=1}^{n}X_{i}$ and $\delta>0$,
then $\mathbb{P}\left[X\leq{n\over 2}(1+\delta)\right]\leq
2e^{{-n\delta^{2}}\over{2}}$.

###  6.3 Unimodality, and Misc.

  1. 1.

(Gauss [1]) Suppose $X$ follows a unimodal distribution with mode $\nu$, and
define $\tau^{2}=E(X-\nu)^{2}$. Then

$\mathbb{P}[|X-\nu|>\epsilon]\leq\begin{cases}{{4\tau^{2}}\over{9\epsilon^{2}}},&\epsilon\geq\sqrt{{4}\over{3}}\tau\\\
1-{{\epsilon}\over{\tau\sqrt{3}}},&\epsilon\leq\sqrt{{4}\over{3}}\tau\end{cases}$
(29)

  2. 2.

(Vysochanskiĭ-Petunin [1]) Suppose $X$ follows a unimodal distribution, and
define $\xi^{2}=E(X-\alpha)^{2}$ for arbitrary $\alpha$. Then

$\mathbb{P}\left[|X-\alpha|>\epsilon\right]\leq\begin{cases}{{4\xi^{2}}\over{9\epsilon^{2}}},&\epsilon\geq\sqrt{{8}\over{3}}\xi\\\
{{4\xi^{2}}\over{9\epsilon^{2}}}-{{1}\over{3}},&\epsilon\leq\sqrt{{8}\over{3}}\xi\end{cases}$
(30)

  3. 3.

(Hoeffding I [14]) Let $Y_{1},\dots,Y_{n}$ be independent observations such
that $\mathbb{E}Y_{i}=0$ and $a_{i}\leq Y_{i}\leq b_{i}$ for all $i$. If
$\epsilon>0$ and $t>0$, then

$\mathbb{P}\left[\sum_{i=1}^{n}Y_{i}\geq\epsilon\right]\leq
e^{-t\epsilon}\prod_{i=1}^{n}e^{t^{2}(b_{i}-a_{i})^{2}/8}$ (31)

  4. 4.

(Hoeffding II [14]) Let $X_{1},\dots,X_{n}$ be independent Bernoulli($p$). If
$\epsilon>0$, then

$\mathbb{P}\left[\left|\sum_{i=1}^{n}X_{i}-np\right|\geq\epsilon\right]\leq
2e^{-2n\epsilon^{2}}$ (32)

  5. 5.

(Saw) Suppose $X_{1},\dots,X_{n}$ are iid with finite first and second order
moments. Let $\bar{X}={{1}\over{n}}\sum_{i=1}^{n}X_{i}$ and
$S^{2}={{1}\over{n-1}}\sum_{i=1}^{n}(X_{i}-\bar{X})^{2}$. Let $k>0$,
$\nu(t)=\max\left\\{m\in\mathbb{N}|m<{{n+1}\over{t}}\right\\}$,
$\alpha(t)={{(n+1)(n+1-\nu(t))}\over{1+\nu(t)(n+1-\nu(t))}}$, and
$\beta={{n(n+1)k^{2}}\over{n-1+(n+1)k^{2}}}$. Then

$\mathbb{P}[|X-\bar{X}|\geq
kS]\leq\begin{cases}{{1}\over{n+1}}(\nu(\beta)-1)&\text{ if }\nu\text{ is odd
and }\beta>\alpha(\beta)\\\ {{1}\over{n+1}}\nu(\beta)&\text{
otherwise.}\end{cases}$ (33)

##  7 Kannan Combinatoric Inequalities

Kannan [16] furnishes an array of inequalities helpful in analyzing graphs and
other objects of combinatoric import.

  1. 1.

(Chromatic Number) Let $G(\\{1,\dots,n\\},P)$ be a random graph with edge
probabilities $P=\left(p_{ij}\right)$. The chromatic number $\chi=\chi(G)$ is
the least number of colors necessary to color $G$ such that no two vertices
sharing an edge receive the same color. Let
$p={{\sum_{i,j}p_{ij}}\over{n\choose 2}}$. Then there exists a constant $c>0$
such that for $t\in(0,n\sqrt{p})$,

$\mathbb{P}[|\chi(G)-E\chi(G)|\geq t]\leq e^{{-ct^{2}}\over{n\sqrt{p}\log
n}}.$ (34)

  2. 2.

(Johnson-Lindenstrauss Random Projection) Suppose $k\leq n$, and we pick
$V_{1},\dots,V_{k}$ uniformly randomly from the surface of the unit ball in
$\mathbb{R}^{n}$. Then for $\epsilon\in(0,1)$, there exist constants
$c_{1},c_{2}>0$ such that

$\mathbb{P}\left[\left|\sum_{i=1}^{k}v_{i}^{2}-{{k}\over{n}}\right|\geq{{\epsilon
k}\over{n}}\right]\leq c_{1}e^{-c_{2}\epsilon^{2}k}$ (35)

  3. 3.

(Random Projection) Suppose $m$ is an even positive integer and
$X_{1},\dots,X_{n}$ are real-valued random observations satisfying the strong
negative correlation principle. That is, for all $i$,
$\mathbb{E}X_{i}(X_{1}+\dots+X_{i-1})^{l}<0$ when $l<m$ is odd and
$\mathbb{E}(X_{i}^{l}|X_{1}+\dots+X_{i-1})\leq\left({{n}\over{m}}\right)^{{l-2}\over{2}}l!$
for $l\leq m$ even. Define constants $\\{M_{i,l}\\}$, $\\{K_{i,l}\\}$, and
$\\{L_{i,l}\\}$ such that $\mathbb{E}(X_{i}^{l}|X_{1}+\dots+X_{i-1})\leq
M_{i,l}$, each $K_{i,l}$ is an indicator variable on the typical case of the
conditional expectation where $\mathbb{P}[K_{i,l}]=1-\delta_{i,l}$, and
$\mathbb{E}(X_{i}^{l}|X_{1}+\dots+X_{i-1},K_{i,l})\leq L_{i,l}$ for
$l=2,4,\dots,m$ and $i=1,\dots,n$. Finally, let $X=\sum_{i=1}^{n}X_{i}$. Then

$\begin{array}[]{rl}\mathbb{E}X^{m}\leq&(cm)^{{{m}\over{2}}+1}\left(\sum_{l=1}^{m/2}{{m^{1-{{1}\over{l}}}\over{l^{2}}}}\left(\sum_{i=1}^{n}L_{i,2l}\right)^{1\over
l}\right)^{m\over 2}\\\ \\\
+&(cm)^{m+2}\sum_{l=1}^{m/2}{{1}\over{nl^{2}}}\sum_{i=1}^{n}\left(nM_{i,2l}\delta_{i,2l}^{2/(m-2l+2)}\right)^{2\over{ml}}.\end{array}$
(36)

  4. 4.

(Bin Packing) Suppose $Y_{1},\dots,Y_{n}$ are iid from a discrete distribution
of $r$ atoms each with probability at least $1\over\log n$ and
$\mathbb{E}Y_{1}\leq{{1}\over{r^{2}\log n}}$. Let $f(Y_{1},\dots,Y_{n})$ be
the minimum number of unit capacity bins necessary to pack the
$Y_{1},\dots,Y_{n}$ items. Then there exist constants $c_{1},c_{2}>0$ such
that if $t\in(0,n[(EY_{i})^{3}+Var(Y_{i})])$, then

$\mathbb{P}[|f-Ef|\geq t+r]\leq
c_{1}e^{{-c_{2}t^{2}}\over{n[(EY_{i})^{3}+Var(Y_{i})]}}.$ (37)

  5. 5.

(Strong Negative Correlation) Suppose $m$ is an even positive integer, and
$X_{1},\dots,X_{n}$ are real-valued random observations satisfying the strong
negative correlation principle. That is, for all $i$,
$\mathbb{E}X_{i}(X_{1}+\dots+X_{i-1})^{l}<0$ when $l<m$ is odd and
$\mathbb{E}(X_{i}^{l}|X_{1}+\dots+X_{i-1})\leq\left({{n}\over{m}}\right)^{{l-2}\over{2}}l!$
for $l\leq m$ even. Then

$\mathbb{E}\left(\sum_{i=1}^{n}X_{i}\right)^{m}\leq(24mn)^{{m}\over{2}}.$ (38)

  6. 6.

(Hamiltonian Tour) Suppose $Y_{1},\dots,Y_{n}$ are sets of points generated
independently and respectively from $n$ subsquares of size
${{1}\over{\sqrt{n}}}\times{1\over\sqrt{n}}$ of the unit square, and there
exists a constant $c\in(0,1)$ such that $\mathbb{P}[|Y_{i}|]\leq c$ for all
$i$. Suppose further that for $\epsilon>0$, and $l\in\\{1,\dots,{m\over
2}\\}$, $\mathbb{E}|Y_{i}|^{l}\leq[O(l)]^{(2-\epsilon)l}$. Finally, suppose
$f(Y_{1},\dots,Y_{n})$ is the length of the shortest Hamiltonian tour through
$Y_{1}\cup\dots\cup Y_{n}$. Then

$\mathbb{E}[f(Y_{1},\dots,Y_{n})-Ef(Y_{1}\dots,Y_{n})]^{m}\leq(cm)^{{m}\over{2}}.$
(39)

  7. 7.

(MST) Suppose $Y_{1},\dots,Y_{n}$ are sets of points generated independently
and respectively from $n$ subsquares of size
${{1}\over{\sqrt{n}}}\times{1\over\sqrt{n}}$ of the unit square, and there
exists a constant $c\in(0,1)$ such that $\mathbb{P}[|Y_{i}|]\leq c$ for all
$i$. Suppose further that for $\epsilon>0$, and $l\in\\{1,\dots,{m\over
2}\\}$, $\mathbb{E}|Y_{i}|^{l}\leq[O(l)]^{(2-\epsilon)l}$. Finally, suppose
$f(Y_{1},\dots,Y_{n})$ is the length of a minimum spanning tree of
$Y_{1}\cup\dots\cup Y_{n}$. Then

$E[f(Y_{1},\dots,Y_{n})-Ef(Y_{1}\dots,Y_{n})]^{m}\leq(cm)^{{m}\over{2}}.$ (40)

  8. 8.

(Random Vector) Suppose $\mathbf{Y}=(Y_{1},\dots,Y_{n})$ is a random vector
such that for a fixed $k\leq n$,
$\mathbb{E}(Y_{i}^{2}|Y_{1}^{2},\dots,Y_{i}^{2})$ is a nondecreasing function
of $Y_{1}^{2}+\dots+Y_{i-1}^{2}$ for $i=1,\dots,k$ and for even $l\leq k$,
there exists a $c>0$ such that
$\mathbb{E}(Y_{i}^{l}|Y_{1}^{2},\dots,Y_{i-1}^{2})\leq\left({{cl}\over{n}}\right)^{l\over
2}$. Then for any even $m\leq k$,

$\mathbb{E}\left(\sum_{i=1}^{k}Y_{i}^{2}-EY_{i}^{2}\right)^{m}\leq\left({{\sqrt{cmk}}\over{n}}\right)^{m}.$
(41)

##  8 Means and Variances II

The inequalities to follow furnish mechanisms for the analysis of
interdependence, Markov chains, vectors, and graphs, among others.

  1. 1.

(Talagrand [17]) Let $\mathbf{X}$ be chosen randomly uniformly from
$\\{-1,1\\}^{n}$, let $A$ be a convex subset of $\mathbb{R}^{n}$,
$A_{t}=\\{\mathbf{p}\in\mathbb{R}^{n}|dist(\mathbf{p},A)\leq t\\}$. Then there
exists $c>0$ such that $\mathbb{P}[\mathbf{X}\in A]\mathbb{P}[\mathbf{X}\notin
A_{t}]\leq e^{-ct^{2}}$ for all $t>0$.

  2. 2.

(Talagrand Large Deviation [17]) Let $\mathbf{X}$ be chosen randomly uniformly
from $\\{-1,1\\}^{n}$, $V$ be a $d$-dimensional subspace of $\mathbb{R}^{n}$.
Then there exist constants $c,C>0$ such that
$\mathbb{P}[|dist(X,V)-\sqrt{n-d}|\geq t]\leq Ce^{-ct^{2}}$ for all $t>0$.

  3. 3.

(Gaussian for Lipschitz [17]) Let $\mathbf{X}$ be an $n$-dimensional random
vector such that each $X_{i}$ is an independent $n(0,1)$ variable. If
$f:\mathbb{R}^{d}\to\mathbb{R}$ is a Lipschitz function with scale constant
1333A Lipschitz function $f$ satisfies $|f(x)-f(y)|\leq M||x-y||$ for all
$x,y\in domain(f)$., then there exists a constant $c>0$ such that
$\mathbb{P}[|f(\mathbf{X})-Ef(\mathbf{X})|\geq t]\leq e^{-ct^{2}}$ for all
$t>0$.

  4. 4.

(Azuma [18]) Suppose $X_{0},\dots,X_{n}$ is a martingale
($\mathbb{E}(X_{i}|X_{1},\dots,X_{i-1})=X_{i-1}$ for $i=1,\dots,n$); suppose
further that $X$ is $\mathbf{c}$-Lipschitz ($|X_{i}-X_{i-1}|\leq c_{i}$ for
$i=1,\dots,n$, $c\in\mathbb{R}^{n}$ positive); then

$\mathbb{P}[X_{n}-X_{0}\geq\lambda]\leq
2e^{{-\lambda^{2}}\over{2\sum_{i=1}^{n}c_{i}^{2}}}.$ (42)

  5. 5.

(Bennett [2]) Let $X_{1},\dots,X_{n}$ be independent random variables of zero
mean such that $\mathbb{P}[X_{i}\leq 1]=1$. Let $h(u)=(1+u)\log(1+u)-u$ for
$u\geq 0$ and $\sigma^{2}={{1}\over{n}}\sum_{i=1}^{n}Var(X_{i})$. Then for
$t>0$,

$\mathbb{P}\left[\sum_{i=1}^{n}X_{i}>t\right]\leq
e^{-n\sigma^{2}h\left({{t}\over{n\sigma^{2}}}\right)}.$ (43)

  6. 6.

(Bernstein [2]) Let $X_{1},\dots,X_{n}$ be independent random variables of
zero mean such that $\mathbb{P}[X_{i}\leq 1]=1$. Let
$\sigma^{2}={{1}\over{n}}\sum_{i=1}^{n}Var(X_{i})$. Then for $\epsilon>0$,

$\mathbb{P}\left[{{1}\over{n}}\sum_{i=1}^{n}X_{i}>\epsilon\right]\leq
e^{{-n\epsilon^{2}}\over{2(\sigma^{2}+\epsilon/3)}}.$ (44)

  7. 7.

(McDiarmid Bounded Differences I [19]) Let $X_{1},\dots,X_{n}$ be independent
random variables each whose domain is $\chi$. If $f:\chi^{n}\to\mathbb{R}^{n}$
is a function such that for all $\mathbf{x}\in\chi^{n}$, $y\in\chi$, and
$i\in\\{1,\dots,n\\}$, there exists a constant $c_{i}>0$ such that
$|f(\mathbf{x})-f(x_{1},\dots,x_{i-1},y,x_{i+1},\dots,x_{n})|\leq c_{i}$, then

$\mathbb{P}[f(\mathbf{X})-Ef(\mathbf{X})\geq t]\geq
e^{{-t^{2}}\over{\sum_{i=1}^{n}c_{i}^{2}}}\text{ for all $t>0$}.$ (45)

  8. 8.

(McDiarmid Bounded Differences II [19]) Let $X_{1},\dots,X_{n}$ be independent
random variables each whose domain is $\chi$. If $f:\chi^{n}\to\mathbb{R}^{n}$
is a function such that for all $\mathbf{x}\in\chi^{n}$, $y\in\chi$, and
$i\in\\{1,\dots,n\\}$, there exists a constant $c_{i}>0$ such that
$|f(\mathbf{x})-f(x_{1},\dots,x_{i-1},y,x_{i+1},\dots,x_{n})|\leq c_{i}$, then

$\mathbb{P}[f(\mathbf{X})-Ef(\mathbf{X})\leq-t]\geq
e^{{-t^{2}}\over{\sum_{i=1}^{n}c_{i}^{2}}}\text{ for all $t>0$.}$ (46)

  9. 9.

(Dvoretzky Kiefer Wolfowitz I [20]) Suppose $X_{1},\dots,X_{n}$ are iid
univariate random variables following cdf $F$. Let $F_{n}(x)={1\over
n}\sum_{i=1}^{n}1_{X_{i}\leq x}$ be the empirical distribution. Then for
$\epsilon>\sqrt{{1\over 2n}\log 2}$,

$\mathbb{P}\left[\sup_{x\in\mathbb{R}}(F_{n}(x)-F(x))>\epsilon\right]\leq
e^{-2n\epsilon^{2}}.$ (47)

  10. 10.

(Dvoretzky Kiefer Wolfowitz II [20]) Suppose $X_{1},\dots,X_{n}$ are iid
univariate random variables following cdf $F$. Let $F_{n}(x)={1\over
n}\sum_{i=1}^{n}1_{X_{i}\leq x}$ be the empirical distribution. Then for
$\epsilon>0$,

$\mathbb{P}\left[\sup_{x\in\mathbb{R}}|F_{n}(x)-F(x)|>\epsilon\right]\leq
2e^{-2n\epsilon^{2}}.$ (48)

  11. 11.

(Etemadi Differing Means [21]) Let $X_{1},\dots,X_{n}$ be random variables
with common support. Let $S_{k}=\sum_{i=1}^{k}X_{k}$ be the $k$th partial sum.
Then for $\epsilon>0$,

$\mathbb{P}\left[\max_{1\leq k\leq n}|S_{k}|\geq 3\epsilon\right]\leq
3\max_{1\leq k\leq n}\mathbb{P}\left[|S_{k}|\geq\epsilon\right].$ (49)

  12. 12.

(Etemadi Shared Means [21]) Let $X_{1},\dots,X_{n}$ be random variables with
common support and equal means. Let $S_{k}=\sum_{i=1}^{k}X_{k}$ be the $k$th
partial sum. Then for $\epsilon>0$,

$\mathbb{P}\left[\max_{1\leq k\leq
n}|S_{k}|\geq\epsilon\right]\leq{27\over\epsilon^{2}}Var(S_{n}).$ (50)

  13. 13.

(Kolmogorov [22]) Let $X_{1},\dots,X_{n}$ be independent random variables with
common support such that $\mathbb{E}X_{i}=0$ and $Var(X_{i})<\infty$ for
$i=1,\dots,n$. Let $S_{k}=\sum_{i=1}^{k}X_{k}$ be the $k$th partial sum. Then
for $\epsilon>0$,

$\mathbb{P}\left[\max_{1\leq k\leq
n}|S_{k}|\geq\epsilon\right]\leq{1\over\epsilon^{2}}\sum_{i=1}^{n}Var(X_{i}).$
(51)

  14. 14.

(Chebychev Multidimensional [23]) Let $\mathbf{X}\in\mathbb{R}^{n}$ be a
random vector with covariance matrix
$V=E\left[(\mathbf{X}-E\mathbf{X})(\mathbf{X}-E\mathbf{X})^{T}\right]$. Then
for $t>0$,

$\mathbb{P}\left[\sqrt{(\mathbf{X}-E\mathbf{X})^{T}V^{-1}(\mathbf{X}-E\mathbf{X})}\right]\leq{n\over
t^{2}}.$ (52)

  15. 15.

(Leguerre Samuelson [24]) Let $X_{1},\dots,X_{n}$ be random variables with
common support, and define $\bar{X}={1\over n}\sum_{i=1}^{n}X_{i}$ and
$S^{2}={1\over{n-1}}\sum_{i=1}^{n}(X_{i}-\bar{X})^{2}$. Then for $i=1,\dots,n$
with probability one,

$\bar{X}-S\sqrt{n-1}\leq X_{i}\leq\bar{X}+S\sqrt{n-1}.$ (53)

  16. 16.

(LeCam [25]) Suppose $X_{1},\dots,X_{n}$ are independent binomial random
variables with respective success parameters $p_{1},\dots,p_{n}$. Letting
$\lambda_{n}=\sum_{i=1}^{n}p_{i}$, we have

$\sum_{k=0}^{\infty}\left|\mathbb{P}\left[\sum_{i=1}^{n}X_{i}=k\right]-{\lambda_{n}^{k}e^{-\lambda_{n}}\over{k!}}\right|\leq
2\sum_{i=1}^{n}p_{i}^{2}.$ (54)

  17. 17.

(Doob Martingale [26]) Let $\mathbf{X}\in\mathbb{R}^{n}$ be a martingale
($\mathbb{E}(X_{i}|X_{1},\dots,X_{i-1})=X_{i-1}$ for $i=2,\dots,n$). Then for
$C>0$, $p\geq 1$,

$\mathbb{P}\left[\sup_{1\leq i\leq n}X_{i}\geq
C\right]\leq{{EX_{n}^{p}}\over{C^{p}}}.$ (55)

## References

  * [1] G. Casella and R. Berger, Statistical Inference.  Duxbury, 2002.
  * [2] S. Boucheron, O. Bousquet, and G. Lugosi, Concentration inequalities, Advanced Lectures in Machine Learning.  Springer, 2004.
  * [3] L. Wasserman, “Lecture on probability inequalities.” https://www.stat.cmu.edu/~larry/=stat705/Lecture2.pdf, 2008.
  * [4] J. Duchi, “Probability bounds.” https:////www.cs.berkeley.edu/~jduchi/projects/probability_bounds.pdf.
  * [5] C. D. C Vasile, “A better bound on the variance,” American Mathematical Monthly (Mathematical Association of America), 2000.
  * [6] C. Vasile, “Two generalizations of popovicius inequality,” Crux Mathematicorum, 2001.
  * [7] D. Chapman and H. Robbins, “Minimum variance estimation without regularity assumptions,” Annals of Mathematical Statistics, 1951.
  * [8] J. C. A.Dembo, T.M. Cover, “Information-theoretic inequalities,” IEEE Trans. Inform. Theory, 1991.
  * [9] J. Marcinkiewicz and A. Zygmund, “Sur les foncions independantes,” Fund. Math, 1937.
  * [10] T. Wolff, “Lectures on harmonic analysis,” AMS, 2003.
  * [11] H. Rosenthal, “On the subspaces of $l_{p}$ 2 spanned by sequences of independent random variables,” Israel J. Math, 1970.
  * [12] N. Papadatos, “Maximum variance of order statistics.” www.ism.ac.jp/editsec/aism/pdf/04710185.pdf, 1994.
  * [13] W. Húrlimann, “Generalized algebraic bounds on order statistics functions, with application to reinsurance and catastrophe.” www.actuaries.org/ASTIN/Colloquia/PortoCervo/Huerlimann.pdf, 1970.
  * [14] L. Wasserman, All of Statistics.  Springer, 2004.
  * [15] M. Mitzenmacher and E. Upfal, Probability and Computing.  Cambridge, 2005.
  * [16] R. Kannan, “A new probability inequality using typical moments and concentration results.” www.crm.umontreal.ca/CARP09/pdf/kannan.pdf, 2009\.
  * [17] T. Tao, “Talagrand’s concentration inequality.” http://terrytao.wordpress.com/2009/06/09/talagrands-concentrationinequality, 2009\.
  * [18] L. L. F. Chung, “Complex graphs and networks,” AMS, 2006.
  * [19] P. Bartlett, “Lecture on concentration inequalities.” https://www.cs.berkeley.edu/~bartlett/courses/281b-sp08/13.pdf, 2008.
  * [20] A. Dvoretzky, J. Kiefer, and J. Wolfowitz, “Asymptotic minimax character of the sample distribution function and of the classical multinomial estimator,” Annals of Mathematical Statistics, 1956.
  * [21] N. Etemadi, “On some classical results in probability theory,” Sankhyā Ser, 1985.
  * [22] P. Billingsley, Probability and Measure.  John Wiley, 1995.
  * [23] L. Wasserman, “High-dimensional probability an introduction with applications in data science.” https://www.math.uci.edu/~rvershyn/, 2020.
  * [24] P. Samuelson, “How deviant can you be?,” Journal of the American Statistical Association, 1968.
  * [25] L. LeCam, “An approximation theorem for the poisson binomial distribution,” Pacific Journal of Mathematics, 1960.
  * [26] D. Revuz and M. Yor, Continuous martingales and Brownian motion.  Springer, 1999.


# Predicting the Initial Conditions of the Universe using a Deterministic
Neural Network

Vaibhav Jindal1,2,*
<EMAIL_ADDRESS>&Albert Liang1,3,*
<EMAIL_ADDRESS>Aarti Singh1
<EMAIL_ADDRESS>&Shirley Ho4,5,6
<EMAIL_ADDRESS>&Drew Jamieson7
<EMAIL_ADDRESS>
###### Abstract

Finding the initial conditions that led to the current state of the universe
is challenging because it involves searching over an intractable input space
of initial conditions, along with modeling their evolution via tools such as
N-body simulations which are computationally expensive. Recently, deep
learning has emerged as a surrogate for N-body simulations by directly
learning the mapping between the linear input of an N-body simulation and the
final nonlinear output from the simulation, significantly accelerating the
forward modeling. However, this still does not reduce the search space for
initial conditions. In this work, we pioneer the use of a deterministic
convolutional neural network for learning the reverse mapping and show that it
accurately recovers the initial linear displacement field over a wide range of
scales ($<1$-$2\%$ error up to nearly $k\simeq 0.8$ – $0.9\text{ Mpc}^{-1}h$),
despite the one-to-many mapping of the inverse problem (due to the divergent
backward trajectories at smaller scales). Specifically, we train a V-Net
architecture, which outputs the linear displacement of an N-body simulation,
given the nonlinear displacement at redshift $z=0$ and the cosmological
parameters. The results of our method suggest that a simple deterministic
neural network is sufficient for accurately approximating the initial linear
states, potentially obviating the need for the more complex and
computationally demanding backward modeling methods that were recently
proposed.

11footnotetext: Machine Learning Department, Carnegie Mellon
University22footnotetext: Cohesity33footnotetext: Two Sigma
Investments44footnotetext: Center for Computational Astrophysics, Flatiron
Institute55footnotetext: Department of Physics & Center for Data Science, New
York University66footnotetext: Department of Astrophysical Sciences, Princeton
University77footnotetext: Max Planck Institute for Astrophysics**footnotetext:
Work done while at Carnegie Mellon University

##  1 Introduction

The evolution of our universe can be uniquely determined by its initial
conditions and the laws of physics. To understand this cosmic history,
astrophysicists use a large number of surveys Amendola et al. (2018); Spergel
et al. (2015) and simulations Bagla (2002); Villaescusa-Navarro et al. (2020).
These simulations compute the gravitational evolution of a system of N-body
particles given a set of nearly uniform and typically Gaussian initial
conditions, representing the early universe. These simulations, though, come
with a substantial computational cost and demand an extensive investment of
both time and computational resources.

In recent years, deep-learning techniques have been shown to be extremely
helpful in accelerating the forward modeling process He et al. (2019);
Jamieson et al. (2022) by several orders of magnitude. These deep-learning
models learn the mapping between pairs of inputs and outputs from numerical
N-body simulations and act as fast and accurate approximators for these
simulators.

Figure 1: Qualitative comparison of the $x,y,\text{and }z$ displacements for a
$128\times 128$ slice of particles from a linear field sampled using the
training parameters and the corresponding linear field predicted by our
inverse model.

The problem of inferring the initial state that generates a specific redshift
$z=0$ state of the universe is an inverse problem and poses a more difficult
challenge. Inverse problems are hard as they require a search over an
intractable space of all possible input configurations, and typically involve
a one-to-many mapping if learned as a reverse mapping. Standard neural
networks are one-to-one mappings and are thus not expected to work well in
these problems. Sampling approaches such as Hamiltonian Monte Carlo used by
Bayesian Origin Reconstruction of Galaxies (BORG) Jasche and Wandelt (2013);
Jasche and Lavaux (2019) are computationally prohibitive, requiring thousands
of CPU hours to generate a single posterior sample. One could resort to more
complex generative neural networks such as the recently proposed diffusion
models Legin et al. (2023). However, they are significantly more difficult and
expensive to train compared to deterministic neural networks. Moreover, as we
show in this paper, they are potentially an overkill to this problem as the
distribution of initial conditions is typically Gaussian, where a simple
deterministic neural network like ours already works surprisingly well.

Importantly, cosmological simulations are often deterministic, and therefore
they are reversible in principle. The one-to-many backward problem arises
primarily due to numerical and computational errors which get exacerbated only
at small scales which are dominated by nonlinear effects, causing divergent
backward trajectories. This motivates the approach we demonstrate here:
training a standard deterministic neural network to learn the reverse map and
output the initial states of the N-body simulations using the final states as
input.

We show that despite the one-to-many nature of the reverse mapping at small
scales, a simple deterministic neural network can do a surprisingly excellent
job of predicting the initial states not only at large scales but even down to
relatively small scales ($k>0.1\ \mathrm{Mpc}^{-1}\,h$) where the nonlinear
dynamics of gravitational clustering become important. In fact, our model
continues to have $<1-2\%$ error down to $k\simeq 0.8$ – $0.9\
\mathrm{Mpc}^{-1}\,h$. Our results empirically motivate the use of neural
networks as approximate inverse-mapping black boxes that could directly
generate reliable initial states for a given output state, which could then be
used as starting points for more fine-grained sampling-based inverse modeling
methods.

##  2 Background

Consider an N-body system with particles distributed on a uniform grid with
positions $\mathbf{q}$. Let $\mathbf{\Psi}_{ZA}(\mathbf{q})$ be their linear
Zel’dovich approximation (ZA) approximation at redshift $z=0$ (current time).
Thus, the final positions of the particles when they evolve linearly is

$\displaystyle\mathbf{x}_{lin}(\mathbf{q})=\mathbf{q}+\mathbf{\Psi}_{ZA}(\mathbf{q}).$
(1)

Let the final nonlinear displacement of the particle initially at grid site
$\mathbf{q}$ be $\mathbf{\Psi}_{NL}(\mathbf{q})$. Thus, the final positions of
the particles at redshift $z=0$ under nonlinear evolution is

$\displaystyle\mathbf{x}_{nonlin}(\mathbf{q})=\mathbf{q}+\mathbf{\Psi}_{NL}(\mathbf{q}).$
(2)

In this work, we investigate the problem of predicting the linear displacement
field at redshift $z=0$, given the non-linear displacement field and the
cosmological parameters.

##  3 Methodology

Figure 2: Qualitative comparison of the $x,y,\text{and }z$ displacements for a
$128\times 128$ slice of particles from the original nonlinear field and the
nonlinear field generated from the linear field predicted by our inverse
model. The nonlinear field is generated from the forward modeling emulator
Jamieson et al. (2022). The slice shown here is the same as the one shown in
Figure 1 for a one-to-one comparison.

We train a convolutional neural network (CNN) that takes the nonlinear
displacement field $\mathbf{\Psi}_{NL}(\mathbf{q})$ at redshift $z=0$ and the
value of $\Omega_{m}$ as inputs and predicts the linear displacement field
$\mathbf{\Psi}_{ZA}(\mathbf{q})$ at redshift $z=0$. We directly use the V-Net
architecture used in Jamieson et al. (2022) and train it using 100 pairs of
nonlinear and linear displacement fields. In terms of the training procedure,
our method is almost identical to Jamieson et al. (2022), with the main
difference being that we pass the nonlinear displacement field as the input to
our model and ask it to predict the linear displacement field. One of the key
advantages of using a simple deterministic V-Net, instead of a generative
model such as a diffusion model, is the reduced computational complexity
during both training and inference phases. Deterministic networks do not
involve complex stochastic sampling processes, eliminating the need for
numerous forward passes which makes them significantly faster and more
resource-efficient than the generative models.

For our experiments, we train our model using simulations of $128^{3}$
uniformly distributed particles in a square box with a side-length of $250\
\mathrm{Mpc}/h$. This corresponds to a Nyquist wavenumber of
$k=1.608~{}\mathrm{Mpc}^{-1}~{}h$, the theoretical limit beyond which we can’t
trust the predictions of any model for this setting. For the training data, we
randomly generated 100 linear fields for a fixed set of cosmological
parameters
($\Omega_{m}=0.300,\Omega_{b}=0.050,h=0.700,n_{s}=0.965,\sigma_{8}=0.799$).
Since running N-body simulations on these initial conditions are too
computationally expensive, we use the emulator by Jamieson et al. (2022) to
generate their corresponding nonlinear displacement fields as our model’s
training targets, which are already highly accurate for our purpose.

The architecture of our model involves three downsampling and upsampling
components each and provides a field-of-view of $96^{3}$. That is, a focal
particle’s initial displacement is predicted based on its environment out to
its $48^{\mathrm{th}}$ neighbors on the initial particle grid, corresponding
to a distance of $93.75~{}\ \mathrm{Mpc}/h$. This finite field-of-view has a
benefit: the evolution of the system on large scales is accurately described
by linear theory, so the V-Net model preserves this linear evolution on scales
larger than the field-of-view while allowing for nonlinear evolution at
smaller (medium range of) scales.

On very small scales, the particles clustered tightly into dark matter halos
where their orbits become complicated and difficult to predict. This small-
scale clustering imposes a resolution limit on the inverse mapping, making it
a one-to-many mapping as numerical errors and floating point precision make
the neural network model unable to fully encode the detailed textures of this
virialized motion. This limitation is also present in the forward model
Jamieson et al. (2022) and the diffusion model Legin et al. (2023), which
tends to make halos more diffuse on small scales than in the simulations,
blurring the details of these sharp structures. For the inverse mapping, the
initial linear displacements are blurred for particles that end up inside of
halos, limiting the accuracy of the inverse model predominantly on these very
small scales as shown in Section 4.3.

Sections 4.1, 4.2, and 4.3 show the in-distribution performance of our model
on unseen pairs of fields generated from the forward direction emulator
Jamieson et al. (2022) with the same cosmological parameters as its training
data. We also evaluate the out-of-distribution (OOD) performance of our model
on the Quijote simulation suite Villaescusa-Navarro et al. (2020) in Section
4.4.

##  4 Results and Analysis

We evaluate our method’s performance both qualitatively and quantitatively
with a variety of analyses and statistics.

###  4.1 Qualitative Analysis

Figure 1 shows the $x,y,\text{and }z$ direction displacements for a $128\times
128$ slice of the linear displacement field and the corresponding linear field
predicted by our inverse model. The original linear field was sampled using
the cosmological parameters of the training data. Qualitatively, the
predictions of our model match very well with the original linear field that
we wanted to predict.

For further evaluation, we used the forward-direction emulator again to
generate the nonlinear field when fed the predicted linear field and compared
it with the original nonlinear field in Figure 2. We find these slices match
very closely with insignificant residuals.

###  4.2 One-Point Statistics

Figure 3: Distribution of the displacements of particles for a given linear
field and the corresponding linear field predicted by our model. The
distribution has been calculated by considering the $x,y,\text{and }z$
displacements of $128^{3}$ particles. Relative error denotes the relative
errors in probability density for different bins.

The initial conditions of the simulation are set up in Fourier space, with
each mode of the displacement field drawn from a random Gaussian distribution
with a variance determined by the linear power spectrum $P(k)$, which is
determined by the cosmological parameters. This construction yields a
coordinate-space displacement field that is also Gaussian, so its statistics
are uniquely determined by the two-point correlation function, which is simply
the Fourier transform of the power spectrum. To demonstrate that we have
accurately recovered the initial conditions, we must show that the output of
our model has both the correct power spectrum and that its statistical
distribution is Gaussian.

We plot the histogram of the probability density of the displacements of the
particles for the original linear field and the one predicted by our model
(Figure 3). We expect the distribution of displacements to match
$\mathcal{N}(0,5.275)$ for the simulation setting with $128^{3}$ particles in
a box size of 250 Mpc/$h$. Specifically, the variance of displacements along
the $i^{\mathrm{th}}$ Cartesian direction is given by:

$\displaystyle\sigma_{i}^{2}=\int\frac{\mathrm{d}k^{3}}{(2\pi)^{3}}\frac{(k^{i})^{2}}{k^{4}}P(k),$
(3)

where the integral is over all wave vectors in Fourier space,
$k\equiv|\vec{k}|$ is the magnitude of the wave vector and $k^{i}$ is its
$i^{\mathrm{th}}$ component. We numerically evaluate this integral on a
Fourier space grid with the same dimensions as the initial simulation grid.

From Figure 3 we see that the statistics of our model output agree well with
the expected Gaussian distribution. The bin counts also match the particular
realization from this distribution of the target data out to displacements of
$\sim 10\ \mathrm{Mpc}/h$, or 2$\sigma_{i}$. Extremely large displacements
indicate a particle either flowing outwards in a rare, extremely underdense
environment or inwards towards a rare, high-density peak. Based on the
residuals, we see that the tails of the distribution predicted by the model
are somewhat smaller than the target data, indicating the model misplaces
these particles. This is unsurprising due both to the rarity of these
trajectories and to the fact that these particles are the most affected by
extreme non-linearities in their environments, which exacerbates the one-to-
many problem.

###  4.3 Two-Point Correlation Comparison

(a) Linear Fields

(b) Nonlinear Field

Figure 4: Two-point correlation comparison between (a) the original linear
field and the linear field predicted by our model, and, (b) the original
nonlinear field and the nonlinear field generated from the predicted linear
field given by the inverse model.

The displacement power spectrum for a displacement field $\mathbf{\Psi}$ for
wavenumber $k$ is defined as

$\displaystyle
P(k)=\sum_{i\in\\{x,y,z\\}}\langle\mathbf{\Psi}_{i}(k)\mathbf{\Psi}_{i}(k)\rangle.$
(4)

Using this, we define the transfer function as

$\displaystyle T(k)=\sqrt{P(k)},$ (5)

and the correlation coefficient as

$\displaystyle r(k)=\frac{P_{pred\times
true}(k)}{\sqrt{P_{pred}(k)P_{true}(k)}},$ (6)

where $P_{pred}(k)$ is the displacement power spectrum of the predicted field,
$P_{true}(k)$ is the ground truth power spectrum, and $P_{pred\times true}(k)$
is the cross power spectrum between the predicted and the ground truth fields.
Furthermore, we now define the transfer function fractional error,

$\displaystyle\frac{\Delta
T(k)}{T(k)}=\sqrt{\frac{P_{pred}(k)}{P_{true}(k)}}-1,$ (7)

to measure the discrepancy between amplitudes of the predicted and the true
fields. We also define stochasticity,

$\displaystyle 1-r^{2}(k)=1-\frac{P^{2}_{pred\times
true}(k)}{{P_{pred}(k)P_{true}(k)}},$ (8)

to capture the excess fraction of correlation in the prediction of our model
that cannot be accounted for in the target data. For an ideal match between
the target and the predicted field, the values of both these quantities should
be exactly zero. Figure 4(a) shows the performance of our model in terms of
these quantities. We see that from large scales down to scales where $k\simeq
0.8$ – $0.9$ $\mathrm{Mpc}^{-1}~{}h$, the model achieves 1-2% percent-level
accuracies for both the transfer functions and stochasticities. Note that non-
linearities become important at scales where $k>0.1~{}\mathrm{Mpc}^{-1}~{}h$,
so the model is able to accurately learn the inverse mapping even in the
moderately nonlinear regime for in-distribution fields.

(a) 0th percentile
($\Omega_{m}=0.296,\Omega_{b}=0.067,h=0.523,n_{s}=1.091,\sigma_{8}=0.806$)

(b) 20th percentile
($\Omega_{m}=0.311,\Omega_{b}=0.067,h=0.673,n_{s}=0.993,\sigma_{8}=0.977$)

(c) 40th percentile
($\Omega_{m}=0.373,\Omega_{b}=0.054,h=0.869,n_{s}=0.922,\sigma_{8}=0.678$)

(d) 60th percentile
($\Omega_{m}=0.412,\Omega_{b}=0.036,h=0.840,n_{s}=0.942,\sigma_{8}=0.680$)

(e) 80th percentile
($\Omega_{m}=0.491,\Omega_{b}=0.069,h=0.518,n_{s}=0.932,\sigma_{8}=0.820$)

(f) 100th percentile
($\Omega_{m}=0.497,\Omega_{b}=0.044,h=0.805,n_{s}=0.910,\sigma_{8}=0.600$)

Figure 5: Power spectra comparison between the linear fields and the inverse
model predictions for the 0th, 20th, 40th, 60th, 80th, and 100th percentile
OOD Quijote simulation data points.

To further test the reliability of our model, we generated the nonlinear
displacement field from our predicted linear field by using the forward
direction emulator. Since the mapping from the nonlinear displacement field to
the linear displacement field is one-to-many, it becomes critical to see that
this field matches the actual nonlinear field. Figure 4(b) shows the power
spectra comparison between these two nonlinear displacement fields. We again
see a good match for large to medium scales ($k<0.5~{}\mathrm{Mpc}^{-1}~{}h$).

###  4.4 Out-Of-Distribution Evaluation

Given that our model is trained on simulations generated by a neural network
emulator Jamieson et al. (2022) with fixed cosmological parameters, there is a
legitimate concern about its ability to generalize to actual N-body
simulations with different sets of cosmological parameters. To assess this
out-of-distribution (OOD) performance, we conduct a series of experiments on
simulations from the Quijote suite Villaescusa-Navarro et al. (2020).

The Quijote suite provides 2000 linear and nonlinear fields, each consisting
of $512^{3}$ particles that are uniformly distributed in a cube of side length
$1000\ \mathrm{Mpc}/h$. To quantify the dissimilarity between these
simulations and our training data, we rank them based on the sum of their
relative percentage differences in $\Omega_{m}$ and $\sigma_{8}$ from our
training values, since these two parameters have the most significant impact
on the simulated distributions. This dissimilarity metric is then used to
evaluate the model’s performance on different percentiles, with the 100th
percentile simulation being the most OOD. Notably, our model’s performance is
unaffected by changes in the box size, as long as the mean particle density
remains constant.

To evaluate the model’s performance on OOD Quijote simulation data, we
qualitatively compare the $x,y,\text{and }z$ displacements of a $512\times
512$ slice from the linear and nonlinear fields, similar to Section 4.1. The
slices for the 0th percentile and the 20th percentile simulations are
presented in Figures 8 and 11 respectively. Additionally, the one-point
statistics for these simulations are provided in Figures 6 and 9, and the two-
point correlation comparisons are presented in Figures 7 and 10 respectively.

To examine how the model’s performance decays as the nonlinear input gradually
gets more OOD, we plot the two-point correlations for a range of percentiles
in Figure 5 and Figure 12. As expected, for both the predicted linear field
and the regenerated nonlinear field, the model performs excellently for the
0th and 20th percentiles but gradually gets worse for higher percentiles.

##  5 Conclusion

In this work, we pioneer using a CNN to predict the initial linear field of an
N-body simulation given the final nonlinear field and the cosmological
parameters. We show that despite the many-to-one nature of the inverse
mapping, our CNN can still recover the linear fields for a wide range of
scales, even including the smaller scales where the nonlinear physics of
gravitational clustering becomes important. In addition, we empirically
demonstrate that our model generalizes reasonably well to OOD cosmological
parameters. This suggests that neural networks can be used as approximate,
inverse-mapping black boxes for generating trustworthy initial states for more
fine-grained sampling-based inverse modeling methods. Overall, our work
demonstrates that despite being much simpler and computationally cheaper than
other approaches such as BORG and diffusion models, a deterministic neural
network is already capable of reconstructing surprisingly accurate initial
conditions of the universe.

In future works, we plan to explore sampling-based methods (e.g. Hamiltonian
Monte Carlo Radford (2012), Active Learning Ren et al. (2021), etc.) with
initial states proposed by our model. We expect that these methods will refine
the initial conditions, achieving high accuracy at even smaller scales.
Another direction for future work is to enhance our model to additionally
output uncertainty estimates. This will involve uncertainty quantification
(UQ) methods such as optimizing the Gaussian negative log-likelihood loss Nix
and Weigend (1994), re-architecting our model as a Bayesian neural network
Goan and Fookes (2020), or augmenting our model with conformal predictions
Angelopoulos and Bates (2022).

## References

  * Amendola et al. (2018) Luca Amendola et al.  Cosmology and fundamental physics with the euclid satellite.  _Living Reviews in Relativity_ , 21(1), apr 2018.  doi: 10.1007/s41114-017-0010-3.  URL https://doi.org/10.1007%2Fs41114-017-0010-3.
  * Angelopoulos and Bates (2022) Anastasios N. Angelopoulos and Stephen Bates.  A gentle introduction to conformal prediction and distribution-free uncertainty quantification, 2022.
  * Bagla (2002) J. S. Bagla.  TreePM: A code for cosmological n-body simulations.  _Journal of Astrophysics and Astronomy_ , 23(3-4):185–196, dec 2002.  doi: 10.1007/bf02702282.  URL https://doi.org/10.1007%2Fbf02702282.
  * Goan and Fookes (2020) Ethan Goan and Clinton Fookes.  Bayesian neural networks: An introduction and survey.  In _Case Studies in Applied Bayesian Data Science_ , pages 45–87. Springer International Publishing, 2020.  doi: 10.1007/978-3-030-42553-1_3.  URL https://doi.org/10.1007%2F978-3-030-42553-1_3.
  * He et al. (2019) Siyu He, Yin Li, Yu Feng, Shirley Ho, Siamak Ravanbakhsh, Wei Chen, and Barnabás Póczos.  Learning to predict the cosmological structure formation.  _Proceedings of the National Academy of Sciences_ , 116(28):13825–13832, 2019.  doi: 10.1073/pnas.1821458116.
  * Jamieson et al. (2022) Drew Jamieson, Yin Li, Renan Alves de Oliveira, Francisco Villaescusa-Navarro, Shirley Ho, and David N. Spergel.  Field level neural network emulator for cosmological n-body simulations, 2022.  URL https://arxiv.org/abs/2206.04594.
  * Jasche and Lavaux (2019) J. Jasche and G. Lavaux.  Physical bayesian modelling of the non-linear matter distribution: New insights into the nearby universe.  _Astronomy & Astrophysics_, 625:A64, may 2019.  doi: 10.1051/0004-6361/201833710.  URL https://doi.org/10.1051%2F0004-6361%2F201833710.
  * Jasche and Wandelt (2013) Jens Jasche and Benjamin D. Wandelt.  Bayesian physical reconstruction of initial conditions from large-scale structure surveys.  _Monthly Notices of the Royal Astronomical Society_ , 432(2):894–913, apr 2013.  doi: 10.1093/mnras/stt449.  URL https://doi.org/10.1093%2Fmnras%2Fstt449.
  * Legin et al. (2023) Ronan Legin, Matthew Ho, Pablo Lemos, Laurence Perreault-Levasseur, Shirley Ho, Yashar Hezaveh, and Benjamin Wandelt.  Posterior sampling of the initial conditions of the universe from non-linear large scale structures using score-based generative models, 2023.
  * Nix and Weigend (1994) D.A. Nix and A.S. Weigend.  Estimating the mean and variance of the target probability distribution.  In _Proceedings of 1994 IEEE International Conference on Neural Networks (ICNN’94)_ , volume 1, pages 55–60 vol.1, 1994.  doi: 10.1109/ICNN.1994.374138.
  * Radford (2012) Neal Radford.  Mcmc using hamiltonian dynamics.  _Handbook of Markov Chain Monte Carlo_ , 06 2012.  doi: 10.1201/b10905-6.
  * Ren et al. (2021) Pengzhen Ren, Yun Xiao, Xiaojun Chang, Po-Yao Huang, Zhihui Li, Brij B. Gupta, Xiaojiang Chen, and Xin Wang.  A survey of deep active learning, 2021.
  * Spergel et al. (2015) D. Spergel et al.  Wide-field infrarred survey telescope-astrophysics focused telescope assets wfirst-afta 2015 report, 2015.  URL https://arxiv.org/abs/1503.03757.
  * Villaescusa-Navarro et al. (2020) Francisco Villaescusa-Navarro et al.  The quijote simulations.  _The Astrophysical Journal Supplement Series_ , 250(1):2, 2020.  doi: 10.3847/1538-4365/ab9d82.

##  Appendix A Appendix

###  A.1 Results for the 0th percentile OOD setting of cosmological parameters
($\Omega_{m}=0.296,\Omega_{b}=0.067,h=0.523,n_{s}=1.091,\sigma_{8}=0.806$)

Figure 6: Distribution of the displacements of particles for the 0th
percentile OOD Quijote simulation linear field and the corresponding linear
field predicted by our inverse model. The distribution has been calculated by
considering the $x,y,\text{and }z$ displacements of $512^{3}$ particles
separately. Relative error denotes the relative errors in probability density
for different bins. The theoretical distributions for this setting is
$\mathcal{N}(0,6.193)$ (Equation 3).

(a) Power spectra comparison for linear field

(b) Power spectra comparison for nonlinear field

Figure 7: Power spectra comparison for the 0th percentile OOD Quijote
simulation data point. (a) Comparison between the original linear field and
the linear field predicted by our inverse model. (b) Comparison between the
original nonlinear field and the nonlinear field predicted by the forward
emulator Jamieson et al. [2022] for the linear field predicted by our inverse
model.

(a) Slices from Linear Fields

(b) Slices from Nonlinear Field

Figure 8: Qualitative comparison of the $x,y,\text{and }z$ displacements for a
$512\times 512$ slice of particles for the 0th percentile OOD Quijote
simulation data point. (a) Slice from the original linear field and the
corresponding linear field predicted by our inverse model. (b) Slice from the
original nonlinear field and the nonlinear field predicted by the forward
emulator Jamieson et al. [2022] for the linear field predicted by our inverse
model.

###  A.2 Results for the 20th percentile OOD simulation from the Quijote suite
($\Omega_{m}=0.311,\Omega_{b}=0.067,h=0.673,n_{s}=0.993,\sigma_{8}=0.977$)

Figure 9: Distribution of the displacements of particles for the 20th
percentile OOD Quijote simulation linear field and the corresponding linear
field predicted by our inverse model. The distribution has been calculated by
considering the $x,y,\text{and }z$ displacements of $512^{3}$ particles
separately. Relative error denotes the relative errors in probability density
for different bins. The theoretical distributions for this setting is
$\mathcal{N}(0,7.159)$ (Equation 3).

(a) Power spectra comparison for linear field

(b) Power spectra comparison for nonlinear field

Figure 10: Power spectra comparison for the 20th percentile OOD Quijote
simulation data point. (a) Comparison between the original linear field and
the linear field predicted by our inverse model. (b) Comparison between the
original nonlinear field and the nonlinear field predicted by the forward
emulator Jamieson et al. [2022] for the linear field predicted by our inverse
model.

(a) Slices from Linear Fields

(b) Slices from Nonlinear Field

Figure 11: Qualitative comparison of the $x,y,\text{and }z$ displacements for
a $512\times 512$ slice of particles for the 20th percentile OOD Quijote
simulation data point. (a) Slice from the original linear field and the
corresponding linear field predicted by our inverse model. (b) Slice from the
original nonlinear field and the nonlinear field predicted by the forward
emulator Jamieson et al. [2022] for the linear field predicted by our inverse
model.

###  A.3 Power Spectra Analysis for Nonlinear Fields in OOD settings

(a) 0th percentile
($\Omega_{m}=0.296,\Omega_{b}=0.067,h=0.523,n_{s}=1.091,\sigma_{8}=0.806$)

(b) 20th percentile
($\Omega_{m}=0.311,\Omega_{b}=0.067,h=0.673,n_{s}=0.993,\sigma_{8}=0.977$)

(c) 40th percentile
($\Omega_{m}=0.373,\Omega_{b}=0.054,h=0.869,n_{s}=0.922,\sigma_{8}=0.678$)

(d) 60th percentile
($\Omega_{m}=0.412,\Omega_{b}=0.036,h=0.840,n_{s}=0.942,\sigma_{8}=0.680$)

(e) 80th percentile
($\Omega_{m}=0.491,\Omega_{b}=0.069,h=0.518,n_{s}=0.932,\sigma_{8}=0.820$)

(f) 100th percentile
($\Omega_{m}=0.497,\Omega_{b}=0.044,h=0.805,n_{s}=0.910,\sigma_{8}=0.600$)

Figure 12: Power spectra comparison between the actual nonlinear field and the
nonlinear field generated by the forward emulator for the linear field
predicted by our inverse model for the 0th, 20th, 40th, 60th, 80th, and 100th
percentile OOD Quijote simulation data points.