Entropy of a byte in a compression algorithm? I have a (fixed, long) string of bytes that I want to compress, $C$. I use a typical (good) lossless compression algorithm on it, to generate a compressed string of bytes, $C^*$. Then I define a random variable $X$ which samples a bit uniformly at random from $C^*$. Should I expect Prob[X = 0] to be close to 1/2?


A good compression algorithm is defined as one that achieves good information-theoretic bounds, such as Shannon coding.
A counter-example would be a compression algorithm that achieves, on average, a non-equal proportion of bits as the length of $C$ goes to infinity, where the contents of $C$ itself are chosen uniformly at random among all strings of that length. 
This is to say the following: Let $S(n)$ be a string of length $n$ chosen uniformly at random. Let $C(s)$ be the result of the compression algorithm with input $s$. Let $X(s)$ denote the proportion of '0's in the string $s$. Then the question is whether $X(C(S(n)))$ necessarily converges to $1/2$ as $n$ goes to infinity.
I define a random variable X which samples a bit uniformly at random from C∗. Should I expect Prob[X = 0] to be close to 1/2?


Roughly, yes. The compression algorithm is lossless (bijective), so the entropy of the input is the same as the entropy of the output. Under your hypothetical, the output's length is asymptotically larger than its entropy, so asmyptotically larger than the input's entropy. So the compression algorithm does not reach the Shannon entropy bound.

To see one somewhat-formal argument for why the output's length is asymptotically larger than its entropy, suppose for simplicity the length is $n$ and formalize your hypothesis by, e.g. supposing the fraction of ones is always at least $p$, with $p &gt; 0.5$. Using a Chernoff bound, the total number of such strings is at most $q 2^n$ where $q = 2^{-cn}$  for some constant $c &gt; 0$, and so the maximum entropy of the output is at most the log of this number, which is $n(1-c)$, which is significantly smaller than $n$.

OK, this isn't totally formal, but I hope it's a useful answer.