New answers tagged information-theory
2
Huffman's algorithm is known to be optimal, that is, produce a code which minimizes the average codeword length (with respect to the input distribution).
Let us notice now that there is a code in which each codeword has length $\lceil \log n \rceil$, and in particular the average codeword length is $\lceil \log n \rceil$ (with respect to any distribution). ...
3
Here is an informal proof, which you can try to formalize.
Suppose that we’re looking for 1 in an array of length $n$ of 0s and 1s. We consider the following distribution: each element is 1 with probability $1/n$. (You can also try your luck with the uniform distribution over all arrays with a single 1.)
Given the transcript of the algorithm, you can ...
1
I hadn't heard that term before, but from context, I believe it is talking about codes over a finite alphabet (i.e., discrete random variables as opposed to continuous random variables).
Top 50 recent answers are included
