The tag has no usage guidance.

learn more… | top users | synonyms

2
votes
1answer
42 views

convergence rate of Pearson correlation

I am looking to find the finest bound possible for $$\mathbb{P}\left( | \hat{\rho}(X,Y) - \rho(X,Y) | \geq t\right) \leq ?$$ where $\rho$ is the Pearson correlation defined as $$\rho(X,Y) = ...
1
vote
0answers
65 views

Using Jensen's Inequality to identify blackbox function as convex?

** Edits: In light of the comments I received: I'll appreciate any elaboration on the questions I present. If you can provide examples of what I would need (assumptions, test cases, etc), ...
2
votes
0answers
18 views

Properties of the KL topology [reference request]

I'm trying to understand better what are the implications of a sequence of random variables $X_n$ converging toward some limit $X$ in the KL topology, ie the probability density functions are such ...
0
votes
0answers
9 views

Concentration inequalities for product of gaussians

Are there any concentration inequalities (i.e. probability bounds on how a random variable deviates from its expectation) for the product of $n$ gaussian random variables with zero means and equal ...
0
votes
0answers
39 views

Application of probability-inequalities in machine learning. Hoeffding's inequality

I would like to know a illustrative example of Hoeffding's inequality in machine learning? Does it have something to do with confidence intervals? Thanks in advance!
0
votes
1answer
40 views

How to use Hoeffding's Inequality to find a confidence Interval?

I want an example that shows how to use Hoeffding's inequality to find a confidence interval for a binomial parameter p (probability of succes). Thanks in advance!.
5
votes
1answer
53 views

Comparison of Bernstain and Chebyshev inequalities applied to Bernoulli distribution - simulation in R gives unexpected results

I'm trying to compare Bernstein and Chebyshev inequalities applied to Bernoulli distribution with parameter $p$. More specifically - how good are bounds they give for different sample sizes. I wrote ...
9
votes
1answer
151 views

Does convex ordering imply right tail dominance?

Given two continuous distributions $\mathcal{F}_X$ and $\mathcal{F}_Y$, It is not clear to me whether the relation of convex dominance among them: $$(0)\quad \mathcal{F}_X <_c \mathcal{F}_Y$$ ...
2
votes
1answer
46 views

Shannon entropy and inequality of expectations

Consider two distinct probability distributions $P(X)$ and $Q(Y)$---defined on the same domain---with (Shannon) entropy of $H(X)$ and $H(Y)$. I am interested to prove that $$ H(X) \leq H(Y) \implies ...
2
votes
0answers
41 views

Dvoretzky–Kiefer–Wolfowitz inequality hold for discrete distributions?

I am wondering whether Dvoretzky–Kiefer–Wolfowitz inequality holds for discrete distributions? Any comments or references would be greatly appreciated.
2
votes
0answers
30 views

bound on expectation of a two-variable function under an independent distribution

Consider a probability distribution $P(x)$, a set observed samples $S = \{x_1,\cdots, x_n\}$ where $x_i \stackrel{iid}{\sim} P(x)$ for $i \leq n$, and a symmetric function $h(x,y)$. How can one ...
5
votes
1answer
96 views

Berry-Esseen Theorem with Continuity Correction

