ENCODING ARGUMENTS*

arXiv:1603.08777v2 [] 15 May 2017

Pat Morin, Wolfgang Mulzer, and Tommy Reddad

Abstract.
Many proofs in discrete mathematics and theoretical computer science are based
on the probabilistic method. To prove the existence of a good object, we pick a random
object and show that it is bad with low probability. This method is effective, but the underlying probabilistic machinery can be daunting. “Encoding arguments” provide an alternative presentation in which probabilistic reasoning is encapsulated in a “uniform encoding
lemma”. This lemma provides an upper bound on the probability of an event using the
fact that a uniformly random choice from a set of size n cannot be encoded with fewer
than log2 n bits on average. With the lemma, the argument reduces to devising an encoding where bad objects have short codewords.
In this expository article, we describe the basic method and provide a simple tutorial on how to use it. After that, we survey many applications to classic problems from
discrete mathematics and computer science. We also give a generalization for the case of
non-uniform distributions, as well as a rigorous justification for the use of non-integer
codeword lengths in encoding arguments. These latter two results allow encoding arguments to be applied more widely and to produce tighter results.
Keywords: Encoding arguments, entropy, Kolmogorov complexity, incompressibility, analysis of algorithms, hash tables, random graphs, expanders, concentration inequalities, percolation theory.

* This research is partially funded by NSERC. W. Mulzer is supported by DFG Grants 3501/1 and 3501/2.

Contents

1 Introduction

1

2 An Elementary Tutorial

2

2.1 Basic Definitions, Prefix-free Codes and the Uniform Encoding Lemma . . .

2

2.2 Runs in Binary Strings . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

5

2.3 A Note on Ceilings . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

7

3 More Background and Preliminaries

8

3.1 Encoding Sparse Bit Strings . . . . . . . . . . . . . . . . . . . . . . . . . . . .

8

3.2 Binary Entropy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

8

3.3 Basic Chernoff Bound . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
3.4 Factorials and Binomial Coefficients . . . . . . . . . . . . . . . . . . . . . . . . 10
3.5 Encoding the Natural Numbers . . . . . . . . . . . . . . . . . . . . . . . . . . 11
4 Applications of the Uniform Encoding Lemma

12

4.1 Graphs with no Large Clique or Independent Set . . . . . . . . . . . . . . . . 12
4.2 Balls in Urns . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
4.3 Linear Probing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
4.4 Cuckoo Hashing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
4.5 2-Choice Hashing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
4.6 Bipartite Expanders . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
4.7 Permutations and Binary Search Trees . . . . . . . . . . . . . . . . . . . . . . 24
4.7.1

Analysis of Insertion Sort . . . . . . . . . . . . . . . . . . . . . . . . . 25

4.7.2

Records . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26

4.7.3

The Height of a Random Binary Search Tree . . . . . . . . . . . . . . . 28

i

4.7.4

Hoare’s Find Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . 30

4.8 k-SAT and the Lovász Local Lemma . . . . . . . . . . . . . . . . . . . . . . . . 32
5 The Non-Uniform Encoding Lemma and Shannon-Fano Codes

35

6 Applications of the Non-Uniform Encoding Lemma

36

6.1 Chernoff Bound . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
6.2 Percolation on the Torus . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
6.3 Triangles in Gn,p . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
7 Encoding with Kraft’s Condition

41

8 Summary and Conclusions

44

ii

1

Introduction

There is no doubt that probability theory plays a fundamental role in computer science.
Often, the fastest and simplest solutions to important algorithmic and data structuring
problems are randomized [26, 30]; average-case analysis of algorithms relies entirely on
tools from probability theory [36]; many difficult combinatorial questions have strikingly
simple solutions using probabilistic arguments [2].
Unfortunately, many of these beautiful results present a challenge to most computer scientists, as they rely on advanced mathematical concepts. For instance, the 2013
edition of ACM/IEEE Curriculum Guidelines for Undergraduate Degree Programs in Computer Science does not require a full course in probability theory [1, Page 50]. Instead, the
report recommends a total of 6 Tier-1 hours and 2 Tier-2 hours on discrete probability, as
part of the discrete structures curriculum [1, Page 77].
“Encoding arguments” offer a more elementary approach to presenting these results. We transform the task of upper-bounding the probability of a specific event, E, into
the task of devising a code for the set of elementary events in E. This provides an alternative to performing a traditional probabilistic analysis or, since we are only concerned
with finite spaces, to directly estimating the size of E. Just as the probabilistic method is
essentially only a sophisticated rephrasing of a counting argument with many theoretical and intuitive advantages, encoding arguments likewise offer their own set of benefits,
although they are also just a glorified way of counting. More specifically:
1. Except for applying a simple Uniform Encoding Lemma, encoding arguments are
“probability-free.” There is no danger of common mistakes such as multiplying
probabilities of non-independent events or (equivalently) multiplying expectations.
The actual proof of the Uniform Encoding Lemma is trivial. It only uses the probabilistic fact that if we have a finite set X with r special elements and we pick an
element from X uniformly at random, the probability of selecting a special element
is r/|X|.
2. Encoding arguments usually yield strong results; Pr{E} typically decreases at least
exponentially in the parameter of interest. Traditionally, these strong results require
(at least) careful calculations on probabilities of independent events and/or concentration inequalities. This latter subject is advanced enough to fill entire textbooks
[7, 13].
3. Encoding arguments are natural for computer scientists. They turn a probabilistic

1

analysis into the task of designing an efficient code—an algorithmic problem. Consider the following two problems:
(a) Prove an upper-bound of 1/nlog n on the probability that a random graph on n
vertices contains a clique of size k = d4 log ne.1

(b) Design an encoding for graphs on n vertices so that any graph with a clique of

size k = d4 log ne is encoded using at most n2 − log2 n bits. (Note: Your encoding
and decoding algorithms don’t have to be efficient, just correct.)
Many computer science undergraduates would not know where to start on the first
problem. Even a good student who realizes that they can use Boole’s Inequality will
n
n  −(4 log
2 ).
still be stuck wrestling with the formula 4 log
n 2
We believe that encoding arguments are an easily accessible, yet versatile tool for
solving many problems. Most of these arguments can be applied after learning almost no
probability theory beyond the Encoding Lemma mentioned above.
The remainder of this article is organized as follows. In Section 2, we present an
elementary tutorial on the method, including the Uniform Encoding Lemma, the basis of
most of our encoding arguments. In Section 3, we review more advanced mathematical
tools, such as entropy, Stirling’s Approximation, and encoding schemes for natural numbers. In Section 4 we show how the Uniform Encoding Lemma can be applied to Ramsey
graphs, several hashing variants, expander graphs, analysis of binary search trees, and
k-SAT. In Section 5, we introduce the Non-Uniform Encoding Lemma, a generalization
that extends the reach of the method, This is demonstrated in Section 6, where we prove
the Chernoff bound and consider percolation and random triangle counting problems.
Section 7 presents an alternative view of encoding arguments, justifying the use of noninteger codeword lengths. Section 8 concludes the survey.

2

An Elementary Tutorial

This section gives a simple tutorial on the basic method.
2.1

Basic Definitions, Prefix-free Codes and the Uniform Encoding Lemma

Before we can talk about codes, we first recall some basic definitions about bit strings.
1 Since we are overwhelmingly concerned with binary encoding, we will agree now that the base of logarithms in log x is 2, except when explicitly stated otherwise.

2

• binary string/bit string: a finite (possibly empty) sequence of elements from {0, 1}.
The set of all bit strings is denoted by {0, 1}∗ .
Examples: 0; 1; 101; 00101; 1010; 1101; ε (the empty string).

• length of a bit string x: the number of bits in x, denoted by |x|.
Examples: |0| = 1; |1| = 1; |101| = 3; |00101| = 5.
• n0 (x), n1 (x): the number of 0- and 1-bits in a bit string x.
Examples: n0 (010) = 2; n1 (010) = 1; n0 (1111) = 0; n1 (1111) = 4.
• n-bit string: a bit string of length n, for n ∈ N. The set of all n-bit strings is denoted
by Σn .
Examples: 001 is a 3-bit string; 00101 is a 5-bit string; Σ2 = {00, 01, 10, 11}.
• prefix: a bit string x ∈ Σ∗ is a prefix of another binary string y ∈ Σ∗ if y is of the form
y = xz, for some z ∈ Σ∗ . Here, xz denotes the bit string obtained by concatenating x
with z.
Example: 0, 01, 010, and 0100 are prefixes of 0100, but 1 and 00 are not.
Next, we explain our coding theoretic vocabulary. In the following, let X be a finite
or countable set.
• code for X/encoding of X: an injective function C : X → {0, 1}∗ that assigns a unique
finite bit string to every element of X.
Example: Let X = {a, b, c}. The function C : a 7→ 01, b 7→ 1110, c 7→ 10 is a code for X,
but the function C 0 : a 7→ 01, b 7→ 1110, c 7→ 01 is not.
• codewords of a code C : X → {0, 1}∗ : the elements of the range of C.

Example: The codewords of C : a 7→ 01, b 7→ 1110, c 7→ 10 are 01, 1110, and 10.

• partial code C : X 9 {0, 1}∗ for X: a code that is only a partial function, i.e., not every
element in X is assigned a codeword. We will use the convention that |C(x)| = ∞ if x
is not in the domain of C.
Example: Let X = {a, b, c}. Then C : a 7→ 01, b 7→ 1110 is a partial code for X in which
there is no codeword for c. We have |C(a)| = 2, |C(b)| = 4, and |C(c)| = ∞.
• prefix-free (partial) code: a (partial) code C in which no codeword is the prefix of
another codeword.
Examples: The code C1 : a 7→ 10, b 7→ 111, c 7→ 01 is prefix-free. The code C2 : a 7→
10, b 7→ 111, c 7→ 1011 is not prefix-free, because the codeword for a is a prefix of the
codeword for c.
3

x
a
b
c
d
e
f

C(x)
0
100
1010
1011
110
1111

0

1
0

a
0
b

1
0

1
0

1

c

d

e

1
1
f

Figure 1: A prefix-free code for X = {a, b, c, d, e, f} and the corresponding leaf-labelled binary tree (which can also be viewed as a partial prefix-free code for {a, b, c, . . . , z}).
• fixed-length code for a finite set X: a prefix-free code for X where each codeword
has length dlog |X|e. It is obtained by enumerating the elements of X in some order
x0 , x1 , . . . , x|X|−1 and assigning to each xi the binary representation of i, padded with
leading zeros to obtain dlog |X|e bits.
Example: Let X = {a, b, c, d, e}. Then, a possible fixed-length code for X is C : a 7→
000, b 7→ 001, c 7→ 010, d 7→ 011, e 7→ 100.

It is helpful to visualize prefix-free codes as (rooted ordered) binary trees whose
leaves are labelled with the elements of X. The codeword for a given x ∈ X is obtained by
tracing the root-to-leaf path leading to x and outputting a 0 each time this path goes from
a parent to its left child, and a 1 each time it goes to a right child. (See Figure 1.)
We claim that if a code C is prefix-free, then for any k ∈ N, the code C has not more
b in which
than
codewords of length at most k. To see this, we modify C into a code C,
every codeword of length ` < k is extended to a word of length exactly k by appending
b is a valid code, i.e., all codewords of C
b are pairwise
k − ` zeros. Since C is prefix-free, C
distinct. Furthermore, the number of codewords in C with length at most k equals the
b of length exactly k. Since all codewords of length k in C
b are
number of codewords in C
pairwise distinct, there are at most 2k of them. To illustrate the proof, consider the code
C : a 7→ 0, b 7→ 100, c 7→ 1010, d 7→ 1011, e 7→ 110, f 7→ 1111 from Figure 1. Our claim says
b is as follows.
that C has at most 23 = 8 codewords of length at most 3. The modified code C
b : a 7→ 000, b 7→ 100, c 7→ 1010, d 7→ 1011, e 7→ 110, f 7→ 1111. We see that C
b is indeed a
C
code, and its codewords of length exactly 3 are in correspondence with the codewords of
length at most 3 in C, as claimed.
2k

Finally, we need to review some probability theory.
P
• probability distribution p on X: a function p : X → [0, 1] with x∈X p(x) = 1. We
sometimes write px instead of p(x). We again emphasize that X is a finite or countable
set.
4

Example: for X = {a, b, c}, the function p : a 7→ 1/3, b 7→ 1/2, c 7→ 1/6 is a probability
distribution, but p0 : a 7→ 1/3, b 7→ 1/2, c 7→ 1/5 is not. For X = {1, 2, . . . }, the function
p(x) = 1/2x is a probability distribution.
• uniform distribution on finite set X: the probability distribution p : X → [0, 1] given
by px = 1/|X|, for all x ∈ X.
• Bernoulli distribution on n-bit strings with parameter α ∈ [0, 1]: the probability
distribution p on X = {0, 1}n with px = (1 − α)n0 (x) α n1 (x) . In other words, a bit string x
is sampled by setting each bit to 1 with probability α and to 0 with probability 1 − α,
independently of the other bits. We write Bernoulli(α) for p.
The following lemma provides the foundation on which this survey is built. The lemma
is folklore, but as we will see in the following sections, it has an incredibly wide range of
applications and can lead to surprisingly powerful results.
Lemma 1 (Uniform Encoding Lemma). Let X be a finite set and C : X 9 {0, 1}∗ a partial
prefix-free code. If an element x ∈ X is chosen uniformly at random, then
Pr{|C(x)| ≤ log |X| − s} ≤ 2−s .
Proof. We call a codeword of C short if it has length at most k = blog |X| − sc. Above, we
observed that C has at most 2k short codewords. Since C is injective, each codeword has at
exactly one preimage in X. Since x is chosen uniformly at random from X, the probability
that it is the preimage of a short codeword is at most
2k
2log |X|−s
≤
= 2−s .
|X|
|X|

2.2

Runs in Binary Strings

To finish our tutorial, we give a simple use of the Uniform Encoding Lemma. Let x be a bit
string. A run in x is a consecutive sequence of one bits. For example, 0110111101011111
contains runs of length 2, 4, 1, and 5, and every substring of a run is also a run. We now
show that a n-bit string that is chosen uniformly at random is unlikely to contain a run of
length significantly more than log n. (See Figure 2.)


Theorem 1. Let x = (x1 , . . . , xn ) ∈ {0, 1}n be chosen uniformly at random and let t = dlog ne + s .
Then, the probability that x contains a run of length t is at most 2−s .

5

t
x= ?

···
···

x1
C(x) =

i


?

1

1

xi−1

xi

xi+1

x1


log n

···

···

xi−1

1

?

xi+t−1

xi+t

xi+t

···

···
···

?
xn

xn

n−t

Figure 2: Illustration of Theorem 1 and its proof.
Proof. We construct a partial prefix-free code for strings with a run of length t. For such
a string x = (x1 , . . . , xn ), let i be the minimum index with xi = xi+1 = · · · = xi+t−1 = 1. The
codeword C(x) for x is the binary string that consists of the (dlog ne-bit binary encoding of
the) index i followed by the n − t bits x1 , . . . , xi−1 , xi+t , . . . , xn . (See Figure 2.) For example,
for n = 8 and t = 4, we encode x = 10111110 as 010 10 10, since the first run of length 4 in
x is at position 2, which is 010 as a 3 = dlog 8e-bit number.
Observe that C(x) has length
|C(x)| = dlog ne + n − t ≤ n − s .
To see that C is injective, we argue that we can obtain (x1 , . . . , xn ) uniquely from C(x): The
first dlog ne bits from C(x) tell us, in binary, a position i for which xi = xi+1 = · · · = xi+t−1 = 1;
the following n − t bits in C(x) contain the remaining bits x1 , x2 , . . . , xi−1 , xi+t , xi+t+1 , . . . , xn .
Thus, C is a partial code whose domain are the n-bit strings with a run of length t. Also,
C is prefix-free, as all codewords have the same length. Recall from our convention that
|C(x)| = ∞ if x does not have a run of length t.
Now, there are 2n n-bit strings. Therefore, by the Uniform Encoding Lemma, the
probability that a uniformly random n-bit string has a run of length t is at most
Pr{|C(x)| ≤ n − s} ≤ 2−s .

The proof of Theorem 1 contains the main ideas used in most encoding arguments:
1. The arguments usually show that a particular bad event is unlikely. In Theorem 1 the
bad event is the occurrence of a substring of t consecutive ones.
2. We use a partial prefix-free code whose domain is the bad event, whose elements we
call the bad outcomes. In this case, the code C only encodes strings containing a run
of length t, and a particular such string is a bad outcome.
6

3. The code begins with a concise description of the bad outcome, followed by a straightforward encoding of the information that is not implied by the bad outcome. In Theorem 1, the bad outcome is completely described by the index i at which the run of
length t begins, and this implies that the bits xi , . . . , xi+t−1 are all equal to 1, so these
bits can be omitted in the second part of the codeword.
2.3

A Note on Ceilings

Note that Theorem 1 also has an easy proof using the union bound: If we let Ei denote the
event xi = xi+1 = · · · = xi+t = 1, then


n−t−1  n−t−1


[ 
 X
Pr 
E
≤
Pr{Ei }
(using the union bound)

i




i=0

=

i=0
n−t−1
X

2−t

i=0
−t

(using the independence of the xi ’s)

≤ n2

(the sum has n − t ≤ n identical terms)

≤ 2−s .

(∗)

−dlog ne−s

≤ n2

(using the definition of t)

This traditional proof also works with the sometimes smaller value t = dlog n + se (note the
lack of a ceiling over log n), in which case the final inequality (∗) holds with an equality.
In the encoding proof of Theorem 1, the ceiling on the log n is an artifact of encoding the integer i which comes from a set of size n. When sketching an encoding argument,
we think of this as requiring log n bits. However, when the time comes to write down a
careful proof we need a ceiling over this term as bits are a discrete quantity.
In Section 7, however, we will formally justify that the informal intuition we use
in blackboard proofs is actually valid; we can think of the encoding of i using log n bits
even if log n is not an integer. In general we can imagine encoding a choice from among r
options using log r bits for any r ∈ N. From this point onwards, we omit ceilings this way
in all our theorems and proofs. This simplifies calculations and provides tighter results.
For now, it allows us to state the following cleaner version of Theorem 1:
Theorem 1b. Let x ∈ {0, 1}n be chosen uniformly at random and let t = dlog n + se. Then, the
probability that x contains a run of length t is at most 2−s .

7

3
3.1

More Background and Preliminaries
Encoding Sparse Bit Strings

At this point we should also point out an extremely useful trick for encoding sparse bit
strings. For any α ∈ (0, 1), there exists a code Cα : {0, 1}n → {0, 1}∗ such that, for any bit
string x ∈ {0, 1}n having n1 (x) ones and n0 (x) zeros,


1
1
|Cα (x)| = n1 (x) log + n0 (x) log
.
(1)
α
1−α
This code is the Shannon-Fano code for Bernoulli(α) bit strings of length n [17, 37]. More
generally, for any probability density p : X → [0, 1], there is a Shannon-Fano code C : X →
{0, 1}∗ such that
|C(x)| = dlog(1/px )e .
Moreover, we can construct such a code deterministically, even when X is countably infinite.
Again, as explained in Section 7, we can omit the ceiling in the expression for
|Cα (x)|. This holds for any value of n. In particular, for n = 1, it gives a “code” for a single
bit where the cost of encoding a 1 is log(1/α) and the cost of encoding a 0 is log(1/(1 − α)).
Indeed, the “code” for bit strings of length n > 1 is what we get when we apply this 1-bit
code to each bit of the bit string.
If we wish to encode bit strings of length n and we know in advance that the strings
contain exactly k one bits, then we can obtain an optimal code by taking α = k/n. The
resulting fixed length code has length
k log(n/k) + (n − k) log(n/(n − k)) .

(2)

Formula (2) brings us to our next topic: binary entropy.
3.2

Binary Entropy

The binary entropy function H : (0, 1) → (0, 1] is defined by
H(α) = α log(1/α) + (1 − α) log(1/(1 − α))
and it will be quite useful. The binary entropy function and two upper bounds on it that
we derive below are illustrated in Figure 3. We have already encountered a quantity that
can be expressed in terms of the binary entropy. From (2), a bit string of length n with
exactly k one bits can be encoded with a fixed-length code of nH(k/n) bits.
8

1.6

α log(1/α) + α log e

1.4

(1 − 2α)2
2 ln 2
H(α)
1−

1.2
1.0
0.8
0.6
0.4
0.2
0.0

0

1/4

1/2
α

1

3/4

Figure 3: Binary entropy, H, and two useful approximations.
The binary entropy function can be difficult to work with, so it is helpful to have
some manageable approximations. One of these is derived as follows:
H(α) = α log(1/α) + (1 − α) log(1/(1 − α)) = α log(1/α) + (1 − α) log(1 + α/(1 − α))
≤ α log(1/α) + (1 − α) · α/(1 − α) log e ≤ α log(1/α) + α log e

(3)

since 1 + x ≤ ex for all x ∈ R. Inequality (3) is a useful approximation when α is close to
zero, in which case H(α) is also close to zero.
For α close to 1/2 (in which case H(α) is close to 1), we obtain a good approximation
from the Taylor series expansion at 1/2. Indeed, a simple calculation shows that
H 0 (α) = log(1/α) − log(1/(1 − α))
and that

!
(i − 2)! (−1)i−1
1
−
,
H (α) =
ln 2
α i−1
(1 − α)i−1
(i)

for i ≥ 2. Hence, H (i) (1/2) = 0, for i ≥ 1 odd, and
H (i) (1/2) = −

(i − 2)! 2i
,
ln 2

for i ≥ 2 even. The Taylor series expansion at 1/2 now gives
H(1/2 + β) = H(1/2) +

∞
X
H (i) (1/2)
i=1

i!

∞

∞

i=1

i=1

1 X (2i − 2)!22i 2i
1 X (2β)2i
β = 1−
β = 1−
.
ln 2
(2i)!
2 ln 2
i(2i − 1)
i

9

In particular, for β = ε/2,
∞

ε2
1+ε
1 X ε2i
< 1−
.
= 1−
H
2
2 ln 2
i(2i − 1)
2 ln 2



(4)

i=1

3.3

Basic Chernoff Bound

With all the pieces in place, we can now give an encoding argument for a well-known and
extremely useful result typically attributed to Chernoff [10].
Theorem 2. Let x ∈ {0, 1}n be chosen uniformly at random. Then, for any ε ≥ 0,


2
n
Pr n1 (x) ≤ (1 − ε) ≤ e−ε n/2 .
2
Proof. Encode the bit string x using a Shannon-Fano code Cα with α = (1 − ε)/2. Then, the
length of the codeword for x is
|Cα (x)| = n1 (x) log(1/α) + n0 (x) log(1/(1 − α)) .
Since α < 1/2, we have log(1/α) > log(1/(1 − α)), so for fixed n, the codeword length |Cα (x)|
is increasing in n1 (x) and becomes maximal when n1 (x) is maximal. Thus, if n1 (x) ≤ αn,
then
!
ε2
= n−s ,
|Cα (x)| ≤ αn log(1/α) + (1 − α)n log(1/(1 − α)) = nH(α) ≤ n 1 −
2 ln 2
where the second inequality is an application of (4), and where s = ε2 n/(2 ln 2). Now, x was
chosen uniformly at random from a set of size 2n . By the Uniform Encoding Lemma, we
obtain that
2
Pr{n1 (x) ≤ αn} ≤ Pr{|Cα (x)| ≤ n − s} ≤ 2−s = e−ε n/2 .

In Section 6.1, after developing a Non-Uniform Encoding Lemma, we will extend
this argument to Bernoulli(α) bit strings.
3.4

Factorials and Binomial Coefficients

Before moving on to some more advanced encoding arguments, it will be helpful to remind
the reader of a few inequalities that can be derived from Stirling’s Approximation of the
factorial [35]. Recall that Stirling’s Approximation states that
 n √

 
1
n
2πn 1 + Θ
.
(5)
n! =
e
n
10

In many cases, we are interested in representing a set of size n! using a fixed-length
code. By (5), and using once again that 1 + x ≤ ex for all x ∈ R as well as 1 + x ≥ ex/2 for
x ∈ [0, 1/2], the length of the codewords in such a code is
√
log n! = n log n − n log e + (1/2) log n + log 2π + log(1 + Θ(1/n))
√
= n log n − n log e + (1/2) log n + log 2π + Θ(1/n)
= n log n − n log e + Θ(log n) .

(6)


We are sometimes interested in codes for the nk subsets of k elements from a set
of size n. Note that there is an easy bijection between such subsets and binary strings of
length n with exactly k ones. Therefore, we can represent these using the Shannon-Fano
code Ck/n and each of our codewords will have length nH(k/n). In particular, this implies
that
!
n
log
≤ nH(k/n) ≤ k log n − k log k + k log e
(7)
k
where the last inequality is an application of (3). The astute reader will notice that we

just used an encoding argument to prove an upper-bound on nk without using the formula
n
n!
k = k!(n−k)! . Alternatively, we could obtain a slightly worse bound by applying (5) to this
formula.
3.5

Encoding the Natural Numbers

So far, we have only explicitly been concerned with codes for finite sets. In this section,
we give an outline of some prefix-free codes for the set of natural numbers. Of course,
if p : N → [0, 1] is a probability density, then the Shannon-Fano code for p could serve.
However, it seems easier to simply design our codes by hand, rather than find appropriate
distributions.
A code is prefix-free if and only if any message consisting of a sequence of its
codewords can be decoded unambiguously and instantaneously as it is read from left to
right: Consider some sequence of codewords M = y1 y2 · · · yk from a prefix-free code C.
Since C is prefix-free, then C has no codeword z which is a prefix of y1 , so reading M
from left to right, the first codeword of C which we recognize is precisely y1 . Continuing
in this manner, we can decode the whole message M. Conversely, if for each codeword
y of C, a message consisting of this single codeword can be decoded unambiguously and
instantaneously from left to right, we know that y has no prefix among the codewords of
C, i.e. C is prefix-free. This idea allows us to more easily design the codes in this section,
which were originally given by Elias [14].
The unary encoding of an integer i ∈ N, denoted by U (i), begins with i 1 bits which
11

are followed by a 0 bit. This code is not particularly useful in itself, but it can be improved
as follows: The Elias γ-code for i, denoted by Eγ (i), begins with the unary encoding of
the number of bits in i, and then the binary encoding of i itself (minus its leading bit).
The Elias δ-code for i, denoted by Eδ (i) begins with an Elias γ-code for the number of bits
in i, and then the binary encoding of i itself (minus its leading bit). This process can be
continued recursively to obtain the Elias ω-code, which we denote by Eω . Each of these
codes has a decoding procedure as in the preceding paragraph, which establishes their
prefix-freeness.
The most important properties of these codes are their codeword lengths:
|U (i)| = i + 1 ,

|Eγ (i)| = 2 log i + O(1) ,

|Eδ (i)| = log i + 2 log log i + O(1) ,

|Eω (i)| = log i + log log i + · · · + log · · · log i + O(log∗ i) .
| {z }
log∗ i times

Here, log∗ i denotes the number of times we need to apply the function x 7→ log x to the
integer i until we obtain a number that is smaller than 2. It may be worth noting that the
lengths of unary codes correspond to the lengths of Shannon-Fano codes for a geometric
distribution with density pi = 1/2i+1 , that is,
log(1/pi ) = log 2i+1 = |U (i)| ,
and the lengths of Elias γ-codes correspond to the lengths of Shannon-Fano codes for a
discrete Cauchy distribution with density pi = c/i 2 for a normalization constant c, that is,
log(1/pi ) = 2 log i − log c = |Eγ (i)| + O(1) .
The lengths of Elias δ-codes and ω-codes do not seem to arise as the lengths of ShannonFano codes for any named distributions.

4

Applications of the Uniform Encoding Lemma

We now start with some applications of the Uniform Encoding Lemma. In each case, we
will design and analyze a partial prefix-free code C : X 9 {0, 1}∗ , where X depends on the
context.
4.1

Graphs with no Large Clique or Independent Set

The Erdős-Rényi random graph Gn,p is the probability space on graphs with vertex set V =

{1, . . . , n} in which each edge {u, w} ∈ V2 is present with probability p and absent with
12

probability 1−p, independently of the other edges. Erdős [15] used the random graph Gn, 1
2
to prove that there are graphs that have neither a large clique nor a large independent set.
Here we show how this can be done using an encoding argument.
Theorem 3. For n ≥ 3 and s ∈ N, the probability that G ∈ Gn, 1 contains a clique or an indepen2
√
dent set of size t = d3 log n + 2se is at most 2−s .
Proof. This encoding argument compresses the
appear in row-major order.

n
2

bits of G’s adjacency matrix, as they

Suppose the graph G contains a clique or an independent set S of size t. The encoding C(G) begins with a bit indicating whether S is a clique or independent set; followed by

the set of vertices of S; then the adjacency matrix of G in row major-order, omitting the 2t
bits implied by the edges or non-edges in S. Such a codeword has length
!
!
n
t
|C(G)| = 1 + t log n +
−
.
(8)
2
2
Before diving into the detailed arithmetic, we intuitively argue why we’re heading in the
right direction: Roughly, (8) is of the form:
!
n
|C(G)| =
+ t log n − Ω(t 2 ) .
2
That is, we need to invest O(t log n) bits to encode the vertex set of a clique or an independent set of size t, but we save Ω(t 2 ) bits in the encoding of G’s adjacency matrix. Clearly,
for t > c log n, with c sufficiently large, this has the form
!
n
|C(G)| =
− Ω(t 2 ) .
2
At this point, it is just a matter of pinning down the dependence on c. A detailed calculation beginning from (8) gives
!
!
n
n
2
|C(G)| =
+ 1 + t log n − (1/2)(t − t) =
+ 1 − (1/2)(t 2 − t − 2t log n) .
2
2
The function f (x) = (1/2)(x2 − x − 2x log n) − 1 is increasing for x ≥ log n + 1/2, so recalling
√
that t = d3 log n + 2se, we get
√
f (t) ≥ f (3 log n + 2s)

√
√
√
= (1/2)(9 log2 n + 6 2s log n + 2s − 3 log n − 2s − 6 log2 n − 2 2s log n) − 1
√
√
= (1/2)(3 log2 n + 4 2s log n − 3 log n − 2s) + s − 1 ≥ s
13

for n ≥ 3. Therefore, our code has length

!
!
n
n
|C(G)| =
− f (t) ≤
−s .
2
2

Applying the Uniform Encoding Lemma completes the proof.
Remark 1. The bound in Theorem 3 can be strengthened a little, since the elements of S

can be encoded using only log nt bits, rather than t log n. With a more careful calculation,
√
using (7), the proof then works with t = 2 log n + O(log log n) + s. This comes closer to
Erdős’s original result, which was at the threshold 2 log n − 2 log log n + O(1) [15].
4.2

Balls in Urns

The random experiment of throwing n balls uniformly and independently at random into
n urns is a useful abstraction of many questions encountered in algorithm design, data
structures, and load-balancing [26, 30]. Here we show how an encoding argument can be
used to prove the classic result that, when we do this, every urn contains O(log n/ log log n)
balls, with high probability.
Theorem 4. Let n, s ∈ N, and let t be such that t log(t/e) ≥ log n + s. Suppose we throw n
balls independently and uniformly at random into n urns. Then, for sufficiently large n, the
probability that any urn contains more than t balls is at most 2−s .
Before proving Theorem 4, we note that, for any constant ε > 0 and all sufficiently
large n, taking
&
'
(1 + ε) log n
t=
log log n
satisfies the requirements of Theorem 4, since then
!
!!
(1 + ε) log n
(1 + ε) log n
(1 + ε) log n
log log n
log
=
log log n − log
t log t ≥
log log n
log log n
log log n
1+ε
 log log n  


log 1+ε 

 = (1 + ε) log n − o(log n) .
= (1 + ε) log n 1 −

log log n 
Then,
t log(t/e) = t log t − t log e = (1 + ε) log n − o(log n) ≥ log n + s ,

for sufficiently large n, as claimed.

Proof of Theorem 4. For each i ∈ {1, . . . , n}, let bi denote the index of the urn chosen for the
i-th ball. The sequence b = (b1 , . . . , bn ) is sampled uniformly at random from a set of size
nn , and this choice will be used in our encoding argument.
14

Suppose that urn j contains t or more balls. Then, we encode the sequence b with

the value j (log n bits), followed by a code that describes t of the balls in urn j (log nt bits),
followed by the remaining n − t values in b that cannot be deduced from the preceding
information ((n − t) log n bits). Thus, we get
!
n
|C(b)| = log n + log
+ (n − t) log n
t
≤ log n + t log n − t log t + t log e + (n − t) log n
= n log n + log n − t log t + t log e

≤ n log n − s

(using (7))
(by the choice of t)

n

= log n − s

bits. We conclude the proof by applying the Uniform Encoding Lemma.
4.3

Linear Probing

Studying balls in urns as in the previous section is useful when analyzing hashing with
chaining (see e.g. Morin [27, Section 5.1]). A more practically efficient form of hashing
is linear probing. In a linear probing hash table, we hash the elements of the set X =
{x1 , . . . , xn } into a hash table of size m = cn, for some fixed c > 1. We are given a hash
function h : X → {1, . . . , m} which we assume to be a uniform random variable. To insert
xi , we try to place it at table position j = h(xi ). If this position is already occupied by one
of x1 , . . . , xi−1 , we try table location (j + 1) mod m, followed by (j + 2) mod m, and so on,
until we find an empty spot for xi . To find a given element x ∈ X in the hash table, we
compute j = h(x), and we start a linear search from position j until we encounter either
x or an empty position. Assuming that the hash table has been created by inserting the
elements from X successively according to the algorithm above, we want to study the
expected search time for some item x ∈ X.
We call a maximal consecutive sequence of occupied table locations a block. (The
table locations m − 1 and 0 are considered consecutive.)
Theorem 5. Let n ∈ N, c > e. Suppose that a set X = {x1 , . . . , xn } of n items has been inserted
into a hash table of size m = cn, using linear probing. Let t ∈ N, t ≥ 2, such that
(t − 1) log(c/e) − log t − 3 ≥ s ,
and fix some x ∈ X. Then the probability that the block containing x has size exactly t is at most
2−s .

15

Proof. This is an encoding argument for the sequence
h = (h(x1 ), h(x2 ), . . . , h(xn )) ,
that is drawn uniformly at random from a set of size mn = (cn)n .
Suppose that x lies in a block with t elements. We encode h by the first index b of
the block containing x; followed by the t − 1 elements y1 , . . . , yt−1 of this block (excluding
x); followed by the hash values of x and of y1 , . . . , yt−1 ; followed by the n − t hash values for
the remaining elements in X.
Since the values h(x), h(y1 ), h(y2 ), . . . , h(yt−1 ) are in the range b, . . . , b + t − 1 (modulo
m), they can be encoded using t log t bits. Therefore, we obtain a codeword of length
y1 ,...,yt−1

z }| { h(x),h(y1 ),...,h(yt−1 ) everything else
!
z }| {
z}|{
z}|{
n
+
t log t
+ (n − t) log m
|C(h)| = log m + log
t−1
b

≤ log m + (t − 1) log n − (t − 1) log(t − 1) + (t − 1) log e + t log t + (n − t) log m

(by (7))

= (n − t + 1) log m + (t − 1) log(m/c) + (t − 1) log e + log(t − 1) + t log(t/(t − 1)) (m = cn)

≤ n log m − (t − 1) log c + (t − 1) log e + log t + 3

= log mn − (t − 1) log(c/e) + log t + 3 ≤ log mn − s ,
since we assumed that t satisfies
(t − 1) log(c/e) − log t − 3 ≥ s
and since for t ≥ 2, we have
t log



t
1
t
1
t
=
ln 1 +
≤
·
≤ 3.
t − 1 ln 2
t−1
ln 2 t − 1

The proof is completed by applying the Uniform Encoding Lemma.
Remark 2. The proof of Theorem 5 only works if the factor c in the size m = cn of the linear
probing hash table is c > e. We know from previous analysis that this is not necessary, and
that any c > 1 is sufficient [36, Theorem 9.8]. We leave it as an open problem to find an
encoding proof of Theorem 5 that works for any c > 1.
Corollary 1. Let n ∈ N, c > e. Suppose that a set X = {x1 , . . . , xn } of n items has been inserted
into a hash table of size m = cn, using linear probing. Fix some x ∈ X. Then, the expected search
time for x in the hash table is O(1).

16

Proof. Let T denote the size of the block containing x in the hash table. Let t0 be a large
enough constant. Then, by Theorem 5, the probability that T = t + t0 is at most 2−t log(c/e)/2 ,
since then
(t + t0 − 1) log(c/e) − log(t + t0 ) − 3 ≥ (t + t0 ) log(c/e)/2 − 3 ≥ t log(c/e)/2 .
Thus, the expected search time for x is
E{T } =

∞
X

t Pr{T = t} =

t=1

≤ t0 +

4.4

t0
X

t Pr{T = t} +

t=1
∞
X

∞
X
(t + t0 ) Pr{T = t + t0 }
t=1

(t + t0 )2−t log(c/e)/2 = t0 +

t=1

∞
X

(t + t0 )(c/e)−t/2 = O(1) .

t=1

Cuckoo Hashing

Cuckoo hashing is relatively new hashing scheme that offers an alternative to classic perfect hashing [31]. We present a clever proof, due to Pătraşcu [33], that cuckoo hashing
succeeds with probability 1 − O(1/n) (see also Haimberger [20] for a more detailed exposition of the argument).
We again hash the elements of the set X = {x1 , . . . , xn }. The hash table consists of
two arrays A and B, each of size m = 2n, and two hash functions h, g : X → {1, . . . , m} which
are uniform random variables. To insert an element x into the hash table, we insert it into
A[h(x)]; if A[h(x)] already contains an element y, we insert y into B[g(y)]; if B[g(y)] already
contains some element z, we insert z into A[h(z)], etc. If an empty location is eventually
found, the algorithm terminates successfully. If the algorithm runs for too long without
successfully completing the insertion, then we say that the insertion failed, and the hash
table is rebuilt using different newly sampled hash functions. Any element x either is held
in A[h(x)] or B[g(x)], so we can search for x in constant time. The following pseudocode
describes this procedure more precisely:
Insert(x) :
1:
2:
3:
4:
5:
6:

if x = A[h(x)] or x = B[g(x)] then
return
for MaxLoop iterations do
if A[h(x)] is empty then
A[h(x)] ← x
return

17

7:
8:
9:
10:
11:
12:
13:

x ↔ A[h(x)]
if B[g(x)] is empty then
B[g(x)] ← x
return
x ↔ B[g(x)]
Rehash()
Insert(x)

The threshold ‘MaxLoop’ is to be specified later. To study the performance of insertion in cuckoo hashing, we consider the random bipartite cuckoo graph G = (A, B, E), where
|A| = |B| = m and |E| = n, with each vertex corresponding either to a location in the array A
or B above, and with edge multiset E = {(h(xi ), g(xi )) : 1 ≤ i ≤ n}.
An edge-simple path in G is a path that uses each edge at most once. One can check
that if a successful insertion takes at least 2t steps, then the cuckoo graph contains an edge
simple path with at least t edges. Thus, in bounding the length of edge-simple paths in
the cuckoo graph, we bound the worst case insertion time.
Lemma 2. Let s ∈ N. Suppose that we insert a set X = {x1 , . . . , xn } into a hash table using cuckoo
hashing. Let G be the resulting cuckoo graph. Then, G has an edge-simple path of length at least
s + log n + O(1) with probability at most 2−s .
Proof. We encode G by presenting its set of edges. Since each endpoint of an edge is chosen
independently and uniformly at random from a set of size m, the set of all edges is chosen
uniformly at random from a set of size m2n .
Suppose some vertex v ∈ A ∪ B is the endpoint of an edge-simple path of length t;
such a path has t + 1 vertices and t edges. Each edge in the path corresponds to an element
in X. In the encoding, we present the indices of the elements in X corresponding to the t
edges of the path in order; then, we indicate whether v ∈ A or v ∈ B; and we give the t + 1
vertices in order starting from v; followed by the remaining 2n − 2t endpoints of edges of
the graph. This code has length
|C(G)| = t log n + 1 + (t + 1) log m + (2n − 2t) log m
= 2n log m + t log n − t log m + log m + O(1)

= log m2n − t + log n + O(1)
2n

≤ log m

(since m = 2n)

−s

for t ≥ s + log n + O(1). We finish by applying the Uniform Encoding Lemma.

18

e2
e1

v

v
e1

e2

(a) A cycle with a chord.

(b) Two cycles connected by a path.

Figure 4: The potential minimal subgraphs of the cuckoo graph.
This immediately implies that a successful insertion takes time at most 4 log n+O(1)
with probability 1 − O(1/n). Moreover, selecting ‘MaxLoop’ to be 4 log n + O(1), we see that
a rehash happens only with probability O(1/n).
One can prove that the cuckoo hashing insertion algorithm fails if and only if some
subgraph of the cuckoo graph contains more edges than vertices, since edges correspond
to keys, and vertices correspond to array locations.
Lemma 3. The cuckoo graph has a subgraph with more edges than vertices with probability
O(1/n). That is, cuckoo insertion succeeds with probability 1 − O(1/n).
Proof. Suppose that some vertex v is part of a subgraph with more edges than vertices, and
in particular a minimal such subgraph with t + 1 edges and t vertices. Such a subgraph
appears exactly as in Figure 4. By inspection, we see that for every such subgraph, there
are two edges e1 and e2 whose removal disconnects the graph into two paths of length t1
and t2 starting from v, where t1 + t2 = t − 1.
We encode G by giving the vertex v (log m bits); and presenting Elias δ-codes for
the values of t1 and t2 and for the positions of the endpoints of e1 and e2 (O(log t) bits);
then the indices of the edges of the above paths in order ((t − 1) log n bits); then the vertices
of the paths in order ((t − 1) log m bits); and the indices of the edges e1 and e2 (2 log n bits);
and finally the remaining 2n − 2(t + 1) endpoints of edges in the graph ((2n − 2(t + 1)) log n
bits). Such a code has length
|C(G)| = log m + O(log t) + (t − 1)(log n + log m) + 2 log n + (2n − 2(t + 1)) log m
= 2n log m + (t + 1) log n − (t + 2) log m + O(log t)

= 2n log m + (t + 1) log n − (t + 2) log n − t + O(log t)
2n

≤ log m

− log n + O(1) .

We finish by applying the Uniform Encoding Lemma.
19

(since m = 2n)

4.5

2-Choice Hashing

We showed in Section 4.2 that if n balls are thrown independently and uniformly at random into n urns, then the maximum number of balls in any urn is O(log n/ log log n) with
high probability. In 2-choice hashing, each ball is instead given a choice of two urns, and
the urn containing the fewer balls is preferred.
More specifically, we are given two hash functions h, g : X → {1, . . . , m} which are
uniform random variables. Each value of h and g points to one of m urns. The element
x ∈ X is added to the urn containing the fewest elements between h(x) and g(x) during
an insertion. The worst case search time is at most the maximum number of hashing
collisions, or the maximum number of elements in any urn.
Perhaps surprisingly, the simple change of having two choices instead of only one
results in an exponential improvement over the strategy of Section 4.2. The concept of 2choice hashing was first studied by Azar et al. [3], who showed that the expected maximum
size of an urn is log log n + O(1). Our encoding argument is based on Vöcking’s use of
witness trees to analyze 2-choice hashing [39].
Let G = (V , E) be the random multigraph with V = {1, . . . , m}, where m = cn for some
constant c > 8, and E = {(h(x), g(x)) : x ∈ X}. Each edge in E is labeled with the element x ∈ X
that it corresponds to.
Lemma 4. The probability that G has a subgraph with more edges than vertices is O(1/n).
Proof. The proof is similar to that of Lemma 3. More specifically, we encode G by giving
the same encoding as in Lemma 3. However, since now G is not bipartite, we cannot
immediately deduce for an edge uv in the encoding which endpoint corresponds to which
hash function. Thus, for each edge uv, we store an additional bit indicating whether u =
h(x) and v = g(x), or u = g(x) and v = h(x). This needs t additional bits compared to
Lemma 3. Our code thus has length
|C(G)| = log m + O(log t) + (t − 1)(log n + log m) + 2 log n + (2n − 2(t + 1)) log m + t
= 2n log m − log n − t log c + t + O(log t) ≤ log m2n − log n + O(1) ,

since log c > 1.
Lemma 5. G has a component of size at least (2/ log(c/8)) log n + O(1) with probability O(1/n).
Proof. Suppose G has a connected component with t vertices and at least t − 1 edges. This
component has a spanning tree T . Pick an arbitrary vertex as the root of T . To encode G,
20

we first specify a bit string encoding the shape of T . This can be done in 2(t−1) bits, tracing
a pre-order traversal of T , where a 0 bit indicates that the path to the next node goes up,
and a 1 bit indicates that the path goes down. Then, we encode the t vertices of T , in the
order as they are first encountered by the pre-order traveral (t log m bits). Furthermore,
for each edge e = uv of T , we store log n bits encoding the element x ∈ X corresponding
to e and a bit indicating whether u = h(x) and v = g(x), or u = g(x) and v = h(x). Again,
the edges are stored in the order and direction as they are encountered by the pre-order
traversal. As T has t − 1 edges, this takes (t − 1)(log n + 1) bits. Finally we directly encode
the remaining 2(n−t +1) endpoints of edges in G, in 2(n−t +1) log m bits. In total, our code
has length
|C(G)| = 2(t − 1) + t log m + (t − 1)(log n + 1) + 2(n − t + 1) log m

= 2n log m + t log c − log n + 3t − 3 − 2t log c + 2 log n + 2 log c

= log m

2n

− t log c + 3t + log n + O(1) ≤ log m

as long as t is such that
t≥

2n

(since m = cn)

−s ,

s + log n + O(1)
.
log(c/8)

In particular, for s = log n, the Uniform Encoding Lemma tells us that G has a component
of size at least (2/ log(c/8)) log n + O(1) with probability O(1/n).
Suppose that when x is inserted, it is placed in an urn with t other elements. Then,
we say that the age of x is a(x) = t.
Theorem 6. Fix c > 8 and suppose we insert n elements into a table of size cn using 2-choice
hashing. With probability 1 − O(1/n) all positions in the hash table contain at most log log n +
O(1) elements.
Proof. Suppose that some element x has a(x) = t. This leads to a binary witness tree T of
height t as follows: The root of T is the element x. When x was inserted into the hash
table, it had to choose between the urns h(x) and g(x), both of which contained at least
t − 1 elements; in particular, h(x) has a unique element xh with a(xh ) = t − 1, and g(x) has a
unique element xg with a(xg ) = t − 1. The elements xh and xg become the left and the right
child of x in T . The process continues recursively. If some element appears more than
once on a level, we only recurse on its leftmost occurrence. See Figure 5 for an example.
Using T , we can iteratively define a connected subgraph GT of G. Initially, GT
consists of the single node in V corresponding to the bucket that contains the root element
x of T . Now, to construct GT , we go through T level by level, starting from the root. For
i = t, . . . , 0, let Li be all elements in T with age i, and let Ei = {(h(x), g(x)) : x ∈ Li } be the
21

..
.
x5
x6
x7
x8
x9
x10

h
..
.
1
2
4
1
1
1

g
..
.
1
3
2
2
4
4






























T =




























x10

x8

a(x) = t − 1

x9

x5
x1

a(x) = t

x6
x1 x2

x5

x3

x7
x4

..
.

x2

a(x) = t − 2
a(x) = t − 3
..
.
a(x) = 0

Figure 5: The tree T is a witness tree for the 2-choice hashing instance with elements
. . . , x5 , x6 , x7 , x8 , x9 , x10 inserted in order and according to the hash functions h and g.
corresponding edges in G. When considering Li , we add to GT all edges in Ei , together with
their endpoints, if they are not in GT already. Since every element appears at most once in
T , this adds |Li | new edges to GT . The number of vertices in GT increases by at most |Li |.
P
In the end, GT contains ti=0 |Li | edges. Since GT is connected, with probability 1 − O(1/n),
the number of edges in GT does not exceed the number of vertices, by Lemma 4. We
assume that this is the case. Since initially GT had one vertex and zero edges, the iterative
P
procedure must add at least ti=0 |Li | − 1 new vertices to GT . This means that all nodes in T
but one must have two children, so we can conclude that T is a complete binary tree with
at most one subtree removed. It follows that T (and hence GT ) has at least 2t vertices. If
we choose t = dlog log n + de, then 2t ≥ 2d log n. We know from Lemma 5 that this happens
with probability O(1/n) for a sufficiently large choice of the constant d.
Remark 3. The arguments in this section can be refined by more carefully encoding the
shape of trees using Cayley’s formula, which says that there are t t−2 unrooted labelled trees
on t nodes [9]. In particular, an unrooted tree with t nodes and m choices for distinct

node labels can be encoded using log mt + (t − 2) log t bits instead of t log m + 2(t − 1) bits.
We would then recover the same results for hash tables of size m = cn with c > 2e instead
of c > 8. In fact, it is known that for any c > 0 searching in 2-choice hashing takes time
1/c + O(log log n) [6]. We leave it as an open problem to find an encoding argument for this
result when c > 0.
Remark 4. Robin Hood hashing is another hashing solution which achieves O(log log n)
worst case running time for all operations [12]. The original analysis is difficult, but might
be amenable to a similar approach as we used in this section. Indeed, when a Robin Hood
hashing operation takes a significant amount of time, a large witness tree is again im-

22

plied, which suggests an easy encoding argument. Unfortunately, this approach appears
to involve unwieldy hypergraph encoding.
4.6

Bipartite Expanders

Expanders are families of sparse graphs which share many connectivity properties with
the complete graph. These graphs have received much research attention, and have led to
many applications in computer science. See, for instance, the survey by Hoory, Linial, and
Wigderson [22].
The existence of expanders was originally established through probabilistic arguments [32]. We offer an encoding argument to prove that a certain random bipartite graph
is an expander with high probability. There are many different notions of expansion. We
will consider what is commonly known as vertex expansion in bipartite graphs: For some
fixed 0 < α ≤ 1, a bipartite graph G = (A, B, E) is called a (c, α)-expander if
min
0

A ⊆A
|A0 |≤α|A|

|N (A0 )|
≥c ,
|A0 |

where N (A0 ) ⊆ B is the set of neighbours of A0 in G. That is, in a (c, α)-expander, every set
of vertices in A that is not too large is “expanded” by a factor c by taking one step in the
graph.
Let G = (A, B, E) be a random bipartite multigraph where |A| = |B| = n and where
each vertex of A is connected to three vertices of B chosen independently and uniformly
at random (with replacement). The following theorem shows that G is an expander. The
proof of this theorem usually involves a messy sum that contains binomial coefficients and
probabilities: see, for example, Motwani and Raghavan [30, Theorem 5.3], Pinsker [32,
Lemma 1], or Hoory, Linial, and Wigderson [22, Lemma 1.9].
Theorem 7. There exists a constant α > 0 such that G is a (3/2, α)-expander with probability
at least 1 − O(n−1/2 ).
Proof. We encode the graph G by presenting its edge set. Since each edge is selected uniformly at random, the graph G is chosen uniformly at random from a set of size n3n .
If G is not a (3/2, α)-expander, then there is some set A0 ⊆ A with |A0 | = k ≤ αn and
|N (A0 )|
< 3/2 .
|A0 |

To encode G, we first give k using an Elias γ-code; together with the sets A0 and N (A0 );
and the edges between A0 and N (A0 ). Then we encode the rest of G, skipping the 3k log n
23

bits devoted to edges incident to A0 . The key savings here come because N (A0 ) should take
3k log n bits to encode, but can actually be encoded in roughly 3k log(3k/2) bits. Our code
then has length
!
!
n
n
|C(G)| = 2 log k + log
+ log
+ 3k log(3k/2) + (3n − 3k) log n + O(1)
k
3k/2
≤ 2 log k + k log n − k log k + k log e + (3k/2) log n − (3k/2) log(3k/2)
+ (3k/2) log e + 3k log(3k/2) + (3n − 3k) log n + O(1)

(by (7))

= 3n log n − (k/2) log n + (k/2) log k + βk + 2 log k + O(1)
= log n3n − s(k)

bits, where β = (3/2) log(3/2) + (5/2) log e and
s(k) = (k/2) log n − (k/2) log k − βk − 2 log k − O(1) .
Since

d2
4−k
s(k) =
log e ,
2
dk
2k 2
the function s(k) is concave for all k ≥ 4. Thus, s(k) is minimized either when k = 1, 2, 3, 4,
or when k = αn. We have
s(1) = (1/2) log n + c1 ,

s(2) = log n + c2 ,

s(3) = (3/2) log n + c3 ,

s(4) = 2 log n + c4 ,

for constants c1 , c2 , c3 , c4 . For k = αn we have


1
s(αn) = (αn/2) log 2β − 2 log αn + c5 ,
2 α
for some constant c5 . Thus, 2−s(αn) = 2−Ω(n) for α < (1/2)2β ≈ 0.002. Now the Uniform
Encoding Lemma gives the desired result. Indeed, the encoding works for all values of k,
and it always saves at least s(1) = (1/2) log n + O(1) bits. Thus, the construction fails with
probability O(n−1/2 ).
4.7

Permutations and Binary Search Trees

We define a permutation σ of size n to be a sequence of n pairwise distinct integers, sometimes denoted by σ = (σ1 , . . . , σn ). The set {σ1 , . . . , σn } is called the support of σ . This slightly
unusual definition will serve us for the purpose of encoding. Except when explicitly stated,
we will assume that the support of a permutation of size n is precisely {1, . . . , n}. For any
fixed support of size n, the number of distinct permutations is n!.

24

4.7.1

Analysis of Insertion Sort

Recall the insertion sort algorithm for sorting a list σ = (σ1 , . . . , σn ) of n elements:
InsertionSort(σ )
1:
2:
3:
4:
5:

for i ← 2 to n do
j ←i
while j > 1 and σj−1 > σj do
σj ↔ σj−1 { swap }
j ← j −1

A typical task in the average-case analysis of algorithms is to determine the number

of times Line 4 executes if σ is a uniformly random permutation of size n. The answer n2 /2

is an easy application of linearity of expectation: For every one of the n2 pairs of indices
p, q ∈ {1, . . . , n} with p < q, the values initially stored at positions σp and σq will eventually be
swapped if and only if σp > σq . This happens with probability 1/2 in a uniformly random
permutation. A pair p, q ∈ {1, . . . , n} with p < q and σp > σq is called an inversion, so the
number of times Line 4 executes is the number of inversions of σ .
A more advanced question is to ask for a concentration result on the number of

inversions. This is harder to tackle; because > is transitive, the n2 events being studied
have a lot of interdependence. In the following, we show how an encoding argument
leads to a concentration result. The argument presented here follows the same outline
as Vitányi’s analysis of bubble sort [38], though without all the trappings of Kolmogorov
complexity.
Theorem 8. Let α ∈ (0, 1/e2 ). A uniformly random permutation σ of size n has at most αn2 −
2
n + 2 inversions with probability at most 2n log(αe )+O(log n) . In particular, for a fixed α < 1/e2 ,
this probability is 2−Ω(n) .
Proof. We encode the permutation σ by recording the execution of InsertionSort on σ .
In particular, we record for each i ∈ {2, . . . , n}, the number of times mi that Line 4 executes
during the i-th iteration of InsertionSort(σ ). With this information, one can run the
following algorithm to recover σ :
InsertionSortReconstruct(m2 , . . . , mn ):
σ ← (1, . . . , n)
2: for i ← n down to 2 do
3:
for j ← i − mi + 1 to i do
4:
σj ↔ σj−1 { swap }
1:

25

5:

return σ

We have to be slightly clever with the encoding. Rather than encode m2 , m3 , . . . , mn
P
directly, we first encode m = ni=2 mi using 2 log n bits (since m < n2 ). Given m, it remains

to describe the partition of m into n − 1 non-negative integers m2 , . . . , mn ; there are m+n−2
n−2
such partitions.2
Therefore, the values of m2 , . . . , mn can be encoded using
!
m+n−2
|C(σ )| = 2 log n + log
n−2
bits and this is sufficient to recover the permutation σ . By applying (7), we obtain
|C(σ )| ≤ (n − 2) log(m + n − 2) − (n − 2) log(n − 2) + (n − 2) log e + O(log n)
≤ n log(m + n − 2) − n log n + n log e + O(log n)
≤ n log(αn2 ) − n log n + n log e + O(log n)

= 2n log n + n log α − n log n + n log e + O(log n)

(since m ≤ αn2 − n + 2)

= n log n + n log α + n log e + O(log n)

= log n! + n log α + 2n log e + O(log n)

(by (6))

2

= log n! + n log(αe ) + O(log n) .
Again, we finish by applying the Uniform Encoding Lemma.
Remark 5. Theorem 8 is not sharp; it only gives a non-trivial probability when α < 1/e2 .
To obtain a sharp bound, one can use the fact that m2 , . . . , mn are independent and that mi
is uniform over {0, . . . , i − 1} together with the method of bounded differences [24]. This
shows that m is concentrated in an interval of size O(n3/2 ).
4.7.2

Records

A (max) record in a permutation σ of size n is some value σi , 1 ≤ i ≤ n, such that
σi = max{σ1 , . . . , σi } .
If σ is chosen uniformly at random, the probability that σi is a record is exactly 1/i. Thus,
the expected number of records in such a permutation is
Hn =

n
X

1/i = ln n + O(1) ,

i=1
2 To see this, draw m + n − 2 white dots on a line, then choose n − 2 dots to colour black. This splits the

remaining m white dots into n − 1 groups whose sizes determine the values of m2 , . . . , mn .

26

the n-th harmonic number. It is harder to establish concentration with non-negligible
probability. To do this, one first needs to show the independence of certain random variables, which quickly becomes tedious. We instead give an encoding argument to show
concentration of the number of records, inspired by a technique used by Lucier, Jiang, and
Li [23] to study the height of random binary search trees (see also Section 4.7.3).
First, we describe a recursive encoding of a permutation σ of size n: Begin by providing the first value of the permutation σ1 ; then show the set of indices from {2, . . . , n}
for which σ takes on a value strictly smaller than σ1 and an explicit encoding of the induced permutation on the elements at those indices; finally, give a recursive encoding of
the permutation induced on the elements strictly larger than σ1 . The number of recursive
invocations is equal to the number of records in σ .
If σ contains k elements strictly smaller than σ1 , then the length `(σ ) of the codeword for σ satisfies
!
n−1
`(σ ) = log n + log
+ log k! + `(σ 0 ) ,
k
where σ 0 is the induced permutation on the n − k − 1 elements strictly larger than σ1 . Thus,
we get the following recursion for the length `(n) of the encoding for a permutation of size
n:
!
!
n−1
`(n) = max
log n + log
+ log k! + `(n − 1 − k) ,
k
k∈{1,...,n−1}
with `(0) = 0 and `(1) = 0. This solves to `(n) = log n!, so the encoding described above is no
better than a fixed-length encoding for σ . However, a simple modification of the scheme
yields a result about the concentration of records in a uniformly random permutation.
Theorem 9. For any fixed c > 2, a uniformly random permutation σ of size n has at least c log n
records with probability at most
2−c(1−H(1/c)) log n+O(log log n) .
Proof. We describe an encoding scheme for permutations with at least t = dc log ne records.
Suppose that the permutation σ has t records r1 < r2 < · · · < rt . First, we define a bit string
x = (x1 , . . . , xt ) ∈ {0, 1}t , where x1 = 0 and xi = 1 if and only if ri lies in the second half of the
interval [ri−1 , n], for i = 2, . . . , t. Recalling that n1 (x) represents the number of ones in the
bit string x, it follows that n1 (x) ≤ log n, so n1 (x)/t ≤ 1/c.
To begin our encoding of σ , we encode the bit string x by giving the set of n1 (x)
ones in x; followed by the recursive encoding of σ from earlier. Now, our knowledge of
the value of xi halves the size of the space of options for encoding the position ri . In other
words, our knowledge of x allows us to encode each record using roughly one less bit per
27

record. More precisely, if the number of choices for each record ri in the original encoding
is mi , such that m1 > · · · > mt , then the number of bits spent encoding records in the new
code is at most
t
X
i=1

log dmi /2e ≤
≤
≤

t
X
i=1
t
X
i=1
t
X

log(mi /2 + 1)
log(mi /2) +

t
X

O(1/mi )

(since log(x + 1) = log x + O(1/x))

i=1

log(mi /2) + O(Ht ) =

i=1

t
X
i=1

log mi − t + O(log log n) ,

since c is a constant. Thus, the total length of the code is
!
t
+ log n! − t + O(log log n)
|C(σ )| ≤
n1 (x)
≤ log n! − t(1 − H(n1 (x)/t)) + O(log log n)

(by (7))

≤ log n! − c(1 − H(1/c)) log n + O(log log n) ,
where this last inequality follows since c > 2, so 0 ≤ n1 (x)/t ≤ 1/c < 1/2, and H(n1 (x)/t) ≤
H(1/c) since H(·) is increasing on [0, 1/2]. We finish by applying the Uniform Encoding
Lemma.
Remark 6. The preceding result only works for c > 2, but it is known that the number
of records in a uniformly random permutation is concentrated around ln n + O(1), where
ln n = α log n for α = 0.6931 . . . . We leave as an open problem whether or not this significant
gap can be closed through an encoding argument.
4.7.3

The Height of a Random Binary Search Tree

Every permutation σ determines a binary search tree BST(σ ) created through the sequential insertion of the keys σ1 , . . . , σn . Specifically, if σ L (respectively, σ R ) denotes the permutation of elements strictly smaller (respectively, strictly larger) than σ1 , then BST(σ ) has σ1
as its root, with BST(σ L ) and BST(σ R ) as left and right subtrees.
Lucier, Jiang, and Li [23] use an encoding argument via Kolmogorov complexity
to study the height of BST(σ ). They show that for a uniformly chosen permutation σ , the
tree BST(σ ) has height at most c log n with probability 1 − O(1/n) for c = 15.498 . . . ; we can
extend our result on records from Section 4.7.2 to obtain a tighter result.
For a node u, let s(u) denote the number of nodes in the tree rooted at u. Then, u
is called balanced if s(u L ), s(u R ) > s(u)/4, where u L and u R are the left and right subtrees
28

of u, respectively. In other words, since each node u determines an interval [v, w], where
v is the smallest node in the subtree rooted at u, and w is the largest such node, then u is
balanced if and only if


w+v w−v −1 w+v w−v −1
−
,
+
u∈
,
2
4
2
4
i.e. u is called balanced if it occurs inside the middle interval of length (w − v − 1)/2 of its
subrange.
Theorem 10. Let σ be a uniformly random permutation of size n. There is a constant c <
9.943483 such that BST(σ ) has height at most c log n with probability 1 − O(1/n).
Proof. Let c > 2/ log(4/3), and suppose that the tree BST(σ ) contains a path Y = (y1 , . . . , yt ) of
length t = dc log ne that starts at the root and in which yi+1 is a child of yi , for i = 1, . . . , t − 1.
Our encoding for σ has three parts. The first part consists of a bit string x =
(x1 , . . . , xt ), where xi = 1 if and only if yi is balanced. From our definition, if yi is balanced, then s(yi+1 ) ≤ (3/4)s(yi ). Since n1 (x) counts the number of balanced nodes along Y ,
we get
1 ≤ (3/4)n1 (x) n ⇐⇒ n1 (x) ≤ log4/3 n .
Next, our encoding contains a fixed-length encoding of yt using log n bits.
The third part of our encoding is recursive: First, encode the value of the root y1
using log dn/2e bits. Note that since we know whether y1 is balanced or not, there are
only n/2 possibilities for the root value, by the discussion above. If y2 is the left child y1 ,
then specify the values in the right subtree of y1 , including an explicit encoding of the
permutation induced by these values; and recursively encode the permutation of values
in subtree of y2 . If, instead, y2 is the right child of y1 , proceed symmetrically. (Note that
a decoder can determine which of these two cases occured by comparing yt with y1 since
y2 < y1 if and only if yt < y1 .) Once we reach yt , we encode the permutations of the two
subtrees of yt explicitly.
The first two parts of our encoding use at most
tH(n1 (x)/t) + log n
bits. The same analysis as in the proof of Theorem 9 shows that the second part of our
encoding has length at most
log n! − t + O(log log n) .

29

In total, our code has length
|C(σ )| = log n! − t + tH(n1 (x)/t) + log n + O(log log n)
!
1
+ log n + O(log log n)
≤ log n! − c log n + c log nH
c log(4/3)
!!
1
+ log n + O(log log n) ,
= log n! − c 1 − H
c log(4/3)
where the inequality uses the fact that c > 2/ log(4/3). Applying the Uniform Encoding
Lemma, we see that BST(σ ) has height at most c log n with probability 1 − O(1/n) for c >
2/ log(4/3) satisfying
!!
1
c 1−H
>2 ,
c log(4/3)
and a computer-aided calculation shows that c = 9.943483 satisfies this inequality.
Remark 7. Devroye, Morin, and Viola [11] show how the length of the path to the key i
in BST(σ ) relates to the number of records in σ . Specifically, he notes that the number of
records in σ is the number of nodes along the rightmost path in BST(σ ). Since the height of
a tree is the length of its longest root-to-leaf path, we obtain as a corollary that the number
of records in a uniformly random permutation is O(log n) with high probability; the result
from Theorem 9 only improves upon the implied constant.
Remark 8. We know that the height of the binary search tree built from the sequential insertion of elements from a uniformly random permutation of size n is concentrated around
α ln n + O(log log n), for α = 4.311 . . . [34]. Perhaps if the gap in our analysis of records in
Remark 6 can be closed through an encoding argument, then so too can the gap in our
analysis of random binary search tree height.
4.7.4

Hoare’s Find Algorithm

In this section, we analyze the number of comparisons made in an execution of Hoare’s
classic Find algorithm [21] which returns the k-th smallest element in an array of n elements. The analysis is similar to that of the preceding section.
We refer to an easy algorithm Partition, which takes as input an array σ = (σ1 , . . . , σn )
and partitions it into the arrays σ L and σ R which contain the values strictly smaller and
strictly larger than σ1 , respectively. The element σ1 is called a pivot. The algorithm
Partition can be implemented so as to perform only n − 1 comparisons as follows:
Partition(σ ):
1:

σ L , σ R ← nil
30

2:
3:
4:
5:
6:
7:

for i ← 2 to n do
if σi > σ1 then
push σi onto σ R
else
push σi onto σ L
return σ L , σ R
Using this, we give the algorithm Find:

Find(k, σ ):
1:
2:
3:
4:
5:
6:

σ L , σ R ← Partition(σ )
if |σ L | ≥ k then
return Find(k, σ L )
else if |σ L | < k − 1 then
return Find(k − |σ L | − 1, σ R )
return σ1

Suppose that the algorithm Find sequentially identifies t pivots x1 , . . . , xt before
finding the solution. Let σ (i) denote the value of σ in the i-th recursive call and let ni =
|σ (i) |, so that σ (0) = (σ1 , . . . , σn ) and n0 = n. We will say that the i-th pivot is good if its rank,
in σ (i) , is in the interval [ni /4, 3ni /4]. Note that a good pivot causes the algorithm to recurse
in a problem of size at most 3ni /4.
Lemma 6. Fix some constants t0 ≥ 1 and 0 < α < 1/2. Suppose that, for each t0 ≤ i ≤ t, the
number of good pivots among x1 , . . . , xi is at least αi. Then, Find makes O(n) comparisons.
Proof. If xj is a good pivot, then the conditions of the lemma give that nj ≤ (3/4)nj−1 .
Therefore, ni ≤ (3/4)αi n for each t0 ≤ i ≤ t, and the total number of comparisons made by
Find is at most
t
t
t
X
X
X
ni ≤ t0 n +
ni ≤ O(n) + n
(3/4)αi = O(n) .
i=0

i=t0

i=t0

Theorem 11. Let σ be a uniformly random permutation. Then, for every fixed probability
p ∈ (0, 1), there exists a constant c such that Find(k, σ ) executes at most cn comparisons with
probability at least p, for any k.
Proof. We again encode the permutation σ . Set α = 1/4 and let t0 be a constant depending
on p. Suppose that the conditions of the preceding lemma are not satisfied for α and t0 ,

31

i.e. there is an i ≥ t0 such that the number of good pivots among x1 , . . . , xi is less than αi.
We encode σ in two parts. The first part of our encoding gives the value of i using an Elias
δ-code, followed by the set of indices of the good pivots among x1 , . . . , xi , which costs
log i + iH(α) + O(log log i) .
Note that the pivots x1 , . . . , xi trace a path from the root in BST(σ ). Therefore, the second
part of our encoding is the recursive encoding presented in Section 4.7.3, in which each
pivot can be encoded using one less bit, since knowing whether xj is a good pivot or not
narrows down the range of possible values for xj by a factor of 1/2. In total, our code then
has length
|C(σ )| ≤ log n! − i + iH(α) + log i + O(log log i) = log n! − Ω(i) ,
since α = 1/4 < 1/2. The proof is completed by applying the Uniform Encoding Lemma,
and by observing that t0 ≤ i can be made arbitrarily large.
4.8

k-SAT and the Lovász Local Lemma

We now consider the question of satisfiability of propositional formulas. Let us start with
some definitions.
A (Boolean) variable x is either true or false. The negation of x is denoted by ¬x.
A literal is either a variable or its negation. A conjunction of literals is an “and” of literals,
denoted by ∧. A disjunction of literals is an “or” of literals, denoted by ∨. A formula ϕ is
an expression including conjunctions and disjunctions of literals, and the set of variables
involved in this formula is called the support of ϕ. A clause is a disjunction of literals, i.e.
the “or” of a set of variables or their negations, e.g.
x1 ∨ ¬x2 ∨ x3 .

(9)

Two clauses will be said to intersect if their supports intersect. The truth value which a
formula ϕ evaluates to under the assignment of values α to its support will be denoted by
ϕ(α), and such a formula is said to be satisfiable if there exists an α with ϕ(α) = true. For
example, the clause in (9) is satisfied for all truth assignments except
(x1 , x2 , x3 ) = (false, true, false) ,
and indeed any clause is satisfied by all but one truth assignment for its support. The
formulas we are concerned with are conjunctions of clauses, which are said to be in conjunctive normal form (CNF). More specifically, when each clause has at most k literals, we
call it a k-CNF formula.

32

The k-SAT decision problem asks to determine whether or not a given k-CNF formula is satisfiable. In general, this problem is hard. Of course, any satisfying truth assignment to the variables in a CNF formula induces a satisfying truth assignment for each of
its clauses. Moreover, if the supports of the clauses are pairwise disjoint, then the formula
is trivially satisfiable, and as we will see, this holds even if the clauses are only nearly pairwise disjoint, i.e., if for each clause the support is disjoint from the supports of all but less
than 2k /e other clauses.
This result has been well known as a consequence of the Lovász Local Lemma [16],
whose original proof is non-constructive, and so does not produce a satisfying truth assignment (in polynomial time) when applied to an instance of k-SAT. Some efficient constructive solutions to k-SAT have been known, but only for suboptimal clause intersection sizes. Moser [28] first presented a constructive solution to k-SAT with near optimal
clause intersection sizes, and Moser and Tardos [29] then generalized this result to the full
Lovász Local Lemma for optimal clause intersection sizes. The analysis which we reproduce in this section comes from Fortnow’s rephrasing of Moser’s proof for k-SAT using the
incompressibility method [18].
Moser’s algorithm is remarkably naı̈ve, and can be described in only a few sentences: Pick a uniformly random truth assignment for the variables of ϕ. For each unsatisfied clause, attempt to fix it by producing a new uniformly random truth assignment for
its support, and recursively fix any intersecting clause which is made unsatisfied by this
reassignment. We describe this process more carefully in the algorithms Solve and Fix
below.
Solve(ϕ):
1:
2:
3:
4:
5:

α ← uniformly random truth assignment in {true, false}n
while ϕ(α) = false do
D ← an unsatisfied clause in ϕ
α ← Fix(ϕ, α, D)
return α

Fix(ϕ, α, D):
1:
2:
3:
4:
5:
6:

β ← uniformly random truth assignment in {true, false}k
replace the assignments in α for D 0 s support with the values in β
while ϕ(α) = false do
D 0 ← an unsatisfied clause in ϕ intersecting D
α ← Fix(ϕ, α, D 0 )
return α

33

Theorem 12. Given a k-CNF formula ϕ with m clauses and n variables such that each clause
intersects at most r < 2k−3 other clauses, then the total number of invokations of Fix in the
execution of Solve(ϕ) is at least s + m log m with probability at most 2−s .
Proof. Suppose that Fix is called t = ds + m log me times. Let α ∈ {true, false}n be the initial
truth assignment for ϕ, and let β1 , . . . , βt ∈ {true, false}k be the local truth assignments
produced in each call to Fix. The string γ = (α, β1 , . . . , βt ) is uniformly chosen from a set of
size 2n+tk , and will be the subject of our encoding.
The execution of Solve(ϕ) determines a (rooted ordered) recursion tree T on t + 1
nodes as follows: The root of T corresponds to the initial call to Solve(ϕ). Every other
node corresponds to a call to Fix. The children of a node correspond to the sequence of
calls to Fix that the procedure performs, ordered from left to right. Each (non-root) node in
the tree is assigned a clause and its uniformly random truth assignment produced during
the call to Fix. Moreover, a pre-order traversal of this tree describes the order of function
calls in the algorithm’s execution.
The string γ can be recovered in a bottom-up manner from our knowledge of the
tree T and the final truth assignment α 0 after t calls to Fix. Specifically, let D1 , . . . , Dt be the
clauses encountered in a pre-order traversal of T . In particular, Dt is the last fixed clause in
the execution. Since Dt was not satisfied before its reassignment, this allows us to deduce
k values of the previous assignment before Dt was fixed. Pruning Dt from the tree and
continuing in this manner at Dt−1 , we eventually recover the original truth assignment α
produced in Solve(ϕ).
Therefore, to encode γ, we give the final truth assignment α 0 ; and a description of
the shape of the tree T ; and the sequence of at most m clauses which are children of the
root of T ; and the at most t clauses involved in the calls to Fix in a pre-order traversal of
T.
The key savings come from the fact that each clause intersects at most r other
clauses, so each clause (which is not a child of the root) can be encoded using log r bits.
Each clause which is a child of the root can be encoded using log m bits, and since the order
of these children might be significant, we use m log m bits to encode the full sequence of
these clauses. Finally, as in Lemma 5, the shape of T can be encoded using 2t bits. In total,
the code has length
|C(γ)| ≤ n + 2t + m log m + t log r

≤ n + 2t + m log m + t(k − 3)

= n + tk − t + m log m ≤ n + tk − s .
34

(since r ≤ 2k−3 )

The result is obtained by applying the Uniform Encoding Lemma.
Remark 9. By more carefully encoding of the shape of the recursion tree above, Messner and Thierauf [25] gave an encoding argument for the above result in which r < 2k /e.
Specifically, their refinement follows from a more careful counting of the number of trees
with nodes of bounded degree.

5

The Non-Uniform Encoding Lemma and Shannon-Fano Codes

Thus far, we have focused on applications that could always be modelled as choosing some
element x uniformly at random from a finite set X. To encompass even more applications,
it is helpful to have an Encoding Lemma that deals with non-uniform distributions over X.
First, we recall the following useful classic results:
Theorem 13 (Markov’s Inequality). For any non-negative random variable Y with finite expectation, and any a > 0,
Pr{Y ≥ a} ≤ (1/a) E{Y } .
We will say that a real-valued function ` : X → R satisfies Kraft’s condition if
X
2−`(x) ≤ 1 .
x∈X

Lemma 7 (Kraft’s Inequality and prefix-free codes). If C : X 9 {0, 1}∗ is a partial prefix-free
code, then the function ` : x 7→ |C(x)| satisfies Kraft’s condition. Conversely, for any function
` : X → N satisfying Kraft’s condition, there exists a prefix-free code C : X → {0, 1}∗ such that
|C(x)| = `(x) for all x ∈ X.
The following generalization of the Uniform Encoding Lemma, which was originally proven by Barron [4, Theorem 3.1], serves for non-uniform input distributions:
Lemma 8 (Non-Uniform Encoding Lemma). Let C : X 9 {0, 1}∗ be a partial prefix-free code,
and let p be a probability distribution on X. Suppose we draw x ∈ X randomly with probability
px . Then, for any s ≥ 0,
Pr{|C(x)| ≤ log(1/px ) − s} ≤ 2−s .
Proof. We use Chernoff’s trick of exponentiating both sides before applying the Markov

35

inequality, and Kraft’s inequality:
Pr{|C(x)| ≤ log(1/px ) − s} = Pr{|C(x)| − log(1/px ) ≤ −s}
= Pr{log(1/px ) − |C(x)| ≥ s}
n
o
= Pr 2log(1/px )−|C(x)| ≥ 2s
n
o
E 2log(1/px )−|C(x)|
≤
2s



1 X
= s 
px · 2log(1/px )−|C(x)| 
2
x∈X

1 X −|C(x)| 
 .
2
= s 

2

(Chernoff’s trick)
(Markov’s inequality)

x∈X

By Kraft’s inequality,

P

x∈X 2

−|C(x)|

≤ 1, and the result is obtained.

The Non-Uniform Encoding Lemma is a strict generalization of the Uniform Encoding Lemma: Take px = 1/|X| for all x ∈ X and we obtain the Uniform Encoding Lemma.
As in Section 3.1, we will be interested in using a Shannon-Fano code Cα to encode
Bernoulli(α) bit strings of length n. Recall that for such a string x, this code has length
n1 (x) log(1/α) + n0 (x) log(1/(1 − α)) ,
since for now we are not concerned with ceilings.

6

Applications of the Non-Uniform Encoding Lemma

6.1

Chernoff Bound

We will now prove the so-called additive version of the Chernoff bound on the tail of a
binomial random variable [10]. Theorem 2 dealt with the special case of this result for
Bernoulli(1/2) bit strings.
Theorem 14. If B is a Binomial(n, p) random variable, then for any ε ≥ 0,
Pr{B ≤ (p − ε)n} ≤ 2−nD(p−ε k p) ,
where
D(p k q) = p log(p/q) + (1 − p) log((1 − p)/(1 − q))
is the Kullback-Leibler divergence or relative entropy between Bernoulli(p) and Bernoulli(q)
random variables.
36

P
Proof. By definition, B = ni=1 xi , where x1 , . . . , xn are independent Bernoulli(p) random
variables. We will use an encoding argument on the bit string x = (x1 , . . . , xn ). The proof is
almost identical to that of Theorem 2—now, we encode x using a Shannon-Fano code Cα ,
with α = p − ε. Such a code has length
|Cp−ε (x)| = n1 (x) log(1/(p − ε)) + n0 (x) log(1/(1 − p + ε)) .
Now, x appears with probability px = pn1 (x) (1 − p)n0 (x) . This allows us to express |Cp−ε (x)| in
terms of log(1/px ) as follows
|Cp−ε (x)| = log(1/px ) + n1 (x) log(p/(p − ε)) + (n − n1 (x)) log((1 − p)/(1 − p + ε))
!
!
ε
ε
= log(1/px ) + n1 (x) log 1 +
+ (n1 (x) − n) log 1 +
,
p−ε
1−p
and |Cp−ε (x)| increases as a function of n1 (x). Therefore, if n1 (x) ≤ (p − ε)n, then
|Cp−ε (x)| ≤ log(1/px ) − n(p − ε) log((p − ε)/p) − n(1 − p + ε) log((1 − p + ε)/(1 − p))
= log(1/px ) − nD(p − ε k p) .

The Chernoff bound is obtained by applying the Non-Uniform Encoding Lemma.
6.2

Percolation on the Torus

Percolation theory studies the emergence of large components in random graphs. For a
general study of percolation theory, see the book by Grimmett [19]. We give an encoding
argument proving that percolation occurs on the torus when edge survival rate is greater
than 2/3, i.e. in random subgraphs of the torus grid graph in which each edge is included
independently at random with probability at least 2/3, only at most one large component
emerges. Our line of reasoning follows what is known as a Peierls argument.
√
√
√
Suppose that n is an integer. The n × n torus grid graph is defined to be the
√
graph with vertex set {1, . . . , n}2 , where (i, j) is adjacent to (k, l) if

√
n) and j = l, or
√
• |i − k| = 0 and |j − l| ≡ 1 (mod n).
√
√ √
Theorem 15. Suppose that n is an integer. Let G be a subgraph of the n× n torus grid graph
in which each edge is chosen with probability p < 1/3. Then, the probability that G contains a
cycle of length at least
s + log n
log(1/(3p))
• |i − k| ≡ 1 (mod

is at most 2−s .
37

Proof. Let A be the bit string of length 2n encoding the edge set of G. then the probability
pG that the graph G is sampled is
pG = pn1 (A) (1 − p)n0 (A) .
Suppose that G contains a cycle C 0 of length t ≥ (s+log n+O(1))/ log(1/(3p)). We encode A as
follows: first, we give a single vertex u in C 0 (log n bits). Then, we provide the sequence of
directions that the cycle moves along from u. There are four possibilities for the direction
of the first step taken by C 0 from u, but only three for each subsequent choice. Thus, this
sequence can be specified by 2 + (t − 2) log 3 bits. We conclude with a Shannon-Fano code
with parameter p for the remaining edges of G ((n1 (A)−t) log(1/p)+n0 (A) log(1/(1−p)) bits.
The total length of our code is then
|C(G)| = log n + 2 + (t − 2) log 3 + (n1 (A) − t) log(1/p) + n0 (A) log(1/(1 − p))
≤ log(1/pG ) + log n − t log(1/(3p)) + O(1)
≤ log(1/pG ) − s

by our choice of t, since 2 + (t − 2) log 3 ≤ t log 3. We finish by applying the Non-Uniform
Encoding Lemma.
The torus grid graph can be drawn in the obvious way without crossings on the
surface of a torus. This graph drawing gives rise to a dual graph, in which each vertex
corresponds to a face in the primal drawing, and two vertices are adjacent if and only their
primal faces are incident to the same edge. This dual graph is isomorphic to the original
torus grid graph.
This drawing of the torus grid graph also induces drawings for any of its subgraphs.
Any such subgraph also has a dual, where each vertex corresponds to a face in the dual
torus grid graph, and two vertices are adjacent if and only if their corresponding faces are
incident to the same edge of the original subgraph.
√
√
√
Theorem 16. Suppose that n is an integer. Let G be a subgraph of the n × n torus grid
graph in which each edge is chosen with probability greater than 2/3. Then, G has at most one
component of size ω(log2 n) with high probability.
Proof. See Figure 6 for a visualization of this phenomenon. Suppose that G has at least two
components of size ω(log2 n). Then, there is a cycle of faces separating these components
whose length is ω(log n). From the discussion above, such a cycle corresponds to a cycle of
ω(log n) missing edges in the dual graph, as in Figure 6a. From Theorem 15, we know that
this does not happen with high probability.

38

.

.

(a) When p = 0.33 < 1/3, long cycles are rare.
Dotted lines show missing edges in the dual.

(b) When p = 0.67 > 2/3, there is likely to be
only one large component.

Figure 6: Random subgraphs of the 20 × 20 torus grid graph.
6.3

Triangles in Gn,p

Recall as in Section 4.1 that the Erdős-Rényi random graph Gn,p is the probability space

of undirected graphs with vertex set V = {1, . . . , n} and in which each edge {u, w} ∈ V2 is
present with probability p and absent with probability 1 − p, independently of the other
edges.
By linearity of expectation, the expected number of triangles (cycles of length 3) in

Gn,p is p3 n3 . For p = (6c)1/3 /n, this expectation is c − O(1/n). Unfortunately, even when c is
a large constant, it still takes some work to show that there is a constant probability that
Gn,p contains at least one triangle. Indeed, this typically requires the use of the second
moment method, which involves computing the variance of the number of triangles in
Gn,p . To show that Gn,p has a triangle with more significant probability is even more complicated, and a proof of this result would still typically rely on an advanced probabilistic
inequality [2]. Here we show how this can be accomplished with an encoding argument.
Theorem 17. For c ∈ (0, log1/3 n] and p = c/n, G ∈ Gn,p contains at least one triangle with
3
probability at least 1 − 2−Ω(c ) .
Proof. In this argument, we will produce an encoding of G’s adjacency matrix, A. For
simplicity of exposition, we assume that n is even.
Refer to Figure 7. If G contains no triangles, then we look at the number of ones
in the n/2 × n/2 submatrix M determined by rows 1, . . . , n/2 and columns n/2 + 1, . . . , n.
Note that n1 (M), the number of ones in M, is a Binomial(n2 /4, c/n) random variable with
39

1

1
2

3

9

10

8

4

1
2
3
4
5
6
7
8
9

2
0

3
0
0

4
0
0
0

5
1
0
0
0

6
0
1
0
0
0

7
0
1
0
1
0
0

8
0
0
1
0
0
0
0

9
1
0
0
0
0
0
1
0

10
0
0
1
0
0
0
0
0
0

5

7

6

Figure 7: The random graph Gn,c/n contains triangles when c is large enough. The highlighted 0 bits in the last five rows can be deduced from pairs of 1 bits in the first 5 rows.
expectation cn/4. There are three events to consider:
1. Event E1 : The number n1 (M) of ones in M is at most cn/8. In this case, the number of
ones in this submatrix is much less than the expected number, cn/4. We can simply
3
apply Chernoff’s bound to show that Pr {E0 } = 2−Ω(c ) . We leave this as an exercise to
the reader.
2. Event E2 : Fix n/2 + 1 ≤ j < k ≤ n, and let Bjk be the event that M contains at least
three
1 ≤ i1 < i2 < i3 ≤ n/2 with Ail ,j = Ail ,k = 1, for l = 1, 2, 3. Clearly, we have
n rows
o

6
6 3
Pr Bjk ≤ n/2
3 (c/n) = O c /n . Let E2 be the event that Bjk holds for at least one

6
pair n/2 + 1 ≤ j < k ≤ n. Since there are n/2
2 such pairs, we have Pr {E2 } = O(c /n) =
3
2−Ω(c ) , as we assumed c ≤ log1/3 n.
3. Event E3 : Let E3 be the event that (i) the number of ones in M is greater than cn/8;
(ii) for each pair n/2 + 1 ≤ j < k ≤ n, there are at most two rows in M where both the
entry with index j and the entry with index k are set two one; and (iii) G contains no
triangles. Notice that, for i < j < k if Ai,j = 1 and Ai,k = 1, then the fact that there are
no triangles implies that Aj,k = 0.
Let mi be the number of ones in the i-th row of the submatrix. By specifying rows
1, . . . , n/2, we eliminate the need to specify
!
!
!
n/2
X
mi
2n1 (M)/n
c/4
m ≥ (1/2)
≥ (n/4)
≥ (n/4)
= Ω(c2 n) ,
2
2
2
i=1

zeros in rows n/2 + 1, . . . , n (here, we used the fact that each pair of ones appears in

at most two rows and that the function x 7→ 2x is convex and increasing for x ≥ 1/4).
40

We thus encode G by giving a Shannon-Fano code with parameter p for the first n/2
rows of A; and a Shannon-Fano code with parameter p for the rest of A, excluding the
bits which can be deduced from the preceding information. Such a code has length
|C(G)| = n1 (A) log(1/p) + (n0 (A) − m) log(1/(1 − p))
which results in a savings of
s = log(1/pG ) − |C(G)| = m log(1/(1 − p)) ≥ Ω(c2 n) log(1/(1 − p)) = Ω(c3 ) .
3

It follows that Pr {E3 } ≤ 2−Ω(c ) .
3

Now the probability that G contains no triangles is at most Pr {E1 }+Pr {E2 }+Pr {E3 } = 2−Ω(c ) .
Theorem 18. If p = c/n with c > 0, then G ∈ Gn,p has no triangle with probability at least 1−c3 .
Proof. Suppose that G contains a triangle. We encode the adjacency matrix A of G. First,
we specify the triangle’s vertices; and finish with a Shannon-Fano code with parameter p
for the remaining edges of the graph. This code has length
|C(G)| = 3 log n + (n1 (A) − 3) log(1/p) + n0 (A) log(1/(1 − p))

= log(1/pG ) + 3 log n − 3 log(1/p) = log(1/pG ) + 3 log c = log(1/pG ) + log c3 .

Together, Theorem 17 and Theorem 18 establish the fact that 1/n is a threshold
function for triangle-freeness, i.e. if p = o(1/n), then G ∈ Gn,p has no triangle with high
probability, and if p = ω(1/n), then G has a triangle with high probability.

7

Encoding with Kraft’s Condition

As promised in Section 2.3, we finally discuss why it has made sense to omit ceilings in all
of our encoding arguments.
Let [0, ∞] denote the set of extended non-negative real numbers, supporting the
extended arithmetic operations a + ∞ = ∞ for all a ∈ [0, ∞], and 2−∞ = 0.
Recall from Section 5 that a function ` : X → [0, ∞] satisfies Kraft’s condition if
X
2−`(x) ≤ 1 .
x∈X

41

The main observation is that neither the (Non-)Uniform Encoding Lemma nor any
of its applications has actually required the specification of an explicit prefix-free code: We
know, by construction, that every code we have presented is prefix-free, but we could also
deduce from Kraft’s inequality that, since our described codes satisfy Kraft’s condition, a
prefix-free code with the same codeword lengths exists. Similarly, we will see that it is
actually enough to assign to every element from our universe a codeword length such that
Kraft’s condition is satisfied. These codeword lengths need not be integers.
Lemma 9 (The encoding lemma for the Kraft inequality). Let ` : X → [0, ∞] satisfy Kraft’s
condition and let x ∈ X be drawn randomly where px > 0 denotes the probability of drawing x.
Then
Pr{`(x) ≤ log(1/px ) − s} ≤ 2−s .
Proof. The proof is identical to that of Lemma 8.
The sum of two functions ` : X → [0, ∞] and ` 0 : X 0 → [0, ∞] is the function ` + ` 0 :
X×
→ [0, ∞] defined by (` + ` 0 )(x, x0 ) = `(x) + ` 0 (x0 ). Note that for any partial codes
C : X 9 {0, 1}∗ , C 0 : X 0 9 {0, 1}∗ , any x ∈ X, and any x0 ∈ X 0 ,
X0

(|C| + |C 0 |)(x, x0 ) = |C(x)| + |C 0 (x0 )| = |(C · C 0 )|(x, x0 ) .

In other words, the sum of the functions of codeword lengths describes the length of codewords in concatenated codes.
Lemma 10. If ` : X → [0, ∞] and ` 0 : X 0 → [0, ∞] satisfy Kraft’s condition, then so does ` + ` 0 .
Proof. Kraft’s condition still holds:
X
XX
X
X
0
0
0 0
0 0
2−`(x)−` (x ) =
2−`(x)
2−` (x ) ≤ 1 .
2−(`+` )(x,x ) =
x∈X x0 ∈X 0

(x,x0 )∈X×X 0

x∈X

x0 ∈X 0

This is analogous to the fact that the concatenation of prefix-free codes is prefixfree.
Lemma 11. For any probability density p : X → (0, 1), the function ` : X → [0, ∞] with `(x) =
log(1/px ) satisfies Kraft’s condition.
Proof.

X
x∈X

2−`(x) =

X

2− log(1/px ) =

x∈X

X
x∈X

42

px = 1 .

This tells us that we can ignore the ceiling in every instance of a fixed-length code
and every instance of a Shannon-Fano code while encoding.
We now give a tight notion corresponding to Elias codes.
Theorem 19 (Beigel [5]). Fix some 0 < ε < e − 1. Let ` : N → R be defined as
`(i) = log i + log log i + · · · + log · · · log i − (log log(e − ε)) log∗ i + O(1) .
| {z }
log∗ i times

Then, ` satisfies Kraft’s condition. Moreover, the function ` 0 : N → R with
` 0 (i) = log i + log log i + · · · + log · · · log i − (log log e) log∗ i + c
| {z }
log∗ i times

does not satisfy Kraft’s condition for any choice of the constant c.
It is not hard to see how Lemma 9, Lemma 10, Lemma 11, and Theorem 19 can be
used to give encoding arguments with real-valued codeword lengths. For example, recall
how the result of Theorem 1 carried an artifact of binary encoding. Using our new tools,
we can now refine this and recover the exact result.
Theorem 1b. Let x = (x1 , . . . , xn ) ∈ {0, 1}n be chosen uniformly at random and let t = dlog n + se.
Then, the probability that x contains a run of t ones is at most 2−s .
Proof. Let ` : {0, 1}n → [0, ∞] be such that if x contains a run of t = dlog n + se ones, then
`(x) = log n + n − t, and otherwise `(x) = ∞. We will show that ` satisfies Kraft’s condition.
Let the function f : {1, . . . , n−t+1} → [0, ∞] have f (i) = log n for all i ∈ {1, . . . , n−t+1},
and g : {0, 1}n−t → [0, ∞] have g(y) = n − t for all y ∈ {0, 1}n−t . Both f and g satisfy Kraft’s
condition by Lemma 11. By Lemma 10, so does the function
h = f + g : {1, . . . , n − t + 1} × {0, 1}n−t → [0, ∞] ,
where h(i, y) = log n+n−t for all i and y. Crucially, each element (i, (y1 , . . . , yn−1 )) ∈ {1, . . . , n−
t + 1} × {0, 1}n−t yields to an n-bit binary string containing a run of t ones, namely
(y1 , . . . , yi−1 , 1, 1, . . . , 1, yi , . . . , yn−t ) ,
| {z }
t times

and this mapping is surjective. Thus, ` is as desired. We finish by applying Lemma 9.

43

8

Summary and Conclusions

We have described a simple method for producing encoding arguments. Using our encoding lemmas, we gave original proofs for several previously established results.
Encoding arguments often give natural and short proofs for results in the analysis
of algorithms, particularly for algorithms which directly handle bit strings. Many of our
results concern the worst-case running time of algorithms, but encoding arguments can
also be used to study other measures of algorithmic complexity, such as the average-case
running time of algorithms, or the communication complexity of Boolean functions [8].
Typically, to produce an encoding argument, one would invoke the incompressibility method after developing some of the theory of Kolmogorov complexity. Our technique
requires only a basic understanding of prefix-free codes and one simple lemma. We are
also the first to suggest a simple and tight manner of encoding using only Kraft’s condition with real-valued codeword lengths. In this light, we posit that there is no reason to
develop an encoding argument through the incompressibility method: our Uniform Encoding Lemma is simpler, the Non-Uniform Encoding Lemma is more general, and our
technique from Section 7 is less wasteful. Indeed, though it would be easy to state and
prove our Non-Uniform Encoding Lemma in the setting of Kolmogorov complexity, it
seems as if the general encoding lemma from Section 7 only can exist in our simplified
framework.

Acknowledgements
This research was initiated in response to an invitation for the first author to give a talk
at the Ninth Annual Probability, Combinatorics and Geometry Workshop, held April 4–
11, 2014, at McGill University’s Bellairs Institute. Many ideas that appear in the current
paper were developed during the workshop. The author is grateful to the other workshop
participants for providing a stimulating working environment. In particular, Xing Shi Cai
pointed out the application to runs in binary strings (Theorem 1) and Gábor Lugosi stated
and proved the Non-Uniform Encoding Lemma (Lemma 8) in response to the first author’s
half-formed ideas about a non-uniform version of Lemma 1, and then later pointed us to
the proof in Barron’s thesis. We would also like to thank Yoshio Okamoto, Günter Rote,
and the anonymous referees for valuable comments.

References
[1] ACM/IEEE-CS Joint Task Force on Computing Curricula. Computer science curricula 2013: Curriculum guidelines for undergraduate degree programs in computer
44

science. Technical report, ACM Press and IEEE Computer Society Press, December
2013.
[2] N. Alon and J. H. Spencer. The Probabilistic Method. Wiley Series in Discrete Mathematics and Optimization. Wiley-Interscience, 4 edition, 2016.
[3] Y. Azar, A. Z. Broder, A. R. Karlin, and E. Upfal. Balanced allocations. SIAM Journal
on Computing, 29(1):180–200, February 2000.
[4] A. R. Barron. Logically Smooth Density Estimation. PhD thesis, Stanford University,
September 1985.
[5] R. Beigel. Unbounded searching algorithms. SIAM Journal on Computing, 19(3):522–
537, 1990.
[6] P. Berenbrink, A. Czumaj, A. Steger, and B. Vöcking. Balanced allocations: The heavily loaded case. SIAM Journal on Computing, 35(6):1350–1385, 2006.
[7] R. Boucheron, G. Lugosi, and P. Massart. Concentration Inequalities: A Nonasymptotic
Theory of Independence. Oxford University Press, Oxford, United Kingdom, 2013.
[8] H. Buhrman, T. Jiang, M. Li, and P. Vitányi. New applications of the incompressibility
method: Part II. Theoretical Computer Science, 235(1):59–70, 2000.
[9] A. Cayley. A theorem on trees. Quarterly Journal of Mathematics, 23:376–378, 1889.
[10] H. Chernoff. A measure of asymptotic efficiency for tests of a hypothesis based on the
sum of observations. The Annals of Mathematical Statistics, 23(4):493–507, 12 1952.
[11] L. Devroye. Applications of the theory of records in the study of random trees. Acta
Informatica, 26(1):123–130, 1988.
[12] L. Devroye, P. Morin, and A. Viola. On worst-case Robin Hood hashing. SIAM Journal
on Computing, 33(4):923–936, 2004.
[13] D. P. Dubhashi and A. Panconesi. Concentration of Measure for the Analysis of Randomized Algorithms. Cambridge University Press, New York, New York, 2009.
[14] P. Elias. Universal codeword sets and representations of the integers. IEEE Transactions on Information Theory, 21(2):194–203, March 1975.
[15] P. Erdős. Some remarks on the theory of graphs. Bulletin of the American Mathematics
Society, 53:292–294, 1947.

45

[16] P. Erdős and L. Lovász. Problems and results on 3-chromatic hypergraphs and some
related questions. In A. Hajnal, R. Rado, and V. T. Sós, editors, Infinite and Finite Sets,
volume 10 of Colloquia Mathematica Societatis János Bolyai, pages 609–627. NorthHolland, 1973.
[17] R. M. Fano. The transmission of information. Technical Report 65, Research Laboratory of Electronics at MIT, Cambridge, Massachusetts, 1949.
[18] L. Fortnow.
A Kolmogorov complexity proof of the Lovász local
lemma.
http://blog.computationalcomplexity.org/2009/06/
kolmogorov-complexity-proof-of-lov.html, 2009.
(last accessed November
28, 2015).
[19] G. R. Grimmett. Percolation. 321. Springer-Verlag Berlin Heidelberg, 2 edition, 1999.
[20] T. Haimberger. Theoretische und Experimentelle Untersuchung von KuckucksHashing. Bachelor’s thesis. Freie Universität Berlin, 2013.
[21] C. A. R. Hoare. Algorithm 65: Find. Communications of the ACM, 4(7):321–322, July
1961.
[22] S. Hoory, N. Linial, and A. Wigderson. Expander graphs and their applications. Bulletin of the American Mathematical Society, 43(4):439–561, October 2006.
[23] B. Lucier, T. Jiang, and M. Li. Average-case analysis of Quicksort and binary insertion
tree height using incompressibility. Information Processing Letters, 103(2):45–51, July
2007.
[24] C. McDiarmid. On the method of bounded differences. In J. Siemons, editor, Surveys
in Combinatorics: Invited Papers at the 12th British Combinatorial Conference, number
141, pages 148–188. Cambridge University Press, 1989.
[25] J. Messner and T. Thierauf. A Kolmogorov complexity proof of the Lovász local
lemma for satisfiability. Theoretical Computer Science, 461:55–64, November 2012.
[26] M. Mitzenmacher and E. Upfal. Probability and Computing: Randomized Algorithms
and Probabilistic Analysis. Cambridge University Press, 2005.
[27] P. Morin. Open Data Structures: An Introduction. Athabasca University Press, Edmonton, 2013. Also freely available at opendatastructures.org.
[28] R. A. Moser. A constructive proof of the Lovász local lemma. In Proceedings of the
41st Annual ACM Symposium on Theory of Computing, STOC ’09, pages 343–350, New
York, NY, USA, 2009. ACM.

46

[29] R. A. Moser and G. Tardos. A constructive proof of the general Lovász local lemma.
Journal of the ACM, 57(2):11:1–11:15, January 2010.
[30] R. Motwani and P. Raghavan. Randomized Algorithms. Cambridge University Press,
New York, New York, 1995.
[31] R. Pagh and F. F. Rodler. Cuckoo hashing. Journal of Algorithms, 51(2):122–144, 2004.
[32] M. S. Pinsker. On the complexity of a concentrator. In The 7th International Teletraffic
Conference, volume 4, pages 1–4, 1973.
[33] M. Pătraşcu.
Cuckoo hashing.
http://infoweekly.blogspot.ca/2010/02/
cuckoo-hashing.html, 2010. (last accessed April 15, 2015).
[34] B. Reed. The height of a random binary search tree. Journal of the ACM, 50(3):306–
332, May 2003.
[35] H. Robbins. A remark on Stirling’s formula. The American Mathematical Monthly,
62(1):26–29, jan 1955.
[36] R. Sedgewick and P. Flajolet. An Introduction to the Analysis of Algorithms. AddisonWesley Longman Publishing Co., Inc., Boston, MA, USA, 1996.
[37] C. E. Shannon. A mathematical theory of communication. Bell Systems Technical
Journal, 27:379–423, 1948.
[38] P. Vitányi. Analysis of sorting algorithms by Kolmogorov complexity (a survey). In
Entropy, Search, Complexity, volume 16 of Bolyai Society Mathematical Studies, pages
209–232. Springer-Verlag New York, 2007.
[39] B. Vöcking. How asymmetry helps load balancing. Journal of the ACM, 50(4):568–589,
July 2003.

47

