Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [large-deviation-theory]

Use this tag for question on large deviations theory

1
vote
1answer
24 views

Large Deviations rate function and Cramérs Theorem

Given $X_1,...$ of iid random variables. We know that if the moment generating function $M(\theta) < \infty, \forall \theta $ from Cramérs Theorem we get: $\lim_{n\to \infty} \frac{1}{n}\log \...
0
votes
0answers
50 views

Sum of variables of a martingale

I have the sequence $X_1, X_2,...X_n$ as a martingale, each of which is bounded. Now I want to explore some upper bound for the sum $S_n=X_1+X_2+...+X_n$, e.g., the format like Hoeffding inequality or ...
0
votes
2answers
28 views

Integrate: $\int_{-\infty}^\infty \exp(-||\vec x||^2) ||\vec x||^{-m}\mathrm{d}\vec{x}$

Let $m,n$ be two positive integers with $0 < m < n$. Can we integrate this: $$I = \int_{-\infty}^\infty \mathrm{d}x_1 \dots \int_{-\infty}^\infty \mathrm{d}x_n \left(\sum_{i=1}^n x_i^2\right)...
0
votes
0answers
26 views

Derivation of Sanov's theorem for continuous variables

Where can I find a derivation of Sanov's theorem for continuous variables? I am familiar with the derivation for discrete variables. I am looking hopefully for something similarly intuitive.
2
votes
2answers
94 views

Integrate: $\int_0^1 ||\vec x||^{-m}\mathrm{d}\vec{x}$

Let $m,n$ be two positive integers with $0 < m < n$. Can we integrate this: $$I = \int_0^1 \mathrm{d}x_1 \dots \int_0^1 \mathrm{d}x_n \left(\sum_{i=1}^n x_i^2\right)^{-m/2}$$ If a closed ...
3
votes
0answers
52 views

Simplify $\int_a^b \mathrm{d}x_1 …\mathrm{d}x_m \int_c^d \mathrm{d}y_1 …\mathrm{d}y_n \prod_{i=1}^m \prod_{j=1}^n f(x_i y_j)$

Let $a \le b$ and $c\le d$ be real numbers and $f$ a real function. I am struggling with an integral of the form: $$I = \int_a^b \mathrm{d}x_1 ...\mathrm{d}x_m \int_c^d \mathrm{d}y_1 ...\mathrm{d}...
1
vote
0answers
74 views

Cramer's theorem and central limit theorem

I just came across Cramer's theorem for large deviations. If $X_1,..,X_n$ are i.i.d and $S_n$ is the mean of the first $n$, then: $$\lim_{n \rightarrow \infty} \frac{\log P(S_n >x)}{n}=-I(x)\...
0
votes
0answers
16 views

Probability relating the sum of tilted distributions

Say I have $iid$ Bernoulli random variables with probability $p$ $$P(X_i = 1) = p$$ I derive the tilted probability $X_i^{(\lambda)}$ such that: $$P(X_i^{(\lambda)} = 1) = \frac{e^{\lambda}p}{e^{\...
0
votes
0answers
27 views

Limit of derivative of moment generating function

Suppose $X>0$ is an integer-valued with $P(X=k)=q_ke^{-t_0k}$, where $t_0>0$ and $\{q_k\}$ satisfies $\frac{1}{k}\log q_k \rightarrow 0$. Let $\phi(t)$ be the MGF of $X$. Let $t_{\text{max}}=\...
0
votes
1answer
42 views

Large deviation 2.6 Durrett's book

I'm reading 2.6 of Durrett's book. If we define $\phi(t)=\mathbb{E}[e^{tX}]$ and for $a>\mu$, where $\mu$ is the expectation of corresponding random variable, and we define $$I(a)=\sup_{t>0} \ (...
2
votes
0answers
67 views

Laplace Method - Estimation of an integral

I am just working on a paper by Shinzo Watanabe on "Asymptotic Evaluations of Wiener Functional expactations": $μ(dx)$ is the $d$-dimensional Gaussian distributions So that is the interesting ...
3
votes
2answers
92 views

Why Large deviation theory?

I am trying to understand why we need Large deviation theory/principle. Here is what I understand so far based on the Wikipedia. Let $S_n$ be a random variable which depends on $n$. We are ...
2
votes
1answer
68 views

Is there any intuitive way to see $\frac{e^{\delta}}{(1+\delta)^{1+\delta}}\leq e^{-\delta^2/3}$ $0<\delta<1$

I am reading the proof of Chernoff bound ,there's one step here : $$\frac{e^{\delta}}{(1+\delta)^{1+\delta}}\leq e^{-\delta^2/3}$$ where $0<\delta<1$ the book prove that by using the second ...
1
vote
1answer
32 views

Large Deviation Principle

I have been reading Amir Dembo's book, and at the very beginning, I found this result that came across and unfortunately, I cannot derive it by myself. So, I'm looking for some help. It happens that ...
2
votes
2answers
213 views

Hoeffding inequality for conditional probability (conditioned on event)

Suppose I have independent $X_1\sim\text{Bin}(n,\theta_1)$, $X_2\sim\text{Bin}(n,\theta_2)$ with $X=X_1+X_2$. Suppose that $\theta_1,\theta_2\in(0,1)$. Define the constant (but still depends on $n$) $...
1
vote
0answers
13 views

Equivalence of two large deviation statements

Let $\{X_n\} \subset \mathcal{X}$ be a sequence of random variables on a compact metric space $(\mathcal{X},d)$. The sequence is Cauchy, i.e. $d(X_n, X_{n+1}) \rightarrow 0$ and it satisfies the ...
0
votes
0answers
39 views

Reconciling definitions of large deviations principle

I am reading some notes on the Large deviations principle and I want to reconcile the definitions I've seen in the abstract measure theoretic framework and one that is used on an introduction to the ...
4
votes
0answers
32 views

Limit of a mixture of binomial distributions

Let $0 < r \leq 1/2$ and let $B(n,p)$ be the notation for binomial distribution. Consider the random variable $Z_n$ defined by the recursive equation $$ Z_{n+1} = Z_n + X_n I(Z_{n} \geq r n^2) + ...
2
votes
1answer
69 views

Why is the rate function given by Schilder's theorem infinite outside of CM space? Can we understand Schilder's theorem through CM theorem?

Schilder's theorem from large deviations theory tells us that scaled Brownian motion $\sqrt{\varepsilon} W_t$ on Wiener space $C_0([0,T],\Bbb R^d)$ satisfies a large deviation principle with good rate ...
0
votes
0answers
38 views

Gärtner-Ellis theorem on Markov chains

Let $Z_n \in \mathcal{X}$ be a sequence of independent random variables where $\mathcal{X}$ is a topological vector space and let $\mu_n$ the probability measures associated with $Z_n$. Suppose that $...
4
votes
1answer
73 views

What does it mean that “the central limit theorem does not hold far away from the peak”?

So I know nothing about large deviations theory, and I'm reading some notes. They claim that: The CLT does not hold far away from the peak I am not sure how to parse this statement. There are many ...
0
votes
1answer
93 views

Good book on large deviations theory

I am interested in reading about large deviations theory. Can anybody please suggest me any good book regarding this. Thanks in advance.
1
vote
0answers
71 views

Finite Exponential Moment

Consider $X_1, X_2, X_3$ ... random variables i.i.d. such that $P(X_i=1)=p$ and $P(X_i=-1)=1-p$. Consider the random walk $(S_n)_{n\ge 0} $ with $S_0=0$ and for $n\ge 1 $, $S_n = \displaystyle\sum^{...
0
votes
1answer
100 views

Large deviation principle for Gaussian random variables with mean $0$ and variance $1/n$.

Problem: Let $\mu_n$ be the Gaussian distribution with mean zero and variance $1/n$ on $\mathbb{R}$. Show that $\mu_n$ satisfies a large deviation principle with rate $1/n$ and rate function $x^2/2$. ...
0
votes
0answers
58 views

Prove that MGF is differentiable at everywhere? and $\lim_{s \rightarrow \infty} \frac{\log M(s)}{s} = \infty$?

I am reading the some notes on probability theory and the notes(Chernoff lower bound) left some gap that I should fill in, however I don't even know how to start yet. Here is the assumption the gives ...
1
vote
0answers
51 views

Pontryagin principle, Optimal control or Numerical scheme ? logical constraint?

I have the following optimal control problem : $ \textit{ Minimize } \qquad J(u,x,T) =\displaystyle \int_0^T \Big[ u_1(t)\log\frac{u_1(t)}{ x_1(t)x_2(t)} - u_1(t) +x_1(t)x_2(t) \qquad \qquad \...
0
votes
2answers
49 views

Polynomial term for random walk large deviations

Let $S_n = \sum_1^n X_i$ with $P(X_i =1) = p>1/2$ and $P(X_i = -1) = 1-p$ be a biased random walk. Large deviations tell us that $p_0=P(S_n \leq 0) \leq n^a(2 \sqrt{p(1-p)})^n$. We are curious what ...
0
votes
0answers
15 views

Dominant term on summation of Q-Functions with very large argument in $\mathcal{Q}(x)$

It happens I am dealing with a expression that looks this way: $P = \mathcal{Q}(\alpha x) - \mathcal{Q}(\beta x)$, where $\mathcal{Q}(x) = \int_{x}^{\infty} \frac{1}{2\pi} \exp{(-x^2/2)} dx$ Is ...
1
vote
0answers
26 views

WKB form, large deviation expansion of the stationary PDF

I am currently reading the book theory and applications of stochastic processes an analytical approach, on page 304, we have the equality: $$ \int_{\mathbb{R}} [p_{\varepsilon}(y-\varepsilon \xi) w(\...
1
vote
0answers
60 views

an Optimal control problem : infinite time horizon and free end point

i've never worked on optimal control problem before and have an issue with this problem : Let $x_0\in \mathbb{R}^2_+$ and a constant $\lambda \neq0$ be fixed. I want to minimize, $\qquad$ over ...
0
votes
0answers
39 views

Weighted chi-square large deviations bound?

For a fixed $n$, let $x_1,\dots,x_n$ be $n$ i.i.d. draws from a chi-square distribution with $n$ degrees of freedom. Let $\Delta^{n-1}$ be the $(n-1)$-simplex and $g_n$ a function mapping a point in $\...
1
vote
0answers
42 views

Connection between large deviation principle and weak convergence/

What is the relationship between large deviation and weak convergence? Consider a sequence of random variables {X_n}, does the LDP of sample mean imply the the distribution of X_n converge? If so, ...
1
vote
1answer
66 views

Understanding Legendre-fenchel Transform, looking for an easy example and intuition

Looking for help in understanding this transform. I have no background in real analysis but need this stuff for my research. I hope someone can give me some light on the intuition behind this ...
0
votes
1answer
62 views

some questions on large deviations

the following excerpt is from den hollander: i just don't get the point. what is meant by cheapest realization? is it, loosely speaking, the realization occuring with highest probability because of ...
1
vote
1answer
31 views

Alternate Characterization of Rate of Convergence

Let $\{x_n\}$ be a sequence converging to $L$. According to Wikipedia, if there exists a $\mu\in(0,1)$ satisfying $$\lim_{k→∞}\frac{|x_{k+1}−L|}{|x_k−L|}=μ$$ then we say $\{x_n\}$ converges ...
2
votes
1answer
96 views

Doubt in Proof of lower bound in Cramer's theorem

I read proof of Cramer's theorem from the book : 'Large Deviations and Applications' by A.Dembo and Ofer Zeitouni. I have a doubt in the proof of the lower bound. Cramer's theorem(Lower bound) : ...
2
votes
1answer
550 views

What does Cramer's Theorem tell us?

Cramer's Theorem States, Let $(Y_i)_{i\geq 1}$ be a sequence of i.i.d. random variables, ${S_n=\frac{1}{n}\sum_{i=1}^n Y_i}$ be their average sum and $M_{Y_1}(u):=\mathrm{E}[e^{uY_1}]<\infty$ be ...
1
vote
1answer
274 views

Difference between “large deviation estimate” and “moderate deviation estimate” in probability theory

I am from physics background. Recently, I am reading a book on "limit theorems in probability theory". My question is, What are the fundamental differences between "large deviation estimate" and "...
1
vote
1answer
85 views

Understanding a proof in Varadhan's large deviations and applications

I am currently writing a thesis that serves as an introduction to the theory of large deviations for people on about my level. The task is to closely follow Varadhan's booklet "Large Deviations and ...
2
votes
0answers
60 views

How do we conclude that $h_c$ is non decreasing? A question concernig a paper from Varadhan (2003)

In the paper Large Deviations for Random Walks in a Random Environment (2003) One reads on page 1226: $h_c$ is obtained as the following limit: $$h_c(y) = \lim_n \frac{1}{n} -\log \sup_m \big(\pi^m(...
1
vote
0answers
77 views

Reference request: Large deviations for a conditional probability

Suppose a sequence of probability measures $(\mathbb P_n)_{n\in\mathbb N}$ on a Polish space $X$ satisfies the large deviations principle with a good rate function $I$ and rate $n$. Informally ...
1
vote
1answer
70 views

Computing large deviations probabilities for sums of gaussians

Let $R_i$ be i.i.d. normally distributed with $\mu = 1$ and $\sigma^2 = 0,1$ and $S_n = \sum_{i=1}^n R_i$ and let $c \geq E[R_i]$. What is the probability that $P(S_n > nc)$ for large $n$? I've ...
1
vote
0answers
102 views

Large Deviations result for asymptotically independent variables

I'm wondering if there is a large deviations result for asymptotically independent and identical distributed (a.i.i.d.) variables. If $\{(X^i_n)_{i=1,\dots,n}\}_{n\in\mathbb{N}}$ is a sequence of a....
2
votes
1answer
83 views

Having trouble in an exercice on Large Deviations.

In the book "Large deviations" by Frank den Hollander, one reads in pg 30: Exercise III.10 (Suggested by G. O'Brien.) Let $Z_n$ be a single random variable with a binomial distribution with ...
2
votes
1answer
297 views

Proof of Cramer's Large Deviation Theorem

https://ocw.mit.edu/courses/sloan-school-of-management/15-070j-advanced-stochastic-processes-fall-2013/lecture-notes/MIT15_070JF13_Lec4.pdf On page 6 (proof of Cramer's theorem), it says $$\limsup_n ...
0
votes
1answer
41 views

Equivalence in the formulation of the “Large Deviation Principle”

I'm reading this notes on the Internet http://staff.utia.cas.cz/swart/lecture_notes/LDP4.pdf. And I'm stuck in this proposition: Let E be a Polish space. A sequence of finites measures $\{\mu_n\}$ ...
6
votes
2answers
131 views

Let $X$ be standard normal and $a>b>0$, prove that $\lim\limits_{\epsilon\to 0}\epsilon^2\log P(|\epsilon X -a|<b)=-\frac{(a-b)^2}{2}$

Let $X$ be a standard normal random variable, with $a,b>0$ and $a-b>0$, prove that $$\lim_{\epsilon\to 0}\epsilon^2\log P(|\epsilon X -a|<b)=-\frac{(a-b)^2}{2}$$ I'm studying for a qual and ...
1
vote
0answers
76 views

large deviation problem with rate function

Let X1, X2, . . . be i.i.d. random variables such that $P(X_1 = -1) = 2/3$ and $P(X_1 = 2) =1/3$ and for each integer $n \geq 1$ put $S_n := X_1 +X_2 +\cdots+X_n$. For a sufficiently large $n$, ...
0
votes
1answer
99 views

Use of Sanov's Theorem, Optimisation Problem

Suppose we roll a die 10000 times, and observe that the mean is 3.8. How many sixes did we roll? I know that this is an application of Sanov's theorem for finite alphabets - if the sample mean of a ...
1
vote
0answers
24 views

Large deviations principle for $X^{\lfloor \alpha N \rfloor}/N$

Let $(X^N/N, N \in \mathbb{N}$) satisfy a large deviations principle in $\mathbb{R}$ with convex rate function $I$. Let $\alpha$ be a positive real number. Show that $X^{\lfloor \alpha N \rfloor}/N, N ...