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.

Filter by
Sorted by
Tagged with
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 ...
user avatar
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 ...
user avatar
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,...
user avatar
  • 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 &...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
  • 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: ...
user avatar
  • 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}\...
user avatar
  • 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 \...
user avatar
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\}$$ ...
user avatar
  • 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$} $$ ...
user avatar
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)...
user avatar
  • 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 ...
user avatar
  • 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)$ ...
user avatar
  • 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{...
user avatar
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 ...
user avatar
  • 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 $...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
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? ...
user avatar
  • 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} = ...
user avatar
-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 ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
  • 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 $...
user avatar
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 ...
user avatar
  • 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)} = \...
user avatar
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 ...
user avatar
  • 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 =...
user avatar
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 ...
user avatar
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. ...
user avatar
  • 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\}$. ...
user avatar
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 ...
user avatar
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 \...
user avatar
  • 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 $...
user avatar
  • 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 \...
user avatar
  • 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 ...
user avatar
  • 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, ...
user avatar
  • 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{...
user avatar
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: $$\...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
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 ...
user avatar
  • 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\...
user avatar
  • 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 ...
user avatar
  • 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/...
user avatar
  • 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\...
user avatar
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}𝑃...
user avatar
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 ...
user avatar
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}^{+}$. ...
user avatar