Skip to main content

Questions tagged [large-deviation-theory]

Use this tag for question on large deviations theory

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

$\forall x:\mathbb P(M/n\leq x\mid S=n\mu +N)\to 1$ if $N=o(n)$?

Let $(X_n)_n$ be a sequence of iid random variables with values in $\mathbb N$ and expected value $\mu$, $S_n=X_1+\ldots+X_n$, $M_n=\max(X_1,\ldots,X_n)$. Furthermore suppose that $N=o(n)$ and $\...
Filippo's user avatar
  • 3,584
0 votes
0 answers
33 views

on the Thompson sampling proof

I was reading recently the Thompson sampling paper https://arxiv.org/pdf/1205.4217. The non-constant (w.r.t $T$) leading term of the regret is obtained (begining of page 5) by bounding $\sum_{t=1}^T\...
Pierre's user avatar
  • 352
2 votes
1 answer
30 views

Tail probability of the maximum of Gaussians

Consider $N$ i.i.d. standard Gaussian variables, and let $X_m$ be the maximum. It is known that $E[X_m] \approx \sqrt{2 \log N}$ and that the variance goes to zero as $N$ grows. However, I'm looking ...
info_theorist's user avatar
2 votes
1 answer
43 views

Intuition on Kolmogorov 3 Series Theorem

This is rather general question and there might be no such thing as a right answer, but I would admire any replies. Prelude Recall that Khintchine-Kolmogorov Theorem: if $X_i$ are independent and $L^...
Simone Licciardi's user avatar
1 vote
0 answers
28 views

Limit of $\Lambda'(\lambda)$ when $\lambda\rightarrow\infty$

Let $X:\Omega\rightarrow \mathbb{R}$ be a random variable over the probability space $(\Omega,\mathcal{F}, \mathbb{P})$. The cumulant generating function of $X$ is defined as $\Lambda(\lambda):=\log \...
Grothendieck00's user avatar
0 votes
0 answers
18 views

Running minimum of exponential random walk

Let $X_i$ be a collection of i.i.d. Exp$(1)$ random variables. For $k \in \mathbb{Z}_{>0}$, define $$S_k = \sum_{i=1}^k X_i$$ and note that $\mathbb{E}[S_k] = k$. I was wondering if there is any ...
Xiao's user avatar
  • 9,586
1 vote
0 answers
25 views

why non-gaussian case we do not have $S_n>an$ being rare?

I am taking a course on Large deviation theory but I'm a bit stuck at the first place. The lecturer gave an example to motivate the study of large deviation. First, if $X_1$ is standard gaussian, and $...
chloe's user avatar
  • 1,052
1 vote
0 answers
31 views

What does it mean to deviate macroscopically from the mean? And what does it mean to deviate in terms of fluctuations?

Let $\{X_{n}\}_{n\in \mathbb{N}}$ be a sequence of random variables. Suppose that $\{X_{n}\}_{n\in \mathbb{N}}$ fulfills certain regularity conditions described below. The random variables $X_{n}$ are ...
Elias Costa's user avatar
  • 14.8k
1 vote
1 answer
52 views

Large Deviation Inequality with a Gaussian type bound

I am trying to follow Terence Tao's notes on concentration of measure, particularly the derivation of equation $(8)$ . Suppose $\{X_i\}$ is a collection of random variables normalised to have mean ...
J.B.R's user avatar
  • 117
0 votes
0 answers
56 views

Convergence rate of Laplace principle in Large Deviations

Let $H:A \to \mathbb R$ be a continuous function defined on a compact subset $A\subset \mathbf{R}^n$. Then the Laplace principle shows that $$ \lim_{\theta\to \infty }\frac{1}{\theta}\log \int_A ...
John's user avatar
  • 13.3k
1 vote
0 answers
32 views

Concentration 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
  • 13.3k
0 votes
0 answers
32 views

From Large Deviations to Finite Time Probability Tails

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 obtain such a result is ...
Benjamin's user avatar
  • 789
3 votes
1 answer
169 views

Sanov's Theorem for Empirical Measure

I am working through the proof of Sanov's Theorem for the Empirical Measure (as found in Hollander's Large Deviations text), and am hoping someone could provide a bit of clarity on some of the steps ...
2307's user avatar
  • 334
0 votes
0 answers
10 views

Large deviation upper bound in an article

How are $Q(W)$ and $\int W_i d\zeta^\lambda$ eliminated and get the last line? On page 508 of the article: Kifer Y. Large deviations in dynamical systems and stochastic processes[J]. Transactions of ...
Trinifold's user avatar
0 votes
0 answers
21 views

