Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit 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.

1
vote
0answers
19 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
32 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 ...
5
votes
2answers
102 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
25 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
82 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
19 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
26 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
46 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
46 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
50 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
23 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
38 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
24 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
46 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
34 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$? ...
0
votes
1answer
37 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
49 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 ...
0
votes
0answers
55 views

Establishing an upper bound for the tail probability $P(X-\lambda \geq z)$ for any $z>0$, where $X$ is Poisson r.v. w/ parameter $\lambda$

Poisson random variable $X$ with the parameter $\lambda$ has, respectively, the pmf and the moment generating function of the forms $$P(X = k) = \dfrac{e^{-\lambda}\lambda^k}{k!}, \quad k=0,1,2,\...
4
votes
1answer
41 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
96 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
104 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
50 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
81 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,\...
0
votes
0answers
88 views

Why is it that generalization is not guaranteed for 1-nearest neighbors?

I wanted to understand from a statistical learning theory perspective why 1-nearest neighbors doesn't have generalization. I define generalization as empirical risk converging to expected risk as N ...
1
vote
0answers
50 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
72 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
116 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
103 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
22 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
60 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
111 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
vote
1answer
58 views

$CTE(p)$ is generally greater than $VaR(p+\frac{1}{2}\cdot(100-p))$, $p$ being a percentile

Let's assume we are in the insurance business and the values we are observing are losses. So there is a general statement that says the Conditional Tail Expectation at percentile $p$ is usually ...
12
votes
1answer
894 views

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 ...
2
votes
0answers
80 views

Tight bound for Binomial distribution or, equivalently, the Incomplete Beta function?

Suppose $X \sim Binomial(n,p)$ with known $n$ but unknown $p$, and let $G(p,k) = P[X \geq k)$ for $k=0, \ldots, n$. I am looking for a tight upper bound on $|G(p_1, k) - G(p_2, k)|$ for some given $k$....
3
votes
0answers
56 views

Concentration inequalities for weighted sums of gaussians

Suppose that $x \sim \cal{N}(0,I_d)$ be a $d$-dimensional standard Gaussian vector and let $x_1,\ldots,x_n$ denote $n$ i.i.d. samples drawn from the same distribution. For some fixed vector $\theta \...
3
votes
0answers
388 views

Concentration of maximum of subexponential random variables

I'm looking for a concentration bound on the maximum of a collection of sub-exponential random variables, which are not necessarily independent. More specifically, I have the following collection: \...
0
votes
1answer
205 views

the normalization constant

On page 4 of this article, the authors wants to find the normalizing constant $c$ but it is very hard to compute so I used the same formula to bound $c$. Take the non-negative integers $~0 \leq x_1,...
1
vote
0answers
94 views

Cantelli Inequality Variant

In the JASA (1968, vol. 63, no. 324, pp. 1522-1525) article "How Deviant Can You Be?" Paul Samuelson notes two versions of Chebyshev's inequality: $$P \left( \lvert {X-\mu} \rvert \geq k \sigma \...
6
votes
1answer
108 views

Zero-mean RV $X$, probability of being positive using moments

For zero-mean RV $X$ with finite fourth moment, prove that $$ P(X>0)\ge \frac{\mathbb{E}(X^2)^2}{4\mathbb{E}(X^4)} $$ I tried Chebyshev with adding $t$ to both sides, but I could not get fourth ...
1
vote
0answers
37 views

Convergence of a sequence in finite number of steps

Here is the setup of my problem. It is a sequential problem and there are two possible actions A and B. Now, when either action $A$ or $B$ is taken at the $j$th time point, we observe some outcome say ...
3
votes
0answers
58 views

Characteristic function inequality

Random variable $X$ and its characteristic function $\phi_X(t)$ then $$\Pr\left(|X|>\frac2T\right) \leq 2\left(1 - \frac1{2T}\int_{-T}^{T}\phi_X(t)dt\right) $$ I cannot find a way how to ...
2
votes
1answer
81 views

Why does conditional expectation have this property for independent random variables?

For a reference, please see pp. 53-54 of Boucheron, Lugosi, Massart, Concentration Inequalities: A Nonasymptotic Theory of Independence. Let $f: \mathcal{X}^n \to \mathbb{R}$ be a measurable function (...
0
votes
1answer
36 views

Increased probability of event during period of time

In game of FIFA there are packs by opening which a user receives soccer player cards. The higher the rating of a player card the rarer it drops depending on some kind of random number generator. Since ...
0
votes
0answers
119 views

Linear combination of truncated normals

I am trying to calculate the following expression: $$ Z = \mathbb{E}\left[\left| \langle \mathbf{a}, u \rangle \right| \right] = \left| \sum_{i=1}^d a_i u_i \right|, \quad \left\| u \right\| = 1 $$ ...
4
votes
2answers
1k views

Using Chebyshev's inequality to obtain lower bounds

Let $X_1$ and $X_2$ be i.i.d. continuous random variables with pdf $f(x) = 6x(1-x), 0<x<1$ and $0$, otherwise. Using Chebyshev's inequality, find the lower bound of $P\left(|X_1 + X_2-1| \le\...
2
votes
0answers
56 views

Bounds on tail conditional expectation of random variable given variance

Given a random variable $X$ with CDF $F(X)$, mean $E(X)=0$, and variance $Var(X) =\sigma^2$, I would like to bound the tail conditional expectation where $X$ is in the tail with probability $1-p$: $E(...
4
votes
1answer
157 views

Proof that $E(|X_1 - X_2|)$ is bound by twice the mean

Let $X_1$, $X_2$ be iid random variables. How do I show that for non-negative variables $E(|X_1 - X_2|)$ is bound from above by twice the expected value of $X_1$ (or $X_2$)?
6
votes
1answer
240 views

How do I show this using the Cauchy-Schwarz inequality

From Two Population We have two $p$ dimensional sampels $\mathbf{X}_1$ and $\mathbf{X}_2$ with sample size $n_1$ and $n_2$ respectively, Let We have $\mathbf{\Lambda} = \mathrm{diag}\{(\sigma_{11}^2 + ...
1
vote
1answer
204 views

Does this Bonferroni styled inequality also hold for characteristic functions?

This is the popular Bonferroni inequality. Does it also hold for characteristic functions of random variables, as in when $P(A_i)$ is replaced by the characteristic function $\chi(A_i)$ and so forth? ...
8
votes
3answers
300 views

What's higher, $E(X^2)^3$ or $E(X^3)^2$

So I had a probability test and I couldn't really answer this question. It just asked something like this: "Considering that $X$ is a random variable, $X$ $\geqslant$ $0$, use the correct inequality ...