Questions tagged [probability-inequalities]

Probability Inequalities are useful for bounding quantities that might otherwise be hard to compute. A related concept is a concentration inequality, which specifically provides bounds on how far a random variable deviates from some value.

Filter by
Sorted by
Tagged with
0
votes
1answer
36 views

What does the general case of bounded random variables mean in terms of Hoeffding's Inequality?

The following equation is Hoeffding's Inequality from Wikipedia for the general case of bounded random variables. I have just come to understand Hoeffding's Inequality for the special case of ...
1
vote
1answer
33 views

Need mathematical steps for Hoeffding's Inequality applied to Bernoulli Distribution

I am trying to understand Hoeffiding's Inequality in Machine Learning and I am referring to WikiPedia for it. Hoeffding's Inequality is defined as follows: $ P(|\hat{\theta} - \theta)| \ge \epsilon) \...
2
votes
0answers
27 views

How to derive Bonferroni's Inequality using Boole's Inequality?

I'm trying to derive Bonferroni's inequality using : $$P(\cup^{\infty}_{i=1} A_i) \leq \Sigma^{\infty}_{i=1} P(A_i)$$ for any sets A_1, A_2, ... (Boole's Inequality) The result I want is (Bonferroni'...
0
votes
0answers
13 views

Connection between subgaussian/subexponential and exponential family

I am wondering if there is any relationship between subgaussian/subexponential with (one parameter) exponential family. In particular, is there any sub-family density that belongs to both ...
0
votes
0answers
12 views

Bound on sample size- Hoeffdings inequality

Studying for my upcoming statistics exam I tried to solve the following: In some population, each individual likes exactly one out of 30 possible music genres. In some survey, n people are drawn ...
2
votes
0answers
15 views

Hoeffding's inequality vs DKW inequality

What is the difference between Hoeffding's inequality: $$\mathrm{P}(|\hat{F}_n(x)-F(x)|\geq \epsilon) \leq 2e^{-2n\epsilon^2}$$ and the Dvoretzky-Kiefer-Wolfowith (DKW) inequality: $$\mathrm{P}(\...
1
vote
1answer
51 views

Prove that $E[e^{2(m−1)X^2}]\le m$

I'm reading "Understanding Machine Learning: From theory to algorithms". The problem is as follows, which is Exercise 31.1 of the book on page 416. Let $X$ be a random variable that satisfies $P[X \...
1
vote
0answers
35 views

Show that if $Y$ has $E(Y)=μ,Var(Y)=σ^2$, and $P(|Y-μ|<σ)=0$, then $Y$ has the same distribution as $X$ described below for $k=1$

I'm having a hard time proving the second and third case of $X$: Show that if $Y$ has $E(Y)=μ,Var(Y)=σ^2$, and $P(|Y-μ|<σ)=0$, then $Y$ has the same distribution as $X$ described below for $k=1$. $...
2
votes
1answer
46 views

How can I show that $P\{|(X-\mu_X)+(Y-\mu_Y)| \ge k\sigma\} \le (2(1+\rho))/k^2$?

Let $\sigma^2$ be the common variance of the random variables $X$ and $Y$, with their correlation coefficient being $\rho$. Show that $\forall k>0$, $P\{|(X-\mu_X)+(Y-\mu_Y)| \ge k\sigma\} \le (2(...
1
vote
0answers
17 views

Markov inequality and Boundness in probability

Let $\{X_n\}$ and $\{a_n\}$ be sequences of random variables and real numbers, respectively. Say that $X_n=O_P(a_n)$ iff $\forall\epsilon>0$, $\exists N,M>0$ such that for all $n>N$, we ...
1
vote
1answer
18 views

Does this expectation inequality holds?

Let $X\in L_p(P), p>1$. Is the following result true? $$E[\lvert X\rvert I(\lvert X\rvert>C)]\leq C^{1-p}E\lvert X\rvert^p.$$ where $C>0$. It can be found in the proof of Corollary A.1 (...
2
votes
0answers
28 views

Exponential Inequality For Probability of Being Close to Maximum

Given $n$ independent identically distributed random variables $X_1, X_2, \ldots, X_n$ that have $|X_i| < \lambda$ for all $i$. Let $\max(X)$ be the maximum of these $n$ variables. Is there a ...
1
vote
2answers
33 views

Can Markov inequality be used to define bounds in a meaningful way?

Suppose $X\sim \text{Binomial}(100,0.5)$. Recall Markov's inequality. $$\Bbb{P}(X\geq 5) \leq \frac{\Bbb{E}[X]}{5}=\frac{100*0.5}{5} = 10$$ Why is this inequality valuable? Since I'm working with a ...
0
votes
0answers
41 views

What is the probability that maximum likelihood algorithm is right in Bernoulli trials?

Let $\varepsilon\in(0,1)$ and $p:=\frac{1+\varepsilon}{2}$. Suppose that we have a sequence of independent Bernoulli random variables of parameter $p$, say $(X_k)_{k\in\mathbb{N}}$ defined on a ...
4
votes
0answers
72 views

Sum bounded in probability

Suppose that $\sum_{n=1}^N|c_n| = O(1)$ and that $X_n = O_p(1)$ in the sense that for every $\epsilon>0,\exists M<\infty$ such that $$\sup_nP(|X_n|>M)<\epsilon$$ Can we claim that $\sum_{...
0
votes
0answers
27 views

Usefulness and validity of Alternative definitions of “quantile”

According to textbook, the $p\,$th quantile of a random variable $X$ is any real value $x$ satisfying $P(X \geq x)\geq 1-p$ and $P(X \leq x) \geq p$. Why isn't the alternative definition, a $p\,$th ...
4
votes
0answers
59 views

A consistent estimator with infinite expectation?

Typical (or common) approaches to prove an estimator is consistent require finite mean and variance. The proofs usually follow from concentration bounds, e.g. Markov, Chebyshev, etc. I'm wondering ...
2
votes
0answers
21 views

Probability of sparse spectrum

Consider a vector $v$ such that $v \sim \mathrm{Unif}(\mathbb{S}^{d-1})$, the uniform distribution on the unit sphere in $d$ dimensions. Question: is there an upper bound on the probability that $v$ ...
1
vote
0answers
37 views

Concentration inequality for max component of a multivariate Gaussian in the general case

I am looking to bound the variance of the maximum component of a vector distributed multivariate Gaussian in the general case where the Gaussian distribution has arbitrary mean and full covariance ...
1
vote
1answer
44 views

Unusual Markov inequality for normal distribution

I'm trying to answer the following question from Larry Wassermans book on statistical inference. My question is how did they arrive at the Markov bound, it does not seem like the normal form of the ...
1
vote
0answers
21 views

probability density of a random vector greater than some value? [duplicate]

In single dimension, the probability that a random variable $X$ is greater than some value $x$ is easily related to the cumulative distribution(c.d.f.) as $Pr(X > x) = 1 - F(x)$ if only $Pr[X \leq ...
0
votes
1answer
37 views

Estabilishing an upper bound for the probability of an impossible event, by sampling [duplicate]

Lets suppose there is an event that gives a random outcome each time it happens. The set of possible events is finite, but their probabilities differ, sometimes by orders of magnitude. (imagine a ...
0
votes
1answer
67 views

How can I prove $ P(X> 0) \geq \frac{(E[X])^2}{E[X^2]}$ for a random variable $X$?

For a random variable $ X \geq 0 $ and $E[X^2] < \infty $, I'm asked to prove the following: $$ P(X> 0) \geq \frac{(E[X])^2}{E[X^2]}$$ It makes intuitive sense to me that it must be the case, ...
5
votes
2answers
192 views

Order Statistics of Poisson Distribution

I have been given the following question, Let $n ≥ 2$, and $X_1, X_2, . . . ,X_n$ be independent and identically distributed $Poisson (λ)$ random variables for some $λ > 0$. Let $X_{(1)} ≤ ...
0
votes
1answer
30 views

Getting From Concentration Inequality to Interval Length

I've seen this used some times and I would like to ask what steps are taken on the way to getting there: E.g. assuming bounded variance, we can use Chebyshev concentration inequality: for any $t>0$...
1
vote
1answer
138 views

General solution of expected value of E(f(X))?

This is maybe a trivial question I came up while solving a few examples and understanding Markov/Chebyshev inequalities and subsequently in evaluating Chernoff bounds. Suppose $X$ is a random variable ...
0
votes
0answers
38 views

Best confidence interval for sample mean of any variable in L2

I was thinking about a very basic matter, and arrived at the conclusion I know a lot less about it than I thought. When people have data $ X_1^N $ sampled i.i.d. from a distribution: $ X_1^N \sim X $,...
3
votes
0answers
54 views

Concentration inequality for mean of Gaussian mixture

Say I have i.i.d. samples $X_1, \ldots, X_n \sim p \mathcal{N}(\mu_1, \sigma^2) + (1 - p) \mathcal{N}(\mu_2, \sigma^2)$. Then suppose I estimate the mean with the sample mean $$ \widehat{\mu} = \frac{...
2
votes
1answer
60 views

Machine learning for inequalities

This is a very general question about machine learning. Two of the most standard problems in ML are classification and regression. E.g. if we have pictures of buildings, we can classify them as two-...
3
votes
1answer
104 views

Algebra in Cantelli-Cheybyshev Inequality Proof

I am confused by the following (possibly simple) algebra in the proof of the Cantelli-Cheybyshev inequality. I am following Rohatgi and Saleh (2015, Section 3.4 Lemma 1) where we plug in $\phi(x)=(x+c)...
1
vote
2answers
81 views

Two distributions, same mean, different variance: Stochastic dominance for deviation from mean?

Say you have two (bounded) random variables, $X$ and $Y$, on the same discrete probability space, such that $E(X)=E(Y)$ but $Var(X) < Var(Y)$. Do I know that, for any $k \geq 0$, $$ \text{Prob}(|X-...
1
vote
0answers
30 views

Bounds on quantiles of the minimum of summations of (possibly dependent) random variables

Suppose I have $2N$ continuous random variables $X_1, \ldots, X_N, Y_1, \ldots, Y_N$ and that I can evaluate the quantiles of the respective distributions. Given a value $w \in [0, 1]$ I would like to ...
2
votes
2answers
40 views

Does an inequality hold as an expectation over a probability distribution?

Suppose I have to functions $f(x)$ and $g(x)$ such that $$ f(x) \leq g(x) \quad \forall x. $$ For a distribution $\pi(x)$ on $x$, is it necessarily true that $$ E_\pi[f(x)] \leq E_\pi[g(x)]? $$ My ...
1
vote
0answers
28 views

Simplification using Cauchy Schwartz Inequality

Can someone please help me understand how the last step in the highlighted part in the equation is arrived at? I did not get how the Cauchy Schwartz Inequality comes into play here. The full paper is ...
1
vote
1answer
57 views

Intuition behind the no convergence of the variance of sum of random variables

$$Var[\bar{X}] = \sigma^2/n $$ $$Var [\sum{X}_i] = n\sigma^2$$ $$lim_{n \to \infty} Var[\bar{X}] = 0 $$ wich means at $\infty$ we will always get the same $\bar{X}$ after every simulation. I ...
3
votes
1answer
46 views

Effect of scaling on the mean of 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$? ...
1
vote
1answer
43 views

How to prove the concentration equality for standard normal?

The following inequality is given in some of Yale's online lecture notes $$P(|Z|>x) \leq 2 \sqrt{2 \pi} \phi(x)$$ Where $Z \sim N(0,1)$ with density $\phi(x)$. They call it a concentration ...
1
vote
0answers
97 views

Tight upper bound on the expectation of a concave function

N is a random variable whose sample space is [0,$\infty$). I have an expression in terms of the expectation of this variable and I want to find a tight upper bound on the whole expression. The ...
4
votes
1answer
48 views

Comparing suprema of inner products of Gaussian variables

I'm given two i.i.d. standard normal vectors $x, y \sim \mathcal{N}(0, I_n)$, and vectors $a \in \mathbb{S}^{n-1}$, the unit sphere in $n$ dimensions. Additionally, given a set $S \subseteq [n]$, I ...
2
votes
1answer
226 views

An inequality giving a sharper bound than that given by the Chebyshev's?

Let $X > 0$ be a random variable; let $P$ be the underlying probability measure; let $\delta > 0$. I wonder if there is already in probability literature a known result giving a sharper bound ...
3
votes
0answers
131 views

Which concentration inequalities apply when moments are infinite?

I have 2 questions: Suppose I have a finite mean but an infinite variance for a discrete distribution w/support $\{1,2,\dots\}$. Is there any probability inequality tighter than Markov in this case? ...
1
vote
1answer
83 views

Concentration for Conditional Random Variable

Consider a conditional random variable \begin{equation} X = \begin{cases} Y & \quad\quad ,X \in A \\ Z & \quad\quad ,X \in A^\complement \end{cases} \end{equation} $Y$ ...
5
votes
1answer
87 views

Upper bound for the probability $P\left[\left|\frac{Y_n}{n}-p^2\right|>\varepsilon\right]$

Let $X_1,X_2,\cdots,X_{n+1}$ be independent random variables with $$P(X_i=1)=p=1-P(X_i=0)\quad\text{ for all }i$$ Define $Y_i$ to be the number of $i$'s such that $X_i=X_{i+1}=1\,,\quad i=1,2,\...
1
vote
0answers
52 views

Conditional distribution relations

There is a probability density function of the form, $f_S(s)=\displaystyle\iint f_S(s|x,y)f_{X,Y}(x,y)dxdy$ that is used for evaluation of expectation of some monotonic function $\mathbb{E}[g(S)]=\...
2
votes
0answers
104 views

Lower bounds on covering numbers for sparse vectors

Consider the set $S_k$, which is defined as the subset of $k$-sparse vectors in the unit sphere in $d$ dimensions: $$ S_k \triangleq \left\{ x \in \mathbb{R}^d : \| x \|_2 = 1, \, \left|\operatorname{...
5
votes
1answer
169 views

How good an approximation is sampling with replacement to sampling without replacement?

I'm learning about probability with Feller's book and he states that, when the population size $n$ is big in comparison with the sample size $r$, then $n_r$, which is a shorthand for $\frac{ n!}{(n-r)!...
5
votes
1answer
114 views

Covering the unit sphere with sparse vectors

I'm looking for references for covering the $d$-dimensional unit sphere $$ \mathbb{S}^{d - 1} = \left\{ x \in \mathbb{R}^d : \| x \| = 1 \right\} $$ I'm trying to cover $\mathbb{S}^{d-1}$ with ...
1
vote
1answer
25 views

Concentration Square Increments of a MDS

I have a martingale difference sequence $\{ X_t \}$ where each $X_t$ is subGaussian. Are there concentration inequalities for $$ \sum_{t=1}^T X^2_t - E \left( \sum_{t=1}^T X^2_t \right) $$
0
votes
1answer
86 views

Is my solution correct for this measure-concentration related task?

I'm reading the book "Concentration inequalities" by Boucheron, Lugosi, Massart. There is an exercise section after each chapter. I've tried to solve one and would like to understand, whether it would ...
3
votes
1answer
176 views

Accuracy of empirical cumulative distribution function

I have a random variable with an unknown distribution and I want to find its cumulative distribution function. I sample the distribution $N$ times, with $$X_1, \dots, X_N$$ being iid random ...

1 2 3 4 5