All Questions
Tagged with pr.probability inequalities
346 questions
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 $\...
- 288
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[...
- 233
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
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 ...
- 4,049
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$...
- 4,049
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
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
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. ...
- 710
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
3
votes
3
answers
6k
views
Probability of a random variable greater than its expected value
We have a lot of probabilities lower bounding as (e.g. chernoff bound, reverse markov inequality, Paley–Zygmund inequality)
$$
P( X-E(X) > a) \geq c, a > 0 \quad and \quad P(X > (1-\theta)E[...
- 141
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
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 ...
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 ...
- 223
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 $...
- 470
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 ...
- 343
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
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 \ |...
- 331
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 \{...
- 237
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
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
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 ...
- 1,503
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\...
- 1,495
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
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 ...
- 97
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]$...
- 121
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 ...
- 237
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
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]$....
- 13
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 ...
- 1,326
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$, ...
- 562
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
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=...
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
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 ...
- 101
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,\...
- 1,329
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%...
- 123
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 ...
- 65
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,...
- 245
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$, ...
- 1,495
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 ...
13
votes
2
answers
1k
views
A comprehensive list of random walk inequalities?
I am interested in finding a comprehensive list of all noticeable random walk inequalities.
ie. $S_n = \sum_{k\leq n} X_i$ for i.i.d symmetric $X_i$
I can only seem to find books/papers that list ...
- 231
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$?
- 1,495
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
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$ ...
- 183
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 ...
- 1,326
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
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 ...
- 128k