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
34
votes
3answers
4k views

Does a sample version of the one-sided Chebyshev inequality exist?

I am interested in the following one-sided Cantelli's version of the Chebyshev inequality: $$ \mathbb P(X - \mathbb E (X) \geq t) \leq \frac{\mathrm{Var}(X)}{\mathrm{Var}(X) + t^2} \,. $$ Basically, ...
10
votes
2answers
8k views

Random variables for which Markov, Chebyshev inequalities are tight

I am interested in constructing random variables for which Markov or Chebyshev inequalities are tight. A trivial example is the following random variable. $P(X=1)=P(X=-1) = 0.5$. Its mean is zero, ...
11
votes
1answer
5k views

Understanding proof of a lemma used in Hoeffding inequality

I am studying Larry Wasserman's lecture notes on Statistics which uses Casella and Berger as its primary text. I am working through his lecture notes set 2 and got stuck in the derivation of lemma ...
21
votes
4answers
4k views

What is a tight lower bound on the coupon collector time?

In the classic Coupon Collector's problem, it is well known that the time $T$ necessary to complete a set of $n$ randomly-picked coupons satisfies $E[T] \sim n \ln n $,$Var(T) \sim n^2$, and $\Pr(T &...
12
votes
3answers
462 views

Regarding convergence in probability

Let $\{X_n\}_{n\geq 1}$ be a sequence of random variables s.t $X_n \to a$ in probability, where $a>0$ is a fixed constant. I'm trying to show the following: $$\sqrt{X_n} \to \sqrt{a}$$ and $$\frac{...
1
vote
1answer
2k 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 ...
2
votes
4answers
232 views

If $P(A \mid E) > P(B \mid E)$ and $P(A \mid \neg E) > P(B \mid \neg E)$, then is $P(A) > P(B)$ true?

If $P(A \mid E) > P(B \mid E)$ and $P(A \mid \neg E) > P(B \mid \neg E)$, then is $P(A) > P(B)$ true? If it is, how to prove it? Intuitively, I'm thinking it should be true, but I don't ...
1
vote
0answers
43 views

Can we use Frechet inequalities to infer significance of collections of hypothesis tests?

There are numerous issues that have been identified both in the theory and practice of $p$-values, including the arbitrariness of confidence levels, interpretation, and tail-risk in the ...
37
votes
2answers
2k views

Probability inequalities

I am looking for some probability inequalities for sums of unbounded random variables. I would really appreciate it if anyone can provide me some thoughts. My problem is to find an exponential upper ...
13
votes
1answer
2k views

One sided Chebyshev inequality for higher moment

Is there an analogue to the higher moment Chebyshev's inequalities in the one sided case? The Chebyshev-Cantelli inequality only seem to work for the variance, whereas Chebyshevs' inequality can ...
17
votes
1answer
594 views

In statistical learning theory, isn't there a problem of overfitting on a test set?

Let's consider the problem about classifying the MNIST dataset. According to Yann LeCun's MNIST Webpage, 'Ciresan et al.' got 0.23% error rate on MNIST test set using Convolutional Neural Network. ...
8
votes
1answer
5k views

Cantelli's inequality proof

I am trying to prove the following inequality: EDIT: Almost immediately after I posted this question, I discovered that the inequality I am being asked to prove is called Cantelli's inequality. When ...
6
votes
2answers
607 views

$E(X)E(1/X) \leq (a + b)^2 / 4ab$

I've worked on the following problem and have a solution (included below), but I would like to know if there are any other solutions to this problem, especially more elegant solutions that apply well ...
4
votes
1answer
366 views

convergence rate of Pearson correlation

I am looking to find the finest bound possible for $$\mathbb{P}\left( | \hat{\rho}(X,Y) - \rho(X,Y) | \geq t\right) \leq ?$$ where $\rho$ is the Pearson correlation defined as $$\rho(X,Y) = \frac{\...
4
votes
1answer
784 views

Relations between probabilities of "almost" independent random variables

Let $X$ and $Y$ be two random variables, such that the (average) mutual information is very small: $$ 0 \le I(X;Y) \le \epsilon \ll 1$$ In this case, we say that $X$ and $Y$ are almost independent. ...
2
votes
1answer
4k views

Is Jensen's inequality applicable for two variables? [closed]

This is the Jensen's inequality I saw in my textbook: $$E{ f(X) } \geq f( E(X) ),$$ where $f$ is a convex function. Is this also applicable for two random variables--independent or otherwise--like ...
6
votes
2answers
1k views

Is Hoeffding's bound tight in any way?

The inequality: $$\Pr(\overline X - \mathrm{E}[\overline X] \geq t) \leq \exp \left( - \frac{2n^2t^2}{\sum_{i=1}^n (b_i - a_i)^2} \right)$$ Is this bound (or any other form of hoeffding) tight in ...
5
votes
2answers
290 views

Concentration bounds on a sequence of (0,1)-experiments

I have a $(0,1)$-experiment that returns $1$ with probability $p$ and $0$ with probability $1-p$. Let $X_i$ be the random variable describing the outcome of iteration $i$ of the experiment. I'm ...
4
votes
0answers
192 views

The practical use of the lower/upper semivariance adaptation of Chebyshev's inequality for sampled data

The wikipedia article about Chebyshev's inequality also lists a one-sided sharpened variant, based on upper/lower semivariances. It is additionally mentioned there there that "The inequality with the ...
4
votes
0answers
196 views

About tail distribution of a sum

Do we know anything about the tail distribution of sum of squares of a limited number of i.i.d exponentially distributed random variables? I'm looking for a good bound.
3
votes
1answer
2k views

Can the mean deviation about mean exceed the standard deviation for the Pareto distribution?

Can the mean deviation about mean exceed the standard deviation for the Pareto distribution? I just went through some books and found they are claiming that it cannot. How can I prove that? What is ...
2
votes
1answer
81 views

Distribution of a transformation of a random variable

I have started off by this: $F_Y(Y)=P(Y\leq y)=P(X^2 \leq y).$ Now, I have been told that $P(X^2 \leq y) = P(- \sqrt y \leq X \leq \sqrt y) $. I don't quite understand why this is and any help would ...
1
vote
1answer
814 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
1answer
132 views

Chebyshev's Inequality

A certain type of light bulb has an average lifetime of 10,000 hours. The SD of bulb lifetimes is 470 hours. What fraction of bulbs could last more than 10,705 hours? I think the correct answer should ...