Room and Times
Tuesday/Thursday, 2 pm, beginning June 23,
141 Altgeld Hall.
Course Description
There are many situations in mathematics where one encounters expressions,
such as sums over binomials, integrals, series, that cannot be evaluated
exactly, or where exact answers are too complex to yield useful
information. In
many of these instances it is possible to to obtain relatively simple
approximate evaluations which in applications are often just as useful as
an exact formula. Asymptotics (or, more precisely, asymptotic
analysis) deals with methods to obtain such approximations. The
terminology comes from the fact that the expressions usually involve a
parameter (e.g., an integer n), and that the approximation gets better
the larger this parameter is.
Asymptotic analysis has a wide range of applications, both to areas of
pure mathematics such as combinatorics, number theory, probability theory,
analysis, and to applied mathematics and computer science, for
example, in the analysis of the running time of computer algorithms.
Here are some typical problems that illustrate such applications.
- Size of the middle binomial coefficient. The largest of the
binomial coefficients (n choose k) is the middle one, with k = [n/2]. When
n is even, this coefficient represents 2^n times the probability of
getting exactly n/2 heads in n tosses with a fair coin.
How does this probability behave
for large n?
- Decay of binomial coefficients and Central Limit Theorem.
The binomial coefficients
decrease in size as one moves away from the middle coefficient.
Because of the probabilistic interpretation it is of interest to
determine more precisely the nature of this decay. It turns out that,
when n is large, the decay follows very closely a properly scaled "bell
curve". This is special case of the Central Limit Theorem in
Probability Theory.
- Sums over binomial coefficients.
The sum of the binomial coefficients (n choose k) over all k from 0 to n
is 2^n, by the Binomial Theorem. By symmetry, it follows that if n is
even, the partial sum up to n/2 is exactly half of the complete sum.
But what if the sum is cut off at some intermediate point between 0 and
n/2, say at n/3? In this case, an exact evaluation is no longer possible,
but with asymptotic techniques one can obtain good approximate answers.
- Partial sums of the exponential series.
The sum over the terms x^n/n! in the exponential series
from n=0 to infinity, is, of course, given by the
exponential function e^x. What if the sum is truncated at some finite
index N? This question has again a natural probabilistic
interpretation, this time in terms of the Poisson distribution: Given a
random variable with Poisson distribution with parameter x, the
probability that this random variable is at most N equals e^(-x) times
the above truncated exponential series. There is no closed formula for
such truncated sums, but when x is large, one can use asymptotic
methods to get good estimates and, in particular, show that, as x gets
larger, the Poisson distribution, after appropriate scaling, takes on
the characteristic "bell curve" shape of the normal distribution.
- Harmonic numbers. The n-th partial sum of the harmonic series,
the sum of 1/k from k=1 to k=n, is denoted by Hn and called the
n-th harmonic number. There is no "closed" formula for these numbers, but
using an asymptotic technique called "Euler-McLaurin summation" one
can obtain remarkably accurate estimates.
- The W-function. Trying to solve the equation w^w = x for w
leads to the "W-function", w=W(x), a function that arises in many
contexts. The W-function cannot be expressed in terms of elementary
function. However, using asymptotic techniques such as "bootstrapping"
and iteration, one can give good approximations for x large.
- Infinite series: The infinite
series x1 + x2 + x4 +
x8+ ... (where the exponents are the powers of 2) converges
for every x between -1 and 1, but there is no closed form for its sum.
What is the behavior of this series as x approaches 1 from below?
Obviously, it approaches infinity, but at what rate? The same question
can be asked about the alternating series x1 -
x2 + x4 - x8+ ...? The latter is a
surprisingly deep and subtle question, with an unexpected answer. (Try
to explore the latter series numerically and guess its behavior as x
approaches 1.)
- Tails of the normal distribution.
The function exp(- x2) is the famous "bell curve function" that
gives rise to the normal (Gaussian) distribution in probability theory.
This function cannot be integrated in elementary terms; i.e., the
indefinite integral of this function cannot be expressed as as an
"elementary" function. One therefore has to resort to numerical or
asymptotic methods to obtain approximations to definite integrals over
this function. Asymptotic methods are particularly suitable for the
"tail integrals", i.e., integrals from x to infinity, for large x.
This course will provide an accessible introduction to this theory.
Resources
I plan to distribute lecture notes.
For applications to combinatorics (binomial
coefficients, binomial sums, etc.) the most accessible treatment of
asymptotics can be found in Chapter 9 of Graham/Knuth/Patashnik,
"Concrete Mathematics" (which, incidentally, is a book well worth
purchasing). This text, however, does not cover applications to
analysis (such as the integrals or infinite series in the above
examples), and there is no text covering this material at a similarly
elementary level as Graham/Knuth/Patashnik.
At a (much) more advanced level, the classic text on the subject is
"Asymptotic Methods in Analysis" by N.G. DeBruijn, which first came out
half a century ago and remains to this date a standard reference.
Last modified: Wed 09 Sep 2009 02:02:35 PM CDT
ajh@uiuc.edu