All Questions
Tagged with pr.probability inequalities
346 questions
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
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}}(...
- 128k
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 \...
- 5,429
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) < \...
- 63.9k
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\...
- 128k
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 ...
- 128k
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)\...
- 421
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?
$$...
- 14.2k
1
vote
1
answer
285
views
Exponential upper bounds for sums of martingale differences
Let $(X_{i})_{i\geq 1}$ be a sequence of centered real-valued martingale-differences with respect to some filtration $(\mathcal{F}_{i})_{i \geq 1}$. Define $S_{n} = \sum_{i=1}^{n}X_{i}$ and $\Sigma^{2}...
- 65
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 ...
- 128k
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-...
- 29.8k
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 $ ...
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}^...
- 5,429
-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
0
votes
1
answer
179
views
How to show $\max_{1\leq i\leq n}(X_i+Y_1)\preceq \max_{1\leq i\leq n}(X_i+Y_i)$?
Let two collections of random variables $\{X_i\}$ and $\{Y_i\}$ be independent and let $\{Y_i\}$ be i.i.d. Then
$$\max_{1\leq i\leq n}(X_i+Y_1)\preceq \max_{1\leq i\leq n}(X_i+Y_i).$$
where $\...
- 128k
3
votes
2
answers
402
views
Something between the Chernoff and Hoeffding bounds
Suppose I have $n$ independent 0-1 random variables $X_1, \cdots, X_n$ and I want to show a concentration of $X = \sum_i X_i$.
I can use either the Chernoff bound or the Hoeffding bound.
Suppose $E[...
- 128k
0
votes
2
answers
124
views
Bounding $E[\|\Sigma^{-1/2}(X-\mu)\|_2^3]$ for 2-dimensional Bernoulli
Let $X\in\{0,1\}^2$ have mean $\mu=\left[\begin{smallmatrix}p_1\\p_2\end{smallmatrix}\right]$ and $\Pr[X_1 = X_2 = 1] = p\le \min\{p_1,p_2\}$.
(Note we must have $1-p_1-p_2+p\ge 0$ for the ...
0
votes
1
answer
199
views
Is this probability inequality true?
This question may be simple, though I'm not managing to find an answer. Let $X$ and $Y$ be two dependent random vectors in in $\mathbb{R}^d$, with joint probability density $\mu(x,y)$ (with respect to ...
- 195
3
votes
2
answers
1k
views
Expected value of a truncated binomial
Let $X\sim B(n,p)$ be a binomial random variable and fix $0<k<n$. Are there any well-known bounds for $\mathbb{E} (X-k)^+$, where $(X-k)^+ =\max\{0,X-k\}$? I am particularly interested in ...
- 128k
1
vote
1
answer
144
views
A uniform mixture of order statistics
Let $0<k<n$ be integers, and let $X$ be a random variable obtained as follows: sample $n$ points independently and uniformly at random in the unit interval, and select (uniformly) one of the $k$...
CommunityBot
- 1
1
vote
2
answers
50
views
Cyclic inequality for 2 dimensional simplex elements
Let $p=(p_{1},p_{2},p_{3})\in\Delta$, with $\Delta:=\lbrace p\in(0,1)^{3}\ |\ p_{1}+p_{2}+p_{3}=1 \rbrace$. I aim to prove (not knowing whether it is true though) that
\begin{equation}
p_{1}^{p_{3}-p_{...
- 128k
0
votes
1
answer
1k
views
Bounding $L^p$ norms in terms of lower-order $L^q$ norms
Suppose $f,g\in L^q(\Omega)$ ($\Omega\subset \mathbb{R}^n$) for all $1\le q\le p$. Here, $L^p(\Omega)$ is defined with respect to some measure $\mu$ that is absolutely continuous wrt Lebesgue measure. ...
- 12.9k
4
votes
0
answers
405
views
A symmetrization-majorization inequality for i.i.d. zero mean random variables
Let $k\geq 2$ and
$$f(x_1,\ldots,x_k)=\Bigl(\prod_{i\leq k}(1+x_i)+\prod_{i\leq k}(1-x_i)\Bigr)\log\Bigl(\prod_{i\leq k}(1+x_i)+\prod_{i\leq k}(1-x_i)\Bigr)-k(1-x_1 x_2)\log(1-x_1 x_2).$$
If random ...
- 175
1
vote
0
answers
60
views
Maximum value of $\int (aF^2(x)g(x)+G^2(x)f(x))dx$ over all $f,g$ densities satisfying $\int F(x)g(x)dx=1/2$
I want to maximise $$I(f,g):=\int_{-\infty}^\infty (aF^2(x)g(x)+G^2(x)f(x))dx$$ where $a>0$ is a given constant, over all possible probability densities $f,g$ satisfying $$\int_{-\infty}^\infty F(x)...
- 319
3
votes
1
answer
431
views
Inequality on the Hellinger distance between Poisson and mixture of Poisson
Let $H$ denote the Hellinger distance; i.e., for two discrete distributions $p,q$ (identified with their pmf) over $\mathbb{N}$,
$$
H(p,q)^2 = \frac{1}{2}\sum_{n=0}^\infty \left(\sqrt{p(n)}-\sqrt{q(n)}...
- 1,372
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$, ...
- 52.3k
4
votes
0
answers
205
views
Dimension reduction for low-order moments of Rademacher-weighted sums of vectors
Let $x_1,\dots,x_n$ be vectors in a Euclidean space $H$. Let $\varepsilon_1,\dots,\varepsilon_n$ be independent Rademacher random variables (r.v.'s), so that $P(\varepsilon_i=\pm1)=1/2$ for all $i$.
...
- 2,288
4
votes
3
answers
161
views
Find distribution that minimises a function of its moments
Imagine a probability density function $f(x)$, defined for positive $x$, and let's note its $n$th non-centred moment $x_{n}$. The mean $x_{1}$ is fixed (and positive).
How can I find $f(x)$ that ...
- 17.2k
0
votes
0
answers
166
views
Lower bound on probability of sum of independent random variables
I'm interested in estimating the following quantity
\begin{equation}\lim_{k \to \infty} \sum \limits_{i=1}^l \sum \limits_{l_1 = 0}^{i} {{nk-k}\choose{l_1}} \Big( \frac{1}{k}\Big)^{l_1} \Big( \frac{...
- 237
2
votes
2
answers
268
views
An "obvious" probability lemma about random words
Fix some positive integers $p,n,k$. Let $w$ be chosen uniformly at random from $[k]^n$ (the set of $n$ length words/sequences where each entry is in $\{1,\ldots,k\}$). Let $A_i$ be the event that $...
- 128k
2
votes
1
answer
406
views
Mean squared absolute value of inner product of unit vectors
Given a nonempty finite subset $S$ of the unit sphere of $d$-dimensional complex Hilbert space, let $\lambda(S) = \frac{1}{\lvert S \rvert^2} \sum_{x,y \in S} \lvert \langle x,y \rangle \rvert^2$ be ...
- 10.4k
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 ...
- 175
5
votes
1
answer
274
views
Precise probability that $m$ random vectors in $n$ dimensional space are nearly-orthogonal
Consider $m$ vectors $v_1,\dots,v_m$ in $\mathbb R^n$, drawn uniformly and independetly from unit sphere. It is pretty straightforward from Chebyshev inequality that
$$
\mathrm P (\forall i\ne j \ |...
- 128k
1
vote
0
answers
286
views
General Hoeffding inequality with two uncorrelated random vectors
Let $X_1,\ldots, X_n$ be independent sub-Gaussian variables with sub-Gaussian norm $K$. Let $a_1,\ldots,a_n$ be a random vector such that $\mathbb{E}[a_j X_i]=0$ for all $i,j\in \{1,\ldots ,n\}$ and ...
- 31
1
vote
1
answer
210
views
Tighter upper bound for $\mathbb{E} [\max_{\sigma \in \{ \pm 1\}^n} \sigma^T W \sigma]$
Following this question I was thinking about ways to improve the upper bound and came up with the following argument. We want to find an upper bound for
\begin{equation}
\mathbb{E} [\max_{\sigma \in \{...
CommunityBot
- 1
1
vote
2
answers
295
views
Monotonicity of maximum of convex combination of two scaled concave functions
Let $f:R\rightarrow R$ be a concave function with a unique and finite maximum. Let $$g(x, \beta) = \beta f(\alpha \cdot x) + (1-\beta) f((1-\alpha) \cdot x), $$ where $\alpha \in [0,1/2]$ and $\beta \...
- 1,053
1
vote
1
answer
607
views
Hanson-Wright inequality with random matrix
I'm interested in bounding the tail probabilities of a quadratic form
$x^t A x$ where $x\in \mathbb{R}^n$ is a sub-Gaussian vector with independent entries. $A\in \mathbb{R}^{n\times n}$ is a matrix. ...
- 1,731
4
votes
3
answers
300
views
Reconstructing probability distribution with high probability
Sample $m$ times from unknown probability distribution $p=(p_1,p_2,\cdots,p_n)$, we can construct a probability distribution $q=(q_1.q_2,\cdots,q_n)$.
How large $m$ should be to achieve that the ...
- 128k
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\...
- 4,361
2
votes
1
answer
286
views
An inequality for abstract Cauchy problem
Consider the following abstract Cauchy problem: $x'(t)=Ax(t)$, in $(0,T)$, with $x(0)=x_0$, where $A$ generates an analytic $C_0$-semigroup on a Banach space $X$. How we can prove an inequality of ...
- 128k
2
votes
1
answer
90
views
A probability inequality: $p+(1-p)E[v|v\geq a] \geq E[v|v \geq p+(1-p)a]$
There is a random variable $v \sim F(\cdot)$ with support $[0,1]$. For a parameter $p \in (0,1)$ and $a \in (0,1)$. Define $A$ and $B$ as the following:
$$A=p+(1-p)E[v|v\geq a], B=E[v|v \geq p+(1-p)a]$...
- 128k
1
vote
1
answer
143
views
Comparison of hitting probability of two Markov chains both with only one absorbing state version 2 under stronger condition
Let $N_n:=\{1,2,\cdots,n\}$. Given two finite states Markov chains $\big(X^{(j)}_i\in N_n\}\big)_{i=0}^\infty$ for $j\in\{1,2\}$, both of which have two absorbing states at $1$ and $n$.
$\text{Pr}\...
- 2,239
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 ...
- 128k
0
votes
1
answer
339
views
Expectations, double integrals and Jensen's inequality
$\def\anonfunc#1{#1(\cdot)}$Consider two random variables distributed $v\sim \anonfunc G$ and
$c \sim \anonfunc F$ with pdfs $\anonfunc g$ and $\anonfunc f$. Let the supports of $c$ and
$v$ be $[x,y]$....
- 128k
2
votes
1
answer
222
views
Does the inequality $\mu F(\mu)^2\geq \int_{\mu}^{b}F(x)\cdot(1-F(x))\,\mathrm dx$ hold for compactly supported continuous random variables?
This question was originally asked on the Mathematics StackExchange by User smcc
Consider a continuous random variable $V$ with cumulative distribution function $F$ and density function $f$. Suppose ...
- 128k