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 ...
- 128k
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}
...
- 128k
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 ...
- 128k
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 ...
- 128k
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{...
- 6,155
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 ...
- 29.7k
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 $\...
- 61.9k
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,361
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 $...
- 128k
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^{-...
- 14.2k
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 $(...
- 128k
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&...
- 128k
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-...
- 7,514
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{\...
- 128k
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., ...
- 128k
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>\...
- 14.2k
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 + ...
- 37.7k
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 \...
- 6,045
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 ...
- 2,101
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 ...
- 1,904
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=...
- 7,514
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 ...
- 7,514
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 ...
- 6,541
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 ...
- 470
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} \...
- 406
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\|...
- 128k
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 \...
- 14.2k
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 ...
- 148k
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$.
...
- 128k
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 ...
- 128k
Only top scored, non community-wiki answers of a minimum length are eligible