Given independent but non-identical random variables $X_1, X_2, \ldots ,X_n$ with $E[X_i]=0,$ $E[X_i^2]=\sigma_i^2=1$ and finite absolute third moments $\rho_i=E[|X_i|^3].$ Let $$S_n = {\sum_{i=1}^n ...
1
vote
1answer
20 views

Inequalities for maxima over random functions

Let R be the set of real numbers. Say we have a function $f(x,X) \in R $ where $X \in R^d$ is a random variable over $\Omega$ and $x \in R$. I'm searching for an upper bound for the expected value of ...
11
votes
3answers
148 views

Regarding convergence in probability

Let $\{X_n\}_{n\geq 1}$ be a sequence of random variables s.t $X_n \to a$ in probability, where $a>0$ is a fixed constant. I'm trying to show the following: $$\sqrt{X_n} \to \sqrt{a}$$ and ...
2
votes
0answers
27 views

upper bound for expected maximum of difference of two kernel-Estimations

I'm searching for an upper bound for a function like $$ E\left[ \max_{x \in R} \left( \frac{ \sum_{i=1}^n K(\frac{x-X_i}{f(x,X_1, \dots X_n)}) \cdot Y_i } { \sum_{i=1}^n ...
2
votes
2answers
109 views

Moving an expectation inside a probability?

Let $X$ and $Y$ be two independent random vectors such that $E[X^TY]>0$, and all components of $X$ are positive valued. Then, is it true that, $P_{X,Y}\{X^T Y > 0\} \le P_{Y}\{E_X[X]^T Y > ...
6
votes
0answers
123 views

A question related to Borel-Cantelli Lemma

Note: Borel-Cantelli Lemma says that $$\sum_{n=1}^\infty P(A_n) \lt \infty \Rightarrow P(\lim\sup A_n)=0$$ $$\sum_{n=1}^\infty P(A_n) =\infty \textrm{ and } ...
1
vote
1answer
38 views

How to combine probability inequalities that are w.r.t. different random variables?

Let $x$ and $z$ be two independent random variables. Suppose I know the following two facts: $P_z[f(x,z) < g(x)] > 1-\delta$ uniformly for all x; $P_x[g(x) < h(x)] > 1-\delta_h$ How can ...
2
votes
0answers
44 views

Probability inequality implication

Let $X$ and $Y$ be independent random variables, and $A(X,Y)$ a predicate with values true or false. Suppose we know the following: $P_Y[\forall X, A(X,Y) \Rightarrow B(X)] > 1-\delta$. Can we ...
3
votes
2answers
104 views

$E(X)E(1/X) \leq (a + b)^2 / 4ab$

I've worked on the following problem and have a solution (included below), but I would like to know if there are any other solutions to this problem, especially more elegant solutions that apply well ...
1
vote
1answer
93 views

Chi-square test on a sample from population having an unequal distribution

I got a sample with an unequal gender distribution ($30$ males to $200$ female). This distribution is quite "representative" for the population the sample is taken from. Nevertheless, in a paper, ...
1
vote
0answers
26 views

Results stronger than Dvoretzky–Kiefer–Wolfowitz inequality?

There is the DKW inequality which controls the extent to which the empirical cdf of a sample from a real-valued random variable differs from the true cdf. Are there any stronger results (i.e. ...
2
votes
0answers
31 views

Is this a true inequality over multinomial parameters?

Let $p_1,\ldots,p_k$ be the multinomial parameters sampled from a Dirichlet distribution. Assume $\bar{p_1},\ldots,\bar{p}_k$ be the mean of Dirichlet distribution. Then, $$Pr( ...
0
votes
0answers
15 views

Getting a “friendly” tailbound from a closed-form description of the probability density (the case of the n-th order statistic)

Suppose I have a probability distribution of an $n$-th order statistic $X_n$ with mean $\mu$ and density $f_n(x)$, where $n$ scales to infinity. If one wants a concrete example, the one I care about ...
2
votes
0answers
20 views

Identifying values responsible for producing inequality or concentration within a distribution

(This may be a dumb question I simply don't know enough to know is dumb, but it's foxing a surprisingly large chunk of my social circle) I have a dataset web requests - specifically, the page, and ...
1
vote
0answers
33 views

Tail bound on dependent sum

Let R be a random variable, and let X_i be a nonlinear, nonconvex function that takes R and outputs a value in [-1,1]. I'm trying to get a tail bound on the following dependent sum: ...
3
votes
1answer
79 views

Understanding a step of a proof of Markov's inequality

$X$ is a positive valued random variable, $\theta$ is greater than $1$, $P$ is a probability measure. Why is the following inequality true: $$\int_{\theta E(X)}^{+\infty} x dP_{X}(x) \ge ...
1
vote
0answers
29 views

Families of distributions with bounded variations

For what family of probability distributions $f(x)$ do we have the following property? $$ \forall x, \quad \int f(u) - f(u+x) du \leq L\| x \| $$ for some $L$. Can we say anything about the ...
1
vote
1answer
119 views

Tail bounds for Beta distribution

Say $X\sim\mathrm{Beta}(\alpha,\beta)$. Are there any "nice" closed form upper bounds for the tail probability $P(X\geq\epsilon)$, that are reasonably tight when $\beta$ is large? By "nice" I mean ...
0
votes
0answers
30 views

how can Cauchy-Schwarz help here?

From http://math.stackexchange.com/questions/1004544/if-mathrme-x2-exists-then-mathrme-x-also-exists If $\mathrm{E} |X|^2$ is finite, then $\mathrm{E} X$ exists and is finite, because $$ ...
0
votes
0answers
32 views

I don't understand the solution to this Chernoff inequality?

I have a sum, $S_n = \sum_{i=1}^n X_i$ of n iid Poisson distributed random variables $X_1,...X_n$ I am supposed to apply the Chernoff bound to $S_n$. My professor gave us the solution: However, I ...
5
votes
1answer
197 views

How to bound a probability with Chernoff's inequality?

In my class, we were given Chernoff's inequality as $$P(X\le -t) \le e^{(-(\lambda t - \log( E(e^{-\lambda x}))))}$$ $$P(X\ge -t) \le e^{(-(\lambda t - \log( E(e^{\lambda x}))))}$$ It says that to ...
3
votes
1answer
121 views

Does vector version of the Cauchy-Schwarz inequality ensure that the correlation coefficient is bounded by 1?

I have been trying to understand the proof that the correlation between two random variables $X$ and $Y$ is between $-1$ and $1$. For simplicity, suppose $X$ and $Y$ have mean zero. Then ...
6
votes
1answer
598 views

Cantelli's inequality proof

I am trying to prove the following inequality: EDIT: Almost immediately after I posted this question, I discovered that the inequality I am being asked to prove is called Cantelli's inequality. When ...
2
votes
0answers
51 views

Concentration inequality of weighted sum of random variables given a tail inequality

I'm reading this book on concentration inequalities and I'm trying to solve all of the exercises in the book. The following problem is from the book which I couldn't manage to solve. I have also ...
9
votes
3answers
344 views

Exponential upper bound

Suppose we have IID random variables $X_1,\dots,X_n$ with distribution $\mathrm{Ber}(\theta)$. We are going to observe a sample of the $X_i$'s in the following way: let $Y_1,\dots,Y_n$ be independent ...
2
votes
1answer
117 views

Proof of density inequality

I was wondering if there is an easy way to find sufficient conditions for the following inequality to hold $$ \int f(x,y)^2 \:\mathrm{d}x \:\mathrm{d}y - \int f(x)^2 f(y)^2 \:\mathrm{d}x\:\mathrm{d}y ...
3
votes
4answers
392 views

Given more information, can a probability lessen?

Let $A$, $B$ and $C$ be events in the same probability space. Does $$\begin{align} \mathbb P(A\,|\,B\cup C) \ge \mathbb P(A\,|\,B) \end{align}$$ hold?
1
vote
0answers
26 views

Need help on Cramér-Chernoff method in concentration inequalities

I am reading up on the Cramér-Chernoff method in concentration inequalities. The idea is to use Markov's inequality and the monotonic transformation $\phi(t) = e^{\lambda t}$ where $\lambda \geq 0$. ...
0
votes
1answer
56 views

Probability of ($x\le 2Y$)

$X$ and $Y$ are independent and their probability density functions are $$f_X(t)=f_Y(t)=\left\{\begin{array}{l} e^{-t},\:\text{if $t \geq 0$;} \\ 0,\:\text{otherwise.}\end{array}\right.$$ $P(X \leq ...
2
votes
0answers
44 views

$\sigma^2 \le (\mu-a)(b-\mu)$ for all probability distributions bounded on $[a,b]$? [duplicate]

Let $\mu$ be the mean and $\sigma$ the standard deviation of a probability distribution defined on the bounded interval $[a,b]$ (that is, the probability that the random variable lies outside $[a,b]$ ...
3
votes
1answer
119 views

Bivariate One-Sided Chebyshev Inequality (Symmetric Case)

Let $X$ and $Y$ be random variables with finite means $\mu_X$ and $\mu_Y,$ finite variances $\sigma_X^2$ and $\sigma_Y^2,$ and correlation $\rho.$ Let $A$ be the event that $X \leq \mu_X + k\sigma_X$ ...
1
vote
1answer
169 views

Randomized Response, calculating probability

I have a problem with randomized response method when calculating the probability of critical attribute. For any of you who are not familiar with the method, you can check it here, Wikipedia Entry for ...
21
votes
2answers
786 views

Does a sample version of the one-sided Chebyshev inequality exist?

I am interested in the following one-sided Chebyshev inequality: $$ \mathbb P(X - \mathbb E (X) \geq t) \leq \frac{\mathrm{Var}(X)}{\mathrm{Var}(X) + t^2} \,. $$ Basically, if you know the ...
0
votes
1answer
99 views

Variance Inequality for Random Vectors

I know that if X and Y are random scalar variables, then: \begin{align*} \mathrm{Var}(X+Y) & = \mathrm{Var}(X) + \mathrm{Var}(Y) + 2\mathrm{Corr}(X,Y)\sqrt{\mathrm{Var}(X)\mathrm{Var}(Y)} \\ ...
3
votes
1answer
123 views

Is it true that $E[e^{tX}] \le e^{E[t^2X^2/2]}$?

I've seen some one use the inequality $E_X[e^{tX}] \le e^{E_X[t^2X^2/2]}$. However, I don't know if it is true and can not prove it. Thanks for help.
2
votes
0answers
73 views

Is Hoeffding's bound tight in any way?

The inequality: $$\Pr(\overline X - \mathrm{E}[\overline X] \geq t) \leq \exp \left( - \frac{2n^2t^2}{\sum_{i=1}^n (b_i - a_i)^2} \right)$$ Is this bound (or any other form of hoeffding) tight in ...
2
votes
0answers
67 views

An inequality involving expectation

Let $f,g$ be two pdfs, and suppose $X$ is a random variable that has pdf $f$. Is it necessarily true that $E[f(X)] \ge E[g(X)]$? Although I doubt this will help, but I got this problem from studying ...
4
votes
1answer
78 views

If Chebyshev's upper bound gives same value as the actual probability calculation, what can we conclude?

As an example, if Chebyshev tells $P(|X-\mu|\geq k\sigma)\leq 0.25$ and the actual probability for $k=2$ is also $0.25$.
5
votes
2answers
232 views

Concentration bounds on a sequence of (0,1)-experiments

I have a $(0,1)$-experiment that returns $1$ with probability $p$ and $0$ with probability $1-p$. Let $X_i$ be the random variable describing the outcome of iteration $i$ of the experiment. I'm ...