# Questions tagged [large-deviation-theory]

Use this tag for question on large deviations theory

193 questions
Filter by
Sorted by
Tagged with
14 views

• 352
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 ...
43 views

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 ...
• 9,586
1 vote
25 views

• 115
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 ...
• 3,162
97 views

• 939
1 vote
42 views

• 5,783
133 views

• 317
1 vote
147 views

• 397
1 vote
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 ...
• 417
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 ...
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 ...
### 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 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 \$\...