All Questions
Tagged with pr.probability inequalities
346 questions
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{...
- 14.2k
4
votes
2
answers
2k
views
Bounds on the mills ratio
How do I show the following bounds on the mills ratio :
$\frac{1}{x}- \frac{1}{x^3} < \frac{1-\Phi(x)}{\phi(x)} < \frac{1}{x}- \frac{1}{x^3} +\frac{3}{x^5} \ \ \ \ \ \ \ $ for $ \ \ \ x>0$ ...
- 5,407
18
votes
3
answers
3k
views
Entropy and total variation distance
Let $X$, $Y$ be discrete random variables taking values within the same set of $N$ elements. Let the total variation distance $|P-Q|$ (which is half the $L_1$ distance between the distributions of $P$ ...
5
votes
0
answers
205
views
Strange inequality relating Binomial pmf and cdf
I'm encountering a strange inequality I need to prove, relating the Binomial pmf and cdf.
Suppose we have $n$ coin flips, and fix an arbitrary $k \le n/2$ heads. Suppose further that we have some ...
- 2,600
5
votes
1
answer
208
views
Expected supremum of normalised random walk
Let $X^i\in \mathbb R^d$ be iid. random variables for $i=1$ to $n$.
Assume $\mathbb E[X^i]=0$ and the covariance matrix $\mathbb C[X^i] = \mathbb E[X^iX^{iT}] = I$ is the identity matrix.
Define $S^k=...
- 4,746
4
votes
2
answers
193
views
Minimal coupling
Let $\mu,\nu$ be probability measures defined on a common measure space $(\Omega,\mathcal F)$. A coupling of $\mu,\nu$ is a probability measure $\pi$ on $(\Omega^2,\mathcal F^2)$ with marginals $\mu,\...
- 24.8k
4
votes
1
answer
358
views
Bound for type of correlation measure
Assume you have a finite, discrete probability distribution for a joint random variable and such that $P(X=i,Y=j) = p_{i,j}$ for $i \in \{1, \dots, |X|\},j \in \{1, \dots, |Y|\}$. The marginal ...
CommunityBot
- 1
2
votes
1
answer
287
views
Bernstein Inequality for continous local martingale
I'm looking for a simple proof of the following fact, which is somehow Bernstein inequality in continuous time.
Let $(M_t)_{t\geq 0}$ be a continuous local martingale. Then :
$$P\left(\sup_{t\in [0,...
- 3,968
16
votes
6
answers
3k
views
A normal distribution inequality
Let $n(x) := \frac{1}{\sqrt{2\pi}} e^{-\frac{x^2}{2}}$, and $N(x) := \int_{-\infty}^x n(t)dt$. I have plotted the curves of the both sides of the following inequality. The graph shows that the ...
- 63.9k
3
votes
1
answer
364
views
Can anyone give a reference to the proof of this concentration inequality?
The following concentration inequality for the supremum of a Gaussian process indexed by a separable metric space appears here: http://math.iisc.ac.in/~manju/GP/6-Concentration%20and%20comparison%...
- 128k
2
votes
1
answer
78
views
Existence of stationary stochastic processes with very high correlation
A question was recently asked by a new user, SomeoneHAHA, and then deleted by the user, after receiving an answer. I think the question and the answer (QA) to it may be of interest to some users. ...
- 128k
3
votes
1
answer
152
views
Question on example 3.0.1 in Yurinsky's book "Sums and Gaussian vectors"
Good day to All.
Let $S_{1,n} = \sum_{i=1}^{n}\xi_{i}$, where $(\xi_{i})_{i \in \mathbb{N}}$ be independent RV with values in some Banach space.
On pages 79-80 in this book author provides an ...
- 128k
2
votes
1
answer
248
views
Ratio of expectation involving random unit vectors
Let $u=(u_1,...,u_n), v=(v_1,...,v_n)$ be two random vectors independently and uniformly distributed on the unit sphere in $\mathbb{R}^n$. Define two other random variables $X=\sum_{i=1}^nu_i^2v_i^2$, ...
- 61.9k
2
votes
1
answer
675
views
Moment generating function of random unit vector
Let $X$ be uniformly distributed on the unit sphere $S^{n-1}$. Is there any result concerning the calculation or bound (particularly lower bound) of
$$\mathbb{E}[\exp(X^Tv)]$$
for any $v$?
CommunityBot
- 1
2
votes
0
answers
80
views
Bridging between Rosethal Inequalities and log convex tails
Let $X_1,\ldots,X_n$ be independent with $\mathbf{E}[X_i] = 0$ and $\mathbf{E}[|X_i|^t] < \infty$ for some $t \ge 2$. Write $\|X\|_p = (E|X|^p)^{1/p}$.
Then we have the classical "Rosenthal-type ...
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
2
votes
0
answers
58
views
Bounds for $\sum_{t=1}^Tn_t(s_t)^{-\alpha}\mu(s_t)$ where $n_t(s) = \sum_{1 \le t' \le t} 1_{\{s_{t'}=s\}}$ for $s \in [k]$ and $\mu \in \Delta_k$
Disclaimer: I'm not certain this is the right venue for this post, but I'll give it a try...
So trying prove some bounds in my ongoing work in theoretical reinforcement learning, I encountered the ...
- 6,853
2
votes
1
answer
235
views
Kolmogoroff condition for truncated random variables
Question summary. Does the Kolmogoroff condition $\sum_{n=1}^\infty\frac{\mathbb V Y_n}{n^2} < \infty$ hold for truncated random variables $Y_n := X_n \cdot 1_{\{X_n \le n\}}$ (see below for a more ...
- 128k
5
votes
2
answers
185
views
Density near at $0$ for the integral of the positive part of the Brownian motion
This question was asked recently on MO and then deleted by the owner, user Aalon. I think the question deserves to be answered, which is what I will try to do here. Aalon was reading this paper, where ...
- 66
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_{\...
- 128k
4
votes
1
answer
336
views
Binomial Distributions and Inequality
Suppose $c>2$ is a real number, and $x$ solves equation $f(\frac{1}{2}+x,m,2m)=(2m+1)cx$ for some $m>0$ integer number, where $f$ is probability mass function for binomial distribution, with ...
- 128k
3
votes
0
answers
185
views
Measure change bound for function of subgaussian r.v
Let $X$ be a (sub)gaussian r.v. on $\mathbb{R}^d$; say $X\sim\mathcal{N}(\mathbf{0},\mathbb{1}_d)$; and let $a\colon\mathbb{R}^d\to [0,1]$ be a function with $\mathbb{E}[a(X)] > 0$.
It is not hard ...
- 1,372
4
votes
1
answer
206
views
Inner product of sorted Gaussian vector
Suppose $X_1,\ldots,X_n$ are i.i.d. standard normal. I'm wondering how to analyze the following quantity:
$$\left|\frac{X_{(1)}X_{(n)}+X_{(2)}X_{(n-1)}+\cdots+X_{(n)}X_{(1)}}{n}\right|$$
where $X_{(1)}...
CommunityBot
- 1
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$?
...
- 128k
5
votes
1
answer
169
views
Сoincidence of discrete random variables
Let $\xi, \eta$ be a discrete random values and $\mathbb E| ξ |$, $\mathbb E | η | < +\infty$, and any value of these
values are accepted with a non-zero probability. How to prove that from $\...
4
votes
1
answer
406
views
Expectation of exponential of a function of independent Rademacher r.v.'s involving the error function
Let $Z,Z'\in\{-1,1\}^n$ be two independent vectors of i.i.d. Rademacher r.v.'s, where $1\leq n \leq d$ are two integers ($d\gg 1$). I am trying to get an upper bound on
$$
\mathbb{E}_{ZZ'}\left[ \exp\...
CommunityBot
- 1
2
votes
1
answer
280
views
Complicated bound after using Stirling's approximation
I have this inequality $$\frac{1}{a}\exp\bigl\{-\frac{4}{h^2}\bigr\} \geq \frac{1}{f}$$ where $$ a \leq \Bigl(\pi^{d/2}\Gamma(\frac{1}{2}d+1)^{-1} + 1\Bigr) \left(\frac{h^{d+1}}{2} \Gamma \left(\frac{...
- 225
4
votes
1
answer
863
views
Hoeffding's inequality for Hilbert space valued random elements
Suppose that $\mathbb H$ is a separable Hilbert space and $X_1,\ldots,X_n$ are independent zero mean $\mathbb H$-valued random elements such that $\|X_i\|\le s$ for each $1\le i\le n$, where $\|\cdot\|...
- 128k
2
votes
0
answers
330
views
Concrete Hanson-Wright inequality?
I'm working on a paper that requires bounding
$$\Pr\left[|\vec x^\top Q \vec y| >= t\right]$$ where $Q$ is a matrix (happens to be symmetric) and $\vec x,\vec y$ are iid real mean-zero subgaussian ...
- 21
3
votes
2
answers
189
views
Is the covariance of squares always bounded from below by two times the covariance?
I came across the following inequality in one of my calculations ($X,Y$ are centered random variables):
$$\operatorname{E}(X^2Y^2)-\operatorname{E}(X^2)\operatorname{E}(Y^2) \geq 2 \operatorname{E}(...
- 128k
-1
votes
1
answer
76
views
Transforming random variables for having good property?
For arbitrary functions $A$ and $B$ and independent random variables $X$ and $Y$, assume that
\begin{align}
\Omega&\triangleq \{(x,y): A(x,y)=1\},\\
\Lambda&\triangleq \{x: B(x)=1\}.
\end{...
6
votes
4
answers
1k
views
Improvement of Chernoff bound in Binomial case
We know from Chernoff bound
$P\bigg(X \leq (\frac{1}{2}-\epsilon)N\bigg)\leq e^{-2\epsilon^2 N}$ where
$X$ follows Binomial($N, \frac{1}{2}$).
If I take $N=1000, \epsilon=0.01$, the upper bound is ...
- 128k
1
vote
2
answers
462
views
lower bound the probability of at least L collisions
Lets say we get a list $M$ containing $|M|=\sqrt{L\cdot N}$ randomly and independtly drawn elements from a set of size $N$. And lets denote the $i$-th element of the list $M$ by $M[i]$.
If we now ask ...
- 128k
0
votes
1
answer
143
views
Right tail decay of F distribution [closed]
Suppose $X\sim F(a,b)$. Is there any sharp upper bound of the following probability with large $x$?
$$\mathbb{P}(X\geq x)$$
what is the order of the above probability as $x\to+\infty$?
- 128k
3
votes
1
answer
171
views
Why does the assumption $|U_t| \le \frac1{p_{\min}}$ work in this paper?
I am reading a 2009 paper right now "Importance Weighted Active Learning" and on page 5, there is a theorem that uses the inequality $|U_t| \leq \frac{1}{p_{\min}}$. I am not sure how the paper found ...
14
votes
2
answers
2k
views
Is the conditional expectation a contraction in weak $\mathbb L^p$ spaces?
Let $(\Omega,\mathcal F,\mu)$ be a probability space. It is well-known that if $\mathcal A$ is a sub-$\sigma$-algebra of $\mathcal F$, $p\geqslant 1$ and $X$ is an element of $\mathbb L^p$ which takes ...
CommunityBot
- 1
3
votes
1
answer
209
views
Log concavity of the maximum of dependent Gaussians
Let $Z_1,\dots,Z_n$ be dependent Gaussian random variables. Is it true that $X=\max\{Z_1,\dots,Z_n\}$ has a log-concave distribution function? This is true for the independent case, but is it true in ...
- 128k
12
votes
3
answers
549
views
A probabilistic angle inequality
Conjecture: There is a universal constant $c$ such that for any fixed nonzero real vector $q$ of any dimension $n$ and any random vector $p$ of the same dimension $n$ with independent components ...
- 3,873
8
votes
1
answer
416
views
Expectation inequality for sampling without replacement
Is the following proposition correct?
$X_1, X_2, X_3$ are uniformly at random sampled from a finite set $\mathcal X$ without replacement.
$f : \mathcal X^2 \rightarrow \mathbb R_{\ge0}$ is symmetric:...
- 109k
3
votes
1
answer
235
views
Inequality for exponential sum in Dvoretzky 1972
I'm currently trying to figure out the following inequality. It looks like an inequality for the exponential sum, but I can't verify it or find a source explaining it any further. Most likely it has ...
- 128k
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) \...
- 128k
3
votes
1
answer
105
views
A gaussian based inequality
I came across an inequality in the paper of 'Estimation of a function with discontinuities ...' (AoS, 1998, p.1374) and tried to prove it, but could not get to the result. Some simulations also seemed ...
- 23.2k
1
vote
1
answer
499
views
property of iid random variable
Let $ (\xi_i)_{i \ge 1} $ be independent identically distributed random variables, taking values in $ (1,3]$.
Can we show:
$P( \exists N \in \mathbb{N}, \text{ s.t. } \forall k \ge 0, \prod_{i=1}^{...
- 128k
5
votes
1
answer
279
views
Mixed norm inequality
Suppose we have a product space $(X_1\times X_2,\mu_1\otimes\mu_2)$, with finite measures $\mu_1,\mu_2$ and $p>1$.
Is there a possibility that an inequality of this form holds on the product space?
...
- 128k
0
votes
0
answers
112
views
On certain integrals of exponential functions with respect to Gaussian measures
I have questions about the integral
$$F(a,b,c)=\sqrt{\frac{a}{\pi}}\int_{0}^{\infty}e^{-bx^4+cx^3-ax^2}dx$$
for $a,b,c>0$.
What is the asymptotic behavior of $F(a,b,c)$ for small $a,b,c$? In ...
CommunityBot
- 1
4
votes
2
answers
432
views
How to prove the sum of n squared binomial probabilities does not increase as n increases
Let $F\left( n \right) = \sum\limits_{k = 0}^n {{{\left( {C_n^k{p^k}{{\left( {1 - p} \right)}^{n - k}}} \right)}^2}} $, prove $F\left( n \right) \ge F\left( {n + 1} \right)$.
UPDATE: More general, ...
- 43
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_{\...
- 128k
6
votes
2
answers
2k
views
Is there a name for this theorem?
I wonder if there is a name or reference for the following fact. It is not the proof I am looking for.
Let $s_1, s_2, ...,s_n$ be non-negative real numbers ordered in a non-increasing way. Let $b_1,...
- 1,299
5
votes
1
answer
348
views
A Minkowski-like inequality
Assume that $X$ and $Y$ are two arbitrary non-negative random variables. Is the following inequality true for $1\leq\alpha\leq 2$?
\begin{align}
\left(\mathbb{E}\left[X^\alpha\right]-\mathbb{E}\left[...
- 128k
4
votes
1
answer
1k
views
Does variants of Bernstein and Freedman concentration inequalities exist with NO uniform bound on the range of RV or martingale differences
A classic formulation of the Bernstein inequality (from Wikipedia) is as follow:
Let $X_1, \ldots, X_n$ be independent zero-mean random variables. Suppose that $|X_i|\leq M$ almost surely, for all $i$...
- 128k