Questions tagged [large-deviations]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
0 votes
0 answers
28 views

Moment generating function for product states

In the sequel $B=M_\ell(\mathbb{C})$. For $M\in\mathbb{N}$ fixed and $N\geq M$ I consider the symmetrizer $\pi_{M,N}(x_M)\in B^{\otimes N}$, which is the symmetrized tensor product of $a_1$,...,$a_M$ ...
Kris's user avatar
  • 63
0 votes
0 answers
37 views

Weak convergence of Gibbs measures with converging energy functions

Let $H$ be a continuous energy function defined on a compact subset $A\subset \mathbf{R}^n$ and let $Q$ be a fixed probability measure on $A$. For each $\theta>0$, define the probability ...
John's user avatar
  • 483
1 vote
0 answers
42 views

From large deviations to finite time probability tails

Cross-Post from Math.SE Let $(B_t)$ be a standard $d$-dimensional Brownian motion. It is well-known that $$\mathbb P(\sup_{s\in[0,t]}|B_s|\ge \alpha) \le 4de^{-\alpha^2/2dt}.$$ One possibility to ...
Benjamin's user avatar
  • 235
0 votes
0 answers
63 views

On the asymptotic behaviour of the kernel of a Toeplitz operator

Consider the following Berezin Topelitz operator on the 2-sphere: $$Q_N(f)=\frac{N+1}{4\pi}\int_{\mathbb{S}^2}d\Omega \, f(\Omega)|\Omega\rangle\langle\Omega|_N,$$ where $f\in C^\infty(\mathbb{S}^2)$,...
Kris's user avatar
  • 63
1 vote
0 answers
125 views

Large-deviation inequalities for a class of simple random multivariate polynomials

Let $N$ be a large positive integer and let $[N] := \{1,2,\ldots,N\}$. For any $k$, let $K_{N,k}$ denote the collection of $k$-element subsets of $[N]$. Let $x=(x_1,\ldots,x_N)$ be a uniformly random ...
dohmatob's user avatar
  • 6,716
1 vote
0 answers
95 views

Freidlin Wentzell for stochastic differential inclusions

Consider the SDI $$dX^\varepsilon(t)\in b(X^\varepsilon(t))\,dt + \varepsilon \sigma(X^\varepsilon(t)) \, dB(t).$$ Is there any Freidlin-Wentzell large deviations principle for $X^\varepsilon$?
user479223's user avatar
  • 1,250
1 vote
0 answers
82 views

Large deviation inequalities for number of coupon types collected by a coupon collector with fixed budget

In the generalized Coupon Collector's Problem, there are $N$ types of coupon, and for any $i \in [N] := \{1,2,\ldots,N\}$, $p_i \ge 0$ is the probability of obtaining a type-i coupon on any trial. ...
dohmatob's user avatar
  • 6,716
2 votes
0 answers
90 views

How much is known about the action functional for small noise diffusions with general volatility coefficients?

Let $W$ be a d-dimensional Brownian motion, and for every $\varepsilon > 0$, let $X^\varepsilon$ be the solution to the SDE $$dX^\varepsilon_t = b(X^\varepsilon_t) \, dt + \varepsilon \sigma (X^\...
Nate River's user avatar
  • 4,822
2 votes
0 answers
48 views

How to determine speed (rate) in large deviation principle for geometric Brownian motion

By reading Asymptotics for volatility derivatives in multi-factor rough volatility models by Lacombe, Muguruza and Stone, I am not familiar with the way they deduce the speed (or rate) when showing ...
Mili's user avatar
  • 21
3 votes
0 answers
153 views

A variant of the Laplace principle

$\newcommand{\R}{\mathbb R}\newcommand{\eps}{\varepsilon}$In $\R^d$ I am given a sequence of smooth functions $f_\eps(x)$ that converges uniformly to some $f(x)$, which is assumed to be a good rate ...
leo monsaingeon's user avatar
2 votes
0 answers
107 views

Large deviation principle for product of iid bounded symmetric random variables

Let $n$ and $k$ be positive integers. Let $X$ be the empirical mean of $n$ iid Rademacher random variables. Note that the distribution of $X$ is symmetric about 0, and also $|X| \le 1$ w.p 1. Let $X_1,...
dohmatob's user avatar
  • 6,716
4 votes
2 answers
242 views

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

Let $n$ be a large positive integer. Sample $N \ge 2$ points $x_1,\ldots,x_N$ iid from the uniform distribution on the $n$-dimensional hypercube $\{0,1\}^n$. Define the gap $\delta_{N,n} := \min_{i \...
dohmatob's user avatar
  • 6,716
3 votes
1 answer
154 views

Small noise limits with irregular drift

Let $W$ be a standard $d$-dimensional Brownian motion. Suppose $b: \mathbb R^d \to \mathbb R^d$ is measurable and bounded. Consider, for every $\varepsilon > 0$, the solution $X^\varepsilon$ on $[0,...
Nate River's user avatar
  • 4,822
2 votes
1 answer
312 views

Lower bound on sum of independent heavy-tailed random variables

I have a sum of $n$ i.i.d random variables $X_i$ such that $E[X_i] = 0$,$\mathrm{E}[|X_i|^{1 + \delta}]$ exists for some $0 < \delta < 1$ but $\mathrm{E}[|X_i|^{1 + \delta+ \epsilon}]$ does not ...
Kaiyue Wen's user avatar
3 votes
1 answer
128 views

Mutual information in large deviation theory

Many information theoretic quantities such as entropy and relative entropy appear in rate functions in large deviation theory (LDT). Is there any result in LDT that relates mutual information and rate ...
minhtoan's user avatar
  • 1,404
5 votes
0 answers
1k views

What exactly is the relationship between Donsker-Varadhan variational formula and the Laplace principle?

Given a nice real valued functional $C$ on some probability space $(\Omega, \mathcal F, P_0)$ we have the following Donsker-Varadhan variational representation $$\log E_{P_0}\left[e^C\right]=\sup_{P\...
user479223's user avatar
  • 1,250
4 votes
1 answer
288 views

Large deviations for sequences that are not sums of iid

Suppose $(S_n)_n$ is a sequence of real random variables. Denote their cumulant generating functions by $K_n(t) = \log\mathbb{E}\left[\mathrm{e}^{t S_n}\right]$, and assume that each $K_n$ is finite ...
Vladimir's user avatar
  • 1,210
5 votes
2 answers
651 views

Endpoint of Brownian motion conditional on high maxima

Note: This question is closely related to an earlier question: A large noise limit. Let $W$ be a standard one dimensional Brownian motion. For every $\varepsilon > 0$, let $A_\varepsilon$ denote ...
Nate River's user avatar
  • 4,822
0 votes
1 answer
164 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 ...
DJA's user avatar
  • 425
2 votes
1 answer
103 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-...
Viktor B's user avatar
  • 704
2 votes
1 answer
299 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 ...
Nate River's user avatar
  • 4,822
1 vote
1 answer
90 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 ...
Matt's user avatar
  • 97
1 vote
1 answer
193 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 ...
rime's user avatar
  • 445
2 votes
2 answers
148 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 ...
leeyee's user avatar
  • 265
3 votes
0 answers
77 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 {...
Synia's user avatar
  • 549
2 votes
1 answer
95 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 ...
Joe_Affine's user avatar
1 vote
0 answers
77 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\...
MikeG's user avatar
  • 665
5 votes
1 answer
204 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 ...
jlewk's user avatar
  • 1,344
0 votes
0 answers
623 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 ...
Jane's user avatar
  • 11
1 vote
1 answer
243 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 ...
SL_MathGuy's user avatar
0 votes
1 answer
223 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 ...
SL_MathGuy's user avatar
3 votes
0 answers
59 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(...
user78370's user avatar
  • 891
4 votes
3 answers
726 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 ...
Robert's user avatar
  • 173
8 votes
1 answer
584 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$...
Luis L.'s user avatar
  • 183
9 votes
1 answer
330 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 ...
Adam's user avatar
  • 323
0 votes
1 answer
207 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 ...
lye012's user avatar
  • 103
1 vote
0 answers
80 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 ...
ABIM's user avatar
  • 5,019
0 votes
0 answers
103 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 ...
Circonflexe's user avatar
0 votes
1 answer
123 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$. ...
dohmatob's user avatar
  • 6,716
0 votes
1 answer
88 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(...
Student88's user avatar
  • 503
3 votes
2 answers
694 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 ...
ABIM's user avatar
  • 5,019
0 votes
0 answers
51 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$. ...
ABIM's user avatar
  • 5,019
1 vote
0 answers
86 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 + \...
ABIM's user avatar
  • 5,019
0 votes
1 answer
144 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(...
DJA's user avatar
  • 425
2 votes
1 answer
214 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 ...
ABIM's user avatar
  • 5,019
5 votes
1 answer
325 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 ...
Ben Golub's user avatar
  • 1,058
6 votes
3 answers
491 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 ...
DJA's user avatar
  • 425
4 votes
1 answer
188 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}...
gregarki khayal's user avatar
2 votes
1 answer
235 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]$. ...
Bogdan's user avatar
  • 743
1 vote
0 answers
113 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}$. ...
dohmatob's user avatar
  • 6,716