All Questions
Tagged with pr.probability inequalities
346 questions
37
votes
3
answers
3k
views
An entropy inequality
Let $X,Y$ be probability measures on $\{1,2,\dots,n\}$, and set $K=\sum_i\sqrt{X(i)Y(i)}$ so that $Z:=\frac{1}{K}\sqrt{XY}$ is also a probability measure on $\{1,2,\dots,n\}$. How can we prove the ...
- 11.4k
36
votes
3
answers
4k
views
the following inequality is true，but I can't prove it
The inequality is
\begin{equation*}
\sum_{k=1}^{2d}\left(1-\frac{1}{2d+2-k}\right)\frac{d^k}{k!}>e^d\left(1-\frac{1}{d}\right)
\end{equation*}
for all integer $d\geq 1$. I use computer to verify ...
- 363
26
votes
3
answers
3k
views
An $L^0$ Khintchine inequality
Suppose that $\epsilon_1,\epsilon_2,\ldots$ are IID random variables with the Bernoulli distribution $\mathbb{P}(\epsilon_n=\pm1)=1/2$, and $a_1,a_2,\ldots$ is a real sequence with $\sum_na_n^2=1$. ...
- 17.1k
24
votes
1
answer
1k
views
A Rademacher ‘root 7’ anti-concentration inequality
Let $r_1,r_2,r_3,\dotsc$ be an IID sequence of Rademacher random variables, so that $\mathbb P(r_n=\pm1)=1/2$, and $a_1,a_2,\dotsc$ be a real sequence with $\sum_na_n^2=1$. For $S=\sum_na_nr_n$, does ...
- 17.1k
21
votes
7
answers
2k
views
Identities and inequalities in analysis and probability
Usually, at the heart of a good limit theorem in probability theory is at least one good inequality – because, in applications, a topological neighborhood is usually defined by inequalities. Of course,...
21
votes
2
answers
2k
views
A strange variant of the Gaussian log-Sobolev inequality
Let $\phi : \mathbb{R}^d \to \mathbb{R}$ be a convex function, and assume that it grows at most linearly at infinity for simplicity. Denote by $\gamma$ the standard Gaussian measure on $\mathbb{R}^d$, ...
- 562
20
votes
2
answers
6k
views
Constants in the Rosenthal inequality
Let $X_1,\ldots,X_n$ be independent with $\mathbf{E}[X_i] = 0$ and $\mathbf{E}[|X_i|^t] < \infty$ for some $t \ge 2$. Write $X = \sum_{i=1}^n X_i$. Then we have the family of "Rosenthal-type ...
- 201
19
votes
1
answer
1k
views
Zinn's "doubling" conjecture on weighted sums of independent Rademacher random variables
Let $a_1,\dots,a_n$ be real numbers such that $a_1^2+\dots+a_n^2=1$. Let $\eta_1,\dots,\eta_n$ be independent Rademacher random variables (r.v.'s), so that $P(\eta_i=\pm1)=\frac12$ for all $i$. Let $S:...
- 128k
18
votes
3
answers
3k
views
Entropy and total variation distance
Let $X$, $Y$ be discrete random variables taking values within the same set of $N$ elements. Let the total variation distance $|P-Q|$ (which is half the $L_1$ distance between the distributions of $P$ ...
- 20.2k
16
votes
3
answers
708
views
An inequality for two independent identically distributed random vectors in a normed space
Suppose that $X$ and $Y$ are independent identically distributed random vectors in a separable Banach space $B$. Does it always follow that $E\|X-Y\|\le E\|X+Y\|$?
Some background information on ...
- 128k
16
votes
6
answers
3k
views
A normal distribution inequality
Let $n(x) := \frac{1}{\sqrt{2\pi}} e^{-\frac{x^2}{2}}$, and $N(x) := \int_{-\infty}^x n(t)dt$. I have plotted the curves of the both sides of the following inequality. The graph shows that the ...
- 2,239
16
votes
1
answer
743
views
Inequalities for marginals of distribution on hyperplane
Let $H = \{ (a,b,c) \in \mathbb{Z}_{\geq 0}^3 : a+b+c=n \}$. If we have a probability distribution on $H$, we can take its marginals onto the $a$, $b$ and $c$ variables and obtain three probability ...
- 156k
15
votes
1
answer
703
views
Information inequalities
What are the feasible $2^n$-tuples of entropies $h(S) := H(X_{i_1},\dots,X_{i_{|S|}})$ where $X_1,\dots,X_n$ are discrete random variables with some (unknown) joint probability distribution as $S=\{...
- 19.7k
15
votes
0
answers
749
views
Prove $\int_{0}^{\infty} \cos(\omega x) \exp(-x^{\alpha}) \, {\rm d} x \ge {\alpha^2 \sqrt{\pi} \over 8} \exp \left( -\frac{\omega^2}{4} \right)$
I would like to prove that
$$\int_{0}^{\infty} \cos(\omega x) \exp(-x^{\alpha}) \, {\rm d} x \ge
{\alpha^2 \sqrt{\pi} \over 8} \exp \left( -\frac{\omega^2}{4} \right)$$
for any $\omega > 0$ and $...
- 178
14
votes
2
answers
2k
views
Is the conditional expectation a contraction in weak $\mathbb L^p$ spaces?
Let $(\Omega,\mathcal F,\mu)$ be a probability space. It is well-known that if $\mathcal A$ is a sub-$\sigma$-algebra of $\mathcal F$, $p\geqslant 1$ and $X$ is an element of $\mathbb L^p$ which takes ...
- 3,958
13
votes
2
answers
1k
views
A comprehensive list of random walk inequalities?
I am interested in finding a comprehensive list of all noticeable random walk inequalities.
ie. $S_n = \sum_{k\leq n} X_i$ for i.i.d symmetric $X_i$
I can only seem to find books/papers that list ...
- 231
13
votes
2
answers
1k
views
Probability vector $p$ majorizes its normalized entropy vector $\small \frac{-p\log p}{H(p)}$
I guess the following inequality
$$ \sum_{i=1}^n g \left (\frac{-p_i \log p_i}{H(\boldsymbol{p})} \right ) \le \sum_{i=1}^n g (p_i)$$
holds for any continuous convex function $g$ and any probability ...
- 303
13
votes
4
answers
535
views
Alignment of random points
Whenever I draw randomly about ten points, I see that there will be always 3 points that are "almost" collinear. This observation leads me to considering the following questions:
Question 1: Suppose $...
- 131
13
votes
3
answers
1k
views
A property of unimodal sequences
It is well-known that $(-1)^j \sum_{i=0}^j (-1)^i\binom{n}{i} \geq 0$. This inequality can be used to prove Bonferroni's inequalities for example. Recently I noticed that a similar inequality applies ...
- 619
13
votes
2
answers
656
views
Random matrix with given singular values
Let $\sigma_1\geq\sigma_2\geq...\geq\sigma_n\geq0$ be any deterministic sequence of positive real numbers such that $\sum_{i=1}^n\sigma_i^2=1$. Let
$$D=diag\{\sigma_1,...,\sigma_n\}\in\mathbb{R}^{n\...
- 1,495
12
votes
3
answers
549
views
A probabilistic angle inequality
Conjecture: There is a universal constant $c$ such that for any fixed nonzero real vector $q$ of any dimension $n$ and any random vector $p$ of the same dimension $n$ with independent components ...
- 3,873
12
votes
1
answer
525
views
An inequality about unit vector orthogonal to $(1,1,...,1)$
Does there exist a constant $\alpha>0$ such that the following holds?
$$\liminf_{n\to\infty}\inf_{x\in\mathbb{R}^n, \sum_{i=1}^nx_i^2=1, \sum_{i=1}^nx_i=0}\frac{\sum_{i<j, |i-j|\leq\frac{n}{4}}(...
- 1,495
11
votes
2
answers
934
views
Decoupling inequality/counterexample
I am embarrassed to be stuck on this seemingly simple question.
Suppose that $X,Y$ are mean-zero real-valued random variables and $\tilde X,\tilde Y$ are their "independent copies": $\tilde ...
- 6,541
11
votes
1
answer
676
views
Entropy arguments used by Jean Bourgain
My question comes from understanding a probabilistic inequality in Bourgain's paper on Erdős simiarilty problem: Construction of sets of positive measure not containing an affine image of a given ...
- 196
10
votes
3
answers
803
views
Discrete entropy of the integer part of a random variable
Let $X$ be a real valued random variable. Of course, the integer part $\lfloor X \rfloor$ of $X$ is a discrete random variable taking values in $\mathbb{Z}$. We can therefore define its discrete ...
- 2,306
10
votes
3
answers
4k
views
Extension of the Azuma-Hoeffding inequality (when the differences are bounded with large probability)
Let $(X_i)$ be a super-martingale and suppose their differences are bounded ''with high probability'', that is
$$\mathbb{P}(\exists\,i=1,\dots,n\text{ s.t. }|X_i-X_{i-1}|>c_i) \,\leq\, \epsilon$$
...
- 223
9
votes
1
answer
395
views
An inequality on the simplex involving $x^x$
Is anything known about the behavior of the function $$f(x)=\prod_{i=1}^n x_i^{x_i}$$ on the standard simplex, i.e. the set $\{x\in\mathbb{R}^n:\sum_{i=1}^n x_i=1, x_i\geq0\}$? I ask because I have ...
- 93
9
votes
3
answers
868
views
Rosenthal like inequality for weak $\mathbb L^p$-norms
Let $p$ be a real number greater than $1$. It is well known (see Hall and Heyde's Martingale limit theory and its applications, Theorem 2.10) that there exists a constant $C_p$ such that if $(X_i)_{i=...
- 3,958
9
votes
5
answers
1k
views
estimate the error term in CLT
Let $X_m = \frac{1}{\sqrt{m}}\sum_{k=1}^m Z_k$ where $Z_k$ are iid equally likely on $\{\pm 1\}$. Then $X_m$ convergens to $X \sim \mathcal{N}(0,1)$ in distribution by CLT.
Let $f$ be a smooth ...
- 1,839
9
votes
1
answer
700
views
An inequality for positive definite matrices
Let $K$ and $K^\prime$ positive definite $n \times n$ matrices, such that for all vectors $f \ge 0$ with nonnegative coordinates we have
$$\sum_{i,j} K_{ij} f_i f_j \le \sum_{ij} K^\prime_{ij} f_i ...
- 4,010
9
votes
2
answers
519
views
The fraction of the sphere a fixed distance from a subspace
The following problem has a beautiful geometric interpretation in terms of the proportion of points on the Euclidean sphere in $\mathbb{R}^d$ that lie at least a certain distance away from a $k$-...
- 91
8
votes
3
answers
595
views
Jensen-like inequality for random matrix: $\Bbb E[\det X^2]\ge\det\Bbb E[X^2]$
Let $X\in M_n(\Bbb R)$ be a random matrix with iid elements following a continuous distribution.
What are the necessary and sufficient conditions for $$\Bbb E[\det X^2]\ge\det\Bbb E[X^2]$$ to hold? Is ...
- 1,459
8
votes
1
answer
718
views
Relative Entropy and p-norm
I asked this question on StackExchange but could not get any answer, therefore, I am posting it here.
I am currently reading the book "A Dynamical Approach to Random Matrix Theory". The ...
- 371
8
votes
2
answers
4k
views
Lower bounds on Kullback-Leibler divergence
This was originally a question on Cross Validated.
Are there any (nontrivial) lower bounds on the Kullback-Leibler divergence $KL(f\Vert g)$ between two measures / densities?
Informally, I am ...
- 710
8
votes
2
answers
486
views
concentration inequality for entropy from sample
Consider a measure $\mu$ on a finite set, and let $x_1, \ldots, x_n$ be i.i.d samples from $\mu$. Then the expression $S_n = -\frac{1}{n} \sum_{i=1}^n \log \mu(x_i)$ converges by a.s. to the entropy $...
- 83
8
votes
3
answers
628
views
Expected distance between two uniform points in distinct rectangles
Are there any good approximations (especially upper bounds) for the quantity $E(\|X_1-X_2\|$), where each $X_i$ is uniformly distributed in a rectangle $[a_i,b_i]\times[c_i,d_i]$? It does not appear ...
- 4,049
8
votes
2
answers
889
views
Stochastic dominance between (products of) binomials
Suppose $p \leq q \leq 1/2$, and $n,m\geq 1$ two integers. Let $X\sim \mathrm{Bin}(n,p)$, $Y\sim \mathrm{Bin}(m,p)$ and $X'\sim \mathrm{Bin}(n,q)$, $Y'\sim \mathrm{Bin}(m,q)$ be independent.
Is it ...
- 1,372
8
votes
2
answers
2k
views
Median and mean of the sample mean of i.i.d. log-normal
Let $y:=\frac1n\sum_{i=1}^n x_i$, where $\{x_i\}_{i=1}^n$ is a set of i.i.d. random variables, and every $x_i$ has a lognormal distribution $x_i \sim\text{Lognormal}(\mu,\sigma^2)$. Let $\text{Med}[y]$...
- 2,239
8
votes
1
answer
416
views
Expectation inequality for sampling without replacement
Is the following proposition correct?
$X_1, X_2, X_3$ are uniformly at random sampled from a finite set $\mathcal X$ without replacement.
$f : \mathcal X^2 \rightarrow \mathbb R_{\ge0}$ is symmetric:...
- 83
7
votes
1
answer
736
views
How is the Gronwall lemma used in this paper?
Let $(X_t, t \ge 0)$ be a $\mathbb R^d$-valued stochastic process. Let $\lambda>0$. Assume we have $\mathbb E [|X_0|^2] < \infty$ and
$$
\mathbb E [|X_t|^2] - \mathbb E [|X_0|^2] \le -2 \lambda \...
- 835
7
votes
3
answers
3k
views
expected value of squared infinity norm of vector of iid gaussians
Given a random vector
\begin{equation}
x=(x_1, \ldots, x_n)
\end{equation}
with independent and identically distributed entries $x_i \sim \mathcal{N}(0,\sigma^2)$, I would like to find a lower ...
- 237
7
votes
1
answer
556
views
A variation on the Borel–Cantelli lemma theme
Let $X,X_0,X_1,\dots$ be nonnegative independent identically distributed (i.i.d.) random variables. Let
\begin{equation*}
E:=\bigcap_{n\ge0}B_n,
\end{equation*}
where
\begin{equation*}
B_n:=\...
- 128k
7
votes
2
answers
392
views
On a von Bahr–Esseen-type inequality for pairwise independent zero-mean random variables
For $p\in(1,2)$, let $C_p$ be the smallest constant factor $C$ in the von Bahr–Esseen-type inequality
\begin{equation}\label{eq:pair}\tag{1}
E\Bigl\lvert\sum_{j=1}^n X_j\Bigr\rvert^p\le C\sum_{j=1}...
- 128k
7
votes
1
answer
265
views
Is this simple-looking moment inequality true?
Let $p \ge 1$ be an integer. Does there exist a constant $C_p$ such that for every random variable $X \ge 0$,
$$
\mathbb{E} \left[ \left(X - \mathbb{E} \left[ X \right] \right)^{2p} \right] \le C_p \...
- 562
7
votes
1
answer
583
views
Inequality for the maximum of Gaussian variables
Let $X=(X_1,\dots,X_n)$ and $Y=(Y_1,\dots,Y_n)$ be centered Gaussian vectors
with variance matrix $\Gamma_X$ and $\Gamma_Y$. We assume that the matrix
$\Gamma_Y-\Gamma_X$ is positive definite. Is it ...
- 103
7
votes
1
answer
499
views
Moments of a random variable and of its conditional expectation
Let $X$ be a bounded random variable with $\mathbb{E}X=0$. Since $X$ is bounded, all its moments exist. Let $\mathcal{G}$ be any $\sigma$-field and let $Y:=\mathbb{E}[X|\mathcal{G}].$ I am interested ...
- 1,269
7
votes
2
answers
816
views
Rademacher average based Hoeffding Inequality
I am following these lecture notes:
Given the i.i.d. $\mathcal{Z}$-valued random variables $Z_1,\dotsc,Z_m$ and $\mathcal{G}$ is a set of bounded functions $g\colon \mathcal{Z}\to[a,b]$.
Corollary 2....
- 619
6
votes
2
answers
2k
views
Is there a name for this theorem?
I wonder if there is a name or reference for the following fact. It is not the proof I am looking for.
Let $s_1, s_2, ...,s_n$ be non-negative real numbers ordered in a non-increasing way. Let $b_1,...
- 371
6
votes
2
answers
2k
views
Is there a universal bound for this ratio of expectations?
Let $X$ and $Y$ be two zero-mean independent and identically distributed random variables. Is there a bound for the following ratio,
$$\frac{\mathbb{E}[|X+Y|]}{\mathbb{E}[|X|+|Y|]}=\frac{\mathbb{E}[|...
- 287
6
votes
4
answers
1k
views
Improvement of Chernoff bound in Binomial case
We know from Chernoff bound
$P\bigg(X \leq (\frac{1}{2}-\epsilon)N\bigg)\leq e^{-2\epsilon^2 N}$ where
$X$ follows Binomial($N, \frac{1}{2}$).
If I take $N=1000, \epsilon=0.01$, the upper bound is ...
- 191