5
$\begingroup$

How can I randomly generate a probability mass function such that the entropy of a random variable that follows that probability mass function is a specific value $h$?

Basically, I need to randomly generate a probability distribution over $n$ states with probability $p_i$ of being in state $i$. We can represent the distribution as a vector: $\vec{p}={p_1,p_2,p_3,...p_n}$ such that:

$$\sum_{i=1}^n p_i\ =\ 1$$

and

$$Entropy(\vec{p})=-\sum_{i=1}^n p_i\ log_2(p_i)\ =\ h$$

for a known $h$ between $0$ and $log_2(n)$. Specifically, I know $h$ and I want to randomly select $n$ values that satisfy the above conditions for that $h$.

The set of values ${p_1,p_2,p_3,...p_n}$ should be uniformly distributed. In other words, the probability density function of a point should match the probability density function of a point uniformly distributed on a simplex. See this post about randomly generating points on a simplex. To put it in formal terms, the distribution should be uniform in the sense that it will be the same as though the point were generated through rejection sampling of points on the simplex where any point $\vec{p}$ is rejected if outside of the $Entropy(\vec{p})$ is outside the range range $[h-\epsilon,h+\epsilon]$ for an infinitesimally small $\epsilon$.

Update: If we raise each element of $\vec p$ to a power $x$ and then normalize the result by scaling it so that it sums to one, then we can adjust the entropy arbitrarily (provided that $\vec p$ doesn't represent an exactly uniform distribution). Based on this, I think we can randomly generate a point on the simplex and then just raise it to a power to adjust the entropy to the desired value. Does anyone know how to prove that this won't lead to a bias when compared to rejection sampling?

$\endgroup$
  • $\begingroup$ If $h$ is not choosen to get tye maxent distribution, that condition will not uniquely define a probability distribution. $\endgroup$ – kjetil b halvorsen Apr 23 '17 at 21:44
  • $\begingroup$ Why do you say you want to randomly generate $x_i$? Do you mean that you want to be able to randomly generate samples from some fixed distribution with an entropy of $h$? $\endgroup$ – πr8 Apr 23 '17 at 21:54
  • $\begingroup$ No - I want to randomly generate a distribution with entropy $h$ $\endgroup$ – J. Antonio Perez Apr 23 '17 at 22:14
  • $\begingroup$ Okay, I see now. A couple of points, 1) it's probably better to write $x_1, \cdots, x_n$ as $p_1, \cdots, p_n$, to suggest more explicitly that they're probabilities, 2) your task basically boils down to sampling from a Dirichlet distribution, conditioned to have a fixed entropy $h$. This seems intuitively tricky to me - conditioning on having entropy exactly $h$ is a $0$-probability event, which is obviously tough, and conditioning on having entropy close to $h$ (within an $\varepsilon$ tolerance) is definitely possible with rejection sampling, but probably slow. I'll have a think about it. $\endgroup$ – πr8 Apr 23 '17 at 22:20
  • $\begingroup$ I rewrote it slightly to make it clearer. If $h$ is close to zero and $n$ is large, then rejection sampling to even get close to $h$ is so slow as to be untenable. $\endgroup$ – J. Antonio Perez Apr 23 '17 at 22:28

Your Answer

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

Browse other questions tagged or ask your own question.