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
1answer
131 views

Concentration for Conditional Random Variable

Consider a conditional random variable \begin{equation} X = \begin{cases} Y & \quad\quad ,X \in A \\ Z & \quad\quad ,X \in A^\complement \end{cases} \end{equation} $Y$ ...
5
votes
1answer
101 views

Upper bound for the probability $P\left[\left|\frac{Y_n}{n}-p^2\right|>\varepsilon\right]$

Let $X_1,X_2,\cdots,X_{n+1}$ be independent random variables with $$P(X_i=1)=p=1-P(X_i=0)\quad\text{ for all }i$$ Define $Y_i$ to be the number of $i$'s such that $X_i=X_{i+1}=1\,,\quad i=1,2,\...
1
vote
0answers
52 views

Conditional distribution relations

There is a probability density function of the form, $f_S(s)=\displaystyle\iint f_S(s|x,y)f_{X,Y}(x,y)dxdy$ that is used for evaluation of expectation of some monotonic function $\mathbb{E}[g(S)]=\...
3
votes
0answers
217 views

Lower bounds on covering numbers for sparse vectors

Consider the set $S_k$, which is defined as the subset of $k$-sparse vectors in the unit sphere in $d$ dimensions: $$ S_k \triangleq \left\{ x \in \mathbb{R}^d : \| x \|_2 = 1, \, \left|\operatorname{...
5
votes
1answer
383 views

How good an approximation is sampling with replacement to sampling without replacement?

I'm learning about probability with Feller's book and he states that, when the population size $n$ is big in comparison with the sample size $r$, then $n_r$, which is a shorthand for $\frac{ n!}{(n-r)!...
6
votes
1answer
138 views

Covering the unit sphere with sparse vectors

I'm looking for references for covering the $d$-dimensional unit sphere $$ \mathbb{S}^{d - 1} = \left\{ x \in \mathbb{R}^d : \| x \| = 1 \right\} $$ I'm trying to cover $\mathbb{S}^{d-1}$ with ...
1
vote
1answer
34 views

Concentration Square Increments of a MDS

I have a martingale difference sequence $\{ X_t \}$ where each $X_t$ is subGaussian. Are there concentration inequalities for $$ \sum_{t=1}^T X^2_t - E \left( \sum_{t=1}^T X^2_t \right) $$
0
votes
1answer
163 views

Is my solution correct for this measure-concentration related task?

I'm reading the book "Concentration inequalities" by Boucheron, Lugosi, Massart. There is an exercise section after each chapter. I've tried to solve one and would like to understand, whether it would ...
1
vote
0answers
387 views

Constant concentration for chi square variables

Reposted from math stackexchange (https://math.stackexchange.com/questions/2779699/constant-concentration-for-chi-square-variables) as suggested by another user. I would like to have a certain ...
3
votes
1answer
245 views

Accuracy of empirical cumulative distribution function

I have a random variable with an unknown distribution and I want to find its cumulative distribution function. I sample the distribution $N$ times, with $$X_1, \dots, X_N$$ being iid random ...
1
vote
1answer
76 views

$CTE(p)$ is generally greater than $VaR(p+\frac{1}{2}\cdot(100-p))$, $p$ being a percentile

Let's assume we are in the insurance business and the values we are observing are losses. So there is a general statement that says the Conditional Tail Expectation at percentile $p$ is usually ...
17
votes
1answer
3k views

Oracle Inequality : In basic terms

I'm going through a paper that uses oracle inequality to prove something but I'm unable to understand what it is even trying to do. When I searched online about 'Oracle Inequality', some sources ...
2
votes
0answers
154 views

Tight bound for Binomial distribution or, equivalently, the Incomplete Beta function?

Suppose $X \sim Binomial(n,p)$ with known $n$ but unknown $p$, and let $G(p,k) = P[X \geq k)$ for $k=0, \ldots, n$. I am looking for a tight upper bound on $|G(p_1, k) - G(p_2, k)|$ for some given $k$....
4
votes
0answers
87 views

Concentration inequalities for weighted sums of gaussians

Suppose that $x \sim \cal{N}(0,I_d)$ be a $d$-dimensional standard Gaussian vector and let $x_1,\ldots,x_n$ denote $n$ i.i.d. samples drawn from the same distribution. For some fixed vector $\theta \...
4
votes
0answers
985 views

Concentration of maximum of subexponential random variables

I'm looking for a concentration bound on the maximum of a collection of sub-exponential random variables, which are not necessarily independent. More specifically, I have the following collection: \...
0
votes
1answer
428 views

the normalization constant

On page 4 of this article, the authors wants to find the normalizing constant $c$ but it is very hard to compute so I used the same formula to bound $c$. Take the non-negative integers $~0 \leq x_1,...
1
vote
0answers
196 views

Cantelli Inequality Variant

In the JASA (1968, vol. 63, no. 324, pp. 1522-1525) article "How Deviant Can You Be?" Paul Samuelson notes two versions of Chebyshev's inequality: $$P \left( \lvert {X-\mu} \rvert \geq k \sigma \...
6
votes
1answer
124 views

Zero-mean RV $X$, probability of being positive using moments

For zero-mean RV $X$ with finite fourth moment, prove that $$ P(X>0)\ge \frac{\mathbb{E}(X^2)^2}{4\mathbb{E}(X^4)} $$ I tried Chebyshev with adding $t$ to both sides, but I could not get fourth ...
1
vote
0answers
70 views

Convergence of a sequence in finite number of steps

Here is the setup of my problem. It is a sequential problem and there are two possible actions A and B. Now, when either action $A$ or $B$ is taken at the $j$th time point, we observe some outcome say ...
4
votes
0answers
77 views

Characteristic function inequality

Random variable $X$ and its characteristic function $\phi_X(t)$ then $$\Pr\left(|X|>\frac2T\right) \leq 2\left(1 - \frac1{2T}\int_{-T}^{T}\phi_X(t)dt\right) $$ I cannot find a way how to ...
2
votes
1answer
252 views

Why does conditional expectation have this property for independent random variables?

For a reference, please see pp. 53-54 of Boucheron, Lugosi, Massart, Concentration Inequalities: A Nonasymptotic Theory of Independence. Let $f: \mathcal{X}^n \to \mathbb{R}$ be a measurable function (...
0
votes
1answer
43 views

Increased probability of event during period of time

In game of FIFA there are packs by opening which a user receives soccer player cards. The higher the rating of a player card the rarer it drops depending on some kind of random number generator. Since ...
1
vote
0answers
282 views

Linear combination of truncated normals

I am trying to calculate the following expression: $$ Z = \mathbb{E}\left[\left| \langle \mathbf{a}, u \rangle \right| \right] = \left| \sum_{i=1}^d a_i u_i \right|, \quad \left\| u \right\| = 1 $$ ...
4
votes
2answers
4k views

Using Chebyshev's inequality to obtain lower bounds

Let $X_1$ and $X_2$ be i.i.d. continuous random variables with pdf $f(x) = 6x(1-x), 0<x<1$ and $0$, otherwise. Using Chebyshev's inequality, find the lower bound of $P\left(|X_1 + X_2-1| \le\...
2
votes
0answers
133 views

Bounds on tail conditional expectation of random variable given variance

Given a random variable $X$ with CDF $F(X)$, mean $E(X)=0$, and variance $Var(X) =\sigma^2$, I would like to bound the tail conditional expectation where $X$ is in the tail with probability $1-p$: $E(...
5
votes
1answer
177 views

Proof that $E(|X_1 - X_2|)$ is bound by twice the mean

Let $X_1$, $X_2$ be iid random variables. How do I show that for non-negative variables $E(|X_1 - X_2|)$ is bound from above by twice the expected value of $X_1$ (or $X_2$)?
6
votes
1answer
325 views

How do I show this using the Cauchy-Schwarz inequality

From Two Population We have two $p$ dimensional sampels $\mathbf{X}_1$ and $\mathbf{X}_2$ with sample size $n_1$ and $n_2$ respectively, Let We have $\mathbf{\Lambda} = \mathrm{diag}\{(\sigma_{11}^2 + ...
2
votes
1answer
351 views

Does this Bonferroni styled inequality also hold for characteristic functions?

This is the popular Bonferroni inequality. Does it also hold for characteristic functions of random variables, as in when $P(A_i)$ is replaced by the characteristic function $\chi(A_i)$ and so forth? ...
9
votes
3answers
345 views

What's higher, $E(X^2)^3$ or $E(X^3)^2$

So I had a probability test and I couldn't really answer this question. It just asked something like this: "Considering that $X$ is a random variable, $X$ $\geqslant$ $0$, use the correct inequality ...
3
votes
2answers
3k views

Kullback-Leibler divergence lower bound

Are there any (nontrivial) lower bounds on the KL-divergence between two densities? Informally, I am trying to study problems where $f$ is some target density, and I want to show that if $g$ is chosen ...
4
votes
0answers
128 views

Uniform convergence of expectation?

Let $U_i$, $i = 1 ,2\dots, $ be i.i.d. standard normal random variables. For every $n$, let $f_n:\Theta \times \mathbb R^{n} \to [0, 1]$, where $\Theta$ is some compact subset of $\mathbb R$ [may ...
1
vote
1answer
821 views

Bounds on quantiles of the sum of (possibly dependent) random variables

Suppose I have two continuous random variables $X$ and $Y$, and I can evaluate the quantiles of these distributions individually. I aim interested in what kinds of constraints can be put on quantiles ...
2
votes
4answers
232 views

If $P(A \mid E) > P(B \mid E)$ and $P(A \mid \neg E) > P(B \mid \neg E)$, then is $P(A) > P(B)$ true?

If $P(A \mid E) > P(B \mid E)$ and $P(A \mid \neg E) > P(B \mid \neg E)$, then is $P(A) > P(B)$ true? If it is, how to prove it? Intuitively, I'm thinking it should be true, but I don't ...
2
votes
2answers
109 views

A question about conditional probability

Assume $X$ is discrete random variable. It has some distribution on integers $0,1,...,m$ Then is $P(X>k | X=m) \ge P(X>k)$ true? If it is, how to prove it in a rigorous way? For me, it is ...
3
votes
1answer
556 views

Chebyshev Inequality Homework Question

A number of lightbulbs have lifetimes X that are iid and exponentially distributed with a mean of 1/4. As a lightbulb fails, it is replaced with another until the bulbs run out. Using Chebyshev ...
0
votes
0answers
137 views

$P(X+Y>Z)$ given $X,Y,Z$ are i.i.d random variables

Given $X, Y, Z$ i.i.d random variables the probability $P(X+Y>Z)$ can be found by the following three approaches: $X+Y-Z > 0$ region cuts the $X Y Z$ volume into two equal volumes as $X+Y-Z=0$ ...
10
votes
3answers
4k views

If $E(|X|)$ is finite, is $\lim_{n\to\infty} nP(|X|>n)=0$?

For a continuous random variable $X$, if $E(|X|)$ is finite, is $\lim_{n\to\infty}n P(|X|>n)=0$? This is a problem I found on the internet, but I'm not sure whether it holds or not. I know that $...
2
votes
1answer
2k views

Jensen's inequality for two variables

For a random variable X, Jensen's inequality says, $$E[g(x)]\geq g(E[x])$$ for a convex function $g(x)$. Is there a generalization of this to two variables? That is, for two random variables, does $$ ...
4
votes
1answer
71 views

Solving P(TRUE) of finding counterpart pairs in 2 sets with constraints involving the Universal Genetic Code

Alright, I posted this same question over at MSE, https://math.stackexchange.com/questions/2395394/solving-ptrue-of-finding-counterpart-pairs-in-2-sets-with-constraints-involvin, I had a bounty on it ...
0
votes
0answers
81 views

Lower bound for difference of probabilities of a same event under two different distributions

Say $P$ and $Q$ are two probabilities distributions on $[n]$. I can upper bound the difference of the probability of an event $A$ under $P$ and $Q$ by the total variation distance between $P$ and $Q$. ...
1
vote
1answer
132 views

Chebyshev's Inequality

A certain type of light bulb has an average lifetime of 10,000 hours. The SD of bulb lifetimes is 470 hours. What fraction of bulbs could last more than 10,705 hours? I think the correct answer should ...
2
votes
1answer
102 views

How much better is the best Moment Bound?

I've been looking at Gabor Lugosi's wonderful notes on concentration of measure inequalities. On page 7 of the notes the exercise asks you to show that $$ min_q\mathbb{E}(X^q)t^{-q} \leq inf_{s\geq ...
2
votes
1answer
378 views

Demonstrating Markov inequality on a uniform distribution

I was reading about the Markov inequality and tried to see if I could prove it for a uniform distribution. So say we have $X\sim U(a,b)$ and we are trying to prove $$\mathop{\mathbb{P}}(X\ge \lambda)\...
3
votes
2answers
658 views

Is the centered product of a Gaussian and Bernoulli r.v. sub-Gaussian?! Tailbound needed

Let $X_1, X_2, \dots, X_n$ i.i.d. $N(0,\sigma^2)$ and let $Y_1, Y_2, \dots, Y_n$ be independent and identical Bernoulli random variables (where $Y_i$ may depend on $X_i$). I am searching for a ...
8
votes
2answers
236 views

If $\mathbb{E}|X_n|=O(a_n)$, how large is $Y_n = X_n\ln\left(\frac{1}{X_n}\right)$?

If $\mathbb{E}|X_n|=O(a_n)$, where $a_n\to 0$ and $X_n$ is a sequence of positive random variables, how large is $Y_n = X_n\ln\left(\frac{1}{X_n}\right)$? My attempt: by Markov's inequality $\mathbb{...
0
votes
0answers
32 views

Question on Inequalities involving random variables

If $N(k)$ be the number of $X_i$'s such that $|X_i - \bar{X}| \geq k.s$ for some $k > 0$, how can we show that $$\frac{N(k)}{n} \leq \frac{1}{k^2} \;\;\;\;?$$ Here, $\bar{X}$ and $s$ are the mean ...
4
votes
1answer
222 views

Jensen's inequality for one of several variables

Consider some differentiable function $f(X,Y)$, where $X$ and $Y$ are scalar RVs. Assume that $\frac{\partial^2 f}{\partial X^2}>0$ but that nothing is known about the rest of the Hessian of $f$. ...
1
vote
0answers
212 views

Probability of a certain card being UR, SR, R, or N

There are 200 packs in a box, and there are 3 cards in each pack (600 cards total) and you must buy one pack (3 cards) at a time. A pack can contain: An UR (10 total), a SR (24 total), a R (192 total),...
3
votes
1answer
200 views

A Bound based on Jensen's Inequality

Consider: $$X \sim \text{Gamma}(\alpha, \beta)$$ $$Y = \frac{1}{X+c}, \ c > 0$$ I am interested in $E(Y)$, which I'm pretty sure is intractable... $$E(Y) = \frac{\beta^\alpha}{\Gamma(\alpha)}\...
0
votes
0answers
24 views

1_event set notation

I do not understand the notation as given here: The source for the image is page 17 in this paper after equation 18. I understand the first subset notation but what does 1_\e_t mean?