The typical set $S$ is given as consisting of all sequences $x$ with at most three 1s.

Here $x \in ${0,1}$ ^{200} $ and $P(0) = 0.99$

We can use $\log_{2}|S|$ to encode such sequences. And that is the best one can do in case of equal length codewords I think.

But how to get the minimum expected no. of bits required for encoding the sequences in $S$ ?

Should I think in terms of the ceil of the entropy of the least probable one of these sequences times the number of such sequences?

  • $\begingroup$ You should compute the number of sequences in $S$. You then need to pick one out of those, which you can do in $\log_2 |S|$ bits. You may need to find a mapping from the strings of $\log_2 |S|$ bits to the sequences in $S$. I don't think it is clear whether that is required. $\endgroup$ May 20, 2021 at 14:00
  • $\begingroup$ @RossMillikan Can I do better( lesser) than $\log_2 |S|$ bits in the encoding scheme ? $\endgroup$
    – user766787
    May 20, 2021 at 14:05
  • $\begingroup$ No, you can't. You should recognize that $n$ bits give you $2^n$ sequences, so can specify one in $2^n$. The formula computes that $n$ $\endgroup$ May 20, 2021 at 14:08
  • $\begingroup$ @RossMillikan Even not for differing codeword lengths? Can I use something like Huffman coding here? $\endgroup$
    – user766787
    May 20, 2021 at 14:14
  • $\begingroup$ We haven't talked of codewords here at all. You have a list of possible strings. If there were $1024$ of them, you could use $10$ bit strings to indicate one of them. It doesn't matter what the lengths of the $1024$ strings are, just how many of them there are. In your problem, all the strings of $S$ are the same length, $100$ bits. The strings used to indicate one of them will also have the same length (within $1$ if the log doesn't come out evenly). $\endgroup$ May 20, 2021 at 14:19

1 Answer 1


You should have specified you were interested in minimizing the expected codeword length. Lets look at arbitrary $n,$ and consider $\{0,1\}^n.$

In that case you can assign a 1 bit codeword, say $0$, to the all zero sequence which has probability ($p=P(0)$) $$ p^n, $$ In general, you can specify all weight $w$ codewords with $$ W_w = \left\lceil \log_2 \binom{n}{w}\right\rceil $$ bits for $w=1,2,3.$ You have 4 classes of typical sequences $W_0,W_1,W_2,W_3$ and you can specify which class you have with a prefix of 2 bits [note for $p=0.99$ there may be a slightly more efficient use of the prefix but I don't think so since $.99^{200}$ is already a small number]. For the all zero codeword just use the prefix 00 and no extra bits are necessary.

So there exists a good code with small expected codeword length $$ \overline{L}=2+\sum_{w=1}^3 W_w \binom{n}{w} p^{(n-w)}(1-p)^w. $$

Using $\log_2 |S|$ I get 20.347 bits are needed so 21 bits are needed.

The expectation above is approximately 9.64 bits so you can get an expected codeword length of 10+2=12 bits, if I have calculated correctly (please check).

  • 1
    $\begingroup$ Yes, checked it. Thanks ! $\endgroup$
    – user766787
    May 22, 2021 at 9:47

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .