Why is Chaitin's constant absolutely normal? I have repeadetly seen claims that Chaitin's constant is normal in all bases (e.g. on Wikipedia), and I have also seen some proof sketches (e.g. here), but these only show the idea. For example, the linked proof uses the fact that, if $\Omega$ weren't normal, then we could compress it by a linear number of bits, which already contradicts incompressibility. However, while intuitively true, it isn't at all obvious to me how to, for example, compress the expansion if we knew 90% of digits were 0.
Another thing is that, it's even less clear why abnormality in base 3, say, implies that we can also compress the number in base 2.
I wanted to ask exactly how we can derive the facts about high compressibility of $\Omega$, especially in bases other than 2. If possible, I'd wish the proof to not go around by using equivalent statements of Martin-Lof randomness and alike.
Thanks for your answers!
 A: The answer lies in Shannon entropy and Huffman encoding.
First let's discuss Shannon entropy.  The Shannon entropy (in bits) of a random variable $X$ with possible values $\lbrace x_1, \ldots, x_n\rbrace$ is
$$
H(X) = E(-\log_2(P(X)) = - \sum_{i=1}^n P(x_i)\log_2(P(x_i))
$$
Intuitively, the Shannon entropy represents the average amount of information contained in a given random variable. One can show that this is maximized when the distribution is uniform; a random variable over a set of n elements gives the maximum amount of information on average when the distribution is uniform. Thus
$$
H(X) \le - \sum_{i=1}^n \frac{1}{n} \log_2(\frac{1}{n}) = \log_2(n)
$$
Now let's talk about Huffman encoding.  A binary code is a mapping between a set and finite binary strings.  A binary prefix code is a binary code such that no binary code is a prefix of another binary code; this allows us to simply convert a string of elements to a binary string by replacing each element with its binary code, and there is no need for a marker to denote when one binary code ends and another begins.  A Huffman code is a particular binary code defined by continually "pairing up" lowest probabilities.
For example, say we have distribution over four letters $a,b,c,d$, with $P(a) = .4, P(b) = .3, P(c) = .2$, and $P(d) = .1$.  We first pick the two letters with the lowest two probabilities, which are $c$ and $d$, and pair them up $(c,d)$.  The probabilities are now $P(a) = .4, P(b) = .3, P((c,d)) = .3$.  We pick the lowest two probabilities again, which are for $b$ and $(c,d)$, and pair them up $(b,(c,d))$.  We now have just two sets of letters left, $a$ and $(b,(c,d))$.  We give $a$ the binary code $0$, and $(b,(c,d))$ the binary code $1$. We now unpack the set and give $b$ the binary code $10$ and $(c,d)$ the binary code $11$.  Finally we unpack $(c,d)$ and give $c$ the binary code $110$ and $d$ the binary code $111$.
We define the length of a binary code to be the expected length of the binary string, i.e. if $B(x_i)$ is the binary string for $x_i$ and $l(B(x_i))$ is its length, then the length of the binary code $B$ is
$$
l(B) = \sum_{i=1}^n P(x_i) l(B(x_i))
$$
It's not hard to see that the length of any uniquely decodable binary code cannot be less than the Shannon entropy of the random variable.  One can also prove that the length of the Huffman code is no more than the Shannon entropy plus 1, so 
$$
H(X) \le l(B) < H(X)+1
$$
This may not be good enough, but we can do the following trick: if we are dealing with a sequence of iid random variables $X_i$, rather than encode one at a time, we can encode $m$ at a time.  It's not too hard to prove that the entropy of $X^m$ is $m$ times the entropy of $X$, so letting $H_m$ be a Huffman code for $X^m$, we have
$$
m H(X) = H(X^m) \le l(H_m) < H(X^m)+1 = mH(X) + 1
$$
so the average number of bits we need per random variable is
$$
\frac{l(H_m)}{m} < H(X) + \frac{1}{m}
$$
which can be made as close to $H(X)$ as we want, by simply increasing $m$.  In particular, if $H(X) < \log_2 (n)$, we can construct a Huffman code such that the average number of bits per random variable less than $\log_2(n)$.
Suppose that our constant is not uniformly distributed in base b, i.e. the frequency of digits in its base b representation are not equal. (I know that abnormality in base b does not imply nonuniform distribution in base b, but it does imply nonuniform distribution in some base b^n, so we can just change the base.)  We can think of the digits of the constant as random variables with a distribution matching the frequency of the digits.  Since the distribution is not uniform, the Shannon entropy will be less than $\log_2 (b)$, and therefore from the above we can construct a Huffman coding such that the average number of bits per digit is less than $\log_2(b)$.  We can then construct a program that takes a Huffmann encoding of the first $n$ digits of our constant, and converts the code back to the original digits.  The length of the program will be the length of the code plus a constant overhead, and the length of the code will approach $cn$ where $c < log_2(b)$, so this shows that our constant is compressible.
Now, you ask why a constant compressible in base 3 can be compressed in base 2.  The answer is that we can simply do a base conversion from base 3 to base 2.  Now, a possible hangup is that there is a possibility that when converting to base 2, we wind up with a 0 followed by a long string of 1's at the end, and we cannot preclude the possibility that the correct answer is a 1 followed by a long string of 0's at the end.  But, even though we don't know from the base 3 expansion which version to take, nevertheless one of them is correct, so we can construct two compressed programs for the two possibilities, and one of them will be correct.