When can lower bounds on $\ell_2$ minimax risk be used to obtain lower bounds on deviations (with high probability)?

I am reading this paper and Theorem 3.3, says that under some conditions, $$ \inf_{M \in \bf{M}} \sup_{P\in \bf{P}} E|M(X)-\mu|_2^2 \gtrsim \sigma^2\left(\frac{s^* \log d}{n}+\frac{\left(s^* \log d\...
KRam's user avatar
  • 33
2 votes
1 answer
104 views

Bounding with exponential Markov inequality

I have a question applying Markov inequality for the following question: Let $(X_{n})$, $n∈N$ be a sequence of i.i.d. real-valued random variables with $μ := E[X_{1}]$, and $φ(λ) := \text{log}E[e^{λX_{...
엄익훈's user avatar
  • 115
0 votes
0 answers
42 views

How do I compute $=\inf_{x:x\delta_1+(1-x)\delta_0 =y} I_p(x))$ ? ( using the contraction principle to get the rate funct. of the L.D.P in an example)

Consider the following example, Also consider and just in case the contraction principle is quoted below I don't get how they apply the contraction principle to get $H(\alpha)=I_p(s)$ According to ...
some_math_guy's user avatar
3 votes
2 answers
97 views

Probability bound on sum of geometric random variables

Suppose each $X_i$ is a geometric distribution with probability $p = 1/2$. That is $X_i$ measures the number of coin flips it takes until you get a heads. Let $X = X_1 + X_2 + ... + X_n$. Clearly $E[X]...
Rioghasarig's user avatar
  • 1,809
3 votes
1 answer
67 views

How large $\mathbb{E} \bigg[\max_{k \in \{1,\dots,K\}}\sum_{t=1}^T \mathbb{I}\{X_t=k\}\bigg] - \frac{T}{K}$ can be?

For each $K \in \mathbb{N}$, assume that $X_1,X_2,\dots$ is an i.i.d. sequence of (discrete) uniform random variables on the set $\{1,\dots,K\}$ and, for each $T \in \mathbb{N}$, define the quantity $$...
Bob's user avatar
  • 5,783
3 votes
0 answers
39 views

Accumulation in the zeroes of the rate function (Large deviation principle)

Consider a measure space $(\mathcal{X},\mathcal{B})$, where $\mathcal{X}$ is Polish and $\mathcal{B}$ is the Borel $\sigma$-field. Let $(\mu_n)$ be a sequence of probability measure that satisfies the ...
LUCA MAZZUCCO's user avatar
0 votes
1 answer
116 views

Doubts on solution of Longest run of heads problem

There are some steps that I don't understand in the following problem, It would be great it someone could clear them up, I've been days on this: How is the first inequality in (1.15) derived? What ...
some_math_guy's user avatar
0 votes
0 answers
325 views

Cramer Condition

I was reading the book Technical Incerto - Statistical Consequences of Fat Tails by Nassim Nicholas Taleb, in this book the autor writes the following (page 28): "Membership in the ...
CREZPO's user avatar
  • 3
0 votes
1 answer
26 views

Large deviation principle continues to hold when rate function is replaced by its lower semicontinuous regularization

Consider Lemma Suppose $I$ is a function such that (2.1) holds for all measurable sets A. Then (2.1) continues to hold if $I$ is replaced by $I_{\text{lsc}}$ proof: $I_{lsc}\le I$ and the upper bound ...
some_math_guy's user avatar
0 votes
1 answer
45 views

Basic probability arguments applied to find a lower bound of the average length of a decipherable code

I am reading A Course on Large Deviations with an Introduction to Gibbs Measures by Firas Rassoul-Agha and Timp Seppelainen. On section 1.1 they apply the noiseless coding theorem to find a lower ...
some_math_guy's user avatar
2 votes
0 answers
56 views

Large deviation principle for small values of the maximum of the absolute value of a random walk

Let $X_i$ be an i.i.d sequence of symmetric real random variables with variance 1 and $S_n = X_1 + \dots + X_n$. Let $Z_n = \max_{1 \leq k \leq n } (|S_k|)$. $Z_n$ is typically of the order of $C \...
Nathan's user avatar
  • 21
0 votes
0 answers
51 views

Distribution of limit of empirical measures with noise

Suppose that we have a sequence of i.i.d. random variables $X_1,X_2,...$ on $\mathbb{R}^2$ with probability distribution $\mu$ and define random empirical measures as $$\mu_n=\frac{1}{n}\sum_{k=1}^n \...
MathStudent's user avatar
2 votes
1 answer
96 views

Limiting distribution for proportion of MVN components exceeding fixed threshold

Let $X_i$ be the coordinates of a centered $n$-variate normal distribution satisfying $$ \mathrm{cov}(X_i,X_j) = \begin{cases} 1 & \text{if }\; i=j \\ a & \text{if }\; i\neq j \end{cases}, $$ ...
A.S.'s user avatar
  • 93
2 votes
1 answer
153 views

Is McDiarmid's Inequality ever tight?

I have seen over and over McDiarmid's inequality, which I will now re-state for ease for reference (in its most common version): Let $X_1,\ldots,X_n$ be independent random variables and let $f:\...
user1868607's user avatar
1 vote
0 answers
42 views

Use Large Deviation to estimate $\mathbb{P}(\sum_{k=1}^n X_k\geq 1)$

In a problem I'm working on, I'm asked to estimate, for each $n\in\mathbb{N}$, $\mathbb{P}(\sum_{k=1}^n X_n\geq 1)$ using Large Deviation where $X_1,X_2,\ldots$ are IID and uniformly distributed on $[...
mathmd's user avatar
  • 528
3 votes
2 answers
136 views

Prove that $ \lim_{t\to\infty} \frac{\int_{-\infty}^\infty\rho_t(x)\,e^{xt}\cos(\omega xt)\, dx}{\int_{-\infty}^\infty\rho_t(x)\,e^{xt}\, dx}=0.$

I have a continuous family of functions $\rho_t(x)$ that converge pointwise to a Gaussian $$ \lim_{t\to\infty}\rho_t(x) = \frac{1}{\sqrt{2\pi}}e^{-x^2/2}. $$ I would like to prove that $$ \lim_{t\to\...
stochastic's user avatar
  • 2,618
2 votes
2 answers
115 views

Large deviation theory standard normal cdf

I'm reading this paper, and followed the derivation up to 2.4. However, I am not able to understand how they derived 2.4. This implies that $$\lim_{N \rightarrow \infty} - \frac{2}{N} \log \left( \Phi\...
Jackdaw's user avatar
  • 151
5 votes
1 answer
90 views

How much could rearrangements affect Hoeffding's inequality?

Suppose $X,X_1,X_2,X_3\dots$ is a $\mathbb{P}$-i.i.d. family of $[-1,1]$-valued random variables with $\mathbb{E}[X] = 0$. By Hoeffding's inequality, we know that \begin{equation*} \forall T \in \...
Bob's user avatar
  • 5,783
2 votes
0 answers
76 views

Hoeffding's type inequality for isotonic regression

Let $n \in \mathbb{N}$ and let $0 \le y_1 \le \dots \le y_n \le 1$. Suppose that $(Y_{k,t})_{k\in\{1,\dots,n\}, t\in\mathbb{N}}$ is a family of independent random variables such that, for each $k\in\{...
Bob's user avatar
  • 5,783
3 votes
1 answer
133 views

Recurrent random walks with bounded local time at each vertex

Let $c_{n,k}$ be the number of simple random walk trajectories of $n$ steps in $\mathbb{Z}$ starting from the origin such that each vertex is visited at most $k \in \mathbb{N}$ times and define $\mu_k ...
QuantumLogarithm's user avatar
1 vote
0 answers
67 views

proving or disproving a certain inequality

In the attempt of proving a large deviations result, the following quantity pops up: $$H(\delta,h):= \frac{\frac{1}{2\alpha}(2\alpha-8\delta)+ \frac{4}{\alpha}\frac{1}{1-\gamma}\delta^{1-\gamma}}{h^{(\...
Giuseppe Tenaglia's user avatar
0 votes
1 answer
58 views

limit of the integral $\lim_{N \to \infty} \int_b^{\infty} f_N(x) x dx = 0$

Consider a sequence of functions $f_N(x)$ for which I know $\limsup_{N \to \infty} \frac{1}{N} \log f_N(x) = -g(x)$, where $g(x)$ is positive, continuous on $(a, \infty)$, and increases to infinity ...
Rostam22's user avatar
  • 504
3 votes
0 answers
61 views

Is recycling samples better than drawing fresh ones?

At a high level, I am wondering if in a sequential process it is better to reutilize samples even if these samples have been used to make past decisions. Let me formalize my doubts in a toy example ...
user332582's user avatar
13 votes
2 answers
269 views

Can we control the distance between the empirical and theoretical mean on the whole trajectory any better than using Hoeffding and a union bound?

Suppose $X,X_1,X_2,X_3\dots$ is a $\mathbb{P}$-i.i.d. family of $[-1,1]$-valued random variables with $\mathbb{E}[X] = 0$. Hoeffding's inequality implies that \begin{equation*} \forall T \in \...
Bob's user avatar
  • 5,783
0 votes
1 answer
117 views

How well is a binomial distribution with $N=100,000$ approximated by a normal distribution?

When we consider a binomial distribution with large $N$ and $p=0.5$, this is approximately equal to a normal distribution with mean $\frac12N$ and standard deviation $\frac12\sqrt{N}$. However, ...
Riemann's user avatar
  • 717
1 vote
0 answers
67 views

Saddle point method and radius of convergence

I have a question concerning the convergence of the saddle point method. Applying the method to a function $\rho(x)$, defined as \begin{align} \rho(x) = \frac{1}{2\pi}\int dk\, e^{\kappa f(k,\sigma)}, ...
Arthur Faria's user avatar
1 vote
1 answer
123 views

Expectation and variance of homomorphism density into Erdős–Rényi

I am reading "Large deviations for Random Graphs" by Sourav Chatterjee. The exercise (6.3) asks the following question. Let $G_{n, p}$ be the Erdős–Rényi random graph on $n$ vertices with ...
Raghav's user avatar
  • 3,071
1 vote
0 answers
58 views

Upper bound the probability that the maximum of i.i.d. r.v.'s (e.g. busy periods) exceeding a threshold

Suppose that $B_1, B_2,\ldots, B_n$ are a series of positive independent and identically distributed random variables. The moment generating function (MGF) of $B_i$'s is known, denoted as $M_{B}(\...
leeyee's user avatar
  • 317
1 vote
1 answer
147 views

Show that h is lower semicontinuous

The question is as follows: Let C_n be a sequence of probability measures on a metric space $S$, and $f:S\rightarrow[0,\infty]$ a function with the property that for all $x\in S$ we have $\lim_{\...
lauge's user avatar
  • 13
0 votes
0 answers
75 views

large deviation, contraction principle

Let $X_1, X_2, ... , X_n$ be i.i.d. normal random variables with mean $0$ and variance $1$. I want to show that the random variables $Y_n := 1/(2n^2) \sum_{i,j =1}^n X_i X_j$ satisfy a large ...
willwissen's user avatar
1 vote
0 answers
125 views

Surface order large deviation in Ising ferromagnet

Background: A familiar behaviour of independent and identically distributed (i.i.d.) random variables $X_1, X_2,\ldots X_n$ is concentration: the probability that the sum $X_1+X_2+\ldots X_n$ exceeds $...
anurag anshu's user avatar
1 vote
0 answers
29 views

Large deviation rate function for the upper tale of subgraphs count in Erdos-Renyi graphs

Let $H_1,\cdots,H_k$ be $k$ fixed subgraphs on $r_1, \cdots, r_k$ vertices, respectively. Let $T_{1,n}, \cdots , T_{k,n}$ be the number of non-induced copies of $H_1,\cdots,H_k$ in an Erdos-Renyi ...
user3350919's user avatar
2 votes
0 answers
275 views

Cramers theorem for large deviations

Let $(X_n)$ be real-valued i.i.d. random variables such that the cumulant generating function $\Lambda(t):=\log E e^{tX_1}$ is finite for all t and let $S_n:=\frac{1}{n}(X_1+...+X_n)$ denote the ...
user avatar
2 votes
0 answers
448 views

Concentration inequality for Lipschitz Function

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
0 votes
0 answers
30 views

Prove a conclusion of LDP: $\frac{1}{n}\log P(|\hat{S}_n|\geq\delta)\xrightarrow{n\xrightarrow{}\infty}-\frac{\delta^2}{2}$ [duplicate]

I plan to learn something about Large Deviation Principle (LDP). I am reading the book Large Deviations Techniques and Applications and immediately confused by a problem in the first page. The ...
Wannier's user avatar
  • 31
2 votes
0 answers
36 views

How to calculate large deviations for functions of vectors on the n-sphere with delta functions?

I am copying the setup from Sec 2.5 of these notes describing large deviations of an overlap matrix: Let $\sigma_1,\cdots,\sigma_k\in\mathbb{R}^n$, with $k$ fixed and $n\rightarrow\infty$, and $\...
Lute mansion's user avatar