Questions tagged [large-deviations]
The large-deviations tag has no usage guidance.
72
questions
1
vote
0
answers
113
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 ...
- 6,466
1
vote
0
answers
70
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$?
- 874
1
vote
0
answers
59
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. ...
- 6,466
2
votes
0
answers
78
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^\...
- 3,449
2
votes
0
answers
40
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 ...
- 21
3
votes
0
answers
106
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 ...
- 4,564
2
votes
0
answers
93
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,...
- 6,466
4
votes
2
answers
226
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 \...
- 6,466
2
votes
0
answers
42
views
Asymptotic distribution of counting process when we include higher moments (thus not Gaussian)
Question
Consider a counting process $(N(t))_{t \ge 0}$ such that the time $\tau$ between arrivals is I.I.D with some probability distribution $f$. Call $\langle \tau^n\rangle$ the $n$th moment of $$, ...
- 179
3
votes
1
answer
148
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,...
- 3,449
2
votes
1
answer
286
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 ...
- 23
0
votes
0
answers
40
views
Extended large deviation principle on product space
My question is how to prove the large deviation property in a product space if at each coordinate there is a large deviation property. I will explain what I mean in detail as below:
Let me start with ...
- 173
3
votes
1
answer
110
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 ...
- 1,313
5
votes
0
answers
662
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\...
- 874
4
votes
1
answer
244
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 ...
- 1,220
5
votes
2
answers
633
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 ...
- 3,449
0
votes
1
answer
144
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 ...
- 425
2
votes
1
answer
96
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-...
- 694
2
votes
1
answer
295
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 ...
- 3,449
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 ...
- 87
1
vote
1
answer
158
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 ...
- 425
2
votes
2
answers
136
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 ...
- 165
3
votes
0
answers
64
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 {...
- 549
2
votes
1
answer
90
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 ...
- 77
1
vote
0
answers
75
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\...
- 607
4
votes
1
answer
193
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 ...
- 1,069
0
votes
0
answers
463
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 ...
- 11
1
vote
1
answer
223
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 ...
- 135
0
votes
1
answer
177
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 ...
- 135
3
votes
0
answers
58
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(...
- 861
4
votes
3
answers
570
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 ...
- 173
8
votes
1
answer
506
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$...
- 183
9
votes
1
answer
306
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 ...
- 323
0
votes
1
answer
175
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 ...
- 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 ...
- 4,971
0
votes
0
answers
96
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 ...
- 101
0
votes
1
answer
119
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$.
...
- 6,466
0
votes
1
answer
79
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(...
- 503
2
votes
2
answers
557
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 ...
- 4,971
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$. ...
- 4,971
1
vote
0
answers
75
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 + \...
- 4,971
0
votes
1
answer
118
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(...
- 425
2
votes
1
answer
183
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 ...
- 4,971
5
votes
1
answer
304
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 ...
- 1,058
6
votes
3
answers
424
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 ...
- 425
4
votes
1
answer
184
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}...
- 199
2
votes
1
answer
221
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]$. ...
- 743
1
vote
0
answers
109
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}$.
...
- 6,466
4
votes
1
answer
125
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 ...
- 43
2
votes
1
answer
358
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 ...
- 31