Questions tagged [large-deviations]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
2
votes
1answer
98 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 ...
0
votes
0answers
68 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 ...
1
vote
1answer
175 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 ...
0
votes
1answer
73 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 ...
3
votes
0answers
47 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(...
3
votes
3answers
189 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 ...
6
votes
1answer
183 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$...
9
votes
1answer
231 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 ...
0
votes
1answer
81 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 ...
0
votes
0answers
30 views

Hitting Time-Analogue for Chaotic Systems

Let a topologically mixing dynamical map $f$ on $\mathbb{R}^n$, and define the dynamical system with initial value $x \in \mathbb{R}^n$ by $$ x_{t+1}^x = f(x_t^x),\, x_0^x=x . $$ Fix $y\in\mathbb{R}^n$...
1
vote
0answers
71 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 ...
0
votes
0answers
56 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 ...
0
votes
1answer
82 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$. ...
0
votes
1answer
56 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(...
2
votes
2answers
138 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 ...
0
votes
0answers
41 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$. ...
1
vote
0answers
47 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 + \...
0
votes
1answer
90 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(...
2
votes
0answers
120 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 ...
5
votes
1answer
208 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 ...
6
votes
3answers
262 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 ...
4
votes
1answer
149 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}...
2
votes
1answer
197 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]$. ...
1
vote
0answers
71 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}$. ...
4
votes
1answer
85 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 ...
2
votes
1answer
251 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 ...
5
votes
4answers
216 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. ...
3
votes
0answers
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 ...
5
votes
0answers
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^...
1
vote
0answers
23 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 ...
1
vote
0answers
145 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 ...
2
votes
1answer
115 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{...
3
votes
2answers
209 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 ...
3
votes
1answer
136 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\...
2
votes
2answers
181 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 ...
2
votes
1answer
93 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 ...
7
votes
0answers
507 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 ...
3
votes
1answer
143 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_{...
2
votes
0answers
112 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{...
2
votes
0answers
153 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 ...
1
vote
0answers
69 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.
7
votes
2answers
300 views

Large deviation/concentration inequality for submartingale

Let $S_t = M_t + D_t$ be the sum of a martingale $\left(M_t\right)_{t=1,2,\ldots}$ and a predictable process $(D_t)_{t=1,2,\ldots}$ such that the variance of the increments of $M$ is uniformly bounded ...
5
votes
0answers
251 views

universality for large deviations?

This is a question about universality in probability theory, with combinatorics in mind. Consider a sequence of polynomials $P_n$ in one variable, with positive coefficients. Combinatorics is a large ...
2
votes
0answers
54 views

tail bounds for sum of n iid variables divided by power of n

Let $X_i, 1\leq i\leq n$ be i.i.d. random variables with finite moments. Then $Y_n :=\frac{1}{n^{1+\delta}}\sum_{i=1}^nX_i$ goes to 0 almost surely for any $\delta >0$. What are some good non-...
2
votes
0answers
46 views

LDP respectively almost sure convergence in the context of randomly weighted trees

I am currently working on the following Problem: Imagine you are given a $d$-ary tree $T_d$, which means an infinite tree with one vertex $x_0$ on top and in which each vertex has $d$ children. Next,...
1
vote
0answers
123 views

Large deviations type results for sum of i.i.d. random functions

Assume that $f_1, f_2, f_3,\ldots$ are i.i.d. random functions $[0,1]\mapsto \mathbb{R}$ such that (1) random variables $M_k=\sup_{x\in[0,1]}f_k(x)$ have exponential tails, (2) $f$'s are a.s. ...
2
votes
0answers
149 views

A generalized Ballot theorem

Let $\{X_n\}_{n \in \mathbb{N}}$ be i.i.d. real random variables with $\mathbb{E}[X_i] = \mu \in \mathbb{R}$. Let $S_n = X_1 + X_2 + \cdots + X_n$. Let $\nu \leq \mu$ be such that $\mathbb{P}[S_n <...
4
votes
1answer
844 views

What is “tilting” in the context of large deviations?

I have seen references to the "tilting method" in the theory of large deviations. Is there a simple explanation of what this is, exactly?