10 ms·

> Interestingly, this is the best possible approach, whether we know the bias of the input bit stream or not. Would love to see a proof of that. It feels a bit

> Interestingly, this is the best possible approach, whether we know the bias of the input bit stream or not. Would love to see a proof of that. It feels a bit unintuitive to me. (But on second thought that might be because I’m thinking of cases of correlated bits.)

LegionMammal978 2y ago
In general, I think you could show that an 'arithmetic coding' approach is optimal, if the distribution of each bit given the previous bits is known. From there, you'd just have to show that the von Neumann approach for i.i.d. bits is no worse on average.
- Darmani 2y ago
  This is correct, and I came to the comments to say the same thing. It takes some work to implement without arbitrary-precision floating point, but arithmetic coding can make use of the full entropy in the input stream, whereas the approach in the article discards a lot of information.
  - bjornsing 2y ago
    I had this thought too. But can you be sure that there won’t be any statistical patterns / correlations in the output bitstream with that approach?
atq2119 2y ago
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.
- ralegh 2y ago
  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.
- deleted 2y ago
  [deleted]
- contravariant 2y ago
  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.
- Maro 2y ago
  OP here. Thanks for the comment. I'm not a mathematician, will double-check my wording/phrasing on this.
  - Maro 2y ago
    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..
- bjornsing 2y ago
  That’s a good counter example. :) Thanks.

LegionMammal978 2y ago

In general, I think you could show that an 'arithmetic coding' approach is optimal, if the distribution of each bit given the previous bits is known. From there, you'd just have to show that the von Neumann approach for i.i.d. bits is no worse on average.

Darmani 2y ago
This is correct, and I came to the comments to say the same thing. It takes some work to implement without arbitrary-precision floating point, but arithmetic coding can make use of the full entropy in the input stream, whereas the approach in the article discards a lot of information.
- bjornsing 2y ago
  I had this thought too. But can you be sure that there won’t be any statistical patterns / correlations in the output bitstream with that approach?

atq2119 2y ago

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.

ralegh 2y ago
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.
deleted 2y ago
[deleted]
contravariant 2y ago
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.
Maro 2y ago
OP here. Thanks for the comment. I'm not a mathematician, will double-check my wording/phrasing on this.
- Maro 2y ago
  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..
bjornsing 2y ago
That’s a good counter example. :) Thanks.