A (Not So) Short Stay in Hell - Appendix

Appendix to the post A (Not So) Short Stay in Hell. This is a hodge-podge proofs and results to fill in gaps which I felt were too much of a diversion from the point of the original post. The sections are sorted in the order they appear in the original post.

Table of Contents

• Numerically Stable Computation of Scientific Notation
• The Size of the Library
• Bounds on the Expected Search
• The Generalized Fibonacci Recurrence
• Joint and Conditional Probability Distributions
• Typical Set Bound Proofs
• Stochastic, Stationary, and Ergodic Processes
• Estimating the Entropy Rate of English

Numerically Stable Computation of Scientific Notation

In the main post, I was required to compute the scientific notation of lots of very large numbers. In this section of the appendix I will explain the procedure for these calculations.

Suppose you are given any arbitrary real numbers $a > 0$, $b > 1$, and $c > 1$. We want to convert them to real number $0 < s < 1$ and integer $e \in \mathbb{Z}$ such that

Remembering our log-rules, we can define the following intermediate value

Now define our target quantities as the following.

And it’s easy to verify that

The important detail here is on your calculator you should not enter $\log_{10} (c \cdot b^a)$ as $b^a$ might be a huge number which your calculator cannot compute. Instead, enter $a \cdot \log_{10} b + \log_{10} c$ and more likely than not this will be tractile to compute. This is a simple example of why logarithms are extremely useful in practical applications. This procedure can be summarized as the following code.

import math

def compute_scientific_notation(a, b, c=1.0):
    """
    convert c * b^a into s * 10^e
    """ 
    x = a * math.log10(b) + math.log10(c)
    e = math.floor(x)       # exponent
    s = 10 ** (x - e)       # significand
    return s, e

The Size of the Library

In the original short story The Library of Babel, the library has a more complicated geometry of hexagonal rooms. In the book A Short Stay in Hell, the library is essentially two dimensional. It consists of two extremely large square walls of books running parallel to each other (like two sheets of aluminum). I’m going to simplify it even further. Let’s assume we just have one giant wall of books. If we assume this wall is square, what are its side lengths?

From the appendix of the book, the author assumes the books are 1.5 inches thick and require 1.5 feet of vertical shelf space. So effectively, we have a rectangle of proportion $1:12$. So 12 books standing vertically side-by-side on a shelf will take up exactly 1.5 by 1.5 square feet of space. We can do a quick calculation.

Therefore, taking the square root of this number gives the side lengths of this enormous wall of books.

To put this number into perspective, the observable universe is only $4.65 \times 10^{10} \ \text{lightyears}$ in diameter.

Just for fun, let’s suppose the books are arranged into a giant cube. Assume 12 books stacked adjacent to each other creates a perfect cube of 1.5 by 1.5 by 1.5 feet. We can redo this calculation.

Therefore, taking the cube root of this number gives the side length of this enormous cube of books.

Again, let’s put this number into perspective. A Planck length is about $1.71 \times 10^{-51} \ \text{lightyears}$. The observable universe is about $4.65 \times 10^{10} \ \text{lightyears}$ in diameter. So the magnitude difference between the Planck length compared to the current observable universe ($10^{61}$) is barely even a rounding error compared to the size of this mega cube of books.

Bounds on the Expected Search

The claim in the original post is equivalent to the following. Suppose $a, b \in \mathbb{R}_{>0}$ and $a \geq b$, then

First, I’ll show the right half of the inequality.

and $\frac{a - b}{b(b+1)} \geq 0$ since the denominator is positive and $a \geq b$. Therefore, $\frac{a}{b} - \frac{a+1}{b+1} \geq 0$, which implies the second part of the claim.

Now, I show the left half of the inequality.

Clearly, $a \leq ab$. Again the denominator in positive. Therefore, $\frac{a - ab - 2b}{2b(b+1)} \leq 0$ and thus $\frac{a}{2b} - \frac{a+1}{b+1} \leq 0$, which implies the first part of the claim.

The Generalized Fibonacci Recurrence

To reduce complexity in notation, I will define $S_{\ell} := \lvert Z_{\ell} \rvert$.

Proving the Recurrence from the Summation

Consider the following summation.

Noting that $\binom{0}{0} = 1$, it’s easy to directly compute that

Now consider $n S_{L-1}$ and $n S_{L-2}$. In $n S_{L-2}$ we can substitute $k = j+1$.

When $k = 0$, we’ll define $\binom{L-2}{-1} = 0$, so this term does not contribute. Therefore

