# Using all the entropy in an biased bit

Suppose we have $n$ bits of random-looking data, and we want to encode it in such a way that instead of 1/2 the bits being 1's, we have (say) 3/4 the bits being 1's. The entropy of each bit in the new encoding is $-0.75\log_2(0.75)-0.25\log_2(0.25)\approx 0.81$, so we should be able to do it in about $1.23n$ bits.

(By 3/4 the bits being 1's, I mean that each bit should be indistinguishable from an event that happens with probability 3/4; as opposed to a long block of unbiased random bits followed by an equal length block of 1's.)

We could try, for each bit, put the next bit of the original data with probability 1/2, and put a 1 with probability 1/2. Then somehow include extra information about which bits encode the original data, and which are filler. But this reqiures at least $2n$ bits, well above the theoretical minimum. So how can the minimum actually be achieved?

Suppose you want exactly $3/4$ of the bits to be 1. If the encoded vector is of length $m$, it can be identified as a subset of $\{1,\ldots,m\}$ of size $(3/4)m$, of which there are $\binom{m}{(3/4)m}$. If $\binom{m}{(3/4)m} \geq 2^n$ then you can encode every $n$-bit string as such a subset using the technique of binomial encoding. Since $\binom{m}{(3/4)m} \approx 2^{mh(3/4)}$, this works as long as $m \gtrsim n/h(3/4) \approx 1.23n$.
Binomial encoding relies on Pascal's identity $$\binom{a}{b} = \binom{a-1}{b-1} + \binom{a-1}{b}.$$ To encode a number $x$ in the range $[0,\binom{a}{b})$, we act as follows:
1. If $x < \binom{a-1}{b-1}$ then we recursively encode $x$ as a subset $S$ of $\{1,\ldots,a-1\}$ of size $b-1$, and output $S \cup \{a\}$.
2. If $x \geq \binom{a-1}{b-1}$ then we recursively encode $x - \binom{a-1}{b-1}$ as a subset $S$ of $\{1,\ldots,a-1\}$ of size $b$, and output $S$.