All Questions
Tagged with pr.probability inequalities
346 questions
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:
$...
- 13
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
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
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
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_{\...
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
1
vote
1
answer
132
views
Approximating Moment of Sum of RVs
Given
$X_i$ are independent random variables.
$|X_i| < 1$
$E[X_i] = 0$
$X = \sum_i^n X_i$
$var(X)=\sigma$
Prove:
$$ E(X^p)^{1/p} = O(\sqrt{p}\sigma +p)$$ for all even p
Things I've tried:
...
- 11
1
vote
1
answer
129
views
A martingale puzzle about sum of expected squared bounds
I'm trying to get one of those "with $1-\delta$ probability, the following holds"-style bounds, and the following martingale problem looks solvable by some Freedman or Bernstein-style bound, ...
- 353
1
vote
1
answer
186
views
Kolmogorov inequality for Bernoulli random variables
This question is also asked on math stackexchange. The question is about one inequality which shows in Kolmogorov's paper (inequality (3.1)) but is not proved. The inequality says that, if we assume $...
- 33
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 ...
- 3,477
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. ...
- 133
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 ...
- 708
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 ...
- 6,853
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
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_{...
- 289
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. ...
- 31
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 \...
- 13
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
1
vote
1
answer
143
views
Lower bound for log-Ratios
Can we find a universal constant $c>0$ such that for all $p,q\in\Delta:=\lbrace x\in (0,1)^{n}\ \colon\ x_{1}+\dots+x_{n}=1\rbrace$ it is true that
\begin{equation}
|p_{i}-q_{i}|\le c\left|\ln\frac{...
- 289
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
1
vote
1
answer
313
views
Bounds on difference between "logsumexp" and variance?
Let $Z$ be a random variable with finite moment-generating function $M_Z(\theta):=E[e^{\frac{1}{\theta}Z}]<\infty$ for all $\theta > 0$, and for $\delta \in (0,1]$, define
$C_Z^\delta := \inf_{\...
- 6,853
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
1
vote
1
answer
121
views
Probability for high mutual coherence on all subsets of a Gaussian vector set
We examine as set of independent normal vectors:
$$ \forall i \in [N]\triangleq \{1,\dots,N\}:\,\mathbf{x}_{i}\sim\mathcal{N}\left(0,\mathbf{I}_{d}\right)$$
For any $\epsilon>0$ and $K\leq N$, we ...
- 968
1
vote
1
answer
207
views
Computing probability that $Ax\geq0$ where $x$ is a vector of iid gaussians and $A$ is matrix of $1$s and $0$s
This question came up in my research: What is the probability that $Ax\geq0$ where $x$ is a vector of iid gaussians and $A$ is matrix of $1$s and $0$s?
So far I only figured out that I can do Monte ...
- 113
1
vote
1
answer
478
views
Distance between the product of marginal distributions and the joint distribution
Given a joint distribution $P(A,B,C)$, we can compute various marginal distributions. Now suppose:
\begin{align}
P1(A,B,C) &= P(A) P(B) P(C) \\
P2(A,B,C) &= P(A,B) P(C) \\
P3(A,B,C) &= P(...
- 49
1
vote
0
answers
80
views
Inequality involving random vectors and absolute values
Let $\mathbb{X}, \mathbb{Y} \subset \mathbb{R}^d$ be finite sets. Suppose random vectors $X \in \mathbb{X}$ and $Y \in \mathbb{Y}$ are sampled according to a joint distribution $\mathbb{P}_{XY}$. ...
1
vote
0
answers
45
views
Inequality Involving Concave Monotonic Function
Assume that $ f: \mathbb{R} \to \mathbb{R}_+ $ is a concave, non-decreasing and positive function. Let $\mathbb{X}$ be a finite set consisting of $ 0\leq x_1 \leq x_2 \leq x_3 \leq \ldots \leq x_n$. ...
1
vote
0
answers
43
views
Moments on the Stiefel manifold
Let $S_{n, k} = \{V \in \mathbb{R}^{n \times k} : V^T V = I_k\}$ denote the Stiefel manifold, $1 \leq k \leq n$.
Let $P \in \mathbb{R}^{n \times n}$ denote a symmetric real, positive definite matrix, ...
- 420
1
vote
0
answers
92
views
Multilinear non-commutative Khintchine inequality
Let $g_1,\ldots,g_k$ be independent standard Gaussians and for each index $(i_1,\ldots,i_k)\in [n]^k$ let $A_{i_1,\ldots,i_k}$ be a $d\times d$ symmetric matrix.
Question: Is there a known bound for ...
- 156
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 ...
- 111
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
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 ...
- 13
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
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
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
1
vote
1
answer
335
views
Finding a connection between two types of convergence
Please, help me find connections between two types of convergence:
Let $\{X_n\}_{n\ge1}: (\Omega,F,P) \rightarrow (\mathbb{R},Bor)$ be a sequence of r.v., there are two convergences:
1) $X_n \...
- 31
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
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
0
answers
98
views
Joint distribution of two weighted sums of IID random variables
Let $X_1, X_2, \dots$ be independently uniformly distributed random variables in $\{-1, +1\}$ and let $a_1, b_1,a_2,b_2, \ldots \in \mathbb{R}$ be fixed, bounded and of non-zero average. Let $Y_n=...
- 341
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
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
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
1
vote
0
answers
282
views
Strict monotonicity of conditional variances
Let $K \geq 2$ be a positive integer and $C$ be any $K \times K$ non-singular matrix (if necessary, can assume that all $K$ rows of $C$ are needed to span the coordinate row vector $e_1'$). For ...
- 765
1
vote
0
answers
93
views
Bounds on the spherical measure of sub-level sets of quadratic forms
I'm wondering if there are any bounds on the spherical measure of sets of the form
$$
\mu_n\left(\{y\in S^{n-1} : \frac{y_1^2}{y_2^2} < \alpha\}\right) \leq f(\alpha)
$$
where $\alpha$ is some ...
- 205
1
vote
1
answer
229
views
Tail inequality for orthomartingales/martingale difference random fields
It is known that if $(S_i= \sum_{j \leqslant i }X_i, \mathcal F_i)$ is a martingale,
then for each
$
\beta>1$, $\delta\in (0,\beta-1)$ and $\lambda>0$, and each integer $N \geqslant 1$, the ...
- 3,958
1
vote
0
answers
171
views
An inequality for moments of a random variable
I'm interested in a class C of $R^1$-valued random variables $\xi$ which satisfy
an inequality of the type
$$
(1) \qquad E|\xi|^p \leq F(E|\xi|^2),
$$
where $p>2$, $F$ is a certain non-...
- 195
1
vote
0
answers
181
views
Nonstationary Markov chain maximal inequality
Let $X_i$ be a (finite-state, irreducible, aperiodic) Markov chain, not necessarily stationary. (That is, it doesn't start from the invariant distribution; I'm happy to have it be time-homogeneous if ...
- 1,069
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
0
votes
1
answer
381
views
Help prove a maximal inequality
Let $X_1,…,X_n$ are exchangeable of random variables, and $n$ is an even number.
$S_k=X_1+\dots+X_k$. $M_k=X_{n/2}+\dots+X_{n/2+k}$.
I want to prove:
$$\Pr(\max_{1 \le k \le n}{|S_k|>\epsilon}) \...
- 177