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
2
votes
0answers
11 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 ...
0
votes
0answers
8 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 ...
0
votes
0answers
29 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 ...
0
votes
0answers
29 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 ...
3
votes
0answers
71 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 ...
0
votes
0answers
30 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 ...
3
votes
1answer
37 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 ...
2
votes
0answers
25 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 \...
0
votes
0answers
37 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, $...
1
vote
1answer
42 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 ...
6
votes
2answers
137 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:...
4
votes
1answer
87 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} = \...
1
vote
0answers
35 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\...
0
votes
1answer
86 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 ...
1
vote
0answers
42 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 ...
1
vote
1answer
43 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 $\...
0
votes
0answers
17 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
2
votes
0answers
48 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 ...
1
vote
1answer
67 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 ...
1
vote
1answer
16 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 ...
2
votes
0answers
51 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 ...
0
votes
0answers
32 views

Expect hitting time of a discrete time random walk with complex step size distribution

Suppose a random walk starts from $S_0=0$. The iterative equation is $$S_{t+1}=\max\{S_t+y_{t+1}-k,0\},$$ where $k$ is a fixed value that is larger than 1, and $y_t$, $t=1,2,\cdots$, are i.i.d. and $$...
2
votes
1answer
25 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$ ...
1
vote
1answer
25 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 ...
0
votes
0answers
43 views

sums for random variables for which markoff inequality is tight

This answer describes random variables for which markoff or chebyshev inequality is tight. What about random varibles $X$, such that the average of an iid sequence makes markoff tight: $P(\overline{X}&...
4
votes
2answers
87 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 ...
1
vote
0answers
34 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 ...
0
votes
0answers
19 views

Chebyshev bounds [duplicate]

Can Chebyshev bound be greater than 1? The following question is just in contradiction to the above stated question: a) A rv assume values -1,1,3,5 with respective probabilities, 1/6,1/6,/16,1/2. Find ...
0
votes
0answers
10 views

Bayesian error in binary classification when covariates are conditionally iid

In the setting of this problem, $\eta(\vec{x})$ is $P(Y=1|\vec{X}=\vec{x})$, $Y \in {0,1}$, $X \in R^d$. Being the true probability know, the classification rule is simply $\eta(\vec{x})>0.5 \...
4
votes
1answer
81 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 ...
3
votes
1answer
21 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$ ...
3
votes
2answers
101 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 ...
0
votes
0answers
33 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
3
votes
2answers
87 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}...
3
votes
1answer
61 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 ...
2
votes
2answers
116 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 ...
4
votes
2answers
133 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{...
2
votes
1answer
21 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 ...
1
vote
0answers
35 views

Bounds on distance between two independently variables drawn from the same distribution

Suppose $X_1$ and $X_2$ are iid from an arbitrary distribution with variance $\sigma^2$. How can we derive an upper bound for: $$P(|X_1-X_2|\ge\delta)$$ One simple idea is Chebyshev's Inequality, ...
0
votes
0answers
74 views

Convergence in probability and Chebyshev inequality

Given problem: The elegant solution is to use Markov inequality for $X^2_n$. But my solution was via Chebyshev inequality, smth like that: $P(|X_n - 1/n| \ge k) \le \frac{\sigma^2}{k^2}$, now lets ...
1
vote
0answers
26 views

Generalization of the Payley-Zigmund inequality

The Payley-Zigmund inequality states that for a positive random variable $Z$ the following holds \begin{equation} \operatorname{P}( Z > \theta\operatorname{E}[Z] ) \ge (1-\theta)^2 \frac{\...
3
votes
1answer
264 views

Use Chebyshev's inequality to find a lower bound of a Chi-Square Distribution

I'm trying to solve the following exercise but I'm not sure if what I'm doing is right. "Let $X$ be an r.v. distributed as $\chi_{40}^{2}$. Use Tchebichev’s inequality in order to find a lower ...
1
vote
0answers
27 views

Applicability of Hoeffding's Inequality

I am working through Larry Wasserman's All of Statistics. I am trying to understand why Hoeffding's Inequality was valid for the following problem: Suppose we test a prediction method on a set of $n$ ...
1
vote
0answers
37 views

Covariance of X and Y conditional on X+Y>Z? [closed]

Suppose that $X$, $Y$, and $Z$ are three independent random variables. Is there a way to compute the following conditional covariance? $Cov(X, Y | X + Y \geq Z)$
0
votes
1answer
41 views

Laplace Inequality

I am trying to prove that if $r_i \sim Lap(0,1/\varepsilon)$ where $\varepsilon >0$ then: $$Pr[r_i \geq 1+r^*] \geq e^{-\varepsilon}Pr[r_i \geq r^{*}]$$. I know that for $r*>0$ it satisfies ...
1
vote
1answer
72 views

I've taken an alternative approach to a convergence in probability problem. Is there any mistake and/or is my conclusion correct?

I am currently studying convergence on my own, which means that I don't have many alternatives for discussing problems in order to improve my understanding. This post was an alternative to get around ...
1
vote
1answer
55 views

Can we bound $\frac{Cov(X,XY)}{Var(X)}$?

The question is can we bound $\beta = \frac{Cov(X,XY)}{Var(X)}$ with the help of the following assumptions : Y is a positive bounded random variable, let's assume $Y \in [0,1]$. X has an expectation ...
0
votes
0answers
89 views

Symmetrization in Proof of Hoeffding's Lemma

This alternative proof of a slightly weaker version of Hoeffding's Lemma features in Stanford's CS229 course notes. What's notable about this proof is its use of symmetrization. However, I find this ...
2
votes
1answer
24 views

Why $Pr[X-\mu \geq t]= Pr[e^{\lambda(X-\mu)} \geq e^{\lambda t}]$ for all $\lambda> 0$

I hope everyone is having a nice day. I don't know why this inequality holds. $$ Pr[X-\mu \geq t]= Pr[e^{\lambda(X-\mu)} \geq e^{\lambda t}] $$ For $\lambda >0$. I guess it has something to do ...
0
votes
0answers
17 views

How to select a set of MCMC samples with some probability?

I have a set of samples gathered using MCMC of random variable $X$. Let's call this set $X_s$. How to select a subset of samples $S$such that $$ Probability(X_s(S) < constant) > 0.01 $$ I want ...

1
2 3 4 5 6