7
votes

Accepted

### Concentration inequalities for very rare events on a multiplicative scale

Let $n:=N$. Let us show that for all natural $n$ and all $p\in(0,1)$
$$P(A_n>\sqrt p)\le\frac{\sqrt p+p}{1+p},\tag{1}$$
so that $P(A_n>\sqrt p)\to0$ whenever $p\downarrow0$.
Consider first the ...

7
votes

Accepted

### Endpoint of Brownian motion conditional on high maxima

$\newcommand{\ep}{\varepsilon}\newcommand{\vpi}{\varphi}\newcommand{\de}{\delta}$Yes, this is true:
By the reflection principle (see e.g. Proposition 2, for $M:=\max_{0\le t\le1}W_t$,
\begin{equation}
...

6
votes

Accepted

### Large deviations: Growth of empirical average of iid non-negative random varialbes with infinite expectations?

Here it is more convenient to consider the order of magnitude of $S_n:=\sum_1^n X_i$, rather than that of $S_n/n$.
Take any real $c>0$. Let $x:=cn^{1/p}$, $Y_i:=X_i\,1(X_i<x)$, $T_n:=\sum_1^n ...

6
votes

Accepted

### Concentration Inequality for Bounding Lipschitz Empirical Lass

Your inequality is trivial and useless as written. On its left-hand side we have a probability which is $\le1$ and goes to $0$ as $t\to\infty$, whereas on the right-hand side we have an expression ...

6
votes

### Endpoint of Brownian motion conditional on high maxima

Iosif Pinelis has already posted an answer, but here is an alternate answer communicated to me by Yuval Peres on a different website. Any typoes/mistakes are most definitely mine.
Write
$$\tau = \text{...

5
votes

### Large deviation/concentration inequality for submartingale

This looks like a weak law of large numbers, and in fact a strong law holds: I claim that $\liminf_{t \to \infty} \frac{S_t}{t} \ge \Delta$ almost surely, which implies the desired result.
The key is ...

5
votes

Accepted

### Lower bound on sum of independent heavy-tailed random variables

Certainly. All you need is $EX^2=+\infty$. Then the characteristic function $f_X(t)$ satisfies $\lim_{t\to 0}\frac{1-|f(t)|}{t^2}=+\infty$, so for every finite interval $I\subset \mathbb R$, we have $\...

4
votes

### Large deviations for discrete uniform distribution

As Iosif Pinelis mentioned this is quite standard in large deviations theory so let me explain a bit the idea of the theorem he quote.
Let $Y$ a random variable defined as $\mathbb{P}(Y=y)=\frac{1}{Z(...

4
votes

Accepted

### Large deviations for discrete uniform distribution

The answer to your question is contained in the following local limit theorem for large deviations, due to V. Petrov, Theorem 6:
Suppose that $X,X_1,X_2,\dots$ are iid random variables such that $...

4
votes

Accepted

### A large noise limit

Let $\varphi$ be the standard normal density. Since
$P[W_1 \ge x] =(1+o(1))\varphi(x)/x$ as $ x \to \infty$ by [1], we obtain for fixed $\delta>0$ that as $\epsilon \to 0$,
$$P[W_1 \ge \epsilon^{-...

3
votes

### Sample average L1 convergence speed

If (say) $s:=\sqrt{EX_1^2}<\infty$ then, by the central limit theorem, $Z_n:=S_n/n^{1/2}\to sZ\sim N(0,s^2)$ (as $n\to\infty$ in distribution). Also, $EZ_n^2=s^2<\infty$ and hence the sequence $(...

3
votes

Accepted

### Probability of a deviation when Jensen’s inequality is almost tight

$\newcommand\ep\epsilon $Let $u:=\eta>0$, so that the probability in question is $P(\ln X>E\ln X+u)$. Note that this probability will not change if we replace there $X$ by $tX$ for any real $t&...

3
votes

Accepted

### Large deviation for Brownian occupation time

This is precisely the Donsker-Varadhan LDP, coupled with an application of the contraction principle. Namely, the rate function is
$$I(x)=\inf\{ J(\mu): \int f d\mu =x\}$$
where $J$ is the Donsker-...

3
votes

Accepted

### Upper bound for $P(X \geq x)$, where $X \sim \operatorname{Pois}(\lambda)$

$\newcommand\Ga\Gamma\newcommand\Z{\mathbb Z}\DeclareMathOperator\Pois{Pois}$Let $t\mathrel{:=}\lambda$ and $k\mathrel{:=}x\in\Z\cap[0,t)$. Then for $X_t\sim \Pois(t)$ we have
$$P(X_t\ge k)=1-\frac{\...

3
votes

Accepted

### Local central limit theorem far from the center

The asymptotics of the ratio
$$r_n(x,y):=\frac1{f_n(\sqrt nx)}f_{n-1}\left(\frac{nx + y}{\sqrt{n-1}}\right)
$$
will very much depend on the tail asymptotics of the density (say $f$) of $X$.
E.g., ...

3
votes

### Large deviation of random walk

Let's assume that $p<1/2$, Otherwise the probability in question does not decay exponentially.
Then
$$ \max_{{1\leq i\leq n}}\Pr\left(S_i>\max_{1\leq i'\leq n}-S_{i'}\right)=
\Pr\left(S_1>\...

3
votes

### Large deviation upper bound for Chi-squared random variable

See B. Laurent and P.Massart, Adaptive estimation of a quadratic functional by model selection, Ann. Stat., 28 (2000) 1302--1338.
Equations (4.3) and (4.4) say that for any $x\gt 0$:
$$P(X_n \ge n + ...

3
votes

Accepted

### Large deviation/concentration inequality for submartingale

For convenience, suppose that $D_0 = 0$ and $M_0=0$. The lower bound $D_{t+1} - D_t \ge \Delta$ implies that $D_{t} \ge \Delta t$ a.s., i.e., $D_t$ grows at least linearly with $t$. Thus, for any $t \...

3
votes

Accepted

### Probability distribution of $\sum_i^n X_i - T$ where $\sum_i^nX_i <T<\sum_i^{n+1} X_i $

What you describe is well known as a renewal process and the random variable $\tau$ is known as deficit (or age or backward recurremce time) at time $T$. The distribution of $\tau$ is well known. You ...

3
votes

### Mutual information in large deviation theory

There's a few results. First of all there is the classical Sanov's Theorem.
One other result is about Gaussian measures.
For a centered Gaussian measure $\mu_0$ on Banach space $\mathcal B$ we can ...

2
votes

Accepted

### Family of large deviation principles

First, to see why this is not enough, suppose all variable involved take value in some compact interval. Suppose the sequence $X_n$ satisfies the LDP, with rate function $J(x)$, and let $X_n^\epsilon=...

2
votes

Accepted

### Large deviations for integrands

It all depends on the shape of $P_2$ and on the assumptions you put on $X_i$. In what follows I'll assume that $\Lambda(\lambda)=\log E_1 e^{\lambda X_1}$ is finite
for all $\lambda$. I will also ...

2
votes

### Concentration inequalities specialized for log-likelihood / log-density functions

Assume $X$ has density $f$ and put $Y=\log f(X)$.
Then, to compute the moment-generating function of $Y$, we write
$$ E e^{\lambda Y}
=E e^{\lambda\log f(X)}
=E[f(X)^{\lambda}]
=\int_{-\infty}^\infty ...

2
votes

Accepted

### Concentration of closed random walks

I believe the following coupling argument shows that (in particular) if we specify that the random walk ends at 0 then halfway through the walk the probability that we're within distance $\lambda$ of ...

2
votes

### Concentration of closed random walks

Why don't you use central limit theorem?
By central limit theorem,
$$ \mathcal{L}\left( \frac{S_{\frac{n}{2}}}{ \sqrt{n}} , \frac{S_{n}}{ \sqrt{n}} \right) \xrightarrow{ n \rightarrow \infty} \...

2
votes

Accepted

### Anti-concentration inequalities: lower bound on realized second moment

Suppose e.g. that $X=X_1+\dots+X_n$, where the $X_i$' are independent zero-mean random vectors with $\|X_i\|\le1$ for all $i$. Then the Hoeffding--Azuma inequality (see e.g. Wikipedia) yields
$$P(\|X\|...

2
votes

### Sample average L1 convergence speed

Theorem 1 (Hsu and Robbins [HR])
Let $X_1,X_2,\ldots$ be i.i.d. random variables with finite mean $\mu$ and
finite variance. Then for all $\epsilon>0$,
$$
\sum_{n=1}^\infty P\bigl(|S_n-n\mu|\ge n \...

2
votes

### Concentration of minimum Hamming distance between $N$ points sampled iid from uniform distribution on $n$-dim hypercube $\{0,1\}^n$

A trivial lower bound is $$p_{N,n,\gamma} \geq 1 - \binom{N}{2} \mathbb P ( d_H (x_1,x_2)< \gamma n) \geq 1 - \binom{N}{2} ( \gamma^{-\gamma} (1-\gamma)^{-(1-\gamma) } 2^{-1} ) ^n $$ with the ...

1
vote

Accepted

### CDF of a log-concave discrete random variable

Indeed, if the probability mass function of an integer-valued random variable is log concave as a function on $\mathbb Z$, then the corresponding cdf is also log concave as a function on $\mathbb Z$.
...

1
vote

Accepted

### Sample average L1 convergence speed

$\newcommand{\ep}{\epsilon}$Somehow, I have only now recalled about Latala's inequalities for moments of the sums of positive independent random variables (r.v.'s), which, in particular, allow one to ...

Only top scored, non community-wiki answers of a minimum length are eligible

#### Related Tags

large-deviations × 74pr.probability × 62

stochastic-processes × 19

probability-distributions × 13

measure-concentration × 12

st.statistics × 10

reference-request × 9

stochastic-calculus × 6

co.combinatorics × 4

stochastic-differential-equations × 4

brownian-motion × 4

gaussian × 4

random-matrices × 3

limits-and-convergence × 3

it.information-theory × 3

random-walks × 3

calculus-of-variations × 2

statistical-physics × 2

lower-bounds × 2

fa.functional-analysis × 1

dg.differential-geometry × 1

real-analysis × 1

ap.analysis-of-pdes × 1

ca.classical-analysis-and-odes × 1

riemannian-geometry × 1