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

It's obviously false. If you know that the bias is 0.5, you can just pass the input stream through unmodified. You can also construct better codes for other biases.


Depends how you define best, I assume best in the article means ‘output is close to 50/50 and independent’, in which case the 01/10 solution is already optimal given the assumptions.

If you define best as the most efficient at converting inputs to outputs as well as the output being 50/50 then there are better ways such as your example.


OP here. Thanks for the comment. I'm not a mathematician, will double-check my wording/phrasing on this.


OP here.

Re-reading this bit, I agree my wording is very clunky. What I meant by "whether we know the bias of the input bit stream or not" was:

[For p≠1/2] whether you know the value of p or not, this is the best approach. Of course, p=1/2 is the trivial case where we can just pass through..


It's worded quite badly, but I think it's the best you can do given 2 independent bits, except for the rare case where 00 and 11 are equally likely.


That’s a good counter example. :) Thanks.




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

Search: