Questions tagged [distribution-tails]
This tag is for questions relating to "tail-distribution" which essentially means how much probability is distributed over the largest values(usually) of the random variable.
194
questions
1
vote
1
answer
40
views
Tail Probabilities of a martingale difference sequence
I'm currently facing the problem, that I can neither prove nor find a counterexample for the following statement.
Let $q \in (1,2)$ and let $(D_n)_{n \in \mathbb{N}}$ be a martingale difference ...
0
votes
0
answers
19
views
uniformly bounded tail probabilities
While reading a book from the 1980's I stumbled across the term of "uniformly bounded tail probabilities".
Consider a sequence of random variables $(X_j)_{j \in \mathbb{N}}$. We shall say ...
0
votes
0
answers
19
views
Gaussian tail probability
Let $z(q)$ be the quaitle of a standard normal random variable $Z$, i.e., $z(q) = k$ when $Pr(Z\geq k) = q$. Then I would like to know why the following two results hold.
(a) If we hold $\alpha$ fixed,...
- 369
1
vote
0
answers
49
views
How to get an "average" of a distribution with no average
Modelling something where I need some sort of average time, I reached Pareto Distribution, and the PDF is
$$
R(t)=\begin{cases}\sqrt{\frac{1}{2\pi t^{3}}}, & \text{for } t > \frac{2}{\pi}\\
0 &...
- 750
1
vote
1
answer
42
views
The additive Chernoff bound for the absolute value.
I am trying to derive a generic, additive Chernoff bound for $\Pr[|X-\mu|\leq a]$ with $a>0$. By generic I mean a Chernoff bound in terms of the moment generating function instead of assuming a ...
- 902
0
votes
0
answers
9
views
tail bound on lowest eigenvalue of sample covariance of multivariate Gaussian vector
Let $X\sim N(0,C)$ be a Gaussian random vector over $R^n$ with covariance $C$ with eigenvalues $\lambda_1\ge \dots \ge \lambda_n$, and let $C':=\frac1k \sum_i^k X_i X_i^\top$, be the sample covariance ...
- 533
2
votes
0
answers
59
views
Numerical simulation of SDE with Lévy noise in Python - Overflow issue
My goal is to simulate a SDE with alpha-stable noise in Python. This is my code:
...
- 21
3
votes
0
answers
47
views
Lower Bound on the Tail of a Binomial Random Variable
Let $X \sim \operatorname{Binomial}\left(n, \frac{1-\varepsilon}{2}\right)$, for $\varepsilon\in(0, 1)$. I believe that the following anti-concentration bound holds:
$$\Pr\left(X \geq \frac{n}{2}\...
- 41
1
vote
1
answer
47
views
A gaussian tail estimation
In the proof of minmax bound for multi-arm bandits, it refers an inequality $$\frac{\exp \left(-x^{2}\right)}{x+\sqrt{x^{2}+2}} \leq \int_{x}^{\infty} \exp \left(-t^{2}\right) d t \leq \frac{\exp \...
- 21
0
votes
0
answers
7
views
Ultra light renewal theorem for heavy tailed renewal processes
I am interested in some "ultra light renewal theorem" in the following sense: We look at the renewal process
$$\mathcal R := \left\{ n: \sum_{i=1}^k R_i = n \mbox{ for some } k \right\}$$
...
- 381
2
votes
1
answer
52
views
Show $\lim_{n \to \infty} \mathbb{E} [ f(S_n) \mid S_n \geq t] \mathbb{P}(S_n \geq t) = 0$
Let $S_n$ be a sequence of positive random variables, such that the following tail bound holds for any $n$:
$$
\mathbb{P} (S_n \geq t) \leq e^{- n t} \hspace{1cm} \text{for sufficiently large $t$}
$$
...
- 31
0
votes
1
answer
37
views
Non-standard tail bound on normal distribution
I'm familiar with a "standard" bound on normal distribution in this form:
If $Z \sim \mathcal{N}(\mu, \sigma^2)$, then
$$
P(|Z - \mu| \geq t) \leq 2 \exp \left(\frac{-t^2}{2 \sigma^2} \right)...
- 141
0
votes
0
answers
56
views
Estimating $n^2$ after observing $X\sim Bin(n,p)$ and knowing $p$
Let $n\in\mathbb N$ be unknown and let $p\in (0,1]$ be known.
Suppose that we observe $X\sim Bin(n,p)$. This allows us to estimate $\widehat n= X/p$ and we can use the Chernoff inequality to bound the ...
- 421
1
vote
1
answer
44
views
Coupling for tail bounds
Let $X_1, X_2$ be two random variables such that $\mathbf{E}X_1=\mathbf{E}X_2=0$ and
$$\forall x\geq 0, \quad \mathbf{P}[X_1\geq x]\leq \mathbf{P}[X_2\geq x].$$
Can we construct a coupling $(Y_1,Y_2)$ ...
- 813
0
votes
0
answers
44
views
What is the the maximum and minimum of a sequence of $n$ random variables having Chi-squared distribution with $k$ degrees of freedom?
Say we have a sequence of $n$ random variables $[X_1,X_2,\ldots,X_n]$, identically distributed, having Chi-squared distribution with $k$ degrees of freedom. Then, what is the upper bound of $\underset{...
- 1
1
vote
1
answer
67
views
Best way to measure the tail weight of a distribution
I am trying to solve this problem and after blindly testing a dozen different distributions. I realised that I am more interested in the extreme values rather than mod/median/mean, therefore I wanted ...
- 750
0
votes
0
answers
20
views
Find size of training set based on Hoeffding bounds
I am new to statistics and I have this problem to solve which has to do with Hoeffding bounds.
My teacher provided me this theorem:
(Hoeffding bounds) Let $x_{1}, x_{2}, \ldots, x_{n}$ be independent $...
1
vote
0
answers
30
views
Concentration bound for the distribution of the difference of two random variables
If we use $\Rightarrow$ to represent convergence in distribution and suppose that $X_n \Rightarrow N(0,\sigma_1)$ and $Y_n \Rightarrow N(0,\sigma_2)$, and $X_n$ and $Y_n$ are independent, then we all ...
- 11
2
votes
0
answers
99
views
Expectation of inverse of sum of iid random variables
Description:
There is an indicator function called $I_{i}^{k}$ as follows:
\begin{align*}
\begin{split}
I_{i}^{k}= \left\{
\begin{array}{lr}
1, \; {\rm if \; the \; event \; happened\; at\; time ...
- 43
3
votes
0
answers
42
views
Tails of function and Fourier transform
I have a questions about Fourier transforms of functions in general.
Let $f$ be a function and $\phi$ its Fourier transform. If $f$ has fat tails, must $\phi$ then necessarily have thin tails? ...
- 486
4
votes
2
answers
274
views
Is there a tail bound for the sum of Bernoulli RVs where $\Pr[X_i = 1]$ is a decreasing function of $X_1, \dots, X_{i - 1}$?
Suppose I have a sequence $X_1, \dots, X_n$ of Bernoulli RVs with the property that for all $i = 1, \dots, n$, the function
$$f(x_1, \dots, x_{i - 1}) := \Pr[X_i = 1 \mid X_1 = x_1, \dots, X_{i - 1} = ...
-2
votes
1
answer
52
views
Two-tailed test: Biased coin [closed]
enter image description here
Can anyone guide me through this question?
From what I gather, I have to do a hypothesis test and get a number of consecutive tails such that I can reject H0.
H0: The coin ...
- 11
1
vote
1
answer
102
views
How to derive a Chernoff bound for the sum of integers independently chosen uniformly at random from $\{0, 1, 2\}$?
The following problem is exercise 4.12 from the first edition of Probability and Computing by Mitzenmacher and Upfal.
Consider a collection $X_1,...X_n$ of $n$ independent integers chosen
uniformly ...
- 196
0
votes
0
answers
65
views
Deriving a Chernoff bound for a casino's total return on slot machines
I'm trying to solve exercise 4.10 from the first edition of Probability and Computing by Mitzenmacher and Upfal:
A casino is testing a new class of simple slot machines. Each game,
the player puts in ...
- 196
6
votes
3
answers
261
views
Probability of more than ${3\over 4}N$ heads in $N$ flips of a coin?
What is the probability of getting more than $ \frac { 3 N } 4 $ heads in $ N $ flips of coins?
I know we need to use binomial distribution formula for this and sum it from $ N = \frac { 3 N } 4 $ to $...
0
votes
1
answer
23
views
What kind of function can model a distribution that is strictly positive and skewed right?
Start with $\text{global minimum}=0, \text{target}=:\text{mean}=\bar{x}, \text{global maximum}→\text{infinity}$ corresponding to a smooth continuous probability distribution of $x$.
Now suppose that ...
- 107
0
votes
0
answers
20
views
Solving for bernoulli parameter with respect to binomial distribution's chernoff bounds
Suppose we have i.i.d $X_i \sim Ber(p)$. We have a binomial r.v. $X = \Sigma_i^n X_i$, $X \sim Bin(n,p)$.
The chernoff bound for this binomial distribution is:
$$
P(X < k) \leq e^{-n D(k/n||p)} = \...
- 555
2
votes
2
answers
86
views
How to show that for any random variable $X$ and $t > 0$, $\Pr(X - E[X] \geq t\sigma[X]) \leq \frac{1}{1 + t^2}$? [duplicate]
The question in the title is from exercise 3.18 in the first edition of Mitzenmacher and Upfal's Probability and Computing. It's essentially asking to prove a bound slightly tighter than Chebyshev's ...
- 196
0
votes
0
answers
34
views
Anti concentration of negatively correlated random variables
Let $X_1,\cdots,X_n$ are binary random variables. We say that they are negatively correlated if for any $I \subset \{1,\cdots,n\}$ and $b\in \{0,1\}$ we have
\begin{align*}
Pr\big[\forall i\in I: X_i =...
- 718
0
votes
1
answer
69
views
An interesting Bound for Binomial Distribution
I have seen the following bound somewhere, but could not find it.
Let $n$ be an non negative integer and $X \sim Bin(n,\frac{1}{2})$. Show that there exists an abosolute constant $c > 0$, such ...
- 718
1
vote
0
answers
55
views
existence of sequence $\{a_n\}$ that make the tail probability decrease at a certain rate
This appeared in example (b), Section 8.8 of An Introduction to Probability Theory and Its Applications, Vol 2, by Feller.
Let $F(x)$ be the cumulative distribution function of some random variable.
...
- 164
1
vote
0
answers
38
views
Sample size required to hit at least a constant fraction of a set.
I have been trying to figure out the following problem for quite some time but have not succedded. May be I am missing something very obvious.
Let $M$ be and integer and define $[M] = \{1,\cdots,M\}$. ...
- 718
0
votes
1
answer
53
views
Tails of a Conditional Normal Distribution
Let $X \sim N (0, \sigma^2)$ and $Y ~ \sim N(0, 1 + \sigma^2)$ be independent. I'm trying to understand and visualize the function
$$f(x) := P(X > Y + x | X > x),$$
for large $x$ (say, $x > 3 ...
1
vote
1
answer
36
views
Concentration / convergence of a gaussian random multivariate polynomial: computing mean and variance
Let $m,d \to \infty$ with $m/d \to \rho \in (0,\infty)$. Let $z_1,\ldots,z_m$ be iid from $N(0,I_d)$ and let $A$ and $B$ be $d \times d$ be deterministic psd matrices. Define the random variable $S \...
- 8,309
3
votes
1
answer
77
views
Distribution of absolute value sum of independent normal random variables
Consider $g\in \mathbb{R}^n$ whose entries are i.i.d. normal random variables, how can I get an estimate of the upper bound of
$$ P(X_s \geq Y_{n-s}) \leq \, ? $$
where $X_s = \sum_{i=1}^s |g_i|$ and $...
- 489
4
votes
1
answer
66
views
The smallest choice of $k$ so that $\sum_{i=0}^k {n \choose i} p^i (1-p)^{n-i}$ is lower bounded by a constant
Let $p \in [0,1/2)$ and $\delta \in [0,1/2)$ be fixed real numbers, and let $n$ be a positive-integer valued variable.
Let $k=k(n)$ be the smallest integer for which $\delta \leq \sum_{i=0}^k {n \...
- 433
0
votes
0
answers
26
views
Occuppation time bound on supermartingale
I want to ask about the bound on the behavior of such a supermartingale $\{X_t\}$, where for each $t$, $X_t\in[0,1]$.
Moreover, there exists $0<a_1<1$ such that for each $t$, it is satisfied ...
- 1
0
votes
0
answers
49
views
How this limit prove the Frechet Distribution has Heavy Tails?
First, we start from the GEV-distribution function:
Theorem 1.1.3 (Fisher and Tippett (1928), Gnedenko (1943)) The class of extreme value fistributions is $G_\gamma(ax+b)$ with $a>0$, $b$ real, ...
- 1
1
vote
0
answers
25
views
Find $\lim_{x\uparrow 1}\mathbb{P}(F_Y(Y)>x|F_X(X)>x)$ where $X,Y$ poisson
Let $X=Y_1+N,Y=Y_2+N$ where $N\sim \text{pois}(\lambda), Y_1\sim \text{pois}(\lambda_1), Y_2\sim \text{pois}(\lambda_2)$ and $N,Y_1,Y_2$ are independent. I'm asked to find $$\lim_{x\uparrow 1}\mathbb{...
user927220
1
vote
0
answers
62
views
Linear mean excess function implies a generalized pareto distribution
I am trying to do the following prove: Let $X$ be a non-negative random variable. Show that if for some
$a \in (-1,\infty), b>0$, it holds that the mean excess function $\epsilon_x(t)$ is:
$$\...
- 21
2
votes
2
answers
175
views
Tail Probabilities of Multi-Variate Normal
For a standard normal random variable $X \sim \mathcal{N}(0,1)$, we have the simple upper-tail bound of
$$\mathbb{P} (X > x) \leq \frac{1}{x \sqrt{2\pi}} e^{-x^2 / 2}$$
and thus from this we can ...
- 6,208
1
vote
1
answer
33
views
Is the following tail bound on the Binomial distribution accurate?
The Poisson distribution has the following tail-bound:
Given $X \leftarrow Po(\lambda)$, for any $t \geq 1$
$Pr(X \geq t) \leq (\frac{e \lambda}{t})^t$
(For $t > \lambda$, this follows directly ...
- 111
1
vote
0
answers
25
views
Are there any known Chernoff/Hoeffding bounds for the case of "almost independence"?
The usual statement of a Hoeffding bound (e.g. https://sites.math.washington.edu/~morrow/335_17/ineq.pdf) requires independent random variables.
My question is: Do there exist bounds similar to ...
- 11
0
votes
1
answer
49
views
product of limits proof
I'm hoping someone might have a hint as to how to prove/disprove the follow claim:
Claim: Let $f,g$ be real valued functions. If $\lim_{x\rightarrow\infty}f(x)g(x)\text{ exists}\space\text{and}\space\...
- 79
1
vote
0
answers
125
views
Proof check: Using Hanson-Wright inequality to concentrate a quadratic form $y^\top A y$ where both $y$ and $A$ are random but independent
Disclaimer. I don't know if this is the right venue to ask this. I'm working out a bigger proof, in a critical step, I'ved used an argument I'm not quite sure about.
Let $n$ be a large positive ...
- 8,309
1
vote
0
answers
16
views
tail of a 2D normal distribution
I have a 2D normal distribution representing a laser profile. The width of the beam is expressed as the diameter that encloses 1 - 1/e^2 ~ 82%. This is a standard way of describing beam width (just 1/...
- 113
1
vote
0
answers
112
views
How does Taleb's Kappa metric relate fat-tailed distributions to Gaussians?
In Chapter 8 of Nassim Nicholas Taleb's Statistical Consequences of Fat Tails, Taleb defines a metric $\kappa$. The relevant definitions are as follows:
$$\mathbb{M}(n)=\mathbb{E}\left(\left\lvert\...
1
vote
1
answer
107
views
Does the standard normal distribution have a heavy right tail?
I read about heavy right tail and I saw that a distribution is said to have a heavy right tail if its tail probabilities vanish slower than any exponential
$$\forall 𝑡>0: \lim_{x\to\infty}e^{tx}𝑃...
- 15
0
votes
1
answer
53
views
Show $Z_n= \frac{X_1 +\cdots + X_n}{\sqrt{n}}$ is uniformly sub-gaussian.
As described above I would like to establish a tail bound for the $Z_n$, using that $X$ is bounded with zero mean and unit variance and $X_n$ are iid copies of $X$. So namely I would like to show that ...
1
vote
0
answers
36
views
Upper bound on the right tail of $bin(n,p)$ evaluated at $k<np$
Consider a binomial RV $N \sim bin(n,p)$.
I am interested in finding an $\textbf{upper bound}$ to the complementary CDF given by:
$\hspace{2.5in}P(N\geq k)$ where $k=np-m$ and $m \in \mathbb{Z}^{+}$.
...
- 55