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
54 views

Why do we need Jensen inequality for variational autoencoders?

Just to clarify, I think I understand all the derivations in context of VAEs pretty well; however, there is one last thing that I need explained. There are multiple related derivations of the evidence ...
user avatar
0 votes
1 answer
45 views

Solving for the parameter of an exponential distribution

Suppose I have a random variable $X$ where $X$ follows an exponential distribution of the following form: $$f_X(x) = \frac{1}{\lambda}e^{-\frac{x}{\lambda}}$$. I want to find the value of $\lambda$ ...
user avatar
0 votes
0 answers
12 views

Product of a series and asequence of random variables

Suppose $\{a_n\}_{n \in N} $ be a bounded sequence positive numberse bounded by $b$ and $Z_j,j=1,2,3,...$ be a sequnce of complex random variables such that $E(|z_j|)<\frac{1}{\sqrt{(j+1)m}}$ for ...
user avatar
1 vote
0 answers
33 views

For $Y \geq 0$, prove that $Pr(Y \geq k) \leq E(Y)/k$

Let $Y$ be a non-negative random variable, $k$ be any positive constant, show that $Pr(Y \geq k) \leq E(Y)/k$. My attempt (using integration by parts): \begin{align} \int_0^k y \,dF(y) &\leq E(Y) \...
user avatar
  • 2,203
6 votes
2 answers
81 views

How to prove this inequality?

For any nonnegative random variable $X$ independent of $U$ where $U \sim \operatorname{Uniform}(-t,t)$ and any $t\ge 0,$ $$P(X+U\ge t)\le\frac{E(X)}{2t}.$$ Any hints to prove this inequality?
user avatar
1 vote
1 answer
46 views

Probability Conditioned on Inequality

