Questions tagged [large-deviations]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
0 votes
1 answer
70 views

LDP for Marchenko Pastur with k/n tending to 0

I am interested in the determinant of $W = X * X'$, where $X \in \mathbb{R}^{k \times n}$ is a matrix with each row drawn IID from some sub-Gaussian distribution on $\mathbb{R}^{n}$. (I am aware of ...
user avatar
  • 405
2 votes
1 answer
66 views

Equivalent of a local limit theorem in the large deviation region and asymptotics of a convolution operator

Let $\{X_i \}_{i \in \mathbb{N}}$ be a sequence of i.i.d. random variables satisfying $\mathbb{E} X_1 = 0$ and $\mathbb{E} X_1 ^2 < \infty$. Assume that $\{S_n  \}_{n \in \mathbb{N}}$ is a non-...
user avatar
  • 653
1 vote
1 answer
189 views

A large noise limit

Let $f: [0, 1] \to \mathbb R$ be a bounded, continuous function, and $W$ a standard Brownian motion. Denote $Y := \int_0^1 f(t) \, dW_t$. For each $\varepsilon > 0$, consider the conditioned random ...
user avatar
  • 1,149
0 votes
0 answers
34 views

Prove the statistical rate lower bound of a given complicated statistics

Given a i.i.d. sequence of random variables $\{Z_i\}_{i=1}^n$ who has mean zero. Two i.i.d. sequence of random vectors $\{X_i\}_{i=1}^n$, $\{Y_i\}_{i=1}^n$ who have the same covariance matrix $\Sigma$....
user avatar
1 vote
1 answer
86 views

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

Let $X_{1}, X_{2}, \ldots, X_{n}$ be IID random variables with mean $\mu$ and variance $\sigma^2$. Let $S_n=\sum_i^{n}X_i.$ Let $T\gg1$ and define $\tau=T-S_n$ where $n$ satisfies the following ...
user avatar
  • 125
1 vote
1 answer
91 views

Large deviation for empirical median

I found this exercise while reading some notes on Large Deviation Principle. This exercise is at the end of the very first chapter, including Cramer's Theorem and essentially nothing more (no Sanov ...
user avatar
  • 395
2 votes
2 answers
108 views

Determine the affine envelope of a random process's MGF

Suppose that a stationary random process $S(t)$ can be characterized as the figure below, which for most of the time is a straight line $S(t)=c\cdot t$, but occasionally would "stall" for a ...
user avatar
  • 165
3 votes
0 answers
46 views

References on precise Large Deviations Principle/Laplace method for binomial sum

