Let $(\Omega,p)$ be a finite space with $p$ a probability defined on this space.
Let $p^{\otimes n}(x_1,\ldots , x_n)=p(x_1) \ldots p(x_n)$ for all $(x_1,\ldots , x_n)\in\Omega^n$.
For $\varepsilon\in ]0,1[~$, we define $S_{\varepsilon}(n)=\inf\bigl\{\mathrm{Card}(A) \mid A\subset\Omega^n ~ \text{and} ~ p^{\otimes n}(A)\geqslant 1-\varepsilon \bigr\}$.
Show that $\displaystyle\lim\limits_{n\rightarrow +\infty}{\frac{\log S_{\varepsilon}(n)}{n}}=-\sum_{x\in\Omega}{p(x)\log p(x)}$ for all $\varepsilon \in]0,1[~$.
Thank you for your help.
The idea is that roughly $e^{H n}$ elements of $\Omega^n$ each have mass roughly $e^{-Hn}$, i.e. $\Omega^n$ gets its total mass from an exponentially small number of elements ($H := -\sum_{x \in \Omega} p(x)\log(p(x))$). Those elements are the ones that have roughly $p(x)n$ elements being $x$, for $x \in \Omega$.
Write $\Omega = \{x_1,\dots,x_k\}$. We first show $\liminf_{n \to \infty} \frac{\log S_\epsilon(n)}{n} \ge H$. Fix any $m_1,\dots,m_k \in [n]$ summing to $n$. Let $\lambda_i = \frac{m_i}{n}$ for each $i$. Then, using Stirling's approximation, $$p^n\left(\{(y_1,\dots,y_n) \in \Omega^n : m_i = \#\{1 \le j \le n : y_j = x_i\} \text{ for each } 1 \le j \le k\}\right)$$ $$ = \frac{n!}{(\lambda_1 n)!\dots (\lambda_k n)!} p(x_1)^{\lambda_1 n}\dots p(x_k)^{\lambda_k n} \sim \frac{\sqrt{2\pi n} \frac{n^n}{e^n}}{\sqrt{2\pi \lambda_1 n}\frac{(\lambda_1 n)^{\lambda_1 n}}{e^{\lambda_1 n}}\dots \sqrt{2\pi \lambda_k n}\frac{(\lambda_k n)^{\lambda_k n}}{e^{\lambda_k n}}}p(x_1)^{\lambda_1 n}\dots p(x_k)^{\lambda_k n}$$ $$= cn^{-k/2+1}\left(\frac{p(x_1)}{\lambda_1}\right)^{\lambda_1 n}\dots \left(\frac{p(x_k)}{\lambda_k}\right)^{\lambda_k n} \le e^{n\left[\lambda_1 \log\frac{p(x_1)}{\lambda_1}+\dots+\lambda_k\log\frac{p(x_k)}{\lambda_k}\right]}.$$ Now, $\lambda_i := p(x_i)$ is the unique maximizer of the final expression with the property that for all $\delta > 0$ there is some $\delta' > 0$ so that if there is some $i$ with $|\lambda_i-p(x_i)| > \delta$, then $\lambda_1\log\frac{p(x_1)}{\lambda_1}+\dots+\lambda_k\log\frac{p(x_k)}{\lambda_k} \le -\delta'$. In other words, $p^n(A_{m_1,\dots,m_k}) \le e^{-\delta' n}$ if there is some $i$ with $|m_i-p(x_i)n| \ge \delta n$, where $A_{m_1,\dots,m_k} := \{(y_1,\dots,y_n) \in \Omega^n : m_i = \#\{1 \le j \le n : y_j = x_i\} \text{ for each } 1 \le j \le k\}$. Therefore, $$\sum_{\substack{(m_1,\dots,m_k) \in [n]^k \\ m_1+\dots+m_k = n \\ |m_i-p(x_i)n| \ge \delta n \text{ for some } 1 \le i \le k}} p^n(A_{m_1,\dots,m_k}) \le n^k e^{-n\delta'}$$ is exponentially small. For $m_1,\dots,m_k$ summing to $n$ with $|m_i-p(x_i)n| \le \delta n$ for each $1 \le i \le k$, it holds that $$p^n(y_1,\dots,y_n) = p(x_1)^{\lambda_1 n}\dots p(x_k)^{\lambda_k n} \le e^{-nH+n\delta[\log(p(x_1))+\dots+\log(p(x_k))]}.$$ whenever $(y_1, \ldots, y_n)\in A_{m_1\ldots m_k}$. Therefore, if $p^n(A) \ge 1-\epsilon$, then $$\text{Card}(A) \ge \frac{1-\epsilon-n^ke^{-n\delta'}}{e^{-nH+n\delta[\log(p(x_1))+\dots+\log(p(x_k))]}}.$$ Taking logs and letting $n \to \infty$ gives $$\liminf_{n \to \infty} \frac{\log \text{Card}(A)}{n} \ge H-\delta[\log(p(x_1))+\dots\log(p(x_k))].$$ Letting $\delta \to 0$ gives the desired inequality.
Now all we have to show is that, for any $\epsilon > 0$, for all large $n$, there is some $A$ with $\log \text{Card}(A) \ge (1-\epsilon)Hn$. To do this, just let $A = A_{p(x_1)n,\dots,p(x_k)n}$ (or $A = \cup_{\substack{(m_1,\dots,m_k) \\ m_1+\dots+m_k = n \\ |m_i-p(x_i)n| \le \delta n}} A_{m_1,\dots,m_k}$ for small $\delta > 0$). The proof that this works is the same Stirling asymptotics done above.