All Questions
52 questions
3
votes
0
answers
90
views
Tighter Freedman's inequality for a special martingale difference sequence
Let $X_{1}, \ldots, X_{T} \in \{0, 1\}$ be a sequence of Boolean random variables with
$$
\mathbb{E}[X_{t} | X_{1}, \dots, X_{t - 1}] = p_{t}.
$$
Consider the sequence $Y_{t} := X_{t} - p_{t}$ (which ...
- 41
2
votes
1
answer
208
views
Proving an exponential sum inequality for symmetric Hamming distance sequences in binary vectors
Background: Let $X = \{0,1\}^k$ represent the set of all binary vectors of length $k$. For two binary vectors $x, y \in X$, the Hamming distance $d_H(x, y)$ is defined as the number of positions where ...
- 349
3
votes
0
answers
80
views
Seeking strong bounds on KL-divergence and martingales for a hypothesis-testing inequality
Let's say we have a finite set $\mathcal{O}$ of observations, and let $\mathcal{C}(\Delta\mathcal{O})$ denote the space of closed convex sets of probability distributions.
We have two hypotheses which ...
- 353
0
votes
0
answers
91
views
Some new questions on Rademacher complexity
For $A\subset R^n$,$A=(a_1,a_2,\dots, a_n)$, $\sigma_i$ are Rademacher random variable.
Is $|\mathbb{E}_\sigma \inf_{a\in A}\sum_{i=1}^n\sigma_ia_i| \le |\mathbb{E}_\sigma \sup_{a\in A}\sum_{i=1}^n\...
- 185
5
votes
1
answer
516
views
Bounding the variance of a truncated Gaussian random variable
Suppose $X_1, X_2, X_3 \sim N(0, 1)$ are three independent standard normal random variables. I am interested in showing that:
$$\text{Var}[X_2\mid X_2 \geq X_1 - a, X_1 \leq X_3 + b] < 1,$$
where ...
- 269
1
vote
1
answer
56
views
Covariance inequality for left skewed distributions
Consider a left skewed random variable $X$ with mean $1$, median $>1$ and support on $[0,2)$. Suppose we have a class of functions $\mathbf{G}$ and each of it's members satisfy $G(x): [0,\infty) ...
- 45
1
vote
2
answers
2k
views
Upper bound about Gaussian tail bound
From the definition of sub-Gaussian distribution $X$ w.r.t. $\sigma$ i.e.
$$\mathbb{P}(|X-\mathbb{E}(X)|\geq t) \leq 2 \exp(-\frac{t^2}{2\sigma^2}).$$
It's natural that when $X \sim \mathcal{N}(\mu, \...
- 81
0
votes
0
answers
78
views
Kernel density estimation is sub-gaussian
Let $X_1, ..., X_n$ be i.i.d. samples drawn from a pdf $f(x)$ on the real line. The kernel density estimator is defined as follows,
$$\hat{f_n}(x) = \frac{1}{nh}\sum_1^n K(\frac{x-X_k}{h})$$
where $K:\...
- 81
4
votes
1
answer
168
views
Existence of copula bound pointwise strictly smaller than the Fréchet-Hoeffding upper bound
Consider bivariate copulas $C_1$ and $C_2$ with $\max\{C_1(u,v), C_2(u,v)\}< M_2(u,v)$ for all $u,v \in(0,1)$, where $M_2(u,v) := \min\{u,v\}$ is the Fréchet-Hoeffding upper bound.
Is there a ...
- 143
2
votes
1
answer
150
views
Normalized concentration inequality for empirical CDF (iid sum)
Consider the empirical and population CDF,
$$
F_n(t) = \frac{1}{n} \sum_{i=1}^n 1\{X_i \leq t\} \quad \mbox{and} \quad
F(t) = \mathbb{E} [F_n(t)],
$$
where above $X_1, \dots, X_n$ are iid, real-...
- 420
5
votes
2
answers
2k
views
Relationship between KL, chi-squared, and Hellinger
There are many well-known relationships between the KL divergence, chi-squared ($\chi^2$) divergence, and the Hellinger metric. In the paper "Assouad, Fano, and Le Cam" by Bin Yu, the author ...
- 63
1
vote
1
answer
251
views
Using Hoeffding inequality for risk / loss function
I've got a question to the Hoeffding Inequality which states, that for data points $X_1, \dots, X_n \in X$, which are i.i.d. according to a probability measure $P$ on $X$, we find an upper bound for:
$...
- 13
2
votes
1
answer
154
views
Random probability following a log concave distribution of order p
In the article "Concentration of the information in data with
Log-concave distributions" of Bobkov and Madiman, it is written that if $X$ is a positive random variable following a log ...
3
votes
2
answers
169
views
On finding an upper bound on the error of a sparse approximation
I posted this question on math.stackexchange earlier, but didn't see any response. So, I am posting it here, in case someone else has an answer.
Original question: https://math.stackexchange.com/...
- 65
1
vote
1
answer
106
views
What is the maximum possible coefficient of variation for data taking values within a specified range?
I have a question that seems very basic, and yet I have not managed to find an answer after probably several hours of Google-searching.
Fix $0<a<b<\infty$, and let $\mathcal{P}_{[a,b]}$ be ...
- 708
2
votes
1
answer
138
views
Comparison between $\|X\|_2$ and $\|X\|_{2,1}$
For any real random variable $X$, define
$$\|X\|_{2,1}=\int_0^\infty \sqrt{\Pr(|X|>t)}dt.$$
This quantity (it is not a norm) appears in various problems, e.g. the multiplier central limit theorem (...
- 197
0
votes
1
answer
133
views
How to demonstrate a correlation inequality? [closed]
If there are 3 vectors X, Y, Z of the same length, for any $x_i \in X,y_i \in Y,z_i \in Z$, we have $0<x_i<1,0<y_i<1,0<z_i<1$.
The correlation between Z, Y is greater than between X, ...
- 11
5
votes
1
answer
150
views
Kullback–Leibler chains
The following question was asked and then deleted by the post author:
Let $P$ and $Q$ be two probability distributions defined over the same space, with $KL(P \parallel Q) < \infty$. For $\epsilon ...
- 128k
2
votes
3
answers
1k
views
How can I prove Chebyshev's sum inequality with probabilistic methods?
I would like to prove Chebyshev's sum inequality, which states that:
If $a_1\geq a_2\geq \cdots \geq a_n$ and $b_1\geq b_2\geq \cdots \geq b_n$, then
$$
\frac{1}{n}\sum_{k=1}^n a_kb_k\geq \left(\frac{...
- 39
0
votes
1
answer
179
views
How to show $\max_{1\leq i\leq n}(X_i+Y_1)\preceq \max_{1\leq i\leq n}(X_i+Y_i)$?
Let two collections of random variables $\{X_i\}$ and $\{Y_i\}$ be independent and let $\{Y_i\}$ be i.i.d. Then
$$\max_{1\leq i\leq n}(X_i+Y_1)\preceq \max_{1\leq i\leq n}(X_i+Y_i).$$
where $\...
- 288
1
vote
1
answer
143
views
Lower bound for log-Ratios
Can we find a universal constant $c>0$ such that for all $p,q\in\Delta:=\lbrace x\in (0,1)^{n}\ \colon\ x_{1}+\dots+x_{n}=1\rbrace$ it is true that
\begin{equation}
|p_{i}-q_{i}|\le c\left|\ln\frac{...
- 289
1
vote
1
answer
285
views
Exponential upper bounds for sums of martingale differences
Let $(X_{i})_{i\geq 1}$ be a sequence of centered real-valued martingale-differences with respect to some filtration $(\mathcal{F}_{i})_{i \geq 1}$. Define $S_{n} = \sum_{i=1}^{n}X_{i}$ and $\Sigma^{2}...
- 65
2
votes
0
answers
80
views
Bridging between Rosethal Inequalities and log convex tails
Let $X_1,\ldots,X_n$ be independent with $\mathbf{E}[X_i] = 0$ and $\mathbf{E}[|X_i|^t] < \infty$ for some $t \ge 2$. Write $\|X\|_p = (E|X|^p)^{1/p}$.
Then we have the classical "Rosenthal-type ...
2
votes
1
answer
235
views
Kolmogoroff condition for truncated random variables
Question summary. Does the Kolmogoroff condition $\sum_{n=1}^\infty\frac{\mathbb V Y_n}{n^2} < \infty$ hold for truncated random variables $Y_n := X_n \cdot 1_{\{X_n \le n\}}$ (see below for a more ...
- 1,326
1
vote
1
answer
313
views
Bounds on difference between "logsumexp" and variance?
Let $Z$ be a random variable with finite moment-generating function $M_Z(\theta):=E[e^{\frac{1}{\theta}Z}]<\infty$ for all $\theta > 0$, and for $\delta \in (0,1]$, define
$C_Z^\delta := \inf_{\...
- 6,853
1
vote
1
answer
365
views
Lower-bound probability of non-centered quadratic form
Let $X\sim N(\mu,\sigma^2I)\in \mathbb{R}^n$ be a non-centered ($\mu\neq 0$) Gaussian vector with independent coordinates. I'm wondering if there is any sharp lower bound of the following probability:
...
- 1,495
4
votes
1
answer
206
views
Inner product of sorted Gaussian vector
Suppose $X_1,\ldots,X_n$ are i.i.d. standard normal. I'm wondering how to analyze the following quantity:
$$\left|\frac{X_{(1)}X_{(n)}+X_{(2)}X_{(n-1)}+\cdots+X_{(n)}X_{(1)}}{n}\right|$$
where $X_{(1)}...
- 1,495
1
vote
2
answers
462
views
lower bound the probability of at least L collisions
Lets say we get a list $M$ containing $|M|=\sqrt{L\cdot N}$ randomly and independtly drawn elements from a set of size $N$. And lets denote the $i$-th element of the list $M$ by $M[i]$.
If we now ask ...
- 123
3
votes
1
answer
171
views
Why does the assumption $|U_t| \le \frac1{p_{\min}}$ work in this paper?
I am reading a 2009 paper right now "Importance Weighted Active Learning" and on page 5, there is a theorem that uses the inequality $|U_t| \leq \frac{1}{p_{\min}}$. I am not sure how the paper found ...
- 33
4
votes
1
answer
1k
views
Does variants of Bernstein and Freedman concentration inequalities exist with NO uniform bound on the range of RV or martingale differences
A classic formulation of the Bernstein inequality (from Wikipedia) is as follow:
Let $X_1, \ldots, X_n$ be independent zero-mean random variables. Suppose that $|X_i|\leq M$ almost surely, for all $i$...
- 53
5
votes
1
answer
164
views
Probability of ruin in the Sparre Andersen renewal risk model
In 1957, Erik Sparre Andersen proposed using a renewal risk model to describe the behavior of the insurers surplus
$$U(t)=u+ct-\sum\limits_{i=1}^{\Theta(t)}Z_i, \quad t \geqslant 0$$
where:
$u \...
8
votes
2
answers
4k
views
Lower bounds on Kullback-Leibler divergence
This was originally a question on Cross Validated.
Are there any (nontrivial) lower bounds on the Kullback-Leibler divergence $KL(f\Vert g)$ between two measures / densities?
Informally, I am ...
- 710
2
votes
2
answers
632
views
An alternative proof of Bayesian Cramer-Rao
My question is:
Are there an alternative proof of Cramer-Rao lower bound that does not use
Cauchy-Swartz inequality?
Let me outline the classical proof and explain why I am interested in this ...
- 671
1
vote
0
answers
376
views
Anti-concentration bounds for folded normal and inverse of gaussian variables
Are there any easy to use bounds on sums of the following kind :
$$
\sum_{i = 1}^{i = N} |a_i| \geq P \\
a_i \sim \mathcal{N}(0, 1) \\
$$
and also for sums of the form :
$$
\sum_{i = 1}^{i = M} \...
- 111
1
vote
1
answer
249
views
On concentration of a sum random variable
Take a random variable defined as
$$r=u_{11}v_{1}v_{1}+u_{12}v_{1}v_{2}+\dots+u_{n,n-1}v_{n}v_{n-1}+u_{nn}v_{n}v_{n}$$ where $v_{i}$ are independent uniform random variables from $\{0,\dots,b\}$, $u_{...
- 13.9k
8
votes
2
answers
2k
views
Median and mean of the sample mean of i.i.d. log-normal
Let $y:=\frac1n\sum_{i=1}^n x_i$, where $\{x_i\}_{i=1}^n$ is a set of i.i.d. random variables, and every $x_i$ has a lognormal distribution $x_i \sim\text{Lognormal}(\mu,\sigma^2)$. Let $\text{Med}[y]$...
- 2,239
1
vote
0
answers
282
views
Strict monotonicity of conditional variances
Let $K \geq 2$ be a positive integer and $C$ be any $K \times K$ non-singular matrix (if necessary, can assume that all $K$ rows of $C$ are needed to span the coordinate row vector $e_1'$). For ...
- 765
4
votes
0
answers
141
views
Is there an example that both Berry-Essen bound and DKW bound are attained?
The Berry-Essen bound stated that
$$\sup _{{x\in {\mathbb R}}}\left|\widehat{F_{n}(x)}-\Phi (x)\right|\leq C_{0}\cdot \psi _{0}$$
where $\psi _{0}(n)={\Big (}{\textstyle \sum \limits _{{i=1}}^{n}\...
- 8,071
6
votes
1
answer
238
views
Positive semidefinite ordering for covariance matrices
Suppose that X and Z are matrices with the same number of rows. Let
$$ D = \left[\begin{array}{cc} X' X & X'Z \\ Z'X & Z'Z \end{array} \right]^{-1} - \left[\begin{array}{cc} (X' X)^{-1} & ...
- 1,068
4
votes
1
answer
347
views
Concentration of functional of Gaussian random variable
Suppose I have two Gaussian distributions
$p(x) = \frac{1}{(2\pi)^{d/2}|\Sigma_p|^{1/2}}\exp(-\frac{1}{2}x^\top \Sigma_p^{-1} x)$ and $q(x) = \frac{1}{(2\pi)^{d/2}|\Sigma_q|^{1/2}}\exp(-\frac{1}{2}x^\...
- 515
1
vote
1
answer
207
views
Computing probability that $Ax\geq0$ where $x$ is a vector of iid gaussians and $A$ is matrix of $1$s and $0$s
This question came up in my research: What is the probability that $Ax\geq0$ where $x$ is a vector of iid gaussians and $A$ is matrix of $1$s and $0$s?
So far I only figured out that I can do Monte ...
- 113
3
votes
2
answers
231
views
Bounds for the fat tail after trimming the mean?
I am interested in the quantity $$f(X,t) = \int_t^\infty\negthinspace x\ p(x)\ dx,$$ where $p$ is a probability distribution for a positive variable $X$.
1) Does this quantity $f(X,t)$ have a name? ...
user44143
4
votes
0
answers
213
views
Optimization problem involving Multivariate Normal
I use $\phi(t)$ to describe the standard normal distribution density and $\Phi(t)$ as the normal distribution CDF and would like to prove that for all
$n\geq3$, the function:
$$h(\mu_{1},\ldots,\...
- 41
3
votes
0
answers
494
views
Maximization of a total variation distance subject to another total variation distance in Markov chain
Suppose two dependent random variables $X$ and $V$ from finite alphabets $\mathcal{V}$ and $\mathcal{X}$ with known joint and marginal distributions are given. Let $P_{XV}$ and $P_X$ and $P_V$ are the ...
- 1,109
6
votes
1
answer
375
views
Deviation bound for the maximum of the norm of Wiener process
Let $W(t)$ be an $n$-dimensional Wiener process. Denote by $\chi_n^2$ a chi-squared random variable with $n$ degrees of freedom. I have recently found the following inequality given without proof:
$$
{...
- 61
2
votes
0
answers
687
views
Placing Bounds on Correlation/Covariance Through Correlation with an Intermediate Variable
I am trying to make the most of computations that have already been performed in previous steps of an algorithm. Throughout this problem statement I am only mentioning correlation, but I think it is ...
- 21
4
votes
2
answers
1k
views
Bound on the tail of the sum of independent and identically distributed (iid) variables
This interesting question was asked at https://math.stackexchange.com/questions/231455/estimator-for-sum-of-independent-and-identically-distributed-iid-variables a while ago but got no answers. The ...
- 41
5
votes
1
answer
1k
views
Probability inequalities
Hi everyone,
I am looking for some probability inequalities for sums of unbounded random variables. I would really appreciate it if anyone can provide me some thoughts.
My problem is to find an ...
- 197
1
vote
1
answer
356
views
Statistical inequality
Let $X$ be a finite discrete variable and $X\ge0$. Is it true that
$$16\operatorname{Var}(X) \le \left[8{\mathbb E}(X) + \operatorname{Range}(X)\right]\operatorname{Range}(X)$$
where $\operatorname{...
- 95
9
votes
5
answers
1k
views
estimate the error term in CLT
Let $X_m = \frac{1}{\sqrt{m}}\sum_{k=1}^m Z_k$ where $Z_k$ are iid equally likely on $\{\pm 1\}$. Then $X_m$ convergens to $X \sim \mathcal{N}(0,1)$ in distribution by CLT.
Let $f$ be a smooth ...
- 1,839