4 ms·

I hate these articles that jump straight into some complex solution without stating the problem clearly... If the problem really is to send a real number using

I hate these articles that jump straight into some complex solution without stating the problem clearly... If the problem really is to send a real number using a single bit (and some shared randomness) then clearly that’s just impossible. Next!

yshklarov 5y ago
But no! The very first sentence clearly states: "In this post, we'll look at the natural problem of how to communicate an estimate of a real value in [0,1], using just 1 bit." The second paragraph sketches the motivation for the problem. How much more exposition do you want from a casual blog post? There's a link to the academic paper if you want full details (you can follow up on the numerous references to other papers, which explain applications.)
- adrian_b 5y ago
  The blog reproduces rather faithfully what the academic paper says. The academic paper is confusing, because it defines the problem as it would have been a singular event, the sender chooses a real number, then sends 1 bit to the receiver and the receiver miraculously guesses the real number. You have to waste time by carefully studying the paper to see that the statistical methods used are meaningless for a singular event, so in fact a large number of transmissions of a single bit are assumed and the accuracy (i.e. the variance) of the estimation of the real number is computed over that very large but unspecified number of transmitted bits. In any real application, the main quality of an estimation algorithm would be determined by how many single bits must be transmitted and received to guarantee a certain accuracy (variance) of the estimation, i.e. a certain number of recovered bits of the real number, but I have lost patience when reading the paper before discovering whether the authors even mention this somewhere. What should be clear for everyone, is that recovering N bits of a real number, i.e. reducing the variance of the estimation to that level, always requires transmitting many more single bits than N. Nevertheless, even if more bits are sent, there are many cases when this is useful, e.g. because losing some single bits or receiving them with errors has little effect, but there may also be other reasons.
asdf3331 5y ago
some of the comments on this article are so embarrassing. It's just a short and clearly written article on a pretty simple and fundamental type of problem in information theory. Similar ideas are the basis for the systems we use in data compression and transmission and error correction among other things. Maybe better to think for a few seconds before dismissing the problem as pointless and claiming to hate it.
- magicalhippo 5y ago
  It describes the problem, but not fully. Either do it properly or link to a complete description. In this case, unlike what the article states as the problem, the point seems not to be how to send a real number using a single bit, but how to aggregate such bits from many agents that measure some shared thing. That's two very, very different things.
asxd 5y ago
The problem is a variation of that, which makes it possible, as explained in the post. The large caveat is that the accuracy is probabilistic, and it’s expected that the receiver is getting many 1-bit from various sensors that are all measuring the same phenomena. It’s a bit like the concept of dithering in images, where visually we can represent shades of grays just by using many 1 bit pixels.
- oh_my_goodness 5y ago
  Yes, it's a variation on the problem ... but sending many bits to the receiver is a really significant variation on just sending one bit. I'm not sure whether so many people would be intrigued to read "How to send a real number using arbitrarily many bits."
  - asxd 5y ago
    I think the motivation here is still compression. You know you’re going to have a bunch of input values coming in, and this is about how to minimize the size of each value. So the overall throughput required does go down in the end.
  - adrian_b 5y ago
    Yes, both the blog and the Arxiv paper are very confusing, because they speak about estimating a real number "Using a Single Bit". It is obvious that there is no way of guessing more than 1 bit of a number after receiving a single bit (unless you have previously established a convention like 0=any_other_number, 1=a_certain_number, when you can estimate many bits when you receive a "1", but no bits when you receive a "0"). Looking at the text of the article, it is obviously that it does not refer to sending "a Single Bit", but to sending "a Single Bit" many times, because only then the variance and the other statistics used by them can be computed. If the problem is rephrased as "How to Send a Real Number Using a Single Bit" at each of many transmissions, then the problem becomes banal and it has been studied for more than 60 years, in the field of analog-digital and digital-analog conversions, under names like "stochastic converters", "delta modulation", "delta-sigma modulation", and a few others, and much better solutions are known than discussed in the article. (The corresponding problem in that field is how to measure an analog signal, i.e. the real number, with a single analog comparator and a single reference value, when you get just 1 bit of information, i.e. whether the measured value is smaller or greater than the reference. The simplest solution is to sum a random noise with the value to be measured, and then compute the average of the 1-bit values, but there are much more sophisticated methods).
magicalhippo 5y ago
> If the problem really is to send a real number using a single bit (and some shared randomness) then clearly that’s just impossible. Next! Not impossible. You can perfectly well send say, pi, by implementing a protocol which sends 1 if the number is pi and 0 if not. And it's about as useful as the mentioned algorithms.

yshklarov 5y ago

But no! The very first sentence clearly states: "In this post, we'll look at the natural problem of how to communicate an estimate of a real value in [0,1], using just 1 bit." The second paragraph sketches the motivation for the problem. How much more exposition do you want from a casual blog post? There's a link to the academic paper if you want full details (you can follow up on the numerous references to other papers, which explain applications.)

adrian_b 5y ago
The blog reproduces rather faithfully what the academic paper says. The academic paper is confusing, because it defines the problem as it would have been a singular event, the sender chooses a real number, then sends 1 bit to the receiver and the receiver miraculously guesses the real number. You have to waste time by carefully studying the paper to see that the statistical methods used are meaningless for a singular event, so in fact a large number of transmissions of a single bit are assumed and the accuracy (i.e. the variance) of the estimation of the real number is computed over that very large but unspecified number of transmitted bits. In any real application, the main quality of an estimation algorithm would be determined by how many single bits must be transmitted and received to guarantee a certain accuracy (variance) of the estimation, i.e. a certain number of recovered bits of the real number, but I have lost patience when reading the paper before discovering whether the authors even mention this somewhere. What should be clear for everyone, is that recovering N bits of a real number, i.e. reducing the variance of the estimation to that level, always requires transmitting many more single bits than N. Nevertheless, even if more bits are sent, there are many cases when this is useful, e.g. because losing some single bits or receiving them with errors has little effect, but there may also be other reasons.

asdf3331 5y ago

some of the comments on this article are so embarrassing. It's just a short and clearly written article on a pretty simple and fundamental type of problem in information theory. Similar ideas are the basis for the systems we use in data compression and transmission and error correction among other things. Maybe better to think for a few seconds before dismissing the problem as pointless and claiming to hate it.

magicalhippo 5y ago
It describes the problem, but not fully. Either do it properly or link to a complete description. In this case, unlike what the article states as the problem, the point seems not to be how to send a real number using a single bit, but how to aggregate such bits from many agents that measure some shared thing. That's two very, very different things.

asxd 5y ago

The problem is a variation of that, which makes it possible, as explained in the post. The large caveat is that the accuracy is probabilistic, and it’s expected that the receiver is getting many 1-bit from various sensors that are all measuring the same phenomena. It’s a bit like the concept of dithering in images, where visually we can represent shades of grays just by using many 1 bit pixels.

oh_my_goodness 5y ago
Yes, it's a variation on the problem ... but sending many bits to the receiver is a really significant variation on just sending one bit. I'm not sure whether so many people would be intrigued to read "How to send a real number using arbitrarily many bits."
- asxd 5y ago
  I think the motivation here is still compression. You know you’re going to have a bunch of input values coming in, and this is about how to minimize the size of each value. So the overall throughput required does go down in the end.
- adrian_b 5y ago
  Yes, both the blog and the Arxiv paper are very confusing, because they speak about estimating a real number "Using a Single Bit". It is obvious that there is no way of guessing more than 1 bit of a number after receiving a single bit (unless you have previously established a convention like 0=any_other_number, 1=a_certain_number, when you can estimate many bits when you receive a "1", but no bits when you receive a "0"). Looking at the text of the article, it is obviously that it does not refer to sending "a Single Bit", but to sending "a Single Bit" many times, because only then the variance and the other statistics used by them can be computed. If the problem is rephrased as "How to Send a Real Number Using a Single Bit" at each of many transmissions, then the problem becomes banal and it has been studied for more than 60 years, in the field of analog-digital and digital-analog conversions, under names like "stochastic converters", "delta modulation", "delta-sigma modulation", and a few others, and much better solutions are known than discussed in the article. (The corresponding problem in that field is how to measure an analog signal, i.e. the real number, with a single analog comparator and a single reference value, when you get just 1 bit of information, i.e. whether the measured value is smaller or greater than the reference. The simplest solution is to sum a random noise with the value to be measured, and then compute the average of the 1-bit values, but there are much more sophisticated methods).

magicalhippo 5y ago

> If the problem really is to send a real number using a single bit (and some shared randomness) then clearly that’s just impossible. Next! Not impossible. You can perfectly well send say, pi, by implementing a protocol which sends 1 if the number is pi and 0 if not. And it's about as useful as the mentioned algorithms.