# Non-asymptotic large deviations for a convex set

Let $X_1,\dots,X_n$ be $n$ i.i.d random variables taking values in a Polish vector space $\mathcal{X}$ and with (Borel) probability distribution $\mu$.

For any convex, compact $\Gamma \subset \mathcal{X}$, it can be proved using Sion's minimax theorem (see for example Exercice 4.5.5 in Dembo and Zeitouni) that: $$\forall n \quad \mathbb{P}\left(\frac{1}{n}\sum_{k=1}^{n}{X_k} \in \Gamma\right) \leq e^{-n \inf_{x\in \Gamma}{I(x)}}$$ with $I$ the Fenchel Legendre transform of the moment generating function.

Using the concept of dominating point (see for example the works of Ney), it can also be shown that for any convex, open set $\Gamma$ (and a few more assumptions): $$\forall n \quad \mathbb{P}\left(\frac{1}{n}\sum_{k=1}^{n}{X_k} \in \Gamma\right) \leq e^{-n \inf_{x\in \Gamma}{I(x)}}$$ The additional assumptions are actually needed to ensure the existence of a dominating point which implies a much stronger result than just the inequality. It is not obvious to me whether the additional assumptions are needed if we're just interested in this inequality?

Actually, let me ask a more general question: are there examples of convex (measurable) $\Gamma$ such that: $$\forall n \quad \mathbb{P}\left(\frac{1}{n}\sum_{k=1}^{n}{X_k} \in \Gamma\right) \leq e^{-n \inf_{x\in \Gamma}{I(x)}}$$ doesn't hold?

I eventually found the answer to my question.

The answer is no: take $\nu$ the uniform distribution on $[0,1]$. Let $\hat{\nu}_n$ be the empirical distribution obtained from $n$ samples of $\nu$.

Let $\Gamma$ be the set of all discrete signed measures. It is a convex subset of the set of all signed measures.

For $x \in \Gamma$, $I(x) = KL(x,\nu) = +\infty$ so $\inf_{x \in \Gamma}{I(x)} = +\infty$ and $$e^{-n \inf_{x\in \Gamma}{I(x)}} = 0$$ Yet $$\mathbb{P}\left(\hat{\nu}_n \in \Gamma\right) = 1$$ since the empirical distribution is of course discrete.

(Note that it is possible to find a topology making the space considered a Polish one, see Dembo and Zeitouni for example.)

So topological arguments are needed, at least in the infinite dimensional setting. Still wondering if the result holds in finite dimension though (it does hold in dimension $1$).

• Of course it may be made Polish space, but is our measure concentrated on $\Gamma$ Borel? Jul 12 '15 at 11:36

Measurable set is sigma-compact modulo 0, and in finite dimension convex measurable set is sigma-convex_compact modulo 0 since convex hull of a compact set is compact again. This allows to reduce (in finite dimension) the case of any convex set to convex compact set.