All Questions
Tagged with pr.probability inequalities
346 questions
0
votes
2
answers
280
views
Bounds tighter than the additive Chernoff
Additive Chernoff
Suppose $X_1, \ldots, X_n$ are i.i.d. random variables, taking values in $\{0,1\}$. Let $p=\mathrm{E}\left[X_i\right]$ and $\varepsilon>0$.
\begin{gather*}
\operatorname{Pr}\left(\...
- 484
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 ...
- 97
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
4
votes
1
answer
320
views
Sub-Gaussian random variables and convex ordering
Suppose that $X$ is a $1$-sub-Gaussian real-valued random variable, i.e. for all $t \in \mathbf{R}$, it holds that $\log \mathbf{E} \exp \left( t X \right) \leqslant \frac{1}{2} t^2 $.
Does there ...
- 1,724
2
votes
1
answer
150
views
Normalized concentration inequality for empirical CDF (iid sum)
Consider the empirical and population CDF,
$$
F_n(t) = \frac{1}{n} \sum_{i=1}^n 1\{X_i \leq t\} \quad \mbox{and} \quad
F(t) = \mathbb{E} [F_n(t)],
$$
where above $X_1, \dots, X_n$ are iid, real-...
CommunityBot
- 1
1
vote
1
answer
195
views
Reference request: Inequalities involving convex sets and Gaussian variables stated in a paper by Talagrand
I'm looking for references for two facts that are stated without proof in the paper:
Talagrand, M., Are all sets of
positive measure essentially convex?, Lindenstrauss, J. (ed.) et al.,
Geometric ...
- 128k
4
votes
0
answers
155
views
Comparing the slackness of Jensen's inequality for some coupled random variables
Let $f:\mathbb{R} \to \mathbb{R}$ be convex and $X,Y$ be random variables with a coupling such that $\mathbb{E}[Y\mid X=x] = x$. A straightforward application of Jensen's inequality gives that $\...
- 141
3
votes
1
answer
205
views
Bound on an integral representing a difference of two relative entropies
Let $ f : [0,1] \to \mathbb{R} $ be a function satisfying: 1.) $ |f(x)| \leqslant a $ for some $ a < 1 $, and 2.) $ \int_0^1 f(x) {\mathrm d}x = 0 $. I would like to know whether the following ...
- 503
2
votes
0
answers
164
views
Log Sobolev inequality for log concave perturbations of uniform measure
Suppose $\Omega$ is a convex bounded open set of $\mathbb{R}^n$ (I would be happy with just $\Omega$ as the $n$-dimensional cube). Let $\mu$ be the uniform measure on $\Omega$ and consider the ...
- 873
5
votes
1
answer
516
views
Bounding the variance of a truncated Gaussian random variable
Suppose $X_1, X_2, X_3 \sim N(0, 1)$ are three independent standard normal random variables. I am interested in showing that:
$$\text{Var}[X_2\mid X_2 \geq X_1 - a, X_1 \leq X_3 + b] < 1,$$
where ...
2
votes
1
answer
199
views
Gaussian Poincare inequality in $1$ dimensions together with localization issue
Let $d\mu$ be a Gaussian measure on $\mathbb{R}$ with the center $a \in \mathbb{R}$ and variance $1$.
Let $B(a,r) \subset \mathbb{R}$ be the interval $[a-r,a+r]$.
Then, for any smooth mapping $f : \...
- 5,474
5
votes
0
answers
159
views
Log Sobolev inequality uniform in parameters
Fix a positive integer $N$. For $\theta \in [0,2\pi]$, set $\sigma_k(\theta) :=(\cos(k\theta),\sin(k\theta)) \in S^1$ for each integer $1\leq k\leq N$. Now for vectors $x_1,\ldots,x_N\in \mathbb{R}^2$,...
- 873
1
vote
0
answers
68
views
A one-sided/monotone version of min/max-stable distributions -- does this have a name?
In a couple of papers I am working on (in random graph theory) I have encountered the following property of certain probability distributions, which I will describe shortly, and I am wondering if this ...
- 5,429
0
votes
1
answer
182
views
Deducing norm concentration from MGF bounds
Suppose that $X$ is a centered, $\mathbf{R}^d$-valued random variable such that for all $t \in \mathbf{R}^d$, there holds the bound $$\log \mathbf{E} \left[ \exp \langle t, X \rangle \right] \leqslant ...
- 2,183
1
vote
1
answer
113
views
How to upper bound the difference between these two Gaussian-like densities?
$
\DeclareMathOperator*{\argmax}{arg\,max}
\DeclareMathOperator*{\argmin}{arg\,min}
\DeclareMathOperator*{\cov}{cov}
\DeclareMathOperator*{\supp}{supp}
\DeclareMathOperator*{\dom}{dom}
\newcommand{\...
- 128k
3
votes
1
answer
346
views
Simple anticoncentration bound for binomially distributed variable
The following question, which arose during my research, seems deceivingly simple to me, but I could not find any elegant and formal argument.
For a binomially distributed variable $X \sim \text{Bin} \...
- 128k
1
vote
0
answers
133
views
Does the Gaussian Poincare inequality hold for infinite dimensional measure metric spaces?
This is a question subsequent to the one:
Does the Gaussian Poincare inequality hold for $p=1$ as well as $p=2$?
There, I received a very helpful answer that the Gaussian poincare inequality for any ...
- 3,477
1
vote
1
answer
227
views
Does the Gaussian Poincare inequality hold for $p=1$ as well as $p=2$?
Let $X$ be a real-valued standard normal variable. Then, for any differentiable function $f: \mathbb{R} \to \mathbb{R}$ such that $E[f(X)^2] < \infty$ and $E[\bigl( f'(X) \bigr)^2] < \infty$, it ...
- 370
1
vote
1
answer
56
views
Covariance inequality for left skewed distributions
Consider a left skewed random variable $X$ with mean $1$, median $>1$ and support on $[0,2)$. Suppose we have a class of functions $\mathbf{G}$ and each of it's members satisfy $G(x): [0,\infty) ...
- 128k
2
votes
1
answer
335
views
The lower bound of bivariate normal distribution
Suppose $(Z_1, Z_2)$ is the zero-mean bivariate normal distribution with covariance $\left( \begin{matrix} 1 & \rho; \\ \rho & 1\end{matrix} \right)$ with positive $\rho > 0$. What I want ...
- 128k
1
vote
2
answers
2k
views
Upper bound about Gaussian tail bound
From the definition of sub-Gaussian distribution $X$ w.r.t. $\sigma$ i.e.
$$\mathbb{P}(|X-\mathbb{E}(X)|\geq t) \leq 2 \exp(-\frac{t^2}{2\sigma^2}).$$
It's natural that when $X \sim \mathcal{N}(\mu, \...
- 5,474
1
vote
1
answer
235
views
Prove inequality on expectation
Random variable $X\geq 0$ and its variance exists. How to prove
$$\mathbb{P}(X\geq(1-t)\mathbb{E}(X))\geq \frac{t^2\mathbb{E}(X)^2}{\mathbb{E}(X^2)}\enspace\text{for}\enspace t\in(0,1]$$
$$\mathbb{E}(\...
- 128k
0
votes
0
answers
78
views
Kernel density estimation is sub-gaussian
Let $X_1, ..., X_n$ be i.i.d. samples drawn from a pdf $f(x)$ on the real line. The kernel density estimator is defined as follows,
$$\hat{f_n}(x) = \frac{1}{nh}\sum_1^n K(\frac{x-X_k}{h})$$
where $K:\...
- 81
0
votes
1
answer
101
views
Can we show that for every $\delta>0$, there exist constants $\alpha>0, \beta>0$ so that the following inequality holds with high probability?
Consider two $n-$dimensional random vectors $u$ and $v$ uniformly distributed on the sphere. Define $X_n :=u\cdot v$. Note that as $n\to \infty$, $\sqrt{n}X_n \to N(0,1)$ as $n\to \infty$. Fix $\...
- 128k
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 \...
- 5,146
0
votes
1
answer
188
views
Equality cases in a certain case of Jensen's inequality
Suppose that $Y$ is an independent copy of a random variable (r.v.) $X$ with a zero-mean nondegenerate distribution. Is there a non-tautological, preferably simple characterization of the cases when
$$...
- 128k
1
vote
1
answer
97
views
A strict inequality for the $L^1$-norm of a symmetrized zero-mean random variable
Suppose that $Y$ is an independent copy of a random variable (r.v.) $X$ with a zero-mean nondegenerate distribution. Is it then always true that $E|X-Y|>E|X|$?
To get the non-strict version of ...
- 36
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 ...
- 63.9k
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
4
votes
1
answer
168
views
Existence of copula bound pointwise strictly smaller than the Fréchet-Hoeffding upper bound
Consider bivariate copulas $C_1$ and $C_2$ with $\max\{C_1(u,v), C_2(u,v)\}< M_2(u,v)$ for all $u,v \in(0,1)$, where $M_2(u,v) := \min\{u,v\}$ is the Fréchet-Hoeffding upper bound.
Is there a ...
- 128k
3
votes
1
answer
109
views
Inequality: multivariate normal distribition
Let $p(u,x)=\frac{1}{(4\pi u)^{q/2}}e^{-|x|^2/(4u)},u>0,x \in \mathbb{R}^q.$
Prove that for $r\geq 0,c>1$ there exists $C>0$ (depending on $r,c$) such that $$\forall x \in \mathbb{R}^q,u>...
- 128k
2
votes
1
answer
796
views
Can we get that $ P(N^{2/3}(\lambda_N-\lambda_{N-1})\le c)\ge 1-\epsilon$?
Following this question: Can we apply the continuous mapping theorem for the limiting joint distribution of the Tracy-Widom law?.
We know that
$$
\lim_{N\to\infty}P(N^{2/3}(\lambda_N-2)\le s_1,\dotsc,...
- 188k
0
votes
1
answer
84
views
Can we find the following $k$ so that the following inequality holds for asymptotic normal?
Following this question:Can we find such $k$ so that the following inequality holds?.
Consider a sequence of independent $n-$dimensional random vectors $u, v_1, v_2,\dots, v_k$ uniformly distributed ...
- 128k
2
votes
3
answers
222
views
Can we find such $k$ so that the following inequality holds?
I found this question: Chernoff style concentration bound for ratio of variables.
I want to ask if we get similar thing for the ratio of the sum and the one Gaussian variable.
Given i.i.d. Gaussian ...
0
votes
0
answers
34
views
Inequalities for generalized variance
Let $(X, \mu)$ be a measured space with $\mu(X) = 1$.
Given $\phi \in L^\infty(X, \mu)$, $\phi > 0$, let me define, for $\alpha \geq 1$, $\beta > 0$, the quantity
$$
I(\alpha, \beta) = \left(\...
- 1,263
0
votes
0
answers
293
views
Can we prove the following anti-concentration inequality of polynomials of square Gaussian variables?
Following this question Anti-concentration of Gaussian quadratic form. We have the following inequality:
Let $X_1,\dots,X_n$ denote i.i.d. standard Gaussian random variables. For every $\epsilon>0$...
- 288
5
votes
4
answers
4k
views
Is there an inequality relation between KL-divergence and $L_2$ norm?
According to the Pinsker inequality, we have the following inequality:
\begin{equation}
\delta_{TV} (p, q)^2 \leq \frac{1}{2} D_{KL}(p,q),
\end{equation}
where $\delta_{TV} (\cdot, \cdot)$ and $D_{KL}...
- 2,183
4
votes
0
answers
131
views
Log of a truncated binomial
Let $X$ follow a binomial distribution with $n$ trials and success probability $p$, and let $0\leq k\leq n$. Are there any natural approximations or bounds for the ratio $$\frac{\boldsymbol{E}\log\...
- 4,049
1
vote
1
answer
92
views
Lower bound $L_{1}$-metric with $L_{2}$-metric for bounded pdfs, on common support
Setup
To clarify, let constants $0 < a < b < \infty$, and $p \in \mathbb{N}$ be fixed. Further let $B \subset \mathbb{R}^{p}$ be a fixed compact support. We then define the space of bounded (...
- 24.2k
1
vote
1
answer
362
views
An inequality involving the Wasserstein distance and chi-squared distance
$\newcommand{\N}{\mathbb N}$Let $P$ be the set of all probability mass functions on $\N_0:=\{0\}\cup\N$, where $\N:=\{1,2,\dots\}$. Let $P_{>0}$ denote the set of all $q=(q_0,q_1,\dots)\in P$ such ...
- 128k
1
vote
1
answer
186
views
Proof of lower bound on variance
I'm reading through the paper Poincaré type and spectral gap inequalities with fractional Laplacians on Hamming cube.
However, I'm having a difficult time understanding the following proof: Lemma 2.1 ...
CommunityBot
- 1
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 ...
- 128k
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=\{...
- 24.2k
5
votes
2
answers
2k
views
Relationship between KL, chi-squared, and Hellinger
There are many well-known relationships between the KL divergence, chi-squared ($\chi^2$) divergence, and the Hellinger metric. In the paper "Assouad, Fano, and Le Cam" by Bin Yu, the author ...
- 128k
3
votes
1
answer
3k
views
Is there a tight lower bound for the expectation of the product of two positive valued random variables?
Let $X,Y$ be two (dependent) random variables with $\mathbb{P}(X\ge 0)=\mathbb{P}(Y\ge 0)=1$.
I want to find a tight lower bound of $\mathbb{E}(XY)$ when $X,Y$ are non-negative, almost surely.
...
CommunityBot
- 1
1
vote
1
answer
296
views
Lower bound for KL divergence of bounded densities and $L_{2}$ metric
I am currently reading "Smoothing of Multivariate Data" by Klemela. It contains Lemma 11.6, which upper and lower bounds the KL-divergence of two densities in terms of the $L_{2}$-metric. ...
- 128k
1
vote
1
answer
251
views
Using Hoeffding inequality for risk / loss function
I've got a question to the Hoeffding Inequality which states, that for data points $X_1, \dots, X_n \in X$, which are i.i.d. according to a probability measure $P$ on $X$, we find an upper bound for:
$...
- 93
1
vote
0
answers
370
views
Lower bound on the sum of the product of random variables
Let $X_i$ be the $i$-th element of the vector $X=(X_1, ..., X_m)$ of i.i.d. random variables.
I am looking for a lower bound for the expression
$\mathbb{P}((\sum^n_{i=1}\prod^{m_i}_{j=1}(X_j))^2 \geq ...
- 129
2
votes
1
answer
154
views
Random probability following a log concave distribution of order p
In the article "Concentration of the information in data with
Log-concave distributions" of Bobkov and Madiman, it is written that if $X$ is a positive random variable following a log ...
- 12.9k
1
vote
0
answers
107
views
$L^p$ inequality for "positively correlated" random variables
Suppose that we have $m$ complex-valued random variables $\xi_1,\ldots,\xi_m$ and assume the following "positive correlation" property: for all non-negative integers $\alpha_1,\ldots,\...
- 7,193