Entropy of a byte in a compression algorithm?
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.