Using Pascal’s identity, $\binom{L-k-2}{k} + \binom{L-k-2}{k-1} = \binom{L-k-1}{k}$, this reduces to our original summation. Therefore,

Bounding the Recurrence

The easiest way to prove this is abstractly. The solution to the recurrence is given by

Without loss of generality, assume that $r_1 \geq r_2$. Furthermore, the first base-case $S_0 = 1$ implies $C_1 + C_2 = 1$. Therefore

Asymptotic Behavior of the Recurrence

The goal is to find the asymptotic behavior as $L$ approach infinity. First, we get an asymptotic bound on $\lvert Z_L \rvert$. Without loss of generality, assume that $r_1 \geq r_2$.

Since $\frac{r_2}{r_1} \leq 1$, then as $L \rightarrow \infty$ we have $\left ( \frac{r_2}{r_1} \right )^L \rightarrow 0$. Also notice that $r_1 = \frac{n + \sqrt{n^2+4n}}{2} = \Theta(n)$. Therefore

Now, we use the inequality bounds on $\mathbb{E}[K]$ and the fact that $\lvert \mathcal{X} \rvert^L = (n+1)^L$.

Since $1 + \frac{1}{n} > 1$, $\mathbb{E}[K]$ and consequently $\mathbb{E}[T]$ grow exponentially with respect to $L$.

Typical Set Bound Proofs

We can reorganize the definition of a typical set as the following

Cardinality Upper Bound

By definition, $A_{\epsilon}^{(\ell)} \subseteq \mathcal{X}^{\ell}$. Therefore,

Therefore

Cardinality Lower Bound

By the Shannon-McMillan-Breiman Theorem theorem,

which directly implies that

Therefore

Therefore

Joint and Conditional Probability Distributions

A Note on Notation

In probability theory, if you wanted to be very rigorous, you can use subscripts to differentiate functions. But in practice, this becomes really tedious and hard to read. So often these subscripts are dropped and the different PMFs are understood via their arguments. For example

Sequence of Joint PMFs over Strings

We can’t just define any sequence of \(\big ( p(x_1, x_2, \ldots, x_{\ell}) \big )_{\ell = 1}^{\infty}\). They are related via the chain rule of probability. In particular

Recursively applying the chain rule of probability, we can write

Thus, we need only define the marginal probability distribution $p(x_1)$ and each conditional probability distributions $p(x_{\ell} \mid x_1, x_2, \ldots, x_{\ell-1})$ for each $0 < \ell < L$. If we define the case of $\ell = 1$ as $p(x_1)$, then this defines a sequence of conditional PMFs (which can be arbitrarily defined)

which ultimately let’s us compute the joint PMFs for each $\ell$-string.

Estimating the Entropy Rate

Now, recall that

Therefore, we can define the sequence

which allows us to take the limit as $\ell \rightarrow \infty$, which is the definition of the entropy rate $h$.

Stochastic, Stationary, and Ergodic Processes

Definitions

A stochastic process is a mathematical model for something that changes over time in a way that involves randomness. In other words, it’s a sequence of random variables indexed by some notion of time or position. Intuitively, stochastic is the opposite of deterministic.

A stochastic process is stationary if its statistical properties are invariant under shifts in time/position. Formally, if \((X_i)_{i \geq 1}\) is generated via a stochastic process, then for every $k, \ell \geq 1$ and every $x_1, \ldots, x_{\ell} \in \mathcal{X}$

Thus, the probability of observing a particular finite pattern does not depend on where in the sequence we look.

A stochastic process is ergodic if observing one sufficiently long realization of the process gives us enough information to recover its statistical properties. Formally, we can write the following for every suitable function $f$

In other words, the time average of a function of the observations converges in probability to its expected value.

Example: Coin Flip

Let \(X_i \in \{ 0, 1 \}\) be a random variable representing a coin flip such that

Then we have

This is a stochastic process since each coin flip is random. This is also a stationary process since it’s independent and identically distributed.

Finally, this process is ergodic. Proving this is a bit involved and out of the scope of this post. It’s not hard to show the case for $f(x) = x$ which redues to proving that $\frac{1}{\ell} \sum_{i=1}^{\ell} X_i = \mathbb{E}[X_1]$, which is an application of the Strong Law of Large Numbers.

Anti-Example: Non-Stochastic

The following is a deterministic process

This process is not random at all. Every $X_i$ is determined by the formula.

Anti-Example: Non-Stationary

Let \(X_i \in \{ 0, 1 \}\) be a random variable representing biased coin flips which shows heads with probability $p_i$. We can write

Now, the outcome of each $X_i$ depends on $p_i$. Therefore in general

so this process is not stationary.

