Hacker Newsnew | past | comments | ask | show | jobs | submitlogin

For certain input distributions, a guaranteed output bandwidth is impossible. For instance, suppose that you had a function that, given a vector of N integers chosen uniformly from (0,1,2), returns a single unbiased output bit. Then, exactly half of the 3^N input vectors would correspond to each output bit. But this is impossible, since 3^N is always odd, so this (0,1,2)-function cannot exist for any fixed N.

Now, suppose that you had a function that turned N input bits with a 1:2 bias into a single bit with no bias. Then you could use this to implement an (0,1,2)-function as above, by collapsing inputs 1 and 2 into input 1. Since such an (0,1,2)-function is impossible, the 1:2-biased function is similarly impossible.

This argument holds for any i.i.d. input source that can be generated from a uniform-integer source with an odd number of possible values.



Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: