<p>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$.</p>

<p>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.</p>

CC BY-SA 3.0
2015-05-10T23:42:33.700Z
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?
user34061
CC BY-SA 3.0
2015-05-11T01:23:58.963Z
@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.
usul
CC BY-SA 3.0
2015-05-10T22:23:52.647Z
2015-05-10T22:23:52.647Z
usul
<p>$\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$.</p>

<p>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.</p>

<pseudorandomness>
On the definition of pseudoentropy
user34061
# On the definition of pseudoentropy

(Asked by: username_0 on 2015-05-10)

$\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.

**Tags:** pseudorandomness


---

## 1 answers

### Answer by username_1 on 2015-05-10. Score: 3 | Accepted answer

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.

> **Comments:**
> **username_0**: 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?  
> **username_1**: @username_0, 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.  

---

