Hacker News Reader

Comment by orangea | Hacker News Reader

The question that this person posed is

> At what value for X is there a 50% chance there [exists] a sequence of X-bits in length that hasn't been transmitted yet?

But if I understand correctly, the question that they answered is "At what value for X is there a 50% chance that, given some specific sequence of X bits, that sequence hasn't been transmitted yet?" Wouldn't these two questions have different answers?

Edit (now that I've thought about it more): On top of that, the expected value of a random variable isn't necessarily a value that it has a 50% chance to be. So even my interpretation of this result is wrong.

View on HN

2^n is half of 2^(n+1), so you'd expect that getting 50% coverage of (n+1)-bit sequences would mean that you have 100% coverage of n-bit sequences. In other words, the answer to your question is at most 1 bit lower than the answer given.

But it is slightly more complicated, because this is an example of the Coupon Collector's Problem [1]. It takes about N ln N random samples to cover a set of size N. If there have been 2^74 samples chosen, then we haven't quite gotten enough to cover N = 2^68.

[1] https://en.wikipedia.org/wiki/Coupon_collector%27s_problem

>Wouldn't these two questions have different answers?

Yes, though in practice they're close.

To answer the actual question asked. We can say that there is a length n, such that all sequences S, of length n, cannot be contained in our total bits transferred, B. This is a consequence of the pigeonhole principle.

Naively, this would be B = n * S, and S = 2^n. So B = n * 2^n. Note that we can actually compress things more though, if we assume that in the worst case every window in the internet bit-corpus is unique.

That this is possible isn't immediately obvious, but consider

01, 00110, 0001011100, 0000100110101111000, 000001000110010100111010110111110000 (which, interestingly, isn't in OEIS, but related sequences: https://oeis.org/A052944 and https://oeis.org/A242323 are).

These bitstrings contain, perfectly overlapping, every bitstring of length n, for n from 1-5. In general, it takes 2^n + n - 1 bits to convey every possible bitstring, if you manage to overlap them perfectly (if someone can prove this, please do. I thought it was grey code/hamiltonian path over hypercube related, but I unconvinced myself of that).

EDIT: Someone else mentioned De Brujin sequences, which these are. And they are based on hamiltonian paths, although not over hypercubes :(. And my sequence is on OEIS, as https://oeis.org/A166315, just converted to decimal. /EDIT

So the real answer is just B = 2^n + n - 1, but for n > 15 or so, n - 1 is so small we can ignore it. In other words, our length n is just log(B). Given the assumption in the article of 3.4067e22 bits, the base 2 log of that is...74.85. This is exactly 1 more than what the article says is the point where you'll have seen half the messages. This isn't a coincidence.

Which raises an interesting question that I leave as an exercise to the reader:

Why is the length for which you cannot have conveyed all bit strings exactly 1 bit more than the point where you've conveyed about half of them?

You’re giving the range for a 50% to 100% chance of non-transmission.

But in the spirit of the original question, I’d suppose we want to find n such that the probability of non-transmission is 2^-n, and the expected number of such transmissions is 1? Is that number similarly close?

Reply on news.ycombinator.com