All Questions
Tagged with pr.probability inequalities
346 questions
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.
...
1
vote
1
answer
701
views
Hanson-Wright inequality (quadratic form concentration inequality) for bounded random vectors
Is there a concentration inequality for quadratic forms of bounded random vectors $X \in [-1, 1]^n$ with zero mean and given covariance matrix $\Sigma \in \mathbb{R}^{n \times n}$ but otherwise ...
user114668
4
votes
1
answer
336
views
Binomial Distributions and Inequality
Suppose $c>2$ is a real number, and $x$ solves equation $f(\frac{1}{2}+x,m,2m)=(2m+1)cx$ for some $m>0$ integer number, where $f$ is probability mass function for binomial distribution, with ...
- 43
1
vote
1
answer
365
views
Lower-bound probability of non-centered quadratic form
Let $X\sim N(\mu,\sigma^2I)\in \mathbb{R}^n$ be a non-centered ($\mu\neq 0$) Gaussian vector with independent coordinates. I'm wondering if there is any sharp lower bound of the following probability:
...
- 1,495
4
votes
1
answer
358
views
Bound for type of correlation measure
Assume you have a finite, discrete probability distribution for a joint random variable and such that $P(X=i,Y=j) = p_{i,j}$ for $i \in \{1, \dots, |X|\},j \in \{1, \dots, |Y|\}$. The marginal ...
- 51
3
votes
0
answers
185
views
Measure change bound for function of subgaussian r.v
Let $X$ be a (sub)gaussian r.v. on $\mathbb{R}^d$; say $X\sim\mathcal{N}(\mathbf{0},\mathbb{1}_d)$; and let $a\colon\mathbb{R}^d\to [0,1]$ be a function with $\mathbb{E}[a(X)] > 0$.
It is not hard ...
- 1,372
4
votes
1
answer
206
views
Inner product of sorted Gaussian vector
Suppose $X_1,\ldots,X_n$ are i.i.d. standard normal. I'm wondering how to analyze the following quantity:
$$\left|\frac{X_{(1)}X_{(n)}+X_{(2)}X_{(n-1)}+\cdots+X_{(n)}X_{(1)}}{n}\right|$$
where $X_{(1)}...
- 1,495
1
vote
1
answer
69
views
Randomly scaled random variables
Consider two possibly correlated scalar random variables $N$
and $X$. It is known that $1\leq N \leq N_{\max}$. Given that $\mathbb{E}[NX]\leq 0$, does it always hold that $\mathbb{E}[X] \leq 0$?
...
- 11
5
votes
1
answer
169
views
Сoincidence of discrete random variables
Let $\xi, \eta$ be a discrete random values and $\mathbb E| ξ |$, $\mathbb E | η | < +\infty$, and any value of these
values are accepted with a non-zero probability. How to prove that from $\...
- 113
4
votes
1
answer
863
views
Hoeffding's inequality for Hilbert space valued random elements
Suppose that $\mathbb H$ is a separable Hilbert space and $X_1,\ldots,X_n$ are independent zero mean $\mathbb H$-valued random elements such that $\|X_i\|\le s$ for each $1\le i\le n$, where $\|\cdot\|...
- 423
2
votes
1
answer
280
views
Complicated bound after using Stirling's approximation
I have this inequality $$\frac{1}{a}\exp\bigl\{-\frac{4}{h^2}\bigr\} \geq \frac{1}{f}$$ where $$ a \leq \Bigl(\pi^{d/2}\Gamma(\frac{1}{2}d+1)^{-1} + 1\Bigr) \left(\frac{h^{d+1}}{2} \Gamma \left(\frac{...
- 225
2
votes
0
answers
330
views
Concrete Hanson-Wright inequality?
I'm working on a paper that requires bounding
$$\Pr\left[|\vec x^\top Q \vec y| >= t\right]$$ where $Q$ is a matrix (happens to be symmetric) and $\vec x,\vec y$ are iid real mean-zero subgaussian ...
- 21
3
votes
2
answers
189
views
Is the covariance of squares always bounded from below by two times the covariance?
I came across the following inequality in one of my calculations ($X,Y$ are centered random variables):
$$\operatorname{E}(X^2Y^2)-\operatorname{E}(X^2)\operatorname{E}(Y^2) \geq 2 \operatorname{E}(...
- 617
4
votes
1
answer
406
views
Expectation of exponential of a function of independent Rademacher r.v.'s involving the error function
Let $Z,Z'\in\{-1,1\}^n$ be two independent vectors of i.i.d. Rademacher r.v.'s, where $1\leq n \leq d$ are two integers ($d\gg 1$). I am trying to get an upper bound on
$$
\mathbb{E}_{ZZ'}\left[ \exp\...
- 1,372
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
0
votes
1
answer
143
views
Right tail decay of F distribution [closed]
Suppose $X\sim F(a,b)$. Is there any sharp upper bound of the following probability with large $x$?
$$\mathbb{P}(X\geq x)$$
what is the order of the above probability as $x\to+\infty$?
- 1,495
1
vote
2
answers
462
views
lower bound the probability of at least L collisions
Lets say we get a list $M$ containing $|M|=\sqrt{L\cdot N}$ randomly and independtly drawn elements from a set of size $N$. And lets denote the $i$-th element of the list $M$ by $M[i]$.
If we now ask ...
- 123
3
votes
1
answer
209
views
Log concavity of the maximum of dependent Gaussians
Let $Z_1,\dots,Z_n$ be dependent Gaussian random variables. Is it true that $X=\max\{Z_1,\dots,Z_n\}$ has a log-concave distribution function? This is true for the independent case, but is it true in ...
- 2,288
3
votes
1
answer
171
views
Why does the assumption $|U_t| \le \frac1{p_{\min}}$ work in this paper?
I am reading a 2009 paper right now "Importance Weighted Active Learning" and on page 5, there is a theorem that uses the inequality $|U_t| \leq \frac{1}{p_{\min}}$. I am not sure how the paper found ...
- 33
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
4
votes
2
answers
654
views
Hypercontractivity of two simple random variables, $E[XY]^s \le E[X^s]E[Y^s].$
For $\alpha,\beta\ge 0$, let $X\in\{1,\alpha\}$ and $Y\in\{1,\beta\}$ be two random variables such that $$XY = \begin{cases}
\alpha\beta \quad & \text{with probability} \quad p_{11}\\
\alpha \quad ...
3
votes
1
answer
235
views
Inequality for exponential sum in Dvoretzky 1972
I'm currently trying to figure out the following inequality. It looks like an inequality for the exponential sum, but I can't verify it or find a source explaining it any further. Most likely it has ...
- 115
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
3
votes
1
answer
105
views
A gaussian based inequality
I came across an inequality in the paper of 'Estimation of a function with discontinuities ...' (AoS, 1998, p.1374) and tried to prove it, but could not get to the result. Some simulations also seemed ...
- 555
0
votes
1
answer
213
views
Show that interval of maximum probability grows no faster than $\sqrt{n}$ for binomial distribution
Let $X \sim \text{Binom}(n, p)$ a binomial random variable. I want to show that : $$\forall 0 < t < 0.9, \quad \exists C, \quad \forall n >1, \quad \mathbb P\bigg(|X-np| \leq C\sqrt{n}\bigg) \...
- 119
1
vote
1
answer
499
views
property of iid random variable
Let $ (\xi_i)_{i \ge 1} $ be independent identically distributed random variables, taking values in $ (1,3]$.
Can we show:
$P( \exists N \in \mathbb{N}, \text{ s.t. } \forall k \ge 0, \prod_{i=1}^{...
- 553
5
votes
1
answer
279
views
Mixed norm inequality
Suppose we have a product space $(X_1\times X_2,\mu_1\otimes\mu_2)$, with finite measures $\mu_1,\mu_2$ and $p>1$.
Is there a possibility that an inequality of this form holds on the product space?
...
- 156
-1
votes
1
answer
76
views
Transforming random variables for having good property?
For arbitrary functions $A$ and $B$ and independent random variables $X$ and $Y$, assume that
\begin{align}
\Omega&\triangleq \{(x,y): A(x,y)=1\},\\
\Lambda&\triangleq \{x: B(x)=1\}.
\end{...
- 287
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
0
votes
0
answers
112
views
On certain integrals of exponential functions with respect to Gaussian measures
I have questions about the integral
$$F(a,b,c)=\sqrt{\frac{a}{\pi}}\int_{0}^{\infty}e^{-bx^4+cx^3-ax^2}dx$$
for $a,b,c>0$.
What is the asymptotic behavior of $F(a,b,c)$ for small $a,b,c$? In ...
- 505
1
vote
1
answer
221
views
Berry-Esseen type bounds with lower moment assumptions
Let $D(\epsilon,C)$ be the collection of all random variables $X$ on $\mathbb{R}$ such that $E[X]=0$, $E[X^2]=1$, and $E[|X|^{2+\epsilon}]\leq C$. Define a function $L_{\epsilon,C}(n)$ by
$$L_{\...
4
votes
2
answers
432
views
How to prove the sum of n squared binomial probabilities does not increase as n increases
Let $F\left( n \right) = \sum\limits_{k = 0}^n {{{\left( {C_n^k{p^k}{{\left( {1 - p} \right)}^{n - k}}} \right)}^2}} $, prove $F\left( n \right) \ge F\left( {n + 1} \right)$.
UPDATE: More general, ...
- 43
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
5
votes
1
answer
348
views
A Minkowski-like inequality
Assume that $X$ and $Y$ are two arbitrary non-negative random variables. Is the following inequality true for $1\leq\alpha\leq 2$?
\begin{align}
\left(\mathbb{E}\left[X^\alpha\right]-\mathbb{E}\left[...
- 287
4
votes
1
answer
1k
views
Does variants of Bernstein and Freedman concentration inequalities exist with NO uniform bound on the range of RV or martingale differences
A classic formulation of the Bernstein inequality (from Wikipedia) is as follow:
Let $X_1, \ldots, X_n$ be independent zero-mean random variables. Suppose that $|X_i|\leq M$ almost surely, for all $i$...
- 53
5
votes
1
answer
164
views
Probability of ruin in the Sparre Andersen renewal risk model
In 1957, Erik Sparre Andersen proposed using a renewal risk model to describe the behavior of the insurers surplus
$$U(t)=u+ct-\sum\limits_{i=1}^{\Theta(t)}Z_i, \quad t \geqslant 0$$
where:
$u \...
2
votes
1
answer
598
views
Cantelli's inequality: the original source
Does anyone know where and when Cantelli's inequality was originally published? Strangely enough, I have not been able to find this information online.
- 128k
0
votes
0
answers
250
views
Can we make two random variables independent at a low cost?
Let $X$ and $Y$ be two discrete random variables with joint probability mass function $p(x,y)$ such that
$$\|p(x,y)-p(x)p(y)\|_1=\sum_{x\in\mathcal{X},y\in\mathcal{Y}}|p(x,y)-p(x)p(y)|\leq\epsilon$$
...
- 287
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
5
votes
0
answers
857
views
Anti-concentration inequality for Gaussian random vector
I am trying to obtain an explicit expression for $C$ in terms of $b$ in the following inequality.
Suppose that $Y$ is a centred Gaussian random vector in $\mathbb R^p$ such that $\operatorname EY_j^...
- 423
2
votes
2
answers
632
views
An alternative proof of Bayesian Cramer-Rao
My question is:
Are there an alternative proof of Cramer-Rao lower bound that does not use
Cauchy-Swartz inequality?
Let me outline the classical proof and explain why I am interested in this ...
- 671
1
vote
0
answers
376
views
Anti-concentration bounds for folded normal and inverse of gaussian variables
Are there any easy to use bounds on sums of the following kind :
$$
\sum_{i = 1}^{i = N} |a_i| \geq P \\
a_i \sim \mathcal{N}(0, 1) \\
$$
and also for sums of the form :
$$
\sum_{i = 1}^{i = M} \...
- 111
1
vote
1
answer
249
views
On concentration of a sum random variable
Take a random variable defined as
$$r=u_{11}v_{1}v_{1}+u_{12}v_{1}v_{2}+\dots+u_{n,n-1}v_{n}v_{n-1}+u_{nn}v_{n}v_{n}$$ where $v_{i}$ are independent uniform random variables from $\{0,\dots,b\}$, $u_{...
- 13.9k
3
votes
0
answers
77
views
A concentration problem of product of matrices
Let $A$ be an $n \times m$ matrix with non-negative entries and $B \in \mathbb{R^{n\times n}_{\geq 0}}, C \in \mathbb{R^{m\times m}_{\geq 0}}$ be random matrices where B and C are both symmetric and ...
- 195
3
votes
1
answer
330
views
Does this probability distance metric have an official name?
Let us define a distance metric between two joint probability math functions $p(x,y)$ and $q(x,y)$ as in the following
\begin{align}
\sum_{y}\sqrt{\sum_{x}p(x)\left(p(y|x)-q(y|x)\right)^2}.
\end{...
- 287
4
votes
1
answer
197
views
Does this moment inequality hold for any probability measure on the positive real line?
Problem statement
Let $P$ be a probability measure on the positive real line and assume all it's raw moments, $\mu_k = \mathbb{E}[x^k]$, $k=1,2,\dots$ exist and $\mu_k < \infty$ for all $k$. Let $...
4
votes
1
answer
81
views
Implication from an equality in terms of expectations for uniqueness proof
I have shown that a solution to a nonlinear equation exists, and I am trying to show it is unique. Let Y > 0 be a continuous non-constant random variable, and $a_1$, $a_2$ real parameters. I have ...
- 353
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
1
vote
0
answers
110
views
Tail bound without independence
Suppose $X_i , X_j\in \mathbb{R}^d$ are gaussian vectors and $A$ is an $n\times n$ symmetric PSD matrix where $A_{ij} = f(\|X_i-X_j\|_2), \quad i,j\in 1,\ldots,n\;$ for some non-negative Lipschitz ...
- 195
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