2
$\begingroup$

I am trying to solve a complicated probability problem related to Shannon Entropy.

Let $(E,p)$ be a finite set with a probability measure $p$ on $E$. $E^n$ is given the probability measure $p^n(x_1, ..., x_n) = p(x_1)...p(x_n)$.

For all $\varepsilon \in \mathopen]0,1[$, denote $$S_\varepsilon(n) = \inf\{\textbf{Card}(A) | A \subset E^n \text{ such that } p^{ n}(A) \geq 1 - \varepsilon\}.$$ Prove that $\frac{1}{n} \log(S_\varepsilon(n))$ converges to a limit independent of $\varepsilon$ when $n \to \infty$, and give an expression of this limit.

It is easy to obtain that in the case of a uniform measure this is $\log(|E|)$. It is also possible to obtain an asymptotic upper bound on $\frac{1}{n} \log(S_\varepsilon(n))$ given by $-\log(p_1)$ where $p_1$ is the maximum probability of an element of $E$. However, I'm struggling to find the limit : a hint in the exercise says this is related to the Shannon entropy of the measure $p$. Would anyone have a clue on how to go further ? Many thanks !

Improve this question
$\endgroup$
2
  • 1
    $\begingroup$ For fixed $m=|A|$ the maximal measure of $A$ is obtained if you take $m$ points $x\in E^n$ with maximal possible $p^n(x)$. For studying how many points satisfy the inequality $p^n(x)>\alpha^n$ for certain fixed $\alpha$ and what is the measure of such points, use law of large numbers. $\endgroup$
    – Fedor Petrov
    Commented May 23, 2022 at 9:11
  • $\begingroup$ Thanks for your insight, solved it :). $\endgroup$
    – Raphaël Kalfon
    Commented May 23, 2022 at 12:47

0

Reset to default

You must log in to answer this question.

Browse other questions tagged .