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
1answer
27 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
11 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
50 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
28 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
23 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
23 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
37 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
74 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
24 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
16 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
9 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
76 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
18 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
53 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
31 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
84 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
43 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
67 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
113 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
19 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
34 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
41 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
25 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
181 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
23 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
35 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
51 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
49 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
63 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
23 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
vote
1answer
64 views

Expectation of (sum subtract the expectation of sum)

Let's say we have random variables $\mathbf{X}$, and we have $P(\mathbf{X}\in [a, b])=1$, we have $\mathbf{S}_n = \mathbf{X}_1 + \mathbf{X}_2, +\dots + \mathbf{X}_n$. If $\mathbf{X}_1, \mathbf{X}_2, ...
1
vote
0answers
123 views

Is there a different way to bound probability, with no distributional assumptions, other than Markov's inequality?

I'm having trouble answering this probability interview question from Interview Query: Let's say there is man who is 5.10 ft tall who doesn't know how to swim. Let's say he wants to swim in a lake ...
1
vote
0answers
127 views

Tail bounds for sample means of i.i.d random variables where the moment generating function exists

I want to figure out the proof of Lemma 4 in the following paper. The lemma states that Let $Y_1, Y_2,\ldots Y_m$ be i.i.d random variables such that $\mathbb{E}\left[e^{zY}\right] < \infty$ ...
2
votes
1answer
37 views

How to using the Markov Inequality to find the upper bound for $\mathbb{P}(X > 2)$ given I only have information about $X^4$?

Let $X$ be a nonnegative random variable that satisfies $\mathbb{E}[X^{4}]=4$ . How should I calculate an estimate for the $\mathbb{P}(X \geq 2)$ using the Markov Inequality? I tried to find a ...
4
votes
2answers
540 views

Formula of the Chebyshev's inequality for an asymmetric interval

The formula for Chebyshev's inequality for the asymmetric two-sided case is: $$ \mathrm{Pr}( l < X < h ) \ge \frac{ 4 [ ( \mu - l )( h - \mu ) - \sigma^2 ] }{ ( h - l )^2 } . $$ What I don't ...
3
votes
1answer
449 views

Showing the weak law of large number of non-IID sequence of random variables

Common proofs on the law of large numbers usually assume a sequence of IID random variables. If $X_1\dots X_n$ has a common expected value $\mu$, finite but not necessarily common variance (hence not ...
0
votes
0answers
26 views

Using Hoeffding's inequality on sum of uniform variables

I have the following problem: $X_1,...,X_n$ are i.i.d. $\sim U(-3,5)$ continuous uniform variables in the support between -3 and 5. $S := X_1 + ... + X_n$. I need to use Hoeffding's inequality to ...
4
votes
1answer
48 views

Basic probability inequality between 4 events

I have been asked to prove the following but am unsure if it is true: $$\mathbb{P}(A,B,C)<\mathbb{P}(D) \implies \mathbb{P}(A) + \mathbb{P}(B) + \mathbb{P}(C) - 2 < \mathbb{P}(D)$$ I don't ...
1
vote
1answer
554 views

Jensen inequality and bias of sample standard deviation

I am currently studying Introduction to Probability, second edition, by Blitzstein and Hwang. In studying the Jensen inequality, the following example is presented: Example 10.1.6 (Bias of sample ...
1
vote
0answers
21 views

How close a sample is to the Normal distribution ( Berry-Esseen Theorem)

My question is how can I use the Berry-Esseen Theorem to know how close to the Gaussian distribution is $L$, where $$L=nLn(2)+Ln(r_1)+Ln(r_2)...Ln(r_n).$$ $r_i \geq 0$ is a i.i.d. random variable ...
0
votes
1answer
122 views

What does the general case of bounded random variables mean in terms of Hoeffding's Inequality?

The following equation is Hoeffding's Inequality from Wikipedia for the general case of bounded random variables. I have just come to understand Hoeffding's Inequality for the special case of ...
1
vote
1answer
84 views

Need mathematical steps for Hoeffding's Inequality applied to Bernoulli Distribution

I am trying to understand Hoeffiding's Inequality in Machine Learning and I am referring to WikiPedia for it. Hoeffding's Inequality is defined as follows: $ P(|\hat{\theta} - \theta)| \ge \epsilon) \...
3
votes
0answers
54 views

How to derive Bonferroni's Inequality using Boole's Inequality?

I'm trying to derive Bonferroni's inequality using : $$P(\cup^{\infty}_{i=1} A_i) \leq \Sigma^{\infty}_{i=1} P(A_i)$$ for any sets A_1, A_2, ... (Boole's Inequality) The result I want is (Bonferroni'...
1
vote
1answer
173 views

Connection between subgaussian/subexponential and exponential family

I am wondering if there is any relationship between subgaussian/subexponential with (one parameter) exponential family. In particular, is there any sub-family density that belongs to both ...
2
votes
0answers
42 views

Hoeffding's inequality vs DKW inequality

What is the difference between Hoeffding's inequality: $$\mathrm{P}(|\hat{F}_n(x)-F(x)|\geq \epsilon) \leq 2e^{-2n\epsilon^2}$$ and the Dvoretzky-Kiefer-Wolfowith (DKW) inequality: $$\mathrm{P}(\...
2
votes
1answer
68 views

Prove that $E[e^{2(m−1)X^2}]\le m$

I'm reading "Understanding Machine Learning: From theory to algorithms". The problem is as follows, which is Exercise 31.1 of the book on page 416. Let $X$ be a random variable that satisfies $P[X \...
1
vote
0answers
47 views

Show that if $Y$ has $E(Y)=μ,Var(Y)=σ^2$, and $P(|Y-μ|<σ)=0$, then $Y$ has the same distribution as $X$ described below for $k=1$

I'm having a hard time proving the second and third case of $X$: Show that if $Y$ has $E(Y)=μ,Var(Y)=σ^2$, and $P(|Y-μ|<σ)=0$, then $Y$ has the same distribution as $X$ described below for $k=1$. $...
2
votes
1answer
62 views

How can I show that $P\{|(X-\mu_X)+(Y-\mu_Y)| \ge k\sigma\} \le (2(1+\rho))/k^2$?

Let $\sigma^2$ be the common variance of the random variables $X$ and $Y$, with their correlation coefficient being $\rho$. Show that $\forall k>0$, $P\{|(X-\mu_X)+(Y-\mu_Y)| \ge k\sigma\} \le (2(...

1
2 3 4 5 6