All Questions
Tagged with pr.probability inequalities
346 questions
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
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_{...
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
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
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
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 ...
- 4,049
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<...
- 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 >...
- 730
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
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} \...
- 730
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}...
- 175
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
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 ...
- 1,127
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.
...
- 167
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. ...
- 233
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
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\...
- 41
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\...
- 197
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$ ...
- 11
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 ...
- 100
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\...
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{...
- 39
0
votes
1
answer
966
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,\...
- 25
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
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 (...
- 233
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
2
votes
1
answer
404
views
Euclidean distance bound with geometric constraints
Let $S_n$ be a set of $n$ points belonging to $\mathcal{B}_d:=\{\mathbf{x}\in\mathbb{R}^d:\|\mathbf{x}\|_2\le 1\}$, where $d\ll \log(n)$.
Let $s_n$ and $\ell_n$ be respectively defined as follows:
$$...
- 1,677
0
votes
1
answer
159
views
Best bounds on the integral of an increasing function
The following question, somewhat edited here, was asked and then closed at The best bound of the integral of a nondecreasing real function in a closed interval.
Let $F\colon[0,1]\to[0,1]$ be a ...
- 128k
2
votes
0
answers
147
views
Is there a way to gain such an estimate?
This problem could be viewed as a polynomial generalization of the Lonely runner conjecture. And $p$, $n$ are taken sufficiently large. Take $n\in \mathbb{N}^*$ fixed, $A_p \subset (\mathbb{Z} / p \...
- 543
0
votes
1
answer
133
views
Projection onto manifold of Gaussian measures by "trunction" of moments
Let $\mathcal{P}_2(\mathbb{R}^n)$ be the set of Borel probability measures on $\mathbb{R}^n$ with finite mean and variance; in the sense that
$$
\int_{x \in \mathbb{R}^n} \|x\|^p d\mathbb{P}(x) < \...
- 5,405
0
votes
1
answer
340
views
Expectation of the ratio of two discrete random variables with combinatorial constraints
We are given a set $S=\{1, 2, \ldots, n\}$ where $n\gg 1$, and for all indices $1\le i \le n$, $i$ is associated with a real value $\alpha_i\!\cdot\! v_i$, where $\alpha_i\in[0,1]$ and $v_i\in(0,1]$.
...
- 1,677
5
votes
2
answers
243
views
Is $\Gamma(s, x=s-1)/\Gamma(s)$ decreasing for real $s>1$? Is $\Gamma(s, x=s)/\Gamma(s)$ increasing?
This has received no full solution at StackExchange.
As per https://dlmf.nist.gov/8.10#E13 we have
$$\frac{\Gamma\left(n,n\right)}{\Gamma\left(n\right)}<\frac{1}{2}<\frac{\Gamma%
\left(n,n-1\...
- 804
2
votes
0
answers
84
views
approximate the square of 2-norm distance between binary distributions with high probability
Suppsose we take $m$ samples from a Bernoulli distribution with probability $p$, and $m$ samples from another probability distribution with probability $q$. We want to calculate a statistic $x$ from ...
- 1,503
1
vote
1
answer
89
views
Inequality for integrals of probability densities
Given three univariate probability densities, $f(x)$, $g(x)$, and $h(x)$, I would like to show that
$\int_{supp(f)\cap supp(g)}\frac{fg}{f+g}dx+\int_{supp(g)\cap supp(h)}\frac{gh}{g+h}dx-\int_{supp(f)\...
- 11
3
votes
2
answers
636
views
Exponential inequality for the sum of martingale differences $X_1, \dots, X_n$ when $\sum_{i=1}^{n} \operatorname{Var}(X_i) \leq B^2$
Let $X_1, X_2, \dots, X_n$ be a martingale difference sequence such that
$$
X_i \leq y \quad \text{and} \quad \sum_{i=1}^{n} \operatorname{Var}(X_i) \leq B^2.
$$
Question 1: Does the following hold?
$$...
- 33
3
votes
1
answer
1k
views
Extension of Bernstein’s Inequality when the random variable is bounded with large probability
Bernstein’s Inequality can be stated as follows : Let $x_1, x_2, \dots, x_n$ be independent bounded random variables such that $\mathbb{E}[x_i] = 0$ and $|x_i| \leq \zeta$ with probability $1$ and let ...
- 33
1
vote
1
answer
91
views
Inequality regarding a probability measure
First of all, I am sorry for the ''not clear title' for this question but I cannot find a better way to describe this seemingly very simple and standard inequality,
So.. I am reading a paper 'Two-...
- 239
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
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
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
4
votes
0
answers
321
views
Examples of measures that satisfy FKG, but not the FKG lattice condition
Let a percolation measure be a measure on $\{0,1\}^n$. We have a natural partial order on $\{0,1\}^n$ given by comparing all coordinates. An event $A$ is called increasing if for all $ \omega \in A $ ...
- 1,054
0
votes
0
answers
106
views
Upper bounding the sum with hypergeometric and binomial probabilities
Could you please help me upper bound this tricky expression:
$$P(A)=\sum_{i=0}^n{\left( 1 - \dfrac{\binom kq \binom {n-k}{i-q}}{\binom {n}{i}} \right)}^I \binom ni p^i {(1-p)}^{n-i}$$.
So far I only ...
- 1
2
votes
0
answers
202
views
Probabilistic inequality for sum of squares of zero mean Gaussian random variables
Let $X_1,...,X_n$ be i.i.d. standard normal random variables. How to show that there is constant $c>0$ such that for every $a_k>0$ and for every $n>0$: $P(\sum_{k=1}^{n}a_kX_k^2>\sum_{k=1}^...
-1
votes
1
answer
283
views
Lowerbounding expectation value of binomial tail
I'm trying to find a lower bound for the following expression for $q\ge p$:
$$f(q,p,n) := \sum_{v=0}^n \sum_{k=v}^n \binom{n}{v} \binom{n}{k}q^v(1-q)^{n-v}p^k(1-p)^{n-k}.$$
It can be thought of as the ...
- 702
3
votes
1
answer
229
views
Inequality for difference of consecutive atom probabilities for binomial distribution
Edit: This post was originally two questions, the first of which has been answered, but a reference would still be appreciated if existent. The second question has been removed and migrated to its ...
- 2,720