Statistical Analysis Stack Exchange
Statistical Analysis Stack Exchange

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.

There are many useful and well studied probability/concentration inequalities including:

  • Markov's inequality
  • Chebyshev's inequality
  • Chernoff bounds
  • Hoeffding's inequality
  • Azuma's inequality

and many others.

291 questions
37
votes
2 answers

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 bound over the probability that the sum of…
Farzad
  • 575
  • 3
  • 7
34
votes
3 answers

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, if you know the population mean and variance, you…
casandra
  • 583
  • 4
  • 8
30
votes
1 answer

When is binomial distribution function above/below its limiting Poisson distribution function?

Let $B(n,p,r)$ denote the binomial distribution function (DF) with parameters $n \in \mathbb N$ and $p \in (0,1)$ evaluated at $r \in \{0,1,\ldots,n\}$: \begin{equation} B(n,p,r) = \sum_{i=0}^r \binom{n}{i} p^i (1-p)^{n-i}, \end{equation} and let…
Luis Mendo
  • 815
  • 7
  • 20
21
votes
4 answers

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 > n \ln n + cn) < e^{-c}$. This upper bound is…
David
  • 313
  • 2
  • 9
17
votes
1 answer

Oracle Inequality : In basic terms

I'm going through a paper that uses oracle inequality to prove something but I'm unable to understand what it is even trying to do. When I searched online about 'Oracle Inequality', some sources directed me to the article "Candes, Emmanuel J.…
Wolcott
  • 171
  • 1
  • 6
17
votes
2 answers

Bound on moment generating function

This question arises from the one asked here about a bound on moment generating functions (MGFs). Suppose $X$ is a bounded zero-mean random variable taking on values in $[-\sigma, \sigma]$ and let $G(t) = E[e^{tX}]$ be its MGF. From a bound used in…
Dilip Sarwate
  • 41,202
  • 4
  • 94
  • 200
17
votes
1 answer

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. Let's denote MNIST training set as $D_{train}$,…
asqdf
  • 353
  • 1
  • 6
14
votes
1 answer

Tail inequality on sum of product of normal variables

For independent random variables $ x_1,..,x_n$ and $y_1,...,y_n$ following normal distribution $N(0,1)$, I need a simple estimate formula for $P(|\sum_1^n x_iy_i|\ge nt) \leq e^{(?)}$ for $t>1$. Thanks.
user16093
  • 141
  • 3
13
votes
1 answer

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 easily be produce for all exponents. Does anyone know…
Andreas Mueller
  • 471
  • 4
  • 9
13
votes
1 answer

A question related to Borel-Cantelli Lemma

Note: Borel-Cantelli Lemma says that $$\sum_{n=1}^\infty P(A_n) \lt \infty \Rightarrow P(\lim\sup A_n)=0$$ $$\sum_{n=1}^\infty P(A_n) =\infty \textrm{ and } A_n\textrm{'s are independent} \Rightarrow P(\lim\sup A_n)=1$$ Then, if…
1190
  • 848
  • 3
  • 8
  • 20
12
votes
1 answer

Understanding measure concentration inequalities

In the spirit of this question Understanding proof of a lemma used in Hoeffding inequality , I am trying to understand the steps that lead to Hoeffding's inequality. What holds the most mystery for me in the proof is the part where exponential…
Leo
  • 306
  • 1
  • 11
12
votes
1 answer

Special probability distribution

If $p(x)$ is a probability distribution with non-zero values on $[0,+\infty)$, for what type(s) of $p(x)$ does there exist a constant $c\gt 0$ such that $\int_0^{\infty}p(x)\log{\frac{ p(x)}{(1+\epsilon)p({x}(1+\epsilon))}}dx \leq c \epsilon^2$…
Sus20200
  • 371
  • 2
  • 12
12
votes
3 answers

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{a}{X_n}\to 1$$ both in probability. I'm here to see…
Savage Henry
  • 361
  • 1
  • 9
12
votes
3 answers

Exponential upper bound

Suppose we have IID random variables $X_1,\dots,X_n$ with distribution $\mathrm{Ber}(\theta)$. We are going to observe a sample of the $X_i$'s in the following way: let $Y_1,\dots,Y_n$ be independent $\mathrm{Ber}(1/2)$ random variables, suppose…
Zen
  • 21,786
  • 3
  • 72
  • 114
11
votes
2 answers

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 used in Hoeffding's inequality (pp.2-3). I am…
Anand
  • 1,092
  • 2
  • 11
  • 21
1
2 3
…
19 20