Skip to main content

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
0 answers
28 views

Concentration inequality for sums of independent gamma random variables

I am dealing with the following problem: Say $X_1, \ldots, X_n$ are independent Gamma random variables, each one having shape and rate parameters $\alpha_i$ and $\beta_i$, respectively. Let $S_n = \...
HeyCool08's user avatar
2 votes
1 answer
36 views

Expectation under convex order by multiplying

I am trying to understand if the following statement is true, or the conditions under it is satisfied. Let $M,N$ and $X>0$ be random variables. If the following inequality holds for any concave non-...
Don P.'s user avatar
  • 157
2 votes
1 answer
48 views

Expectation under convex order

I am trying to understand if the following statement is true. Let $M,N$ and $X$ be random variables. If the following inequality holds for any concave non-decreasing function $u$ \begin{equation} \...
Don P.'s user avatar
  • 157
0 votes
0 answers
8 views

Does there exist a matrix Bernstein type inequality for weakly dependent random variables?

When reviewing the literature, I managed to find the following papers, which deduce Bernstein type inequalities for weakly dependent random variables (where weak dependence is defined in some special ...
Stephen Jiang's user avatar
1 vote
1 answer
46 views

Probability inclusion-exclusion [closed]

Suppose we have $f:G\to H$ group homorphism if $f(x+y)=f(x)+f(y).$ And let $h:G\to H$ be another group homorphism closed to $f,$ then we have $$\mathcal{P}(f(x+y)-f(y)\neq h(x+y) -h(y))=\mathcal{P}(f(...
D. S.'s user avatar
  • 69
1 vote
1 answer
45 views

Probability lower bounds

We have three events $A, B, C.$ Also we have, $$\mathcal{P}(A\cap B\cap C)=\mathcal{P}(A)-\mathcal{P}(A\cap(\overline{B}\cup \overline{C})).$$ From above result how can prove that $$\mathcal{P}(A)-\...
D. S.'s user avatar
  • 69
2 votes
1 answer
51 views

Different versions of additive chernoff

The additive Chernoff Bound says for $X_i \in \{0,1\}$ that satisfies $\mathbb{E}[X_i] = p,$ $$ \mathbb P\left(\sum\limits_{i}^nX_i \geq np+n\epsilon \right) \leq \exp\left(-\frac{(n\epsilon)^2}{2(np+\...
D. S.'s user avatar
  • 69
10 votes
1 answer
120 views

How to arrange the multivariate DKW inequality to an upper bound on n?

The multivariate DKW inequality is given by $$\Pr \left[ \sup_{t \in \mathbb{R}^k} \left| F_n(t) - F(t) \right| > \epsilon \right] \leq (n+1)k e^{-2n\epsilon^2},$$ where $F_n(t)$ is the eCDF, $F(t)...
Galen's user avatar
  • 9,381
11 votes
4 answers
234 views

Upper bound for 1-Wasserstein distance between standard uniform and other distribution on $[0,1]$

I want to use the following metric to measure the distance between the standard uniform distribution and any other probability distribution on $[0,1]$. $$\int_0^1 |F(x) - x| dx$$ $F(x)$ is the cdf of ...
spencergw's user avatar
  • 161
0 votes
1 answer
40 views

$\mathbb{E}[X^2]\leq k \mathbb{E}[X]^2$, upper bound second moment from first moment

Let $X$ be a non-negative random variable bounded on $[0,1]$. Is it true that $\mathbb{E}[X^2]\leq k \mathbb{E}[X]^2$ for some constant $k$? If not, are there any minimal assumptions on $X$ where this ...
ryanriess's user avatar
  • 101
2 votes
1 answer
44 views

Tight upper bound on the function of expected value

Let $R$ be a positive integer, $\mathcal{X}$ be the sample space and $x \in \mathcal{X}$ be an event of the sample space; $P(x)$ denotes the probability of occurrence of event $x$. The problem is to ...
Bhisham's user avatar
  • 319
1 vote
1 answer
39 views

If event $A$ is a union of elements of $S(A)$, then $\min_{Z\in S(A):Z\subset A}P(B\mid Z)\leq P(B\mid A)$ for any event $B$

Let $A$ and $B$ be events in a probability space and $S(A)$ a collection of events such that $A$ is a union of some elements in $S(A)$. How could I then conclude that the conditional probabilities ...
Cartesian Bear's user avatar
1 vote
0 answers
51 views

Concentration around the median implies concentration around the mean [duplicate]

Let $M$ denote the median of a function $f(X)$ that is Lipschitz continuous with $\left \| f \right \|_{Lip}=1$. I am trying to show that if $\left \| f(X)-M \right \|_{\psi_{2}}\leq C$, then $\left \|...
Shawn Kemp's user avatar
1 vote
0 answers
47 views

Probability of at least one element for each class in a multinomial distribution

Given a multinomial distribution $$X \sim \mathcal{M}(n, p_1, \ldots , p_K)$$ If I know $p_1 \ldots p_n$ I can easily obtain the following probability by repeatedly sampling from a multinomial ...
Manuel's user avatar
  • 1,679
1 vote
0 answers
85 views

How to find $\mathbb{E} \left[\frac{\bar{\mu}}{\bar{\sigma}^2}\right]$?

I asked the same question on math stacks: MathStacks:, and some user suggest to ask it here for better insight. So this question has found interest in many research problems, but there have been no ...
coolname11's user avatar
1 vote
0 answers
43 views

Probability of Random variable less than a quantity containing random variable [closed]

What is the probability of the following: $P\left(Z_j>\frac{\epsilon}{a_j*R}\left(\sum^{M}_{m=j+1} ~ a_m*R*X_m+1\right)\right)$ where $Z_j$ and $X_m$ are independent and identically distributed ...
learning statistics 's user avatar
0 votes
0 answers
73 views

What is this nonparametric goodness-of-fit test?

I wrote down a goodness-of-fit test that I have not seen before. However, it is quite elementary and has many applications, so I bet it must have been known. Could someone tell me its name? Setup. The ...
Student's user avatar
  • 235
0 votes
0 answers
31 views

Lower bound on distance between ordered statistic

I have found the following inequality in a manuscript: Let $S_{t}^{i}$ and $S_{t}^{i^{\prime }}$ denote the $i/N$-th and $i^{\prime }/N$-th cross sectional order statistics. We require: \begin{align} \...
NC520's user avatar
  • 125
1 vote
1 answer
175 views

differential-privacy: show $\epsilon$ -differentially privacy

In this problem we consider a sensitive dataset $x \in \{−1, 1\}^n$. We consider the bounded setting where neighboring n-dimensional datasets differ in one coordinate. $A$ mechanism is available that ...
Lifeni's user avatar
  • 305
0 votes
1 answer
36 views

Tests that Quantify Deviation from Null Hypotheses

I have been delving into non-parametric tests recently, and I've come to realize that most of these tests offer only a partial perspective. For example, lets say the underlying distribution is $\theta$...
Student's user avatar
  • 235
0 votes
0 answers
44 views

Concentration Inequality for cross-entropy

I am currently trying to estimate the cross-entropy between two distributions with densities $p$ and $q$. $$ \ell = -\mathbb{E}_{x\sim p(x) }[\log q(x)] $$ I am using a Monte-Carlo estimate: $$ \hat{\...
Nick Bishop's user avatar
0 votes
0 answers
42 views

How to obtain moment bound from importance sampling identity?

Let $m(t) =E[X^t].$ The moment bound states that for a > 0, $$P\{ X \geq a \}\leq m(t)a^{-t} \forall t > 0 .$$ How would you prove this result using importance sampling identity? My answer: ...
Win_odd Dhamnekar's user avatar
0 votes
0 answers
26 views

Unexpected Seasonal Pattern when Comparing Empirical Probability with Hoeffding's Inequality

I am visualizing the difference between the empirical probability and the theoretical upper bound of the deviation of the sample mean from the true mean of successive Bernoulli trials. I'm using ...
Felipe Vieira's user avatar
4 votes
1 answer
153 views

Markov's inequality intuitions

Can someone explain intuitively how Markov's inequality was derived? It seems plausible, but looking a it, I can't 'see' how it's true.
jbuddy_13's user avatar
  • 3,372
2 votes
0 answers
41 views

What is the asymptotic bound for the ratio of sample mean and expectation?

For an i.i.d. observations $X_1,\cdots,X_n$ (bounded), we have the Hoeffding's inequality that establishes the upper bound for the tail probability of $|\bar{X_n}-\mathbb{E}[X_1]|$. I would like to ...
qqhgsjah8221's user avatar
1 vote
0 answers
59 views

Can we obtain a probability interpretation on these bounds obtained from the ADG and Frechet inequalities?

Background The almost-disjoint gap (ADG) is given by $$\mathcal{D}_{\mu} \left( E_1, \ldots, E_n \right) \triangleq \mu \left( \bigcup_{k=1}^{n} E_k \right) - \sum_{k=1}^n \mu \left( E_k \right)$$ ...
Galen's user avatar
  • 9,381
3 votes
3 answers
123 views

Is the pairwise independence gap bounded to $\left[-\frac{1}{4},\frac{1}{4}\right]$? What about for n variables?

The independence gap is defined as $$\phi_{X_1, \ldots, X_n}(x_1, \ldots, x_n) \triangleq F_{X_1, \ldots, X_n}(x_1, \ldots, x_n) - \prod_{j=1}^n F_{X_j}(x_j)$$ where $F_{X_1, \ldots, X_n}(x_1, \ldots, ...
Galen's user avatar
  • 9,381
1 vote
1 answer
96 views

Chernoff Bounds for Independent Bernoulli Sums

What is wrong with this proof? Can you notice that? or I am wrong? In my opinion, in the R.H.S. of the inequality (3.2), the index of 'e' is negative but it must be positive if we use the given proof ...
Win_odd Dhamnekar's user avatar
6 votes
2 answers
168 views

Can positive values with sd > mean have skewness = 0?

I'm trying to create an example of a distribution with all positive values, standard deviation > mean, and skewness =0 (third moment). I cannot. Is that possible? Can you prove it mathematically? ...
GabyLP's user avatar
  • 703
2 votes
1 answer
98 views

A question related to the convergence of series in probability

Let $(X_j)_{j\in \mathbb Z}$ be an strictly stationary sequence of random variables with: $$E[X_j]=0, \quad E[X_j^2] < \infty$$ I want to show that for each positive $\varepsilon$: $$ \sum_{n=1}^\...
André Goulart's user avatar
3 votes
1 answer
241 views

Upper bound for sum of dependent normal variables

I am having difficulties with the following problem: Assuming $X$ and $Y$ follow a bivariate normal distribution with $\mu = 0$ and $\Sigma=\begin{pmatrix} 1 & \rho \\ \rho & 1 \end{pmatrix}$ ...
Coach's user avatar
  • 33
2 votes
0 answers
41 views

Is there a high probability bound of quadratic forms?

I am wondering about the following: For a symmetric matrix $A \in \mathbb{R}^{n \times n}$ and vector $x \in [-1,1]^n$, if $X$ is a random vector in $\mathbb{R}^n$ such that w.h.p. $X_i \not\in [-1,1] ...
swuk's user avatar
  • 43
2 votes
1 answer
120 views

Is truncated mean a biased estimator

We have data $X_1, \dots, X_n$ which are i.i.d copies of $X$. Where we denote $\mathbb{E}[X] = \mu$, and $X$ has finite variance. We define the truncated sample mean: $\begin{align} \hat{\mu}^{\...
Dylan Dijk's user avatar
4 votes
1 answer
105 views

Using Chebyshev's inequality on $X$ to inform distribution on $X^2$

By Chebyshev's inequality it is known that $$\mathbb{P}\left(|X-\mu|<k\sigma\right) \geq 1-\frac{1}{k^2}\,.$$ Then does it follow that $$\mathbb{P}\left((\mu-k\sigma)^2 \leq X^2 \leq (\mu +k\sigma)^...
Irna Mosa's user avatar
5 votes
2 answers
457 views

Upper Bound of MGF for a non-negative random variable with bounded variance

Let $X$ be a non-negative random variable with finite variance. It is obvious that its MGF $E[e^{-\lambda(X-E[X])}]$ exists for $\lambda > 0$. How to prove that $E[e^{-\lambda(X-E[X])}] \le \exp(\...
Ruiyuan Huang's user avatar
0 votes
1 answer
103 views

Asymptotic equivalence of the survival function of a standard Gaussian [duplicate]

My statistics teacher told us the following asymptotic result: $X \sim N(0,1) $ $$ P(X > u) \underset{u \rightarrow +\infty}{\sim} \frac{1}{u} \exp\left(-\frac{u^2}{2}\right). $$ Do you know how to ...
Justin Ruelland's user avatar
2 votes
1 answer
116 views

Proving upper bound for truncated difference

Let $X$ and $Y$ be real valued random variables. And define a truncation operator as: $\begin{align} X(\tau) = (|X| \wedge \tau) \; \text{sign}(X), \quad \tau > 0 \end{align}$ Now, I am not ...
Dylan Dijk's user avatar
5 votes
2 answers
482 views

Using the Chebyshev inequality to uncover saturating distribution

It is well known that if a random variable $X$ has distribution: $$ \mathrm{P}(X = x) = \begin{cases} \frac{1}{2}, & x=0,\\ \frac{1}{2}, & x=1,\\ 0, & \text{otherwise}, \end{cases} $$ (i.e....
Emmy B's user avatar
  • 93
3 votes
1 answer
116 views

Spectral norm of matrices of i.i.d. bounded r.v. is sub-Gaussian

The setting is $A\in \mathbb{R}^{n*n}$ with each entry being i.i.d. bounded r.v. in $[a,b]$. The question is to prove $\Vert A\Vert_2$ is sub-Gaussian. Intuitively I thought since $\{A_{ij}\}_{i,j=1,.....
dc3506's user avatar
  • 65
2 votes
0 answers
58 views

Application of Hoeffding's inequality on the Stochastic Multi-Armed Bandit Problem

I'm following this note to learn about deriving an upper bound of the UCB algorithm on the Stochastic Multi-Armed Bandit Problem. In particular, the proof of Lemma 15.6 there connotes that we can ...
NXWang's user avatar
  • 21
1 vote
1 answer
130 views

Proving upper bound for Bias of truncated sample mean

We have data $X_1, \dots, X_n$ which are i.i.d copies of $X$. Where we denote $\mathbb{E}[X] = \mu$, and $X$ has finite variance. We define the truncated sample mean: $\begin{align} \hat{\mu}^{\...
Dylan Dijk's user avatar
2 votes
1 answer
145 views

Convergence in probability to a constant and absolute value (?)

I am a bit loss with the convergence in probability and the absolute value. Let $X_n$ be a random variable defined in $\mathbb{R}$ with $\lim_{n \rightarrow \infty} E[X_n] = a$ and $V[X_n] = O(n^{-1})$...
Eryna's user avatar
  • 329
1 vote
1 answer
75 views

Probability for all epsilon is one implies for all epsilon probability is one

I am struggling to work out if the following is true. Let $\{A_\epsilon\}$ be an indexed set of events in a probability space. Does it hold that: $$\forall \epsilon > 0, \mathbb{P}[A_\epsilon]=1 \...
MasonTep's user avatar
4 votes
1 answer
91 views

Inequality relating expected value and tail probability

I am currently working through Scornet2015 - Consistency of Random Forests. I'm having trouble understanding a specific inequality that is used in the proofs without further explanation. I am assuming ...
ngmir's user avatar
  • 339
0 votes
0 answers
49 views

What kind of formal guarantee does a confidence interval provide after an observation?

According to my understanding, $C(X)$ is a random variable defined as follows: Let $\mathcal{P}$ be a family of distributions (defined by user). Let $\alpha>0$. Let $\theta$ be some parameter of a ...
orematasaburo's user avatar
3 votes
2 answers
161 views

Is it true that $\langle X^4\rangle \ge 3 \langle X^2\rangle^2$?

Consider a real random variable $X$ with zero mean. Does the following inequality hold in general? $$\langle X^4\rangle \ge 3 \langle X^2\rangle^2$$ I'm not sure how to prove this or if a counter-...
a06e's user avatar
  • 4,440
1 vote
0 answers
106 views

Number of samples for Hoeffding's Bound with Gaussian R.V

I am trying to obtain the required number of sample $n$ for a given confidence interval $\alpha$ and $X_1 ... X_n$ which are Gaussian rv with $\mu$ mean and $\sigma^2$ variance. I know that \begin{...
victoria's user avatar
2 votes
1 answer
66 views

Is kernel density estimation sub-gaussian?

Let $X_1, ..., X_n$ be i.i.d. samples drawn from a pdf $f(x)$ on the real line. The kernel density estimator is defined as follows, $$\hat{f_n}(x) = \frac{1}{nh}\sum_1^n K(\frac{x-X_k}{h})$$ where $K:\...
dc3506's user avatar
  • 65
1 vote
1 answer
40 views

Game of guessing or is it! [closed]

I am trying to learn coding and want to create a simple game. The idea is that there are 20 different animals, and you have 5 rooms, each round 5 out of the 20 animals hide in the room, where behind ...
Disaster's user avatar
3 votes
0 answers
333 views

Inequality on the moment generating function of a centered random variable which is bounded above

I am stuck on the first part of problem 8.2 of the book "A Probabilistic Theory of Pattern Recognition" by Luc Devroye: Show that for any $s > 0$, and any random variable $X$ with $\...
yddc96's user avatar
  • 31

1
2 3 4 5
8