New answers tagged information-theory
1
The function wouldn't be one-to-one otherwise.
The size of the set in the left is $|A|$, and its image would be of size at most $2^l<2^{H_0}=|A|$, therefore, the function wouldn't be injective and thus you wont be able to de-compress some of the data.
Therefore it will be a lossy-compression for any $l<H_0$.
2
One possible direction is looking at the (computational) hardness of distributions. For example, a family of distributions $\{\mathcal{P}_n\}_{n\in\mathbb{N}}$ where $\mathcal{P}_n$ is a distribution over $\{0,1\}^n$ is called polynomialy-samplable (you can substitute here any other type of time/space restriction) if there exists a probabilistic polynomial ...
2
Suppose that we have a random source $X$, and we wish to encode many independent samples $x_1,\ldots,x_n$ taken from $X$. An compression scheme is an algorithm that converts $n$ samples of $X$ to a binary string in a reversible way. Shannon showed that the optimal compression scheme produces binary strings of length roughly $nH(X)$, where $H(X)$ is the ...
Top 50 recent answers are included