Assume that $A \sim \mathcal{N}(0, 1)$, $B \sim \mathcal{N}(0, 1)$. I am trying to calculate $P(A \,|\, A < B)$. For the sake of this problem, we can assume that $A \perp B$, but (for obvious ...
user avatar
2 votes
1 answer
55 views

Is my way of deriving a statistical test from Hoeffding's inequality correct?

I'm trying to deduce from samples of observations from two finite sets of random variables $X_{1}, ..., X_{n}$ and $Y_{1}, ..., Y_{m}$ that the expected values of the average of those random variables ...
user avatar
  • 155
2 votes
1 answer
68 views

symmetrization in glivenko-cantelli proof

In this proof of the Glivenko-Cantelli theorem, page 2 of these notes, two types of symmetrization are used. The first transforms the sup of the centered empirical cdf $$P(\sup_{z\in\mathbb{R}}|(1/n)\...
user avatar
1 vote
0 answers
42 views

Khintchine inequality for the linear combination of sparse Bernoulli random variables

Let $\{\epsilon_{n}\}_{n=1}^{N}$ be i.i.d. random variables with $P(\epsilon_{n} = \pm 1) = 1/2$ for $n=1,2, \ldots, N$ i.e. a sequence of Rademacher distribution. Let $0<p<\infty$ and let $x_{1}...
user avatar
  • 91
0 votes
0 answers
24 views

Training and worst-case errors

After training a neural network with $N$ input-output pairs $\{(x_i, y_i)\}_{i = 1}^N = \{(x_i, f(x_i))\}_{i = 1}^N$ ($x_i$ are randomly sampled in some set $\mathcal{X}$), one gets the maximum error ...
user avatar
4 votes
1 answer
61 views

Multivariate Chebyshev's inequality with Mahalanobis distance

In Chebyshev's inequality, we can generalize the 68-95-99.7 rule from normal distributions to bound how much density is within a certain number of standard deviations from the mean. $$ P\big( \big\...
user avatar
  • 30.9k
1 vote
0 answers
45 views

Probability inequality

Let $X_1,X_2,...X_n$ are independent random variables such that $P(X_i=v_i)=1/v_i$ and $P(X_i=0)=1-1/v_i$, where $1\leq v_i\leq n+1$ for $i=1,2,...,n$. I want to prove that $P(X_1+X_2+...+X_n\geq n+1)\...
user avatar
  • 21
2 votes
1 answer
80 views

Proof utilizing Chebyshev's inequality

I'm being asked to show that $P(|X-\mu|\geq t) \leq \beta_4/t^4,$ where $\beta_4=E((X-\mu)^4)$. I'm familiar with Chebyshev's Inequality, which similarly states that $P(|X-\mu|\geq t) \leq \sigma^2/t^...
user avatar
  • 61
0 votes
0 answers
7 views

Variance inequality for nested sets

Let $X, Y,$ and $Z$ are three random variables/vectors, and let $f(., ., .)$ is a real-valued, deterministic function. If $Z$ is independent of $\{X, Y\}$ (e.g., $X, Y, Z$ are independent) then \begin{...
user avatar
  • 789
0 votes
0 answers
14 views

Test for mean 0 based on Bennett inequality?

Bennett's inequality provides a bound on the probability for the sum of bounded mean 0 random variables to exceed a specified value. It makes no assumptions about distribution, and is stronger than ...
user avatar
2 votes
1 answer
108 views

Independent Bernoulli random variables

My professor left us to solve this problem: Let $\xi_1, \xi_2,...,\xi_n$ be independent Bernoulli random variables defined on a probability space $(\Omega,P(\Omega),\mathbb{P})$ such that: $\mathbb{P}(...
user avatar
  • 109
2 votes
0 answers
18 views

Does Cramer's condition imply strong mixing?

In Theorem 1.4 of D. Bosq the Cramer's condition is a prerequisite for the tail bound of sum of dependent variables. The Theorem is as follows: Let $(X_t,t\in\mathbb{Z})$ be a zero-mean real-valued ...
user avatar
  • 1,030
0 votes
0 answers
24 views

How to bound sub-exponential variables?

I am trying to understand bounding sub-exponential variables. Suppose for $t=2,\cdots,n$, we have \begin{equation} u_{t-1}u_t \end{equation} where $u_t$ and $u_{t-1}$ are sub-Gaussian. We know that ...
user avatar
  • 1,030
0 votes
0 answers
50 views

Does Chebyshev's inequality sacrifice a little power for simplicity?

I followed the proof in Chapter 2 of Ross Introduction to probability and statistics for Engineers. As follows; Chebyshev inequality For any K > 1 ( for K< 1 still holds for 0<K_1 but trivial ...
user avatar
  • 461
0 votes
0 answers
72 views

Would this extension of Khintchine's inequality be correct?

This seems trivial, yet I have to make sure it is indeed correct. Referring to Roman Vershynin's High-Dimensional Probability book, the Khintchine's inequality (Exercise 2.6.5, page 27) is defined as ...
user avatar
  • 1,030
3 votes
0 answers
80 views

What are the arguments in getting from the theorem of Vapnik & Chervonenkis (1971) to the common form seen in Devroye, Györfi & Lugosi (1996)?

Context. The theorem below is attributed to "Vapnik, V., and Chervonenkis, A. (1971). On the uniform convergence of relative frequencies of events to their probabilities. Theory of Probability ...
user avatar
  • 2,206
0 votes
0 answers
82 views

Markov's Inequality and convergence in probability

Theorem: (Markov's Inequality): Let x be a non-negative random variable. Then, for all $b >0$ $P[x \geq b] \leq \frac{E(x)}{b}$. ################# Suppose that $ x_{t}$ is a non-negative random ...
user avatar
4 votes
1 answer
70 views

Corollary of Hoeffding’s Inequality

Question I am not from a statistics background. I came across the following corollary of Hoeffding’s Inequality and couldn't find the derivation or proof for it. Could anyone please share some ...
user avatar
2 votes
0 answers
49 views

Problem understanding the intuition behind Slepian's inequality

Slepian's inequality is defined as follows: Let $X\in\mathbb{R}^n$ and $Y\in\mathbb{R}^n$ be centered Gaussian random vectors such that \begin{align} \mathbb{E}X_iX_j&\geq \mathbb{E}Y_iY_j,\quad \...
user avatar
  • 1,030
0 votes
0 answers
44 views

Hoeffding like result for expected number of pulls

Hoeffding's inequality states that if, $X_1, \ldots, X_n$ are independent random variables bounded by the interval $[0, 1]$, i.e. $0 ≤ X_i ≤ 1$. And the empirical mean of these variables is given by, $...
user avatar
  • 155
1 vote
1 answer
136 views

Markov Inequality for Sum

I don't have proper knowledge of probability, I was surfing around internet about Markov's inequality, I found a paper on JSTOR titled "The Markov Inequality for Sums of Independent Random ...
user avatar
6 votes
2 answers
150 views

Bounding sum of quartic deviations from sample mean

[Cross-posted here with no answers for a few days] I came - to the very best of my knowledge from reading the source - across the following statement in The Jackknife and Bootstrap, Shao and Tu, p. 87:...
user avatar
4 votes
1 answer
147 views

Hoeffding type concentration result for the inverse of a sum of iid random variables

Consider a collection of $n$ i.i.d. Bernoulli random variables $\{ X_i \}_{i=1}^{n}$ with $\mathbb{E}[X_i] = \mu$. Then, if $\hat{\mu}$ is the mean of the $n$ random variables, i.e. if, $$\hat{\mu} = \...
user avatar
  • 155
1 vote
0 answers
46 views

Holder's inequality in the case of $L_1$ and $L_{\infty}$ norm

I am referring to Wainwright's High-Dimensional Statistics book, where at some point it is deduced that \begin{equation} \frac{w'X\Delta}{n}\leq \left\lVert\frac{w'X}{n}\right\rVert_{\infty}\lVert\...
user avatar
  • 1,030
1 vote
1 answer
135 views

Proving Chebyshev's Inequality

I'm working on proving Chebyshev's Inequality. I watched this YouTube video and it almost makes sense. There is one step in the proof I don't understand. Using Markov's Inequality you substitute ...
user avatar
1 vote
0 answers
65 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 ...
user avatar
  • 3,403
1 vote
1 answer
63 views

Minimum number of samples outside interval, unknown distribution

I'm considering a graph that shows the mean of $n$ samples drawn from an unknown, continuous population. It also shows the standard error of the means. From this I calculated the standard deviation $\...
user avatar
  • 123
0 votes
0 answers
19 views

Concentration inequalities

In probability we find inequalities giving upper bounds for P(X≥t) t>0, does there exist any inequalities (may be with some conditions) giving lower bounds for P(X≥t), t>0
user avatar
2 votes
0 answers
53 views

Concrete bound of expected value of a difference of I.I.D. Uniform Random Variables

In the following, $X,X_1,X_2,\dots X_n$ are I.I.D. uniform random variables in $[0,1]^d$ in $\mathbb{R}^d$. The problem I am attempting to solve is Exercise 2.4 from Gyorfi's "A distribution free ...
user avatar
1 vote
1 answer
274 views

How to derive Paley-Zigmund Inequality proof

The Paley-Zygmund inequality is given by \begin{equation} \operatorname{P}( Z > \theta\operatorname{E}[Z] ) \ge (1-\theta)^2 \frac{\operatorname{E}[Z]^2}{\operatorname{E}[Z^2]} \end{equation} I ...
user avatar
1 vote
1 answer
49 views

Finding a consistent sequence of estimators such that $\lim_{n\to\infty} E_\theta[(W_n-\theta)^2]\ne 0$

There are many ways to check if a sequence of estimators is consistent. By definition, a sequence of estimators $W_n = W_n(X_1,X_2,\ldots,X_n)$ is a consistent sequence of estimators of the parameter ...
user avatar
2 votes
0 answers
55 views

0-1 laws in random graphs: probability $\beta$ is large if $k$ is large

How has the author derived here on the page 3 in the context of random graphs and 0-1 laws that $\beta$ is large if $$k\geq ((\frac{2}{\alpha})\log n)^{\frac{1}{2}}$$ ? What I did is this: I've ...
user avatar
3 votes
1 answer
28 views

monotonicity of sample averages tails as a function of sample size

Let $X_1,...$ be iid mean zero random variables. The LLN says $\overline{X}_n\to 0$. I am curious if the following is true: is $P(|\overline{X}_n|>x)>P(|\overline{X}_{n+1}|>x)$ for $x$ ...
user avatar
1 vote
1 answer
32 views

Show $(E|X|^2)/(E|X^2|) \leq P(X \not =0)$

I'm looking to show this inequality is true, and in turn use it to conclude the second moment method's bound. Show that $\frac{E|X|^2}{E|X^2|} \leq P(X \not =0)$. Again, I'm not supposed to use second ...
user avatar
  • 135
4 votes
2 answers
114 views

Does maximizing Jensen–Shannon divergence maximize Kullback–Leibler divergence?

Does maximizing the Jensen–Shannon divergence $D_{\mathrm{JS}}(P \parallel Q)$ maximize the Kullback–Leibler divergence $D_{\mathrm{KL}}(P \parallel Q)$? If so, I'd like to be able to show that it ...
user avatar
1 vote
0 answers
69 views

Upper Bound for 2nd Raw Moment of Positive Random Variable

Let $X$ be a random variable with support $(0,\infty)$. All I know about $X$ is the support, finite higher moments, and $\mathbb{E}(X)=\mu$. I am trying to come up with a more tractable upper bound ...
user avatar
4 votes
1 answer
83 views

Prove that $E[\log(\alpha X_t^2)] < 0 $ implies $\alpha < 3.5622$ with $X_t \sim N(0,1)$

I am trying to prove this statement: If $X_t \sim N(0,1)$ then $$E[\log(\alpha X_t^2)] < 0 \implies \alpha < 3.5622$$ which is a a necessary condition often found in textbooks for strict ...
user avatar
  • 137
3 votes
1 answer
26 views

Implications of zero limiting variance

Assume that I have a sequence of random variables $X_1, X_2, \dots$ with means $\mu_1, \mu_2, \dots$ such that $\lim_{n \to \infty} \operatorname{Var}(X_n) = 0$. Can I claim that for large enough $n$ ...
user avatar
3 votes
3 answers
235 views

A generalization of the data processing inequality

Suppose I have four random variables $X,Y,U,V$ following a distribution which factorizes in the form: $$P(X,Y,U,V) = P(X,Y)P(U|X)P(V|Y)$$ I have the intuition that we should have an inequality of the ...
user avatar
  • 3,348
0 votes
0 answers
37 views

Probability of X greater than Y with different types of random variable [duplicate]

My problem is the following: I have 2 random variables $X \sim Gamma(2,\mu_2)$ and $Y \sim Exp(\mu_1)$. I have to compute $P(X > Y)$. How can I do that ? Thank you
user avatar
  • 195
3 votes
2 answers
90 views

Boundary of $E\left[\frac{\prod_{i=1}^n x_i}{\prod_{i=1}^n x_i+\prod_{i=n+1}^m x_i}\right]$

Suppose $X_i$ are i.i.d. In addition, $X_i>0$ and $E[X_i]>1$. Suppose $E[X_i]$ is known, could we find upper bound or lower bound for the following expectation: $$ E\left[\frac{\prod_{i=1}^n x_i}...
user avatar
3 votes
1 answer
281 views

When is Jensen's Inequality strict?

For a homework problem, I have to prove that for a random sample $X_1, \ldots, X_n$, drawn from a population with finite variance $\sigma^2$, with sample mean $\bar{x}$ and sample variance $s^2$, that ...
user avatar
2 votes
2 answers
230 views

Concentration inequalities for estimated least squares regression coefficients?

I would like to know what is the best concentration inequality we can use for the estimated least squares regression coefficients. Let $\hat \beta_0, \hat \beta_1$ be the estimated regression ...
user avatar
  • 735
4 votes
2 answers
193 views

Sum of continuous i.i.d random variables

Let $X_{1}, X_{2}, \ldots X_{N}$ be non-negative continuous i.i.d random variables such that the probability density function of each $X_{i}$ is given as \begin{equation} f(x) = N e^{-Nx}. \end{...
user avatar
2 votes
1 answer
30 views

Distributive property of probabilistic inequalities involving random variables on both sides

Can I break down $P(h \geq (A + B)$, given all $ A,B,h$ are all random variables. Will the following rule works? $$P[h \geq (A + B)] = P(h\geq A) + P(h\geq B)$$ Actually, in one of my mathematical ...
user avatar
  • 372

1
2 3 4 5 6