All Questions
Tagged with pr.probability inequalities
346 questions
3
votes
0
answers
66
views
Order of $\mathbb{E}[ \max_i |x_i + z_i| - \max_i |z_i|]$
Let $z_1, \dots, z_n$ be iid standard Normal, and let $x \in \mathbb{R}^n$. Put $\|u\|_\infty = \max_i |u_i|$.
Define
$$
F(x) = \mathbb{E}\Big[\|x + z\|_\infty - \|z\|_\infty\Big]
$$
If $\|x\|_\infty \...
- 420
2
votes
0
answers
97
views
+100
Inequalities for norm of centered Gaussian and uncentered Gaussian
Let $g$ denote a standard Gaussian vector in $\mathbb{R}^n$, and $\|\cdot\|$ a norm.
Let $x \in \mathbb{R}^n$ and define
$$
F(x) = \mathbb{E}[\|x + g\| - \|g\|].
$$
I am wondering if it is possible to ...
- 420
0
votes
0
answers
38
views
Bounding the error of a truncated moment problem
Let $\{x_{i}\}_{i=1}^{\infty}$ be a non-increasing sequence of non-negative real numbers, and let $\{y_{j}\}_{j=1}^{B}$ be a non-increasing sequence of non-negative real numbers, where $B$ is a finite ...
- 433
3
votes
0
answers
92
views
Tighter Freedman's inequality for a special martingale difference sequence
Let $X_{1}, \ldots, X_{T} \in \{0, 1\}$ be a sequence of Boolean random variables with
$$
\mathbb{E}[X_{t} | X_{1}, \dots, X_{t - 1}] = p_{t}.
$$
Consider the sequence $Y_{t} := X_{t} - p_{t}$ (which ...
- 41
2
votes
3
answers
183
views
Existence and sharpness of Bernstein-type bounds on the moment-generating function
Let $X$ be a centred random variable with variance $\sigma^2$, and whose moment-generating function exists in an open neighbourhood of the origin.
Say that $X$ satisfies a 'Bernstein-type' MGF bound ...
- 801
0
votes
0
answers
57
views
Class of covariance matrices invariant under permutations
I am reading a paper on covariance matrix estimation, and in this paper is introduced a class of covariance matrices:
\begin{equation}
U(q, c_0(p),M)=\{\Sigma: \sigma_{ii}\leq M,\quad \max_j\sum_{j=1}^...
- 1
2
votes
1
answer
208
views
Proving an exponential sum inequality for symmetric Hamming distance sequences in binary vectors
Background: Let $X = \{0,1\}^k$ represent the set of all binary vectors of length $k$. For two binary vectors $x, y \in X$, the Hamming distance $d_H(x, y)$ is defined as the number of positions where ...
- 349
1
vote
1
answer
50
views
Increasing function of $\theta$ for the Ali-Mikhail-Haq Survival Copula
I have been trying to solve the following function is non-increasing (non-decreasing) with respect $\theta$ where $\theta \in (0,1)$ (resp. $\theta \in (-1,0)$)
\begin{equation}
f(\theta)= \frac{h(t,\...
- 23
3
votes
1
answer
287
views
Expectation comparison inequality for concave function of symmetric random variables
Suppose that $X_i$, $i\in[n]$ are
independent symmetric
random variables. I think the conjectured result holds in greater generality, but we can additionally assume that each $X_i$ takes the values $\...
- 6,541
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}$. ...
2
votes
1
answer
144
views
Concentration inequality for double sum
I am looking for a concentration inequality of a double sum….
Let $X_1,\dots, X_n$ be iid r.v. and also let $Y_1,\dots ,Y_n$ be iid such that even $X_i$ and $Y_j$ are independent.
I am looking for a ...
- 51
13
votes
2
answers
1k
views
Probability vector $p$ majorizes its normalized entropy vector $\small \frac{-p\log p}{H(p)}$
I guess the following inequality
$$ \sum_{i=1}^n g \left (\frac{-p_i \log p_i}{H(\boldsymbol{p})} \right ) \le \sum_{i=1}^n g (p_i)$$
holds for any continuous convex function $g$ and any probability ...
- 303
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$. ...
0
votes
1
answer
158
views
Techniques for bounding the operator norm of the expectation of random matrix?
Let $\mu$ be a distribution on the unit sphere in $\mathbb{R}^n$. Let $u \sim \mu$ and consider the random matrix
$$
A = I_n - uu^T.
$$
Question: What techniques are available to provide (reasonably ...
- 420
1
vote
1
answer
148
views
An inequality about binomial distribution
Statement
Assume that $\sigma,R\in (1,+\infty)$, $N\in\mathbb{N}^*$, $p\in (0,1)$, $n_1\in\{0,1,2,\cdots,N-1\}$. Prove or disprove that
$$B^\frac{1}{\sigma}(n_1)-B^\frac{1}{\sigma}(n_1+1)<1 .$$
...
- 35
2
votes
1
answer
105
views
Inequality for Gaussian measures
Let $\mu$ denote a centered Gaussian measure on $\mathbb{R}^k$, $K=(-\infty, a] \times \mathbb{R}^{k-1}$ ($a\ge 0$) and $L=\mathbb{R}\times C$ where $C$ is a convex set in $\mathbb{R}^{k-1}$, ...
- 197
3
votes
1
answer
232
views
Bounds on relative entropy for MLE in Bernoulli coin tosses
In the context of estimating the parameter $p$ from a dataset of $n$ i.i.d Bernoulli coin tosses, we often use the relative entropy $D(p \parallel \hat{p})$ to measure the performance of an estimator $...
- 63
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
3
votes
1
answer
70
views
Multiplicative approximation for a negative moment of the binomial distribution
Let $X$ be a binomial random variable with parameters $n,p$.
Define the function
$f(n, p, t) = E\frac{1}{1 + t X},
$
where $t > 0$.
Question: Can we find an elementary function $F(n, p, t)$ such ...
- 420
3
votes
0
answers
80
views
Seeking strong bounds on KL-divergence and martingales for a hypothesis-testing inequality
Let's say we have a finite set $\mathcal{O}$ of observations, and let $\mathcal{C}(\Delta\mathcal{O})$ denote the space of closed convex sets of probability distributions.
We have two hypotheses which ...
- 353
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
2
votes
1
answer
106
views
Lower bounds for the expectation of log ratio between the posterior and prior Beta densities
The quantity I'm interested in is expressed as follows:
$$
I = \mathbb{E}_{k\sim \text{Binom}(n,p)} \left[\ln \frac{\text{Beta}(p;a+k,b+n-k)}{\text{Beta}(p;a,b)}\right]
$$
The term inside the ...
- 63
0
votes
0
answers
153
views
Inequalities on the distribution of the maximum of the normalized sum $\max_{k = 1,\dots,n} \frac{|S_k|}{\sqrt{k}}$
Let $\{X_i\}_{i\in\mathbb{N}}$ be i.i.d. random variables with $\mathbb{E}(X) = 0$,$\mathbb{E}(X^2) = \sigma^2$ and finite moments. Let $S_k = \sum_{i = 1}^{k} X_i$ and consider the normalized ...
- 63
2
votes
1
answer
386
views
A maximal inequality
Let $\{X_i\}_{i\in\mathbb{N}}$ be i.i.d. symmetric random variables, with $-1\leq X_i\leq 1$, $\mathbb{E}(X_i) =0$, $\mathbb{E}(X_i^2) = 1$. We have that:
$$
P\left(\bigcap_{k = 1}^{n}\frac{|\sum_{i = ...
- 63
2
votes
0
answers
124
views
Generalization of the triangle inequality to complex exponents: What is $P\left(\left| x^{a+bi} + y^{a+bi} \right| \ge \left|z^{a+bi}\right|\right)$?
Let $x \le y \le z$ be the length of the sides of a triangle whose vertices are uniformly random on the circumference of a circle. In this question, it was proved that if $a \ge 1$, then the ...
- 5,470
2
votes
0
answers
55
views
stochastic process and integral
Let $(X_n(t))_{t\in [1,+\infty], n\geqslant 1}$ be a sequence of nonnegative random variables and $(\mathcal{F}_s)$ a filtration ($\mathcal{F}_s \subset \mathcal{F}_r$ for $s\leqslant r$). We assume ...
- 29
2
votes
1
answer
119
views
Simultaneous Concentration of $\sum_{i = 1}^{n} X_i^2$ and $\sum_{i = 1}^{n} X_i$ with $X_i$ iid. Poisson
Consider $n$ independent Poisson(1)-distributed random variables $(X_i)_{1 \leq i \leq n}$.
This is a (hopefully more interesting) follow-up question to Super-exponential concentration for $\frac{\...
- 578
2
votes
1
answer
138
views
How to lower bound the absolute value of the difference of two Kullback-Leibler divergences given the constrains below?
Given that $\min (D[p_1||p_3],D[p_2||p_4])=a$, how to find a lower bound of the difference $\left \vert D[p_1\parallel p_2]-D[p_3\parallel p_4] \right\vert$ with respect to $a$? If the condition is ...
- 31
1
vote
1
answer
129
views
Small total variation distance between sums of random variables in finite Abelian group implies close to uniform?
Let $\mathbb{G} = \mathbb{Z}/p\mathbb{Z}$ (where $p$ is a prime). Let $X,Y,Z$ be independent random variables in $\mathbb G$.
For a small $\epsilon$ we have $\operatorname{dist}_{TV}(X+Y,Z+Y)<\...
- 23
11
votes
1
answer
676
views
Entropy arguments used by Jean Bourgain
My question comes from understanding a probabilistic inequality in Bourgain's paper on Erdős simiarilty problem: Construction of sets of positive measure not containing an affine image of a given ...
- 196
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
0
votes
0
answers
87
views
Comparison between the expected values of the inverse of the CDF of binomial-distributed random variables
Let us denote with $F(x;j,\mu)$ the cdf of a Binomial distributed random variable with $j$ trial with success probability $\mu$ considered in $x$, and let $f(x;j,\mu)$ be the pmf. Defining $0\leq \...
0
votes
1
answer
92
views
Does point process ordering ever imply conditional intensity ordering?
Let $N$ and $N'$ be regular/non-explosive point processes on $[0,\infty)$. I will take the view that these are collections of random arrival times: $N=(t_n)_{n\in\mathbb N}$ and $N'=(t_n')_{n\in\...
- 215
0
votes
0
answers
91
views
Some new questions on Rademacher complexity
For $A\subset R^n$,$A=(a_1,a_2,\dots, a_n)$, $\sigma_i$ are Rademacher random variable.
Is $|\mathbb{E}_\sigma \inf_{a\in A}\sum_{i=1}^n\sigma_ia_i| \le |\mathbb{E}_\sigma \sup_{a\in A}\sum_{i=1}^n\...
- 185
3
votes
0
answers
86
views
Finite dimensional distribution of a stochastic process Lipschitz on every relatively compact set
Let $X_t$ be a Markovian Itô diffusion process, defined by an SDE
\begin{equation}
dX_t = \mu(X_t)\,dt + \sigma(X_t)\,dW_t\,.
\end{equation}
Let $f(x,t|x_0,0)$ denote its transition density function. ...
7
votes
1
answer
556
views
A variation on the Borel–Cantelli lemma theme
Let $X,X_0,X_1,\dots$ be nonnegative independent identically distributed (i.i.d.) random variables. Let
\begin{equation*}
E:=\bigcap_{n\ge0}B_n,
\end{equation*}
where
\begin{equation*}
B_n:=\...
- 128k
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
172
views
Ratio of the constants of the Marcinkiewicz–Zygmund inequality for p=1
The Marcinkiewicz–Zygmund inequality states that
$$
{\displaystyle A_{p}E\left(\left(\sum _{i=1}^{n}\left\vert X_{i}\right\vert ^{2}\right)_{}^{p/2}\right)\leq E\left(\left\vert \sum _{i=1}^{n}X_{i}\...
- 13
0
votes
2
answers
280
views
Bounds tighter than the additive Chernoff
Additive Chernoff
Suppose $X_1, \ldots, X_n$ are i.i.d. random variables, taking values in $\{0,1\}$. Let $p=\mathrm{E}\left[X_i\right]$ and $\varepsilon>0$.
\begin{gather*}
\operatorname{Pr}\left(\...
- 105
8
votes
3
answers
595
views
Jensen-like inequality for random matrix: $\Bbb E[\det X^2]\ge\det\Bbb E[X^2]$
Let $X\in M_n(\Bbb R)$ be a random matrix with iid elements following a continuous distribution.
What are the necessary and sufficient conditions for $$\Bbb E[\det X^2]\ge\det\Bbb E[X^2]$$ to hold? Is ...
- 1,459
4
votes
1
answer
320
views
Sub-Gaussian random variables and convex ordering
Suppose that $X$ is a $1$-sub-Gaussian real-valued random variable, i.e. for all $t \in \mathbf{R}$, it holds that $\log \mathbf{E} \exp \left( t X \right) \leqslant \frac{1}{2} t^2 $.
Does there ...
- 801
1
vote
1
answer
195
views
Reference request: Inequalities involving convex sets and Gaussian variables stated in a paper by Talagrand
I'm looking for references for two facts that are stated without proof in the paper:
Talagrand, M., Are all sets of
positive measure essentially convex?, Lindenstrauss, J. (ed.) et al.,
Geometric ...
- 484
4
votes
0
answers
155
views
Comparing the slackness of Jensen's inequality for some coupled random variables
Let $f:\mathbb{R} \to \mathbb{R}$ be convex and $X,Y$ be random variables with a coupling such that $\mathbb{E}[Y\mid X=x] = x$. A straightforward application of Jensen's inequality gives that $\...
- 141
2
votes
0
answers
164
views
Log Sobolev inequality for log concave perturbations of uniform measure
Suppose $\Omega$ is a convex bounded open set of $\mathbb{R}^n$ (I would be happy with just $\Omega$ as the $n$-dimensional cube). Let $\mu$ be the uniform measure on $\Omega$ and consider the ...
- 873
3
votes
1
answer
205
views
Bound on an integral representing a difference of two relative entropies
Let $ f : [0,1] \to \mathbb{R} $ be a function satisfying: 1.) $ |f(x)| \leqslant a $ for some $ a < 1 $, and 2.) $ \int_0^1 f(x) {\mathrm d}x = 0 $. I would like to know whether the following ...
- 503
2
votes
1
answer
199
views
Gaussian Poincare inequality in $1$ dimensions together with localization issue
Let $d\mu$ be a Gaussian measure on $\mathbb{R}$ with the center $a \in \mathbb{R}$ and variance $1$.
Let $B(a,r) \subset \mathbb{R}$ be the interval $[a-r,a+r]$.
Then, for any smooth mapping $f : \...
- 3,477
5
votes
1
answer
516
views
Bounding the variance of a truncated Gaussian random variable
Suppose $X_1, X_2, X_3 \sim N(0, 1)$ are three independent standard normal random variables. I am interested in showing that:
$$\text{Var}[X_2\mid X_2 \geq X_1 - a, X_1 \leq X_3 + b] < 1,$$
where ...
- 269
5
votes
0
answers
159
views
Log Sobolev inequality uniform in parameters
Fix a positive integer $N$. For $\theta \in [0,2\pi]$, set $\sigma_k(\theta) :=(\cos(k\theta),\sin(k\theta)) \in S^1$ for each integer $1\leq k\leq N$. Now for vectors $x_1,\ldots,x_N\in \mathbb{R}^2$,...
- 873
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
0
votes
1
answer
182
views
Deducing norm concentration from MGF bounds
Suppose that $X$ is a centered, $\mathbf{R}^d$-valued random variable such that for all $t \in \mathbf{R}^d$, there holds the bound $$\log \mathbf{E} \left[ \exp \langle t, X \rangle \right] \leqslant ...
- 801