One Bit a Letter
Guess the next letter of a sentence until you get it. How far down your guesses the answer sits measures how much English you already know, in bits, and you will beat the machine.
What it is
A sentence, revealed one letter at a time. You guess what comes next, and keep guessing until you get it. Type, or use the keys under the passage.
How many guesses each letter takes is the measurement. A letter you get first time carried almost no information, because you already knew it. A letter that takes nine goes carried a lot. Averaged over a passage, those guess counts bracket the entropy of English, which is the number Shannon put near one bit a letter in 1951.
A character model plays every letter alongside you and its guesses are scored the same way. It has read ten thousand characters of English. You have read rather more.
How it works
Twenty six letters and a space, so a guess made with no knowledge at all would be worth 4.75 bits. Everything below that’s what you know about English.
Shannon’s bounds come from the distribution of guess ranks. The upper bound is the entropy of that distribution. The lower is a sum over ranks weighted by how the distribution falls away, and it’s the looser of the two. Both are exact for a source with no memory and a guesser who knows it, and both open up when the ranks mix contexts of different difficulty, which is what English is.
The model is a character n-gram with backoff. Backoff is doing more work than the smoothing: on a corpus this small it meets contexts it has never seen constantly, and without shortening the context it would fall back to a blind guess and score worse than a model with no context at all.
Its scores on text it hasn’t been trained on:
| context length | bits a letter | right first time | bracket |
|---|---|---|---|
| 1 | 3.133 | 33.7% | 2.27 to 3.21 |
| 2 | 2.705 | 42.8% | 1.87 to 2.89 |
| 3 | 2.690 | 45.0% | 1.85 to 2.90 |
| 4 | 2.749 | 47.0% | 1.88 to 2.93 |
| 5 | 2.835 | 48.6% | 1.91 to 2.98 |
The corpus is written for this page rather than taken from anywhere, so the repo stays self contained and the number is the entropy of this English rather than of English in general. It’s small on purpose, and the learning curve is what makes that a measurement instead of an apology: the model goes from 3.285 bits at 1,280 characters to 2.690 at 10,241.
Fitting that trend and extending it, reaching 1.2 bits a letter would take about 1.8 million characters. Around 300,000 words. Three or four novels, to arrive where you already are before you have read the first sentence on the page.
What surprised me
The model that guesses right more often scores worse. Look at the table again. Going from three letters of context to five raises the share it gets first time from 45.0 to 48.6 per cent, and makes the bits a letter worse, from 2.690 to 2.835.
Both numbers are correct and they’re measuring different things. A first-guess rate only asks whether the top of the list was right. Bits a letter asks how much probability was on the right answer, and punishes being confidently wrong far more than it rewards being confidently right. A longer context makes the model surer, and on a corpus this small a lot of that sureness is misplaced.
So “how often is it right” and “how good is it” come apart, and which one you quote decides which model you would ship. That isn’t a subtlety about entropy, it’s the whole difficulty with picking a metric.
I wrote Shannon’s upper bound from memory and it was wrong by a factor of twenty five. I had it as a telescoping sum of the guess-rank shares. On a uniform alphabet, where the answer is 4.755 bits by inspection, that formula returns 0.176.
It isn’t subtly wrong, it’s nonsense, and it would have sat there producing plausible small numbers for every real passage because real passages are not uniform. The reason it got caught is that the estimator is checked against sources whose entropy can be worked out exactly: uniform distributions, one heavy symbol, an almost certain symbol, and a three state Markov chain with an entropy rate computed from its own stationary distribution. The correct bound is the entropy of the rank distribution, and it brackets all six.
That check took ten minutes and it’s the only reason this page reports anything true.
One call to the wrong function made a longer context worse than a shorter one. The model normalises text before using it, and normalising trims the ends. So a context of “the “ became “the”, and since the space is the commonest character in English, most contexts were being looked up as something other than what had been trained.
The symptom was that order five scored worse than order one, which is impossible for a model that’s working, and that impossibility is what made me look. Contexts are now cleaned without trimming, in a separate function that says why it exists.
What I would do next
Write more corpus and find out whether the extrapolation is honest. The projection to 1.8 million characters comes from fitting a straight line through eight points spanning less than one order of magnitude, and extending it across two more. That’s exactly the kind of extrapolation that’s wrong in an interesting way, and the way to find out is to go and get to 100,000 characters and see whether the line held.
There is a second reason to expect it not to. The best context length grows with the corpus: three is right at ten thousand characters and wouldn’t be right at a million. So the curve I fitted is the curve for a model that stays the wrong size, and the real one bends down faster. The projection is conservative for a reason I can name, which is better than being wrong for a reason I cannot.
The other thing missing is a proper comparison to a person. This page can measure you, and it can’t tell you whether your number is a good one, because I have no distribution of what people score. That needs many people playing it, which isn’t a thing a static page can collect without becoming something else.