CMSC-27100

Discrete Math

Winter Quarter, 2019

Home Lectures Policies

---

Piazza

Lecture 19: Asymptotics, continued

\( \newcommand{\set}[1]{\{#1\}} \newcommand{\comprehension}[2]{\{#1\,\vert\,#2\}} \newcommand{\size}[1]{\left\vert#1\right\vert} \newcommand{\true}{\top} \newcommand{\false}{\bot} \newcommand{\limplies}{\rightarrow} \newcommand{\divides}{\mathbin{\vert}} \newcommand{\mult}{\mathbin{\cdot}} \newcommand{\xor}{\oplus} \newcommand{\union}{\cup} \newcommand{\intersect}{\cap} \newcommand{\complement}[1]{\overline#1} \newcommand{\powerset}{\mathcal{P}} \newcommand{\ixUnion}{\bigcup} \newcommand{\ixIntersect}{\bigcap} \newcommand{\Div}{\mathrm{div}} \newcommand{\gcd}{\mathrm{gcd}} \newcommand{\divmod}{\mathop{\mathbf{divmod}}} \newcommand{\div}{\mathop{\mathbf{div}}} \newcommand{\mod}{\mathop{\mathbf{mod}}} \newcommand{\ceiling}[1]{\lceil#1\rceil} \newcommand{\floor}[1]{\lfloor#1\rfloor} \DeclareMathOperator{\Pr}{Pr} \DeclareMathOperator{\rng}{rng} \DeclareMathOperator{\E}{E} \DeclareMathOperator{\V}{V} \newcommand{\abs}[1]{\left\lvert#1\right\rvert} \)

This material follows Babai Ch. 2.

Let's remind ourselves of a few definitions from calculus:

Definition 19.1. (finite limit of a sequence) Let $\comprehension{a_n}{n\in\omega}$ be an infinite sequence of real numbers. We write $\lim_{n\to\infty} a_n = c$ (or simply $a_n \to c$) if

\begin{equation*} \forall \varepsilon > 0, \exists n_0 \in \mathbb{N}, \forall n \geq n_0, \abs{a_n-c} \lt \varepsilon. \end{equation*}

A sequence converges if it has a finite limit.

Definition 19.2 (infinite limit of a sequence) Let $\comprehension{a_n}{n\in\omega}$ be an infinite sequence of real numbers. We write $\lim_{n\to\infty} a_n = \infty$ (or simply $a_n \to \infty$) if

\begin{equation*} \forall L \in \mathbb{N}, \exists n_0 \in \mathbb{N}, \forall n \geq n_0, a_n \geq L. \end{equation*}

Definition 19.3 Let $a_n$ and $b_n$ be real-valued sequences. We say $a_n$ is asymptotically equal to $b_n$ (denoted $a_n \sim b_n$) if $\lim_{n\to\infty}a_n/b_n = 1$. For the purposes of this definition, for an individual term, $0/0 = 1$.

Note that $\sim$ partitions the set of real-valued sequences more finely than $\Theta$, i.e., $a_n \sim b_n$ implies $\text{$a_n$ is $\Theta(b_n)$}$, but not conversely. The lead constant factor matters for $\sim$, but not for $\Theta$.

Somewhat surprisingly, in light of Exercise 19.5, the asymptotic relation $\sim$ is not preserved under addition. The issue (somewhat surprisingly) is the instability of subtraction. Consider the sequences

\begin{align*} a_n &= 1 + 1/n \\ b_n &= 1 \\ c_n &= -1 \\ d_n &- -1 \\ \end{align*}

We easily see that $a_n \sim b_n$ and $c_n \sim d_n$, but $a_n + c_n = 1/n \not\sim 0 = b_n + d_n$.

Note that the “special circumstances” of Exercise 19.6 are actually a fairly typical case, as we're often interested in comparing sequences/functions that tend to infinity.

Theorem 19.7 (Stirling's Formula)

\begin{equation*} n! \sim \left({n\over e}\right)^n \sqrt{2 \pi n} \end{equation*}

The proof of Stirling's formula goes beyond this class, but it is important and well worth knowing. In particular, it gives us a very useful understanding of the rate of growth of the factorial function.

Let $exp(x) = e^x$, and $\ln x$ denote the natural logarithm function.

Theorem 19.9 (The Prime Number Theorem) Let $\pi(x)$ be the number of primes less than or equal to $x$. Then

\begin{equation*} \pi(x) \sim {x \over \ln x}. \end{equation*}

Again, the proof of this theorem (which was first discovered using analytic number theory) goes well beyond this course, but it is still an important result for us.

Recurrence Relations

We now move to Chapter 8 of Rosen.

One of the most useful techniques in algorithms (and problem solving generally) is divide and conquer. The idea is that we can break a complicated problem apart into simpler sub-problems, solve them, and then produce a solution to the main problem from the solutions to the subproblems. But this poses a challenge for analysis, e.g., estimates of the time a particular algorithm may requires to solve a problem of a given size will be expressed in terms of how long it takes to solve smaller problems, rather than directly in a closed form.

Let's do some examples of analyses that result in recurrence relations:

Example 19.11 (Fibonacci's rabbits) Consider the following (extremely simplified) model of rabbit reproduction:

• Rabbits can be grouped into pairs.
• Mature pairs of rabbits give birth to a single pair of rabbits every month.
• Rabbits aren't mature until their second month.
• Rabbits never die.

Let $f_n$ denote the number of pairs of rabbits after $n$ months, where we begin at time one with a single, newborn pair.

If we think about the population at $n$ months (for $n>2$, we see that it consists of $f_{n-1}$ pairs of rabbits who were alive during the previous generation, plus newly-borne pairs. The number of newly-borne pairs will equal the number of pairs of rabbits that are at least two months old at month $n$, i.e., the number of pairs of rabbits that were alive during month $n-2$. Thus, we have the familiar recurrence

\begin{equation*} f_n = f_{n-1} + f_{n-2}\tag{$n\gt 2$} \end{equation*}

with the initial conditions $f_1 = f_2 = 1$. This is, of course, the famous Fibonacci sequence, which we solved (exactly) way back in Lecture 8.

Example 19.12 (The Towers of Hanoi) The story is told of a Buddhist monastery in Hanoi, in which three diamond tipped posts hold $64$ stacked golden disks of different diameters. The monks are engaged in moving the disks from one post to another, following a strict set of rules: only one disk may be moved at a time, and no disk may be placed on a disk of smaller diameter. When they began, all of the disks were on the first post, stacked from largest to smallest. The following picture illustrates the towers, for the $n=12$ case.

Their duty will end when all of the disks are stacked on the last post, and the world will end with it. The question is to estimate how long this task will take, assuming each transfer of the disk can be done in a second. To that end, let $H_n$ denote the number of steps to move the top $n$ disks from one post to another. It is useful to think of this operation as involving three posts: the source post, where the disks begin; the target post, to which they are to be moved; and the scratch post, which is used to facilitate the move.

We can develop a recurrence for $H_n$, via the following strategy. First, recursively move the top $n-1$ disks to the scratch post (which will function as the target post, for this phase of the algorithm):

Then, transfer the $n$-th disk from its source post to its target post:

Finally, transfer the top $n-1$ disks recursively from the scratch post to the target post.

If we think about this, we can see that (a) this strategy is optimal, so that (b) $H_n = 2 H_{n-1} + 1$. We can establish a starting condition via $H_0 = 0$, which implies $H_1 = 1$. [The $n=0$ case is often surprisingly simple, if thought about the right way.]

But what can we do with such a recurrence? A useful technique is to unwind the recurrence recursively, which gives

\begin{align*} H_n &= 2 H_{n-1} + 1 \\ &= 2 (2H_{n-2} + 1) + 1\\ &= 2^2 H_{n-2} + 2 + 1\\ &= 2^3 H_{n-3} + 2^2 + 2 + 1\\ &= \ldots\\ &= 2^{n-1} H_1 + 2^{n-2} + \cdots + 4 + 2 + 1\\ &= 2^{n-1} + 2^{n-2} + \cdots + 4 + 2 + 1\\ &= 2^n - 1 \end{align*}

Oh, by the way, $2^{64}-1$ seconds is a little less than $585$ billion years, so don't sweat it.

Curiously enough, I'm aware of a second such story, albeit one that is framed in terms of computers assisting Tibetan monks in a somewhat similar generative task, albeit with a far more surprising ending: Arthur C. Clarke's “The Nine Billion Names of God.”

Example 19.14 Find a recurrence relation for the number of bit strings that do not contain two consecutive $0$'s. Let $A_n$ be the set of strings of length $n$. It is useful to think about the strings that end with $0$ and $1$ separately. Each string in $A_n$ that ends with a $1$ consists of a string in $A_{n-1}$, extended by a $1$. Each string in $A_n$ that ends in a $0$ must either consist just of $0$ (in the case $n=1$), or it must consist of a string from $A_{n-2}$, extended by a $10$. If we let $a_n = \size{A_n}$, it immediately follows that for $n \gt 2$, $a_n = a_{n-1} + a_{n-2}$, a very familiar recurrence. Thinking about $n\lt 2$ gives rise to the special cases, $A_1 = \set{0,1}$, and $A_2=\set{01,10,11}$, so $a_1 = 2$ and $a_2 = 3$. It is easy to see (because they satisfy the same recurrences and initial conditions) that $a_n = f_{n+2}$.

Example 19.15 (Catalan Numbers) Consider an expression like this:

\begin{equation*} x_1 \mult x_2 \mult \cdots \mult x_{n+1} \end{equation*}

The number of ways to parenthesize this is known as $C_n$, the $n$-th Catalan number (after the mathematician who first studied this).

It is helpful in such a case to work through some small examples.

n	expr	parens	$C_n$
0	$x_1$	$x_1$	1
1	$x_1 \mult x_2$	$x_1 \mult x_2$	1
2	$x_1 \mult x_2 \mult x_3$	$x_1 \mult (x_2 \mult x_3)$, $(x_1 \mult x_2)\mult x_3$	2
3	$x_1 \mult x_2 \mult x_3 \mult x_4$	$x_1 \mult (x_2 \mult (x_3 \mult x_4))$, $x_1 \mult ((x_2 \mult x_3) \mult x_4)$, $(x_1 \mult x_2) \mult (x_3 \mult x_4)$, $(x_1 \mult (x_2 \mult x_3)) \mult x_4$, $((x_1 \mult x_2) \mult x_3) \mult x_4$	5

The point to such an exercise is to give us confidence that we're doing the counting in the recurrence correctly. In this case, the table is laid out so as to show the essential pattern. If we're parenthesizing an expression with $2$ or more factors, the top level multiplication has to fall between two consecutive factors $x_i$ and $x_{i+1}$. For this particular choice of top-level operation, we can then consider all the ways to parenthesize the first $i$ terms, together with all the ways to parenthesize the remaining $n+1-i$ terms. This gives us the recurrence

\begin{equation*} C_n = \sum_{k = 0}^{n-1} C_k \mult C_{n-k-1} \end{equation*}

for $n \gt 0$.

It can be shown (via generating functions, a technique we'll learn soon) that

\begin{equation*} C_n = {{2n \choose n} \over n+1} \end{equation*}

whence

\begin{equation*} C_n \sim {4^n \over n^{3/2} \sqrt{\pi}} \end{equation*}

via Exercise 19.8.

Pragmatics

It is tempting, and sometimes useful, when confronted with a new recurrence, to explore it computationally, e.g., for the Catalan numbers

#!/usr/bin/env python3 def catalan(n): if n == 0: return 1 else: return sum([(catalan (i) * catalan(n-i-1)) for i in range(0,n)]) for i in range(1,100): print("{:2d} {:10d}".format(i,catalan(i)))

The particulars of output formatting aren't important here, what matters is the translation of the Catalan recurrence into code, which is relatively straightforward given Python's list comprehension syntax (remember here that range produces a half-open interval, so that the top is correctly defined). Unfortunately, running this code reveals a characteristic weakness: a direct translation of the recurrence relation into recursive code runs poorly, because we end up recomputing values of the function over and over again. Computing anything past $C_{15}$ is somewhere between painful and impossible.

We can do better via dynamic programming, wherein we build a table of previously computed values. The logic of this code is decidedly more sophisticated, but is based on the idea that we can view the recurrence as describing a way to extend a sequence of already computed values. The resulting code computes the first $100$ Catalan numbers in $0.028$ seconds, and in doing so, shows that we've dramatically under-provisioned for the $56$ digits of $C_{99}$.

#!/usr/bin/env python3 def catalan_ext(ns): n = len(ns) next = sum([ns[i] * ns[n-i-1] for i in range(0,n)]) return ns + [next] cats = [1] for i in range(1,100): print("{:2d} {:10d}".format(i,cats[-1])) cats = catalan_ext(cats)

Anyway, here's a table to get us started:

$n$	$C_n$
1	1
2	1
3	2
4	5
5	14
6	42
7	132
8	429
9	1,430
10	4,862
11	16,796
12	58,786
13	208,012
14	742,900
15	2,674,440
16	9,694,845

If you enjoy computational exploration of combinatorial problems, let me commend Project Euler to you.

---

© 2016–2019 Stuart A. Kurtz
Last modified: March 13, 2019