Questions tagged [large-deviation-theory]

Use this tag for question on large deviations theory

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

What is the small noise rate function for $\int_0^t g(\omega(s),s)ds+\omega(t)$?

What is the small noise rate function for $\int_0^t g(\omega(s),s)ds+\omega(t)$? I try using contraction principle and Schilder's theorem. Let $T:C_0 \to C_0$ be defined by $T(\omega(t))=\int_0^t g(\...
3
votes
1answer
98 views

Chernoff Bound for sum of sub-gaussian variables via truncation method

I am trying to follow the proof here for Proposition 6 in https://terrytao.wordpress.com/2010/01/03/254a-notes-1-concentration-of-measure/, but I cannot figure out how the computation for the final ...
0
votes
0answers
29 views

Properties of the moment generating function

Suppose $X \in L^1$ has a moment generating function $M(\theta) \equiv E(e^{\theta X})$ that is finite for every $\theta \in \mathbb{R}$ (so that $M'(\theta)$ exists for every $\theta$). It is ...
0
votes
0answers
16 views

Properties of Legendre/Cramer's transformation of the moment generating function

Let $X \in L^1$ be a random variable on some probability space, define $M(\theta) \equiv E(e^{\theta X})$ as its moment generating function and let $D(M) \equiv \{\theta \in \mathbb{R} : M(\theta) <...
4
votes
1answer
190 views

How to estimate this probability of sum of $(-1,+1)$ valued random variables?

Let $x_1,\ldots,x_n$ be independent random variables and $\mathbb{P}(x_i=\pm1)=1/2.$ Prove that exists $C>0$ such that for $0\leq\Delta \leq n/C$, $$ \mathbb{P}\big(\sum_{i=1}^n x_i>\Delta\big)\...
1
vote
0answers
24 views

Convexity of the log-Laplace transform

I read in these notes (and a few other places) that, for a non-negative function, the logarithm of the Laplace transform is convex and lower-semicontinous. For the convexity part I can see intuitively ...
0
votes
0answers
16 views

saddle point method with conjugate complex roots

Here I want to use the saddle point to calculate something. My equation is $$f(x,t)=\int_0^\infty\exp \left(\underbrace{a N^{\frac{1}{1-\alpha }}+b \ln (N)-\frac{x^2+A^2N^2-2ANx}{2 N \sigma ^2}-\frac{...
1
vote
1answer
29 views

Hoeffding for bounded random variables, extension of Rademacher case

In Vershynin's High-Dimensional Probability, he first proves the Hoeffding bound on page 17 $$\mathbb{P}\left\{\sum_{i=1}^N a_iX_i \geq t\right\} \leq \exp \left( -\frac{1}{2} \frac{t^2}{\|a\|^2_2}...
1
vote
1answer
15 views

Probability that most likely outcome will appear more often in finite sequence

Let $(X_n)_{n\geq 1}$ be an i.i.d. sequence of variables with unequal Bernoulli distribution : $P(X=0)=p, P(X=1)=1-p$ with $p\gt \frac{1}{2}$ (so getting a $0$ is more likely than getting a $1$). Let ...
0
votes
1answer
30 views

Edge density in subgraphs of an Erdos-Renyi graph $G(n,p)$

Given an Erdos-Renyi random graph $G\sim G(n,p)$, I want to estimate the probability that all the subgraphs of $G$ (that are not too small, say subgraphs on $m>\epsilon n$ vertices) have edge ...
0
votes
0answers
14 views

Dembo and Zeitouni Lemma 5.6.18 . Stochastic Analysis, Relatively Simple Proof, Assumption of Bounded Diffusion Coefficient not Needed.

I'm reading the classic book on Large Deviations : Large Deviations by Dembo and Zeitouni. On page $217$, Lemma $5.6.18$, they make a proof which is purely stochastic calculus with no tricks. ...
0
votes
0answers
9 views

For transient symmetric random walk on $\mathbb{Z}^d,$ the collision local time $V$ is finite almost surely.

I am trying to learn large deviations. I found a video lecture by Prof. Frank den Hollander on YouTube. In the video, he defines two (symmetric) random walks $(S_k)_{k\ge 0}$ and $(S_k')_{k\ge 0}$ on $...
1
vote
0answers
40 views

Number of sequences from one state to another with fixed transition counts / empirical matrix

I think the answer to this might be well known but I can't find it and I am also bad at combinatorics. First, note that if we have an i.i.d. random variable with finite sample space $A$ we can obtain ...
0
votes
1answer
32 views

$\epsilon$ vs. $n$ in Szemeredi's regularity lemma

In many of the application to Szemeredi's regularity lemma, we use the fact that the number of edges in the graph that does not connect a $\epsilon$-uniform pair is of order $\propto \epsilon n^2$, ...
0
votes
0answers
30 views

Cramer's theorem for large deviations - an extension?

I know that Cramer's Theorem for large deviations is usually applied to $S_n = \sum_{i=1}^n X_i$ where $X_1,X_2,...$ are iid, provided that a moment generating function for the $X_i$'s exist. What ...
0
votes
0answers
34 views

Generalization of large deviation principle

My question arises from the following fact: For $X_i, i \geq 1$ i.i.d. standard normal distribution, we have for $\beta > 1/2$. Since $X_1 + \dots + X_n$ is a Gaussian random variable with mean $0$...
0
votes
0answers
20 views

How can i use large deviation theory to check $X<0$

The Chernoff bound can be used as an upper bound for the tail probability for the average of i.i.d. random variables, e.g., $$ \mathbb{P}\left(\frac{1}{n}\sum_{i=1}^{n} X_i > a \right) \le \left( ...
1
vote
1answer
30 views

Discritization Error Diffusion Process

Let $X_t$ be an $\mathbb{R}^d$-valued diffusion process with initial condition $x\in\mathbb{R}^d$ and $X_t^{\Delta}$ be it discretization along an evenly spaced grid on $[0,1]$ with spacing $1>\...
0
votes
1answer
28 views

Large deviations for sums of random variables that are relatively close

Let $X_1,X_2,\dots$ be a sequence of random variables such that the distribution of their sum $S_n = \sum_{i=1}^n X_i$ satisfies a large deviation principle in the sense that there exists a lower ...
3
votes
1answer
87 views

Large deviation bound for squared norm of the sum of two random variables

I want to pose this question as general as possible and ask for reference of what to do in similar situations. I'll incrementally add details to narrow down the problem. I want to derive large ...
0
votes
0answers
22 views

LDP, Contraction Principle, Freidlin–Wentzell theory Dembo and Zeitouni.

I had a problem with a simple proof in Dembo and Zeitouni. Specifically Theorem 5.6.7 page 215, which is a Freidlin-Wentzell theorem. The idea of the proof is that we approximate the original SDE : ...
0
votes
0answers
56 views

Large Deviation Principle for specific conditional probability measures?

Let $X_1,X_2,\dots$ be an i.i.d. sequence of nonnegative integer valued random variables under $P$. Denote the sum over $X_i$ by $S_n=\sum_{i=1}^n X_i$. For a fixed $m$ and a function $f$ on $m$-...
0
votes
0answers
15 views

Why does the regressor '1/t' in y(t) = B1 + B2(1/t) + u tend to zero?

My textbook says that if n tends to infinity then each observation provides less and less information about B2. This happens due to the fact that (1/t) tends to zero and hence varies less and less ...
1
vote
0answers
45 views

Moments of RW bounded by standard normal moments

I am looking for a prettier proof to show that the scaled moments of a simple random walk can be bounded from above by the moments of a standard normal distribution. More precisely, let $X_1, \ldots, ...
0
votes
0answers
11 views

Importance Sampling Expectation Estimation

Say we have: $dX_t = \epsilon dW_t$ where $\epsilon$ is small. and $X_0 = a$ where $0 < a < 1$. I am intresting in finding the following quantity : $p^{\epsilon} = P(|X_{t=1}| \geq 1)$. One ...
0
votes
0answers
16 views

Unique Uniformily Viscosity Solution

Say we have the following pocess: $$dX^{\epsilon} = b(X^{\epsilon}(s))ds + \sqrt\epsilon \sigma(X^{\epsilon}(s))dW(s)$$ for $s \in [0, T]$ and $X^{\epsilon}(0) = x_0$ We want to estimate a quantity ...
0
votes
1answer
39 views

Cumulant generating function and largest eigenvalue of operator

I am working on a recent paper (arXiv:1805.02887) about an application of large deviation theory to the statistical mechanics of active matter and am a bit bewildered by a result dropped in appendix F ...
0
votes
0answers
22 views

Rate function in Large deviation theory

A function I : X → [0, ∞] is called a rate function, if (i) I ≡ ∞; (ii) I has compact level sets (in particular, it is lower semicontinuous). How can I calculate the rate function $I$ for a ...
2
votes
0answers
34 views

Cramer's Rule when excluding the largest j samples

For a simple case, assume $X_i$ i.i.d and it has moment generating function defined everywhere, i.e for $t\in\mathbb{R}$, $\mathbb{E}(e^{tX_1}) < \infty$. Denote $\mu = \mathbb{E}(X_1)$, then one ...
0
votes
0answers
27 views

projection of a random vector and angle?

I have a random vector $v$ whose expected squared projection length along a unit vector $\hat{u}$ is large, while the expected squared length is small, i.e. $\mathbf{E}[|<v,\hat{u}>|^2]$ is ...
3
votes
0answers
36 views

Approximating $\mathbb{P}(X_t \geq c)$ with the process' limit

I stumbled over the following problem while trying to prove LDP's for branching processes. However, I state the problem more generally: assume $(X_t)_t$ be a stochastic process, with $X_t\rightarrow ...
0
votes
1answer
26 views

Large Deviation Principle for multivariat Gaussian

Let us consider the law $\mu_{\epsilon}$ of a multivariat normally distributed random vector X~$\mathcal{N}(0, \epsilon I)$ with mean vector [0,...,0] and covariance Matrix equal to the identity ...
2
votes
1answer
130 views

Fenchel-Legendre Transform Intuition in Large Deviations

Does anyone have a good intuitive reason why the Fenchel-Legendre Transform appears all over the theory of Large Deviations. The Fenchel-Legendre Transform appears in both Sanov Theory and Friedlin-...
2
votes
1answer
116 views

Large Deviation, Optimal Transport and Machine Learning Reference

I am looking for references (books/sites/articles) on the following three subjects: Large Deviation, Optimal Transport and Machine Learning References. I would like works which involve any of them ...
5
votes
1answer
87 views

Distance from origin of biased random walk conditioned to be positive at time n

Let $S_n$ be the position of a simple random walk on the integers started from $0$ that moves right with probability $p<1/2$. What is the asymptotic behavior of $$E[ S_n \mid S_n >0 ]$$ as $n \...
1
vote
1answer
48 views

Asymptotically tight bounds $P \left[1-\frac{1}{n} \le \frac{\sum_{i=1}^n Z_i^2 }{n} \le 1+\frac{1}{n} \right]$

I am looking for assymptotically tight bounds on \begin{align} P \left[1-\frac{1}{n} \le \frac{\sum_{i=1}^n Z_i^2 }{n} \le 1+\frac{1}{n} \right]=P \left[ \left| E[Z^2] - \frac{\sum_{i=1}^n Z_i^2 }{n} ...
2
votes
1answer
45 views

Asymptotics of binary call option in Black–Scholes model in the large deviations sense

Consider Black–Scholes model where asset log-price is given by $$ X _ { t } = \sigma W _ { t } + \mu t $$ for $W_t$ – Brownian motion. I want to show that $$ P \left[ X _ { t } > k \right] \...
3
votes
0answers
91 views

Is $\inf$ of a differentiable function still differentiable?

I'm new on stackexchange, thanks for this fantastic platform! Let's get to the point. Suppose we have a function $I(x,y) \in \mathbb{R}$, $I(x,y) \geq 0$, convex, and differentiable for $x \in X$ ...
1
vote
1answer
71 views

Reference book on large deviations for mean field theory

I am looking for reference material, notes or published books, which study applications of large deviations on mean field theory / interacting particle systems etc.. I am especially interested in ...
1
vote
0answers
36 views

Determining if a Large Deviation Principle exists for a sequence of probability measures.

Given a sequence $(P_n)_n$ of probability measures on a space satisfies a LDP with rate $r_n$ and rate function $I$ if both the following hold: $$ \limsup_{n}\frac{1}{r_n}\log P_n [F] \le - \inf_{x \...
1
vote
1answer
46 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
73 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
51 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)...
2
votes
2answers
99 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
53 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
176 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
1answer
69 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
112 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 ...
7
votes
2answers
374 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
79 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 ...