New answers tagged

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