All Questions
Tagged with inequalities pr.probability
346 questions
3
votes
2
answers
169
views
On finding an upper bound on the error of a sparse approximation
I posted this question on math.stackexchange earlier, but didn't see any response. So, I am posting it here, in case someone else has an answer.
Original question: https://math.stackexchange.com/...
- 128k
2
votes
0
answers
69
views
A distribution $\pi \propto \exp(-f)$ satisfies log-Sobolev inequality, does $\exp(-af)$ also satisfy LSI?
Assume a distribution $\pi \propto e^{-f}$ satisfies log-Sobolev inequality (LSI)
$$\forall \rho \in P(\mathbb{R}^n), \quad KL(\rho\| \pi) \le \frac{1}{2\lambda} I(\rho \| \pi)$$
with LSI constant $\...
- 21
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 ...
- 23.2k
3
votes
1
answer
142
views
How does the integral of pseudo Gaussian kernel on $(0,\infty)$ depend on its variance?
Let $a, b: \mathbb R_+ \to [0,1]$ be continuous functions. Let $k: \mathbb R_+\times\mathbb R \to [1,2]$ be $1-$Lipschitz. Set, for $0<s<t$ and $y>0$,
$$A(s,t,y):=\int_s^t\frac{k(u,y)}{1+a(u)}...
- 128k
0
votes
1
answer
503
views
Asymptotics of a 1D integral, or the orthant probability of an equicorrelated random Gaussian vector
Problem: Let $\phi(x)$ be the normal probability density function (pdf), and $\Phi(x)$ the normal cumulative distribution (cdf). I'm interested in the asymptotic behavior of the following integral
$I(...
CommunityBot
- 1
5
votes
1
answer
512
views
Concentration inequality for Hilbert space valued random variables
I have read in a paper about the following result:
Let $V$ be a separable Hilbert space and $(\Omega,A_{\Omega},P)$ a probability space. Suppose that $Y_1,Y_2,...$ is a sequence of independent $V$-...
- 3,968
4
votes
1
answer
285
views
Probability of existence of $\lambda$ such that $\lambda a_i \geq b_i$, for i.i.d random variables $a_i$'s and $b_i$'s
Suppose $a_i$'s and $b_i$'s ($1\leq i\leq n$) are i.i.d Gaussian random variables. What's the probability that a $\lambda$ exists such that $\lambda a_i \geq b_i, ~\forall i$?
Actually, an upper bound ...
- 128k
6
votes
1
answer
1k
views
Variance of the norm of a random variable under finite-moment assumptions
There is the following exercise in Vershynin's book on High-Dimensional Probability.
Exercise 3.1.6:
Let $X = (X_1, \dots, X_n) \in \mathbb{R}^n$ be a random vector with independent coordinates $X_i$ ...
- 128k
1
vote
1
answer
106
views
What is the maximum possible coefficient of variation for data taking values within a specified range?
I have a question that seems very basic, and yet I have not managed to find an answer after probably several hours of Google-searching.
Fix $0<a<b<\infty$, and let $\mathcal{P}_{[a,b]}$ be ...
- 128k
2
votes
2
answers
161
views
Determine the affine envelope of a random process's MGF
Suppose that a stationary random process $S(t)$ can be characterized as the figure below, which for most of the time is a straight line $S(t)=c\cdot t$, but occasionally would "stall" for a ...
- 128k
2
votes
1
answer
136
views
Does higher volatility of SDE imply lower probability of staying positive?
Given two SDEs $X^1$, $X^2$ :
$$X^i_t=1+t+\int_0^t\sigma_i(s)dW_s,\quad \forall t\ge 0,$$
where $\sigma_i:\mathbb R_+\to [1/2,1]$ are non-decreasing s.t. $\sigma_1(t)\le \sigma_2(t)$ for all $t\ge 0$....
- 128k
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 ...
- 128k
-1
votes
1
answer
551
views
Lower bound of an expectation
Suppose a random variable $X$ has unit variance i.e. $\sigma^{2} = 1$. Is there a positive constant $c > 0$ such that
$$\mathbb{E}[\ | X - \mathbb{E}[X] | \ ] \ge c $$
My attempt of a solution is ...
- 66
2
votes
1
answer
138
views
Comparison between $\|X\|_2$ and $\|X\|_{2,1}$
For any real random variable $X$, define
$$\|X\|_{2,1}=\int_0^\infty \sqrt{\Pr(|X|>t)}dt.$$
This quantity (it is not a norm) appears in various problems, e.g. the multiplier central limit theorem (...
- 128k
1
vote
1
answer
67
views
Lower-bound for $\mathbb E[e^{-b(v^\top X - c)^2}]$, when $X$ is log-concave in high-dimensions
Let $d$ be a large positive integer. Fix a unit-vector $v \in \mathbb R^d$, and scalars $b,c \in \mathbb R$ with $b > 0$. Let $X$ be a log-concave random vector in $\mathbb R^d$ normalized so that ...
- 128k
0
votes
1
answer
133
views
How to demonstrate a correlation inequality? [closed]
If there are 3 vectors X, Y, Z of the same length, for any $x_i \in X,y_i \in Y,z_i \in Z$, we have $0<x_i<1,0<y_i<1,0<z_i<1$.
The correlation between Z, Y is greater than between X, ...
- 63.9k
2
votes
0
answers
337
views
Conditional probability inequality proof
There are two index sets $I= \{1, 2, \dots, m\}$ and $J = \{1, 2, \dots, n\}$. Then, I have independent random variables $X_{ij}, \forall i \in I, j \in J$. Fix $i \in I$; then we have $X_{ij}$ is ...
- 31
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:
...
CommunityBot
- 1
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
1
vote
0
answers
234
views
"Tails" of a multinomial distribution
Let $X_1,\dots,X_N$ denote a collection of independent samples of a uniform multinomial random variable in $\mathbb{Z}^k$, with the number of trials equal to $n\ll k$. (By "uniform", I mean ...
- 4,049
1
vote
0
answers
77
views
Divergence between random variables after transformation
Let $X$ and $Y$ be random variables with laws $\mu_X$, $\mu_Y$ and $d$ be some $f$-divergence (e.g. KL, total variation, Hellinger). Writing $d(X,Y)$ for the divergence between $\mu_X$ and $\mu_Y$, ...
- 19
4
votes
0
answers
96
views
Is this conjecture about the binomial and beta distributions true?
Let $X$ follow a binomial distribution with parameters $n$ and $p$, and also fix $k$ such that $1<k<n$. Define
$$a = \mathbb{E}(X-k)^+$$
and
$$b = \mathbb{E}\log\binom{X}{(X-k)^+}$$
where the ...
0
votes
1
answer
147
views
Trying to prove an inequality (looks similar to entropy)
I'm trying to prove the following inequality (or something similar, up to a constant factor in either side of the inequality):
$$k\cdot\sum_{i=1}^{k}x_{i}\cdot\ln\left(x_{i}\right)\geq\sum_{i=1}^{k}x_{...
- 1,081
3
votes
0
answers
169
views
Probabilistic behavior of greedy point selection in the plane
Let $\mathcal{X} = X_1,\dots,X_n$ be a collection of independent, uniform samples in the unit square. Let $\mathcal{S}=\{X_1\}$, and consider the following process: for $i=2,\dots,n$, let $x^*$ be ...
- 4,049
0
votes
1
answer
66
views
Bounding parameter satisfying a collection of inequalities
I have a set of equations with some inequality constraints that I expect generally does not have a unique solution.
The equations take the form below:
$$\alpha/N+(1-\alpha)x_1=a_1$$
$$\alpha/N+(1-\...
- 135
3
votes
0
answers
84
views
Weak sufficient conditions for non-negative correlation between functions of correlated random variables?
Consider real, nonnegative random variables $A$, $B$, and $X$, and define
$Z = \exp(-A X)$ and $W = \exp(-B X)$, and also $U = \exp(-X - A)$ and $V = \exp(-X -B)$.
What sorts of minimal sufficient ...
- 61
5
votes
2
answers
202
views
Monotonicity of a parametric integral
For real $x>0$, let
$$f(x):=\frac1{\sqrt x}\,\int_0^\infty\frac{1-\exp\{-x\, (1-\cos t)\}}{t^2}\,dt.$$
How to prove that $f$ is increasing on $(0,\infty)$?
Here is the graph $\{(x,f(x))\colon0<...
- 574
3
votes
1
answer
553
views
How did the story of Kim-Vu type inequalities continue?
I am interested in the concentration of polynomials of random variables. I have been reading Boucheron, Lugosi, and Massart's "Concentration inequalities" and they give some references. ...
CommunityBot
- 1
2
votes
1
answer
198
views
Bounds for the beta CDF
This question is closely related to a previous question that I asked here:
An inequality involving the beta distribution
Let $a,b$ be strictly positive integers, and let $F_{a,b}(x)$ denote the CDF ...
- 128k
4
votes
0
answers
146
views
An inequality for three iid random variables with a log-concave density
It was previously shown that
$$H\ge cG,\tag{1}$$
where $c:=1/14334$,
$$G:=E|X-Y|,\quad H:=E|X-Y|-\tfrac12\,E|X+Y-2Z|,$$
and $X,Y,Z$ are independent random variables with the same log-concave density.
...
- 128k
3
votes
1
answer
197
views
possibility of bounding one functional by another functional
This is a natural follow-up question related to one of my previous questions at here. Assume that $\rho$ is a log-concave probability density function with support $[0,\infty)$ and fixed mean $\mu >...
- 128k
0
votes
0
answers
173
views
Lemma 3.10 of paper 'Periodic nonlinear Schrodinger Equation and Invariant measure' by J.Bourgain
I am reading a paper 'Periodic nonlinear Schrodinger Equation and Invariant measure' by J.Bourgain.
And I have a questions in the proof of lemma 3.10.
Please click the paper title for the link.
The ...
- 239
4
votes
1
answer
225
views
concentration inequality for $d$-dimensional martingale
Are any concentration inequality available for $d$-dimensional martingale. It is easy to find such inequality using the inequalities for single dimension, but that will contain the dimension $d$ in ...
- 128k
2
votes
1
answer
161
views
Trying to bound one functional by another functional
In my little research project, I faced the following problem: Assume that $\rho$ is a probability density function with support $[0,\infty)$ and mean $\mu >0$. Let $$H[\rho] = \iiint_{y,v,w\geq 0} \...
- 128k
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 ...
- 2,618
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 ...
- 12.9k
5
votes
1
answer
150
views
Kullback–Leibler chains
The following question was asked and then deleted by the post author:
Let $P$ and $Q$ be two probability distributions defined over the same space, with $KL(P \parallel Q) < \infty$. For $\epsilon ...
- 128k
3
votes
3
answers
6k
views
Probability of a random variable greater than its expected value
We have a lot of probabilities lower bounding as (e.g. chernoff bound, reverse markov inequality, Paley–Zygmund inequality)
$$
P( X-E(X) > a) \geq c, a > 0 \quad and \quad P(X > (1-\theta)E[...
- 18.7k
5
votes
1
answer
225
views
Anti-concentration of Gaussian when conditioning on event
Let $v$ be a given vector with $\|v\|_{\Sigma^{-1}} \leq 1$, where $\Sigma$ is a positive semi-definite matrix and $\|v\|_{\Sigma^{-1}} = \sqrt{v^\top\Sigma v}$. Meanwhile, let $u$ be a random vector ...
- 128k
1
vote
1
answer
207
views
Expectation of the sum of the squares of the cardinal of an inverse function
I sample a random one-to-one function $\pi:\{0\,;\,1\}^n\to\{0\,;\,1\}^n$. I define $f$ as:
$$\forall x\in\left[0\,;\,2^n-1\right]\cap\mathbb{N},f(x)=x\oplus\pi(x)$$
where $\oplus$ is the bitwise XOR.
...
- 128k
4
votes
0
answers
414
views
Simmons' inequality on binomial random variables
Fix two positive integers $n,m$ such that $n>2m$ and $n\ge 3$, and let $X\sim \text{Bin}(n,\frac{m}{n})$ be a binomial random variable. For each $i\in \{1,\ldots,m\}$, set
$\alpha_i = \mathbb{P}(X\...
- 3,065
1
vote
1
answer
107
views
Tail bounds on random series in Hilbert space
Tail bounds on random series in Hilbert space
Let $X_n$, $n \in \mathbb {N}$, be independent $\pm 1$ symmetric random variables, and $a_n$,
$n \in \mathbb {N}$, be a sequence in a Hilbert space $H$ ...
CommunityBot
- 1
8
votes
3
answers
629
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 ...
- 61.9k
3
votes
1
answer
271
views
Bound on the distribution of a ratio involving Gaussian distributions
Let $U \sim \mathcal{N}(0, I_K)$ be a Gaussian vector of dimension $K$ and $V \sim \mathcal{N}(0,1)$, independent of $U$. Let $\Delta$ be a diagonal matrix with non-negative diagonal elements, $c\in\...
- 61.9k
0
votes
1
answer
447
views
Properties of $l_q$-balls
For a given $q\in (0,1]$, define the $l_q$-ball as
$$\mathbb{B}_q(R_q)\mathrel{:=}\left\{\theta\in\mathbb{R}^d\,\middle\vert\,\sum_{j=1}^d \lvert\theta_j\rvert^q\leq R_q \right\}. $$
For a given ...
- 56
2
votes
3
answers
1k
views
How can I prove Chebyshev's sum inequality with probabilistic methods?
I would like to prove Chebyshev's sum inequality, which states that:
If $a_1\geq a_2\geq \cdots \geq a_n$ and $b_1\geq b_2\geq \cdots \geq b_n$, then
$$
\frac{1}{n}\sum_{k=1}^n a_kb_k\geq \left(\frac{...
- 128k
4
votes
0
answers
190
views
Pedestrian proof of Gaussian chaos for order-two polynomial?
Let $\ell \geqslant 1$. Let us consider $(g_n)_{n \in \mathbb{N}}$ identically distributed independent real gaussian variables and real number $(a_{n_1,\dots n_{\ell}})_{(n_1, \dots, n_{\ell}s)\in\...
- 5,429
0
votes
1
answer
967
views
Bound the norm of sum of random vector that generated from standard basis
I have a question like this:
Consider $N$ samples $X_1, X_2, ..., X_N$ that uniformly random generated from standard basis $\{e_i, i=1,2,...,d\}$, i.e. $(1,0,0,\cdots,0),(0,1,0,\cdots,0),(0,0,1,0,\...
- 128k
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 ...
- 61.9k
2
votes
1
answer
629
views
Beyond union bound
I am very curious whether there are some interesting techniques to deal with cases where union bound is not strong enough to give the desired result. I am only aware of the Bonferroni inequalities (...
- 14.2k