Anti-Example: Non-Ergodic

This is a bit of a weird anti-example. Suppose we have two biased coins such that coin $A$ always flips heads and coin $B$ always flips tails. Our process first picks a coin at random according to $\text{Bernoulli}(0.5)$, and then uses this coin and only this coin to generate \((X_i)_{i \geq 1}\). In other words

Therefore,

but

since the process of picking one of the two coins initially is still $50/50$. Thus, the long-term behavior cannot tell us about the underlying statistical properties of this process. The randomness associated with choosing the initial coin is lost. If I modified the probabilities coin $A$ and $B$ to $60/40$, you could not distinguish this by just observing the long-term behavior $(1,1,1,1, \ldots)$ or $(0,0,0,0, \ldots)$.

Stochastic Stationary Ergodic Process Generating English

A simple way to construct a stationary ergodic process that generates English-like text is with a $k^{\text{th}}$-order Markov model.

where $X_i$ can represent characters, tokens, or words. The model specifies the probability of the next element given the previous $k$ elements (e.g. next token prediction). With an appropriate choice of transition probabilities and initialization, the resulting process can be made stationary and ergodic.

In principle, this amounts to a giant table specifying the probability of every possible next token for every possible sequence of $k$ preceding tokens. For a realistic vocabulary and sufficiently large $k$, this table would be completely intractable. At a surface-level of analysis, modern LLMs can be viewed are learning subsections of this look-up table (training data), and efficiently representing and generalizing the statistical patterns via its model parameters. While it’s not technically true, as a first-order intuition you could think of an LLM as this English-text-generating process.

Estimating the Entropy Rate of English

I don’t want to get too deep into the weeds of the math here (otherwise this section would be huge). I just want to give a taste of the methods. I encourage you to read the papers for more details.

Claude Shannon’s Estimate

Claude Shannon (the pioneer of information theory), conducted the following experiment in his paper. Given a short passage unknown to the participant, the participant was to try to predict the next letter (space included, capitalization and punctuation excluded). If they were wrong, they would keep guessing until they got it right. Shannon would record the number of guesses required for each letter. This produced a result such as the following.

there is no reverse on a motorcycle a friend of mine found this out rather dramatically the other day 
111511211211151171112132122711114111318613111111111116211111121111114111111151111111111161111111111111

Suppose we had an ideal next-character predictor of English text. Let $q_i^{(N)}$ be the fraction of characters correctly guessed by this ideal predictor on the $i^{\text{th}}$ guess when $N−1$ previous characters are known. Skipping a ton of details, Shannon shows the following bounds on the conditional entropy of English.

where

and it can be shown that $H_N \rightarrow h$ as $N \rightarrow \infty$ for stationary processes.

Shannon ran the above experiment for $N = 100$. This allowed him to estimate each of the $q_i^{(N)}$’s using the statistics of human subjects, and ultimately estimate upper and lower bounds on $h$. He acknowledges that human subjects are far from ideal predictors and there are considerable error bounds on this estimate.

Estimates using Cross-Entropy

We’ll use a slightly different notation where if $X \sim p$, then $H(p) := H(X)$. Now, suppose we have two different probability distributions $p$ and $q$ over the same underlying events. Then the cross-entropy of $p$ with respect to $q$ is defined as

Intuitively, this like measuring the entropy of $q$ with using $p$ as the baseline. One can define the relative entropy between $p$ and $q$ called the Kullback–Leibler (KL) divergence, which let’s us write this upper-bound.

For a stationary process, we get

So, if we can empircally estimate $H(p, q)$, then we can get an upper bound on $H(p)$ and the entropy rate $h$.

Brown et al. (1992) use this idea to estimate an upper bound on the entropy rate of printed English. They construct a word-trigram language model $M$, trained on 583 million words of English text, and evaluated on the Brown Corpus. Here, $p$ represents the underlying probability distribution generating English text, and $q$ represents the distribution over text induced by the trigram model $M$. This allows them to estimate this following upper bound.

Montemurro, M. A. (2020) take this one step further by utilizing neural-networks to estimate $H(p, q)$. They investigate how the cross-entropy depends on two parameters: the amount of training data $k$ and the context length $n$. Empirically, they find that the cross-entropy decreases approximately as a power law in both parameters, which they model as

Since $\beta_1$ and $\beta_2$ were empirically estimated to be negative, the $k$ and $n$ terms vanish as $n, k \rightarrow \infty$ (thus $H_{\text{model}}(n, k) \rightarrow h$). Extrapolating to infinite training data and context length gives an estimate of the minimal cross-entropy, and hence an upper bound on the entropy rate: