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
1 answer
32 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
43 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
38 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
36 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
45 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
83 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
72 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
29 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
170 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
33 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
39 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
40 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
24 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
126 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,020
2 votes
0 answers
40 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
57 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
  • 8,502
3 votes
3 answers
117 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
  • 8,502
1 vote
1 answer
83 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
0 votes
0 answers
29 views

Concentration inequality for subgaussian random vector

If I have a vector $Z $ in $\mathbb R_d $ space and a vector $B$ in $\mathbb R_d$ space, $Z $ having independent Subgaussian coordinates, is $Z^\top B$ a Subgaussian random variable? I know sub-...
Ankita Ghosh's user avatar
5 votes
1 answer
108 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
  • 693
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
218 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
0 votes
0 answers
88 views

How to prove this version of Hoeffding inequality?

Based on my studies, Hoeffding inequality is used for bounded or sub-Gaussian random variables which are explained on the Wikipedia page. I am reading the book Introduction to Multi-Armed Bandits by ...
Amin's user avatar
  • 683
0 votes
0 answers
61 views

Differential Entropy of Zero-Mean Gaussian Mixtures

Introduction Consider a univariate circularly symmetric complex Gaussian (CSCG) mixture $Y$ with pdf $$p_Y(y) = \sum_i c_i p_i(y) = \sum_i c_i \frac{\exp(-\lvert y \rvert^2/\sigma_i^2)}{\pi \sigma_i^2}...
SnowzTail's user avatar
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
115 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
104 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
381 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
89 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
113 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
474 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
96 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
56 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
126 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
126 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
  • 309
1 vote
1 answer
70 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
84 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
  • 341
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
155 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,420
1 vote
0 answers
88 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
62 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
39 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
324 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
0 votes
0 answers
49 views

Probability of Roots outside the unit disc

Consider a random polynomial $p(z)=\sum_0^n A_i z^i.$ where $A_i,i=0,12,3,..,n$ are iid uniform variables in the interval $(0,1).$ I want to show that that the probability of the root with min modulus ...
AgnostMystic's user avatar
0 votes
0 answers
74 views

Deriving and visualizing bounds on the conditional probability given marginal conditionals

Suppose I have a binary outcome $Y$ and two binary covariates $X_1$ and $X_2$ with distribution $P(X_1, X_2)$ which I know. In addition to $P(X_1, X_2)$, I know $P(Y\mid X_1)$ and $P(Y\mid X_2)$. I ...
Sergio's user avatar
  • 336
0 votes
0 answers
22 views

probability of being within a 2D grid cell

Consider two joint-normal gaussian variables A and B with known probability density. A and B form a point in 2D space. What is the probability that the sample point falls within a rectangular grid ...
jekain314's user avatar
1 vote
2 answers
309 views

Proof of inequality $P(X \geq \lambda) \leq \frac{\sigma^2}{\sigma^2 + \lambda^2}$

Hello I have the assumptions that $E(X) = 0$ and $\operatorname{Var}(X) = {\sigma}^{2}$ . Why does this inequality hold $P(X \geq \lambda) \leq \frac{{\sigma}^{2}}{{\sigma}^{2} + {\lambda}^{2}}$ for $ ...
Jan's user avatar
  • 35
6 votes
2 answers
452 views

If all moments of a non-negative random variable X are larger than those of Y, is P(X>x) larger than P(Y>x)?

$X$ and $Y$ are two non-negative continuous random variables. The moments of $X$ are $\mu_i$ while that of $Y$ are $\nu_i$. We know that $\mu_1=\nu_1$ and $\mu_i \ge \nu_i$ for $i=2,3,\ldots$ Can one ...
GCru's user avatar
  • 235
0 votes
1 answer
24 views

Is it true for rvs $X,Y$ where $E[X]=E[Y]$ & $V[X] \geq V[Y],$ the Jensen gap of $X$ is larger or equal the Jensen gap of $Y?$

Is it true for rvs $X,Y$ where $E[X]=E[Y]$ and $V[X] \geq V[Y],$ the Jensen gap of $X$ is larger or equal the Jensen gap of $Y?$ It seems intuitive. I failed to prove it or find a reference.
curious's user avatar

1
2 3 4 5
7