$\mathbf{Definition.}$ A random variable $X$ has pseudoentropy $k$ if it is computationally indistinguishable from a random variable $Y$ with $H(Y) = k$, where $H(Y)$ is the Shannon entropy of $Y$.

By this definition, can we say that any random variable has pseudoentropy equals to its Shannon entropy, just because it is computationally indistinguishable from itself? The caveat here is whether or not the definition of computational indistinguishability is still valid when there is only one random variable, not two.


Yes, we can always say that $X$ has pseudoentropy at least $H(X)$. You can take $Y$ to be a completely separate, independent random variable that has the same distribution as $X$. Then $X$ and $Y$ are computationally indistinguishable (indeed they are "completely" indistinguishable): $\Pr[A(X) = 1] = \Pr[A(Y) = 1]$ for all algorithms $A$.

Instead of thinking of psuedoentropy as a property of a random variable, maybe it is more helpful to think of it as a property of a distribution. Not a big difference but emphasizes that, for instance, $X$ and $Y$ are never correlated in the definition.

  • $\begingroup$ Suppose $X \sim U_n$ is uniformly distributed over $\{0, 1\}^n$. Then $X$ is unique. How is it possible to take $Y$ to be completely separate, independent variable? For $X$ over $\{0,1\}^n$ with $H(X) < n$, it might be possible to get different $Y$ with $H(Y) = H(X)$. But for the uniform one, it is not. Right? $\endgroup$
    – user34061
    May 10 '15 at 23:42
  • $\begingroup$ @user34061, this is what I was pointing to in the second paragraph. The uniform distribution on $\{0,1\}^n$ is unique, but there can be many random variables that are independent and distributed according to that distribution. Think of $X$ and $Y$ as two different fair coin flips. Each is uniform on $n=2$, so they have the same distribution, but they are independent. $\endgroup$
    – usul
    May 11 '15 at 1: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.