All Questions
Tagged with pr.probability inequalities
346 questions
5
votes
1
answer
164
views
Probability of ruin in the Sparre Andersen renewal risk model
In 1957, Erik Sparre Andersen proposed using a renewal risk model to describe the behavior of the insurers surplus
$$U(t)=u+ct-\sum\limits_{i=1}^{\Theta(t)}Z_i, \quad t \geqslant 0$$
where:
$u \...
4
votes
2
answers
1k
views
Bound on the tail of the sum of independent and identically distributed (iid) variables
This interesting question was asked at https://math.stackexchange.com/questions/231455/estimator-for-sum-of-independent-and-identically-distributed-iid-variables a while ago but got no answers. The ...
- 128k
2
votes
1
answer
599
views
Cantelli's inequality: the original source
Does anyone know where and when Cantelli's inequality was originally published? Strangely enough, I have not been able to find this information online.
- 188k
0
votes
0
answers
250
views
Can we make two random variables independent at a low cost?
Let $X$ and $Y$ be two discrete random variables with joint probability mass function $p(x,y)$ such that
$$\|p(x,y)-p(x)p(y)\|_1=\sum_{x\in\mathcal{X},y\in\mathcal{Y}}|p(x,y)-p(x)p(y)|\leq\epsilon$$
...
8
votes
2
answers
4k
views
Lower bounds on Kullback-Leibler divergence
This was originally a question on Cross Validated.
Are there any (nontrivial) lower bounds on the Kullback-Leibler divergence $KL(f\Vert g)$ between two measures / densities?
Informally, I am ...
- 128k
5
votes
0
answers
857
views
Anti-concentration inequality for Gaussian random vector
I am trying to obtain an explicit expression for $C$ in terms of $b$ in the following inequality.
Suppose that $Y$ is a centred Gaussian random vector in $\mathbb R^p$ such that $\operatorname EY_j^...
- 423
2
votes
0
answers
687
views
Placing Bounds on Correlation/Covariance Through Correlation with an Intermediate Variable
I am trying to make the most of computations that have already been performed in previous steps of an algorithm. Throughout this problem statement I am only mentioning correlation, but I think it is ...
- 1
5
votes
1
answer
445
views
A two-point inequality
Let $M(p,q) = (2p-\sqrt{p^{2}+q^{2}})\sqrt{p+\sqrt{p^{2}+q^{2}}}$ and set $B(t) = M(x+t, \sqrt{t^{2}+(y+bt)^{2}})$. Given any real $x,y,b$ is it true that $\varphi(t) = B(t)+B(-t)$ is decreasing in $...
CommunityBot
- 1
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
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_{...
- 128k
3
votes
1
answer
330
views
Does this probability distance metric have an official name?
Let us define a distance metric between two joint probability math functions $p(x,y)$ and $q(x,y)$ as in the following
\begin{align}
\sum_{y}\sqrt{\sum_{x}p(x)\left(p(y|x)-q(y|x)\right)^2}.
\end{...
- 287
3
votes
0
answers
77
views
A concentration problem of product of matrices
Let $A$ be an $n \times m$ matrix with non-negative entries and $B \in \mathbb{R^{n\times n}_{\geq 0}}, C \in \mathbb{R^{m\times m}_{\geq 0}}$ be random matrices where B and C are both symmetric and ...
- 195
4
votes
1
answer
197
views
Does this moment inequality hold for any probability measure on the positive real line?
Problem statement
Let $P$ be a probability measure on the positive real line and assume all it's raw moments, $\mu_k = \mathbb{E}[x^k]$, $k=1,2,\dots$ exist and $\mu_k < \infty$ for all $k$. Let $...
- 1,095
4
votes
1
answer
81
views
Implication from an equality in terms of expectations for uniqueness proof
I have shown that a solution to a nonlinear equation exists, and I am trying to show it is unique. Let Y > 0 be a continuous non-constant random variable, and $a_1$, $a_2$ real parameters. I have ...
CommunityBot
- 1
13
votes
4
answers
535
views
Alignment of random points
Whenever I draw randomly about ten points, I see that there will be always 3 points that are "almost" collinear. This observation leads me to considering the following questions:
Question 1: Suppose $...
- 44.4k
6
votes
2
answers
2k
views
Is there a universal bound for this ratio of expectations?
Let $X$ and $Y$ be two zero-mean independent and identically distributed random variables. Is there a bound for the following ratio,
$$\frac{\mathbb{E}[|X+Y|]}{\mathbb{E}[|X|+|Y|]}=\frac{\mathbb{E}[|...
CommunityBot
- 1
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
0
votes
0
answers
141
views
Effect of partitioning the realizations of random variables on the total variation distance?
Let $X$ and $Y$ be two random variables with joint pmf $p(x,y)=p(x)\cdot p(y|x)$ and $X$ has uniform distribution. Also assume that the following relation is satisfied:
\begin{align}
\lVert p(y|x)-p(y)...
- 287
4
votes
1
answer
535
views
Inequality with ratio of Normal CDFs
Let $\theta>0$, $0<\lambda<1$, and $\Phi$ be the standard normal cumulative distribution function. Is it true that
$$\frac{\lambda \Phi(-\theta)}{\Phi(-\lambda \theta) }< e^{\frac{\theta^...
- 109k
2
votes
1
answer
421
views
A question about Gaussian Processes suprema
Suppose $\{X_t; t \in \mathcal{X}\}$ is a centered Gaussian Process with covariance function $k(\cdot,\cdot)$, and let $d(x,y) = \mathbb{E}[(X_x-X_y)^2]$.
I am trying to find a tail bound for the ...
CommunityBot
- 1
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 ...
- 3,968
4
votes
0
answers
141
views
Is there an example that both Berry-Essen bound and DKW bound are attained?
The Berry-Essen bound stated that
$$\sup _{{x\in {\mathbb R}}}\left|\widehat{F_{n}(x)}-\Phi (x)\right|\leq C_{0}\cdot \psi _{0}$$
where $\psi _{0}(n)={\Big (}{\textstyle \sum \limits _{{i=1}}^{n}\...
- 8,071
2
votes
1
answer
563
views
Prove or disprove $ \int_0^\infty \int_{-x}^0 f(x)f(y)\,dy\,dx > \int_0^\infty \int_{-\infty}^{-x} f(x)f(y)\,dy\,dx. $
Consider a symmetric, unimodal distribution $f(x)$ such that $\int_0^\infty f(x)\,dx > 1/2$. I want to prove or disprove the following:
$$
\int_0^\infty \int_{-x}^0 f(x)f(y)\,dy\,dx > \int_0^\...
3
votes
0
answers
125
views
Concentration of sums of random matrices around the mean, in the Loewner order
Recently, I have found myself interested in concentration properties of random matrices.
Specifically I would like to answer questions of the following sort
Let $\{X_i\}_{i=1}^n$ be i.i.d. copies ...
- 393
0
votes
1
answer
126
views
Berg-Kesten-Reimer inequality on infinite spaces?
See this link for a description of the van den Berg-Kesten-Reimer inequality. How important is the assumption that $\Omega_i$ are finite spaces?
When Berg-Kesten state the inequality in their 1985 ...
CommunityBot
- 1
4
votes
1
answer
347
views
Concentration of functional of Gaussian random variable
Suppose I have two Gaussian distributions
$p(x) = \frac{1}{(2\pi)^{d/2}|\Sigma_p|^{1/2}}\exp(-\frac{1}{2}x^\top \Sigma_p^{-1} x)$ and $q(x) = \frac{1}{(2\pi)^{d/2}|\Sigma_q|^{1/2}}\exp(-\frac{1}{2}x^\...
CommunityBot
- 1
-1
votes
1
answer
159
views
Bounding difference of two mutual information with different distributions on random variables
Let $A$, $B$ and $C$ be three random variables and $p_{A,B,C}=p_Ap_Bp_{C|A,B}$ and $q_{A,B,C}=p_Aq_{B|A}p_{C|A,B}$ be two distributions on them. Then, we can conclude that?
\begin{align*}
\lvert I_p(A,...
- 2,720
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
4
votes
1
answer
207
views
Upper bound on the number of binary matrices with small rank
I'm looking for the tightest upper bound on the number of different binary matrices $A \in {\{-1,1\}^{m \times n}}$ for which $\mathrm{rank}(A)\leq r$. I'm interested in the regime $1 \ll r \ll m \...
- 5,781
2
votes
1
answer
246
views
Does small expected value of a random variable show the small probability for its tail?
Do there exist functions $g(\epsilon)$ and $h(\epsilon)$ defined for $\epsilon>0$ such that $g(\epsilon)\to 0$ and $h(\epsilon)\to 0$ as $\epsilon\to 0^+$ with the following property:
If $X$ and $...
- 23.2k
3
votes
0
answers
451
views
concentration bounds on weighted multinomial sum
Consider i.i.d random vectors $Y_{1},..,Y_{n}$ and they are chosen uniformly at random from $\{e_{1},..,e_{L}\}$ where $e_{i}$ is a $L\times 1$ vector with $i$th component be 1 and the others be 0. ...
- 31
9
votes
5
answers
1k
views
estimate the error term in CLT
Let $X_m = \frac{1}{\sqrt{m}}\sum_{k=1}^m Z_k$ where $Z_k$ are iid equally likely on $\{\pm 1\}$. Then $X_m$ convergens to $X \sim \mathcal{N}(0,1)$ in distribution by CLT.
Let $f$ be a smooth ...
- 128k
6
votes
1
answer
239
views
Positive semidefinite ordering for covariance matrices
Suppose that X and Z are matrices with the same number of rows. Let
$$ D = \left[\begin{array}{cc} X' X & X'Z \\ Z'X & Z'Z \end{array} \right]^{-1} - \left[\begin{array}{cc} (X' X)^{-1} & ...
- 128k
4
votes
1
answer
568
views
inequality with exponents
We are given a graph $G$, each vertex $v$ has an assigned value $\gamma_v\in [0,1]$, and it happens that for every $v$ we have $\gamma_v+\sum_{u\in \delta(v)} \gamma_u = 1$. Assume that $\sum_v \...
CommunityBot
- 1
2
votes
1
answer
271
views
How to compute bounding coefficients for McDiarmid's inequality?
I am trying to understand the proof in Sec. A2 of Gretton et al.. To make the question self-contained, I summarize below the key ingredients. At the end of the post, I state my question.
Given a ...
6
votes
2
answers
735
views
Negative probabilities - what are two ordinary pgfs that correspond to the gf of a half-coin?
In Half of a Coin: Negative Probabilities, author considers pgf of a fair coin represented by random variable, $X = 1_H$:
$$G_X(z) = E[z^X] = \sum_{x=0,1} z^xP(X=x) = (z^0)(1/2) + (z^1)(1/2) = \frac{...
- 247
2
votes
1
answer
172
views
Symmetry of concentration bounds on mean
Question summary:
If I have a two-sided bound, can I immediately get a one-sided bound with tighter constants?
Question details:
Let $\mathbf X = X_1,...,X_n$ be $n$ i.i.d. real-valued random ...
- 399
7
votes
1
answer
265
views
Is this simple-looking moment inequality true?
Let $p \ge 1$ be an integer. Does there exist a constant $C_p$ such that for every random variable $X \ge 0$,
$$
\mathbb{E} \left[ \left(X - \mathbb{E} \left[ X \right] \right)^{2p} \right] \le C_p \...
- 562
9
votes
1
answer
395
views
An inequality on the simplex involving $x^x$
Is anything known about the behavior of the function $$f(x)=\prod_{i=1}^n x_i^{x_i}$$ on the standard simplex, i.e. the set $\{x\in\mathbb{R}^n:\sum_{i=1}^n x_i=1, x_i\geq0\}$? I ask because I have ...
- 128k
4
votes
1
answer
346
views
Sharpened Pinsker inequality for special case
Let $B(p)$ denote the Bernoulli distribution over $\{0,1\}$ and $B(p)^n$ the corresponding product distribution over $\{0,1\}^n$. For $n>1$ and $0<x<1$, define
$$P_n(x):=B(\frac12+\frac x2)^n$...
- 128k
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 ...
CommunityBot
- 1
0
votes
0
answers
124
views
Maximal inequality for Markov process
For a Markov process $\{X_n\}$ is there any inequality available for
$$ E[\sup_{0 \leq n \leq k} X_{n}]$$
in terms of moments of $E[X_n], 0 \leq n \leq k$
- 317
8
votes
2
answers
486
views
concentration inequality for entropy from sample
Consider a measure $\mu$ on a finite set, and let $x_1, \ldots, x_n$ be i.i.d samples from $\mu$. Then the expression $S_n = -\frac{1}{n} \sum_{i=1}^n \log \mu(x_i)$ converges by a.s. to the entropy $...
- 128k
0
votes
0
answers
107
views
Conditional version of martingale difference concentration inequality
Let $M_n$ be a $\mathscr{F}_n=\sigma(\eta_m,\theta_m, m\leq n)$ measurable martingale difference sequence. Then is it possible to find a exponential tail bound for the following
$$P(|M_{n+1}| > u|\...
- 317
7
votes
1
answer
583
views
Inequality for the maximum of Gaussian variables
Let $X=(X_1,\dots,X_n)$ and $Y=(Y_1,\dots,Y_n)$ be centered Gaussian vectors
with variance matrix $\Gamma_X$ and $\Gamma_Y$. We assume that the matrix
$\Gamma_Y-\Gamma_X$ is positive definite. Is it ...
- 266
2
votes
0
answers
124
views
Intuitive (?) inequality extremal inequality
Consider $N$ pairs of random variables $(X_i, Y_i)$. $X_i$ are iid, with $EX_i=0$ and $EX_i^2=1$. The same conditions hold for $Y_i$. Moreover all $X_i$ are independent of all $Y_j$. It seems very ...
- 461
3
votes
1
answer
1k
views
concentration inequality for averages of dependent random variables
Let $X \in R^n$ be a random vector such that
$$P(|X_i| > \epsilon) > e^{-\epsilon^2}$$
What is a tight bound on
$$P(\sum_{i=1}^n |X_i| > \epsilon)$$
and on
$$P(\max_{1\le i\le n} |X_i| ...
- 461
2
votes
1
answer
588
views
maximal inequalities for dependent random variables
I want to know literature about maximal inequalities for dependent random variables i.e. upper bound for $P(\max_{n\ge k\ge 1}\sum_{i=1}^{k}X_i > \delta)$ where $X_i$ are dependent random ...
- 3,968
5
votes
0
answers
177
views
Inequality about moments of a random variable and of its conditional expectation
This is a follow-up to a question I asked earlier: Moments of a random variable and of its conditional expectation
My claim turned out to be false. Here is a new claim.
Let $X$ be a bounded random ...
CommunityBot
- 1
7
votes
1
answer
499
views
Moments of a random variable and of its conditional expectation
Let $X$ be a bounded random variable with $\mathbb{E}X=0$. Since $X$ is bounded, all its moments exist. Let $\mathcal{G}$ be any $\sigma$-field and let $Y:=\mathbb{E}[X|\mathcal{G}].$ I am interested ...
- 23.2k