I am looking for an estimate of the following sum/expectation: \begin{align*}%$ J_n & = \mathbb{E}\left( e^{n f(X_n) + \log(n) g(X_n) + h(X_n)} \right) \\ & = \frac{1}{2^n} \sum_{k = 0}^n {...
user avatar
  • 549
2 votes
1 answer
67 views

Concentration Inequality for Bounding Lipschitz Empirical Lass

Let $(\Omega,\mathcal{F},\mathbb{P})$ be a probability space, $(X_n:\Omega\rightarrow \mathbb{R}^m)_n$ be a sequence of i.i.d. random variables and let $L:\mathbb{R}^m\rightarrow [0,\infty)$ be ...
user avatar
1 vote
0 answers
60 views

Problem on definition of large deviation principle

As in many classic textbooks, the definition of large deviation principle is as follows: $\{\mu_n\}$ has LDP with speed $a_n$ and rate $I(x)$ if the following holds for any measurable $A$: $$\limsup\...
user avatar
  • 433
4 votes
1 answer
153 views

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

Let $X_1,X_2,X_3,...$ be iid non-negative random variables with $E[X_i]=\infty$. I am looking for references on the growth in $n$ of the empirical average under assumptions on $X_1.,..,X_n$. A more ...
user avatar
  • 930
0 votes
0 answers
226 views

sub-exponential type upper bound on the Poisson probability

I posted this question on Math Stack Exchange, though I'm not satisfied with the answer I received. Question: For a Poisson random variable $Z$ with the parameter $\lambda,\,$ what would be a good ...
user avatar
  • 11
1 vote
1 answer
187 views

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

I posted the following question in a comment on CDF of a log-concave discrete random variable. Since it is not related to my main question, I thought of reposting it as separate post. Question: Let $X ...
user avatar
0 votes
1 answer
121 views

CDF of a log-concave discrete random variable

In the continuous setting, it's known that if a density function is log-concave , then its CDF is also log-concave. My questions: What can we say about this in the discrete setting?. For ex: Is the ...
user avatar
3 votes
0 answers
53 views

Existence, Uniqueness, and "ODE Characterization" of Minimizers for Variational Functionals from Large Deviations

A [classical result][1] of E. Lieb is that the functional $$\mathcal E(\phi):=\int_{\mathbb R^3}|\nabla\phi(x)|^2~dx-\int_{(\mathbb R^3)^2}\frac{|\phi(x)|^2|\phi(y)|^2}{|x-y|}~dx~dy$$ for $\phi\in W^1(...
user avatar
  • 831
4 votes
3 answers
297 views

Sample average L1 convergence speed

Say $X_1, \cdots, X_n$ are i.i.d random variables with mean zero, let $S_n = \sum_{i=1}^n X_i$, we know by SLLN $$\frac{S_n}{n}\rightarrow 0\text{ a.s}$$ We could further know that the sequence of ...
user avatar
  • 173
7 votes
1 answer
289 views

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

This is a cross-post to a yet unanswered question in Math StackExchange https://math.stackexchange.com/questions/3906767/probability-of-a-deviation-when-jensen-s-inequality-is-almost-tight Let $X>0$...
user avatar
  • 173
9 votes
1 answer
265 views

Concentration inequalities for very rare events on a multiplicative scale

Let $E_1, \dots, E_N$ be independent events, each of probability $p$, where $p$ is very close to $0$. Let $A_N = \frac{1}{N} ( 1_{E_1} + \dots + 1_{E_N} )$ be the proportion of the events $E_i$ that ...
user avatar
  • 251
0 votes
1 answer
136 views

Large deviation for Brownian occupation time

I am asking for reference about the large deviation principle (LDP) for the occupation time of a Brownian motion/bridge. Let $f:\mathbb{R} \to \mathbb{R}$ be smooth and compactly supported. My ...
user avatar
  • 103
1 vote
0 answers
77 views

Large deviations estimate for arbitrary continuous function

Fix $\epsilon>0$ and let $(\Omega,\mathcal{F},\mathcal{F}_t,\mathbb{P})$ be a stochastic base, and let $f:\mathbb{R}^n\to \mathbb{R}^n$ be a continous function with $f(0)=0$. Is there a family of ...
user avatar
0 votes
0 answers
69 views

Comparing Euclidean norm of two normal vectors

Let $X_i$ ($i = 1,2$) be two random vectors in $\mathbb R^n$, with normal distribution with scalar covariance matrix $\sigma_i^2$ and center $\mu_i$ (in my case, $n = 2$). Is there a way to estimate ...
user avatar
0 votes
1 answer
93 views

Tail bounds for the absolute difference of a coupled pair of sub-Gaussian random variables

Let $P$ and $Q$ are sub-Gaussian distributions on $\mathbb R$, and $(X,X')$ be a coupling of $P$ and $Q$, i.e $(X,X') \sim \pi$ for some distribution on $\mathbb R^2$ with marginals $P$ and $Q$. ...
user avatar
  • 5,580
0 votes
1 answer
61 views

Joint typicality of sequences

I know that for two i.i.d distributions $P$ and $Q$ the probability that $Q$ will produce a length $n$ sequence that is $\epsilon$-typical according to $P$ is bounded by $$Q(T_{P,\epsilon})\leq e^{-nD(...
user avatar
  • 451
2 votes
2 answers
237 views

Anti-concentration inequalities: lower bound on realized second moment

Let $X:(\Omega,\Sigma)\rightarrow (\mathbb{R}^d;\mathbb{B}(\mathbb{R}^d))$ be a Borel-measurable random vector. What are some general classes of such random vector for which one can give a "lower ...
user avatar
0 votes
0 answers
46 views

Probabilistic Approximation of non-linear Dynamical System by Diffusion Process

Setting Suppose I have a discrete dynamical system given by: $$ X^{n+1} = f(X^{n}) \qquad X^0 =x , $$ where $f$ is some diffeomorphism from $\mathbb{R}^{d}$ to itself, and some $x \in \mathbb{R}^d$. ...
user avatar
1 vote
0 answers
60 views

Large Deviations Principle for First Exit time of a Diffusion Process

Let $b:\mathbb{R}^d\rightarrow \mathbb{R}^d$ be a smooth Lipschitz function, $x \in \mathbb{R}^d$, $\sigma >0$, and consider the solution to the SDE $X_t^x$ defined by $$ dX_t^x = b(X_t^x)dt + \...
user avatar
0 votes
1 answer
96 views

Bound for Large deviations of sums of independent (not identical) variables

I am working with a sum of variables $X_i$; they are all independent, but not identically distributed. For any $i$, I can show the bound $$\Lambda^*_{X_i}(t) := \sup_t \langle t, x \rangle - \Lambda_X(...
user avatar
  • 405
2 votes
0 answers
129 views

Reference: hitting time of Gaussian process

Let $X_t$ be an OU process and $Y_t$ be the Gaussian process defined by $$ Y_t = y+\int_0^t X_s ds + W_t, $$ for some Brownian motion independent of $X_t$. Let $y,a>0$; is there a large deviation ...
user avatar
5 votes
1 answer
246 views

Bounding the sensitivity of a posterior mean to changes in a single data point

There is a real-valued random variable $R$. Define a finite set of random variables ("data points") $$X_i = R + Z_i \; \text{for } i\in\{1,\ldots,n\},$$ where $Z_i$ are identically and independently ...
user avatar
  • 1,058
6 votes
3 answers
342 views

Large deviations for discrete uniform distribution

(Not sure if this belongs on stack-exchange or overflow; let me know if I should switch it). Given a sum of $n$ IID random variables $\{X_i\}_{i=1}^n$, each uniform on the integers $0,1,...,r$ for ...
user avatar
  • 405
4 votes
1 answer
163 views

Local central limit theorem far from the center

Let $X_i$ be a sequence of iid random variables, $E [X] = 0$, $E [X^2] = 1$ and $E [|X|^k] < \infty$ for some $k \ge 3$. Classical local CLT says that the density function $f_n$ of $\frac1{\sqrt n}...
user avatar
2 votes
1 answer
209 views

Estimating probability that a large sum of i.i.d variables is positive

Let $X$ and $Y$ be i.i.d. random variables with exponential distribution with mean $1$, and let $Z=(X-1)(Y-X)$. Let $Z_1,...,Z_n$ are i.i.d. copies of $Z$, and let $f(n)=P[\sum_{i=1}^n Z_i > 0]$. ...
user avatar
  • 693
1 vote
0 answers
85 views

Sanov-type finite-sample bound on $KL(P\|\hat{P}_n)$

Let $P$ be a distribution on an alphabet of size $k$ and let $\hat{P}_n$ be an empirical version of $P$ via $n$ i.i.d samples $a_1,\ldots,a_n \sim P$, i.e $\hat{P}_n := (1/n)\sum_{i=1}^n\delta_{a_i}$. ...
user avatar
  • 5,580
4 votes
1 answer
98 views

Large Deviations for Self-Normalized Sums

I am trying to understand the main result (Theorem 1.1) in this paper by Shao, which gives a large deviation bound for the self-normalized sum of iid variables $$ \frac{\sum X_i}{\sqrt{n}\sqrt{\sum ...
user avatar
  • 43
2 votes
1 answer
309 views

Large deviation of random walk

1) Let $\{X_i\}_{i=1}^n$ be i.i.d. such that $\Pr(X_i=1 )=1-\Pr(X_i=-1)=p$. Define the random walk $$ S_i = \sum_{j=1}^iX_j $$ for $i=1,2,\ldots,n$. I am looking for "good" exponential upper bounds ...
user avatar
  • 31
5 votes
4 answers
277 views

Concentration of closed random walks

Consider a random walk $S_n=\sum_{i=1}^n X_i$ where $P(X_i=+1)=P(X_i=-1)=1/2$ with $n$ large. By Chernoff's bound we know that, for example, $\sum_{i=1}^{n/2} X_i=O(\sqrt{n})$ with high probability. ...
user avatar
  • 430
3 votes
0 answers
159 views

Asymptotic behaviour of principal eigenfunctions and large deviations

Dear Math Overflowers, I am currently interested in a particular problem involving Large Deviations. I am only going to talk about the PDE side of the problem, but I'll be happy to provide more ...
user avatar
5 votes
0 answers
1k views

Asymptotic behavior of row sums in 2-d array of random variables

Set-up. Let $f : \mathbb{N} \to \mathbb{N}$ be increasing. For each $m \in [0,1]$, consider an infinite two-dimensional array of random variables, where row $n$ has $f(n)$ variables: $B^m_{1,1}$ $B^...
user avatar
1 vote
0 answers
24 views

Large Deviations Rate of Convergence and Robbins Monro

I am looking for a result/paper (if there is any) on the large deviations rate of convergence of the Robbins-Monro (RM) algorithm. Specifically, given $X_k \rightarrow X$ a.s. in the RM algorithm, I ...
user avatar
  • 21
2 votes
0 answers
180 views

Schilder's theorem for brownian bridges

I am really not a probabilist and I apologize if my question is too naive or not appropriate, please feel free to migrate to SE. A bit of context: usually, Schilder's theorem tells us that the ...
user avatar
2 votes
1 answer
126 views

Tail condition (Varadhan's lemma)

I would like your help with the following tail condition, which arises in the theory of large deviations. Let $P(\mathbb{R}^{d})$ the space of probability measures on $\mathbb{R}^{d}$, $ G:P(\mathbb{...
user avatar
  • 165
3 votes
2 answers
315 views

Large deviation upper bound for Chi-squared random variable

Let $X \sim \chi^2_n$ random variable. I am looking for a large deviation upper bound for $X$. The answer here, says that Since you said that you're looking for an upper bound, it should also be ...
user avatar
3 votes
1 answer
162 views

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

Let $P$ be a probability measure and $f$ be some probability density function (not necessarily related to $P$). Consider the function $$ L(X_1,\ldots,X_n) =\frac1n\sum_{i=1}^n\log f(X_i), \quad X_i\...
user avatar
  • 650
2 votes
2 answers
222 views

Fast Algorithms for sum of independent random variables

CLT implies the sum of n i.i.d random variables,after property normalized converge to a Normal distribution as n goes to infinity. Furthermore, Linderberg's condition points out not necessarily ...
user avatar
2 votes
1 answer
94 views

Family of large deviation principles

The following question may be a bit imprecise in its formulation, I guess however the problem I have in mind is clear. Although to me it looks like a fairly standard question, I couldn't find any ...
user avatar
  • 279
7 votes
0 answers
611 views

Calculate the expectation of the maximum of averaged random walks

Let $X_1, X_2, \ldots$ be iid random variables with bounded second moment. The question is to calculate the exact value of $$\mathbb{E} \max_{1 \le j < \infty} \frac{X_1 + \cdots + X_j}{j}.$$ Is ...
user avatar
  • 623
3 votes
1 answer
144 views

Large deviations for integrands

I am a physicist caught in the following situation: I have two probability measures $\mathbb{P}_1$ and $\mathbb{P}_2$ and have to deal with the following integral where $X_i$ are random iid: $$\int_{...
user avatar
2 votes
0 answers
116 views

Modified Wigner semicircle law

The Wigner semicircle law states that for a random GOE-matrix $M^N \in \mathbb{R}^{N \times N}$ in the $N \rightarrow \infty$ limit for any $f \in C^b(\mathbb{R})$ $$\lim_{N \rightarrow \infty}\frac{...
user avatar
2 votes
0 answers
156 views

Most probable path for stochastic Hamiltonian systems

It is known that for a real valued stochastic process $X_t$ satisfying $$ d X_t = b(X_t) d t + \sigma d W_t $$ where $W$ is real valued Wiener process, the equation for the most probable path from ...
user avatar
  • 181
1 vote
0 answers
72 views

Reference: Varadhan's lemma for Finsler Geometry?

Is there a version of Varadhan's lemma for heat-kernels on Finsler manifolds? I expect this to exist but I cannot seem to find any papers on the topic. References would be greatly appreciated.
user avatar