Proof of Sanov's theorem

Question

I'm trying to understand the proof of Sanov. And there is one part that i don't get. Let $\Sigma$ be a finite set and $\mathcal{M}_1(\Sigma)$ the set of probability measures with the total variation norm $\Vert\nu\Vert=\nu^{+}(\Sigma)+\nu^{-}(\Sigma)$. Define $E_n :=\{ \mu\in\mathcal{M}_1(\Sigma) ; \ n\mu(\{x\})\in\mathbb{N}_0 \ \forall x\in\Sigma\} $. Now let $A\subset\mathcal{M}_1(\Sigma)$ open and $\nu\in A$. Since $A$ is open there exists an $\epsilon>0$ such that $B_\epsilon(\nu)\subset A$. For $n\geq \frac{2\#\Sigma}{\epsilon}$ we have $E_n\cap B_\epsilon(\nu) \not=\emptyset $. How do we construct those probability measures or does it even hold for every measure in $E_n$ with large enough $n$?

Answer 1

Well, assume $\nu=\sum_{x\in \Sigma} a_x \delta_x$ with $\sum_{x\in \Sigma} a_x=1$. Pick some $x_0\in \Sigma$ and define $$ \mu_n(\{x\})=\begin{cases} \frac{ \lfloor na_x\rfloor}{n} & x\neq x_0 \\ 1-\sum_{x\neq x_0} \frac{ \lfloor na_x\rfloor}{n} & x= x_0 \end{cases}, $$ where $\lfloor \cdot\rfloor$ denotes the floor function.

Then, $\mu_n\in E_n$ and \begin{align} \|\nu -\mu_n\|&=\sum_{x\neq x_0} \left(a_x-\frac{\lfloor na_x\rfloor}{n}\right)+1-\sum_{x\neq x_0} \left(\frac{ \lfloor na_x\rfloor}{n}\right)-a_{x_0}\\ &=2\sum_{x\neq x_0} \left(a_x-\frac{\lfloor na_x\rfloor}{n}\right)\\ &\leq \frac{2 |\Sigma|}{n}, \end{align} and your desired result follows readily.