2
$\begingroup$

I would like to construct a sequence of discrete random variable $X_2, X_3,...,X_n,...$, where $X_n \in\{0,1,2,...,n-1\}$. Given any $\epsilon \in (0,1)$, its Shannon entropy and min-entropy should satisfy the following relationships

\begin{cases} H(X_n)\geq(1-\epsilon)\log_2(n)\\ H_{min}(X_n)=const \end{cases} for all $n\geq\mathbb{N}_{\epsilon}$ and some $const > 0$.

My understanding is that the Shannon entropy indicates the underlying distribution should be approximately uniform. And the min-entropy suggests that the largest possibility of $X_n$ should be $2^{-const}$. But I am stuck with coming up with such a distribution. Is there anyone who could provide some hints?

$\endgroup$

2 Answers 2

3
$\begingroup$

Since the OP may be interested in what $\epsilon$ are achievable I am providing this alternative to the other answer, where it is correctly stated:

If you fix the maximal atom (say, $p$) of a distribution $\mu$ supported by $n$ points, then its entropy is maximal when all the remaining atoms have the same weight $(1-p)/(n-1)$.

Also note that $$ p\geq \frac{1-p}{n-1} \iff np\geq 1\iff p\geq \frac{1}{n} $$ so that $p$ is indeed the maximal atom of $\mu.$

This means that one actually obtains the equality below for the Shannon entropy: $$ H(\mu) = -p\log p - (1-p)\log(1-p) + (1-p)\log(n-1), $$ when $p$ is fixed which gives $$ H(\mu) = H_2(p) + \left(1-p\right)\log(n-1) $$ or $$ H(\mu) \geq \left(1-p\right)\log(n-1)\sim \left(1-p\right)\log n \quad (1) $$ where $f(n)\sim g(n)$ denotes that $\lim_{n\rightarrow \infty} \frac{f(n)}{g(n)}=1.$ This means that for $n$ large enough you can pick any $\epsilon \geq p$ for which $$ H(\mu)\geq (1-\epsilon) \log n $$ is indeed satisfied.

Depending on what application you have in mind, this may suffice.

$\endgroup$
2
  • $\begingroup$ Really appreciate your effort in helping me out! Thanks a lot! $\endgroup$
    – Luis
    Oct 15, 2021 at 3:22
  • $\begingroup$ no problem. you can accept the answer if iit is satisfactory $\endgroup$
    – kodlu
    Oct 15, 2021 at 3:33
2
$\begingroup$

Such a family doesn't exist. If you fix the maximal atom (say, $p$) of a distribution $\mu$ supported by $n$ points, then its entropy is maximal when all the remaining atoms have the same weight $(1-p)/(n-1)$. Whence $$ \begin{aligned} H(\mu) &\le -p\log p - (1-p)\log\frac{1-p}{n-1} \\ &= -p\log p - (1-p)\log(1-p) + (1-p)\log(n-1) \;, \end{aligned} $$ which grows slower than $(1-\epsilon)\log n$ for sufficiently small $\epsilon$.

$\endgroup$
1
  • $\begingroup$ Great hints, thank you so much! $\endgroup$
    – Luis
    Oct 15, 2021 at 3:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.