Encoding sequence of unfair coin flips The question: Consider transmitting the results of $1000$ flips of an unfair coin where the probability of heads is given by $p_H$. The information contained in an unfair coin flip can be computed:
$p_H\log_{2}(1/p_H)+(1−p_H)\log_{2}(1/(1−p_H))$
For $pH=0.999$, this entropy evaluates to $.0114.$ Can you think of a way to encode $1000$ unfair coin flips using, on average, just $11.4$ bits? (question from https://web.mit.edu/6.02/www/f2011/handouts/2.pdf)
My wrong answer: I thought that I could encode the location of the bits which turn up tails. Since there are 1000 flips, I could encode every flip using 10 bits ($2^{10}=1024$). taking the average expected length to encode each flip and then multiplying by $1000$ for all the flips gives:
$1000[(0.999)(0)+(0.001)(10)]\\
1000(0.001)(10)\\
10$
But I know that any encoding which averages a smaller length in bits than the entropy must have some ambiguity in the message, so since $10&lt;11.4$, what information is my coding system missing?
The problem is the assumed knowledge that the receiver needs to have. In your coding scheme you assume that the receiver knows that you transmit exactly $1000$ symbols. If the receiver didn't know that, there is no way to distinguish the following two cases:

$2$ tails at certain positions inside one block of $1000$ symbols
$2$ tails at the same positions as for case 1. but in two different blocks

So your coding scheme is incomplete and that's why you end up with an average bit rate less than what we would expect from the entropy of the source.
Also note that your scheme, even though incomplete, will exceed the minimum possible bit rate for larger block lengths. That limit of the block length beyond which the required rate becomes larger than the minimum possible rate can be computed as the smallest integer value of $N$ satisfying
$$p\lceil\log_2(N)\rceil&gt;-p\log_2(p)-(1-p)\log_2(1-p)\tag{1}$$
where $p$ denotes the probability of a tail.
Apart from the above, you would also need to assign a codeword to the case that there is no tail inside a given block. Of course, for this likely case it would be wise to choose a short codeword.