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
2
votes
1answer
12 views

Distributive property of probabilistic inequalities involving random variables on both sides

Can I break down $P(h \geq (A + B)$, given all $ A,B,h$ are all random variables. Will the following rule works? $$P[h \geq (A + B)] = P(h\geq A) + P(h\geq B)$$ Actually, in one of my mathematical ...
1
vote
0answers
28 views

Bounds on distance between two independently variables drawn from the same distribution

Suppose $X_1$ and $X_2$ are iid from an arbitrary distribution with variance $\sigma^2$. How can we derive an upper bound for: $$P(|X_1-X_2|\ge\delta)$$ One simple idea is Chebyshev's Inequality, ...
0
votes
0answers
19 views

Convergence in probability and Chebyshev inequality

Given problem: The elegant solution is to use Markov inequality for $X^2_n$. But my solution was via Chebyshev inequality, smth like that: $P(|X_n - 1/n| \ge k) \le \frac{\sigma^2}{k^2}$, now lets ...
1
vote
0answers
20 views

Generalization of the Payley-Zigmund inequality

The Payley-Zigmund inequality states that for a positive random variable $Z$ the following holds \begin{equation} \operatorname{P}( Z > \theta\operatorname{E}[Z] ) \ge (1-\theta)^2 \frac{\...
2
votes
1answer
47 views

Use Chebyshev's inequality to find a lower bound of a Chi-Square Distribution

I'm trying to solve the following exercise but I'm not sure if what I'm doing is right. "Let $X$ be an r.v. distributed as $\chi_{40}^{2}$. Use Tchebichev’s inequality in order to find a lower ...
0
votes
0answers
15 views

Applicability of Hoeffding's Inequality

I am working through Larry Wasserman's All of Statistics. I am trying to understand why Hoeffding's Inequality was valid for the following problem: Suppose we test a prediction method on a set of $n$ ...
1
vote
0answers
30 views

Covariance of X and Y conditional on X+Y>Z? [closed]

Suppose that $X$, $Y$, and $Z$ are three independent random variables. Is there a way to compute the following conditional covariance? $Cov(X, Y | X + Y \geq Z)$
0
votes
1answer
37 views

Laplace Inequality

I am trying to prove that if $r_i \sim Lap(0,1/\varepsilon)$ where $\varepsilon >0$ then: $$Pr[r_i \geq 1+r^*] \geq e^{-\varepsilon}Pr[r_i \geq r^{*}]$$. I know that for $r*>0$ it satisfies ...
1
vote
1answer
36 views

I've taken an alternative approach to a convergence in probability problem. Is there any mistake and/or is my conclusion correct?

I am currently studying convergence on my own, which means that I don't have many alternatives for discussing problems in order to improve my understanding. This post was an alternative to get around ...
1
vote
1answer
35 views

Can we bound $\frac{Cov(X,XY)}{Var(X)}$?

The question is can we bound $\beta = \frac{Cov(X,XY)}{Var(X)}$ with the help of the following assumptions : Y is a positive bounded random variable, let's assume $Y \in [0,1]$. X has an expectation ...
0
votes
0answers
19 views

Symmetrization in Proof of Hoeffding's Lemma

This alternative proof of a slightly weaker version of Hoeffding's Lemma features in Stanford's CS229 course notes. What's notable about this proof is its use of symmetrization. However, I find this ...
2
votes
1answer
21 views

Why $Pr[X-\mu \geq t]= Pr[e^{\lambda(X-\mu)} \geq e^{\lambda t}]$ for all $\lambda> 0$

I hope everyone is having a nice day. I don't know why this inequality holds. $$ Pr[X-\mu \geq t]= Pr[e^{\lambda(X-\mu)} \geq e^{\lambda t}] $$ For $\lambda >0$. I guess it has something to do ...
0
votes
0answers
17 views

How to select a set of MCMC samples with some probability?

I have a set of samples gathered using MCMC of random variable $X$. Let's call this set $X_s$. How to select a subset of samples $S$such that $$ Probability(X_s(S) < constant) > 0.01 $$ I want ...
1
vote
1answer
25 views

Expectation of (sum subtract the expectation of sum)

Let's say we have random variables $\mathbf{X}$, and we have $P(\mathbf{X}\in [a, b])=1$, we have $\mathbf{S}_n = \mathbf{X}_1 + \mathbf{X}_2, +\dots + \mathbf{X}_n$. If $\mathbf{X}_1, \mathbf{X}_2, ...
1
vote
0answers
88 views

Is there a different way to bound probability, with no distributional assumptions, other than Markov's inequality?

I'm having trouble answering this probability interview question from Interview Query: Let's say there is man who is 5.10 ft tall who doesn't know how to swim. Let's say he wants to swim in a lake ...
1
vote
0answers
122 views

Tail bounds for sample means of i.i.d random variables where the moment generating function exists

I want to figure out the proof of Lemma 4 in the following paper. The lemma states that Let $Y_1, Y_2,\ldots Y_m$ be i.i.d random variables such that $\mathbb{E}\left[e^{zY}\right] < \infty$ ...
1
vote
1answer
28 views

How to using the Markov Inequality to find the upper bound for $\mathbb{P}(X > 2)$ given I only have information about $X^4$?

Let $X$ be a nonnegative random variable that satisfies $\mathbb{E}[X^{4}]=4$ . How should I calculate an estimate for the $\mathbb{P}(X \geq 2)$ using the Markov Inequality? I tried to find a ...
4
votes
2answers
288 views

Formula of the Chebyshev's inequality for an asymmetric interval

The formula for Chebyshev's inequality for the asymmetric two-sided case is: $$ \mathrm{Pr}( l < X < h ) \ge \frac{ 4 [ ( \mu - l )( h - \mu ) - \sigma^2 ] }{ ( h - l )^2 } . $$ What I don't ...
3
votes
1answer
226 views

Showing the weak law of large number of non-IID sequence of random variables

Common proofs on the law of large numbers usually assume a sequence of IID random variables. If $X_1\dots X_n$ has a common expected value $\mu$, finite but not necessarily common variance (hence not ...
0
votes
0answers
23 views

Using Hoeffding's inequality on sum of uniform variables

I have the following problem: $X_1,...,X_n$ are i.i.d. $\sim U(-3,5)$ continuous uniform variables in the support between -3 and 5. $S := X_1 + ... + X_n$. I need to use Hoeffding's inequality to ...
3
votes
1answer
44 views

Basic probability inequality between 4 events

I have been asked to prove the following but am unsure if it is true: $$\mathbb{P}(A,B,C)<\mathbb{P}(D) \implies \mathbb{P}(A) + \mathbb{P}(B) + \mathbb{P}(C) - 2 < \mathbb{P}(D)$$ I don't ...
0
votes
0answers
27 views

Are the following terminologies error/risk/marmgin/regret bounds related?

I recently come across papers with titles resembling "Error/Risk/Margin/Regret Bounds" and I can't help but wondering if there is any fundamental (mathematical) difference between these terminologies? ...
1
vote
1answer
308 views

Jensen inequality and bias of sample standard deviation

I am currently studying Introduction to Probability, second edition, by Blitzstein and Hwang. In studying the Jensen inequality, the following example is presented: Example 10.1.6 (Bias of sample ...
1
vote
0answers
15 views

How close a sample is to the Normal distribution ( Berry-Esseen Theorem)

My question is how can I use the Berry-Esseen Theorem to know how close to the Gaussian distribution is $L$, where $$L=nLn(2)+Ln(r_1)+Ln(r_2)...Ln(r_n).$$ $r_i \geq 0$ is a i.i.d. random variable ...
0
votes
1answer
57 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
51 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
50 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'...
1
vote
1answer
57 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
15 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
31 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}(\...
2
votes
1answer
64 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
45 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
57 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(...
2
votes
0answers
21 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 ...
2
votes
1answer
25 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
30 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
46 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
43 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
79 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
33 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
72 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
25 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$ ...
2
votes
0answers
42 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
64 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 ...
0
votes
0answers
22 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
44 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
93 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
443 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
32 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
257 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 ...

1
2 3 4 5