hi

# The Ballot Theorem

Suppose in an election with two candidates, we are certain of the final tally. However, as the votes are counted sequentially, the lead may switch between the candidates during the process. This was certainly the case in the 2020 U.S. presidential election, where in several swing states, different types of votes (mail, early-voting, in-person) were counted at different stages. While the final tally does not change in a recount, the lead change may. One may ask: How likely will there be lead changes in a recount? Can the winning candidate always lead from start to finish? The Ballot Theorem provides a quantitative answer to this question.

(Informal) Suppose candidates and each have and votes, respectively, with . If the ballots are sorted uniformly at random and counted sequentially, the probability that always leads in this sequential count is .

The theorem matches our intuition that if the election is close, i.e., the count difference is small, then it is very likely that in a recount, will be winning at some point, even though will eventually overtake ‘s lead and win it all at the end. Let us formalize the statement in terms of random variables.

If are random variables, is the average of
(Ballot Theorem) Suppose are i.i.d. random variables with , where . Then

To see that the formal statement captures the semantics of ballot counting, imagine that all votes are in a box, and we randomly sample a ballot from a box without replacement. At time , if the -th sample is for Candidate and if the -th sample is for Candidate . Then . In the rest of this post, we will prove the Ballot Theorem using two commonly used techniques in probability, the reflection principle and martingale.

## Reflection Principle

Reflection Principle is a common technique used in Brownian motion, which is a continuous stochastic process that can model the movement of particles or the trajectory of stock prices over time. The idea is that if at any time, the stock price goes up or down equally likely, then any upward trajectory of the stock price has a corresponding downward trajectory (“reflected” along the x-axis). This symmetry allows us to reduce certain questions about a sequence of random variables to just one. For instance, the Ballot Theorem shows the probability that all random variables are positive is reduced to the single constant random variable .

Before writing the proof formally, let us first describe the Ballot Theorem at a high level. Imagine the ballots are sorted, and we start counting the votes one by one. Suppose the first vote belongs to Candidate . Since , at some point during counting, must relinquish its lead and tie with , say with votes each. Now pause the counting (temporarily!), and pair up each of the counted votes for with a unique counted vote for . With this pairing, we can re-create another recount by just swapping every counted vote with its paired vote. Then in this other recount, the first vote belongs to Candidate and afer votes, is tied with . In other words, whenever a recount has losing its initial lead, there is another recount where initially loses its lead as well!

Imagine plotting the vote counts. The scenario that has an initial lead is represented by a curve that is below the x-axis and eventually hits the x-axis. The curve for the imagined recount described above is simply obtained by reflecting the original curve along the x-axis.

The probability that the first vote is for and relinquish this lead is (since does not have enough votes to win in the final tally). By reflection, the probability that the first vote is for and relinquishes this lead is also . So the probability that never falls behind is .

Let be the stopping time when first becomes , i.e.,

Note that , so it suffices to compute . To this end, note that if , by the minimality of , either or .

Now here is the reflection principle at work.

(of Claim) Consider such that . Consider its reflection . Since the are i.i.d. and and are in one-to-one correspondence, the two probabilities are equal.

Again by the minimality of ,

Note that . To see this, if is such that , then . Conversely, if and , there must be some such that .

Thus, putting the above together, we have

And finally, since the random variables are i.i.d.,

finishing the proof.

The proof used a subtle property of the stopping time . When always leads , is defined to be , and so by assumption. At first glance, the definition that if always leads seems arbitrary. However, the semantic of stopping time requires that the event must be “observable” at time . The information that always leads is only determined at time , so must be defined to be . In the language of measure theory, . See the next section where stopping time is formally defined in terms of -algebra.

## Martingale

In a betting system, a gambler often formulates a strategy at time based on previous observations, say the first card draws. For example, if we see a sequence of coin tosses being head, it is tempting to bet big on the 11th toss being a tail. A martingale is essentially a strategy where the expectation valuation at time given the observations up to does not differ from previous valuation. Continuing the coin example, if the coin tosses are fair, then the expected winning on the 11th toss is the same as previous coin tosses.

A sequence of integrable random variables is a martingale if .

At time , a gambler may have access to other information computed from , not just the values of these previous random variables. Thus, we use a larger set, a -algebra that semantically captures all the information available up to time (as opposed to just . More generally,

A sequence of integrable random variables is a martingale with respect to the -algebras if

• is a filtration, i.e., ,,
• is -measurable,
• ,.
• Semantically, the first criterion just says that information at time is cumulative: it includes information available previous time. For the second criterion, by definition , , so it guarantees that actually captures the information at time . Lastly, the third criterion enforces that the betting system is fair as discussed.

In probability, many problems have a hidden martingale, and finding it often illuminates the problem more. Here is roughly how martingale is embedded inside the Ballot Theorem. Imagine we have randomly sorted ballots for a recount. At time (the negative indices will be explained soon), we have ballots uncounted. Since we knew the final tally, and we have just counted ballots, we know how many of the remaining ballots are for Candidates and , just not the specific order that they will come out. Thus, if we draw a random ballot from the remaining ballots, its distribution is exactly , implying that is a martingale (precise calculation within the proof below).

We make the curious choice to index our sample average with negative indices, even though we could have shifted the entire index sequence by to the right. However, in theory, the number of random variables may be infinite (the setting for the Law of Large Numbers). In this case, when the average is taken over just one random variable or zero variable, the martingale stops. It is simply more instructive to let or be the last random variable in this martingale. In fact, martingale with negative indices are also called backward martingale. Backward martingales are easier to work with as they have stronger convergence guarantees. The reason is that a backward martingale has a last random variable, which by definition is bounded and therefore bounds the entire sequence of random variables via the martingale property.

We do not need the full machinery of backward martingale since in our application, , the number of ballots, is bounded. But for pedagogical purposes we will retain the use of negative indices to remind ourselves that is actually a backward martingale with stronger tools should we need to avail ourselves to them.

Similar to the reflection principle, we will also make use of stopping time, but this time we will use it more extensively, so we define it carefully now.

A random variable is a stopping time with respect to if for all , , where is a filtration.

Semantically, when represents the cumulative information at time , any stopping time criterion (bet after five heads are tossed, fold when money is below a threshold, etc) can only depend on the information available up to time . Stopping time is often used in conjunction with martingales. Often it is useful to stop a sequence of random variables, say the first time that hits . If the original sequence forms a martingale, then the sequence up to the stopping time — which itself is a random variable — remains a martingale if is bounded. There are more general statements, but the following suffices for our purpose.

(Martingale Optional Stopping Time) Let be a martingale and a stopping time with respect to the filtration , where . Then .
By the definition of conditonal expectation, it suffices to show that

• is -measurable and
• for all , .
• The first condition is satisfied by definition. For the second, by telescoping, we have

For each term, we have

since and is a martingale with respect to .

(Of Ballot Theorem) For , Define . Let denote the -algebra . We first show that the sample averages form a martingale.

.
(Of Claim) Since the random variables are i.i.d., we have

On the other hand, by i.i.d. again, we have

Now let be the stopping time when first becomes , i.e.,

Since is a stopping time, in the else-case above, must be since . Since form a martingale, by the Martingale Optional Stopping Time Theorem,
we have

Since , by the Law of Total Expectation, we have

Evaluating both sides, and writing , we have

where the third through fifth line follow from if , the definition of , and that if , respectively.

# Normal numbers

Imagine if we sample numbers from the unit interval and count the occurrences of each digit in every number’s infinite decimal representation. For instance, in the number , every non-zero digit appears exactly once, but appears infinitely often (trailing zeros). On the other hand, for the number , the digit occurrences (after the “dot”) is equal for every digit. As the number of samples increases, one may expect that the number of occurrences for each digit in to be close to one another. In fact, the Normal Number Theorem, first formulated by Borel, not only formalizes this intuition but goes a step further: for almost every number in , each digit appears equally likely. Below we discuss this theorem in detail.

We first recall a few basic facts about the representation of a number. Rather than working entirely in base , we work with an arbitrary base .

Let with . We say that has a base- representation if there is some such that the series converges to , with .

In other words, is the integer component of and the fractional component. With , our familiar decimal representation, we know that every real number has a decimal representation, and by identifying as , the representation is unique. Analogously, for every , every real number has a base- representation as well.

(Normal numbers for base b) Let with . We say that is normal with respect to base and digit if , and is normal with respect to base if for every , it is normal with respect to base and digit .

Note that in the definition above, , the digits in the integer component of , are completely ignored. The reason is that for every , its integer component is bounded, so in the above definition is fixed and does not affect the limiting value of digit frequencies.

We say that is normal if for every , is normal with respect to .

We now state the Normal Number Theorem formally:

There is a null set such that every , is normal.
The theorem is non-constructive — while one is almost guaranteed to find a normal number, it does not construct specific normal numbers. Furthermore, it is not known if famous irrational numbers such as and are normal.
The power of the theorem lies in aggregation by 1) non-constructively examining all numbers at once instead of a individual number and 2) considering all digit precision instead of a specific precision. For instance, the frequency of the leading digit often obeys Benford’s Law, where the digits and in a decimal representation tend to appear more frequently than and .

Let us first consider a truncated version of the theorem. Consider tossing a fair coin independently times. From a combinatorial argument, most sequences of coin tosses have about heads and tails. By interpreting a head as and a tail as , most -bit numbers are normal. The passage from bits to infinite bits is the crux of the theorem, since the combinatorial process of selecting a random -bit number no longer extends. The proof illustrates how a measure-theoretic abstraction can circumvent this difficulty. In particular, we will apply the following “-trick” repeatedly.

Let be any probability space. Let be a countable collection of events with each . Then .
Let . By assumption, can be bounded above by . Then

Since was arbitrary, must equal .

(Normal Number Theorem)
First consider the interval , where . By the previous proposition, it suffices to show that the set of non-normal numbers in is null. Now fix . By the proposition again, it suffices to show that the set of numbers in that are not normal with respect to is null. Now fix . By the proposition again, it suffices to show that the set of numbers in that are not normal with respect to base and digit is null. By definition, for , is normal with respect to base and digit iff is normal with respect to base and digit . Thus, without loss of generality, we may further assume that .

Now consider the probability space (, where is the set of Borel sets on , and the Lebesgue (probability) measure. For , define to be , where is the -th digit of the base expansion .

is a sequence of i.i.d. Bernoulli random variable with probability .
(of Claim)
As defined, is an indicator function, and for , the set is just a union of intervals:

which is a Borel set, implying that is a Bernoulli random variable with .

To show independence, it suffices to show that for every , the family of random variables is independent. This follows directly from the observation that (since the interval has length ) and the previous observation that .

Given our setup, we now apply the Strong Law of Large Numbers to conclude: there exists a null set so that for every , converges to , i.e., is normal with respect to base and digit .

As a corollary, we conclude that for every continuous random variable, its output is most likely normal.

Let be a probability space, and a continuous random variable with a probability density function. Then , where is the set of non-normal numbers.
By the Normal Number Theorem, the set of non-normal numbers, denoted , is null, so for every , there is some open set with . Let be the probability density function of , then

finishing the proof.

A continuous random variable having a probability density function is equivalent to the cumulative distribution function of being absolutely continuous. (And recall the Cantor function as an example where may not even have a probability density function!) Alternatively, the above corollary also follows by observing that can be approximated by a finite number of small intervals in (e.g., Littlewood’s First Principle as discussed in a previous blog post), which being absolutely continuous must map into another null set.

# Littlewood’s Three Principles

In measure theory, the notion of measurability restricts sets and functions so that limit operations are sensible. With non-measurabilty manifesting only through the Axiom of Choice, measurability is a semantically rich class, and in particular, Littlewood’s Three Principles specify precisely how measurability relates back to more elementary building blocks as follows:

1. Every measurable set is nearly open or closed.
2. Every measurable function is nearly continuous.
3. Every convergent sequence of measurable functions is nearly uniformly convergent.

Here in this post, we flesh out these principles in detail, with an emphasis on how these various concepts approximate one another. Each section corresponds to one principle and is independent from another. We primarily focus on the Lebesgue measure on Euclidean space before discussing the abstract generalization. While there are many equivalent definitions of measurability, for simplicity we will only use these definitions in this discussion:

A set is measurable if for every , there is some open set containing such that , where is the Lebesgue measure.
A function is measurable if for every open interval , the preimage of under , , is a measurable set.

We will use these facts about the Lebesgue measure throughout.

Let be the Lebesgue measure on . Let be a collection of measurable sets.
1. (Monotonicity) If , then .
3. (Additivity) If are disjoint, .
4. (Upward monotone convergence) If , .
5. (Downward monotone convergence) If with for some , then .

## First Principle

By definition, every measurable set is already arbitrary close in “volume” to an open set. Nonetheless, we can say a lot more about its structure: in , a measurable set can be approximated by a disjoint collection of cubes. In the visual setting where , a measurable set can be approximated by a “pixelation” of squares. We first define the notion of cubes.

We say that is a closed cube of length left-aligned at if .

The structure of measurable sets actually inherit from the structure of open sets, as stated in the following proposition:

Let be open. Then is a countable union of closed cubes, and every pair of these cubes is disjoint except at the boundary.

We first state and prove the First Principle before proving the proposition.

Let be a measurable set with finite measure. For every , there exist disjoint cubes such that , where .
(of theorem) Fix . It suffices to show that there exist disjoint cubes such that and . Since is measurable, there is an open set containing such that . In particular, since . From the above proposition, , where is a closed cube and pairwise disjoint except at the boundary. For each closed cube , there exists a cube such that , and is pairwise disjoint. Now, by the upward monotone convergence of measure, there is some such that . Let . Then by the monotonicity of . For the other case,

where the lines follow from the monotonicity of , additivity of , disjointness of , construction of , sub-additivity of , and construction of , respectively.

(of proposition) Note that can be divided into cubes of length :

with . Let be an open set in , and define

In other words, contains all cubes of length for some integer that reside entirely within . Since is countable and is a subset of countable union of , is countable. By construction . For the other direction, since is open, for every , there is an open ball centered at of radius , , that is contained inside . By Pythagorean Theorem, there exists a cube with length centered at that is contained inside . For every , let . By maximality, , with and at a distance less than from . Thus, is inside the cube of length left-aligned at , implying . Lastly, to see that cubes are almost disjoint except at the boundary, note we may modify so that if a cube is selected from , then we can remove its sub-cubes from for every . By this modification, a selected cube in is never contained in another.

The First Principle can also be extended into any abstract measure space , where is the underlying set, is the set of measurable subsets of , and is the measure for . In the concrete setting, let be a bounded subset of , the set of all measurable sets contained in , and the Lebesgue measure. The First Principle effectively states that every measurable set is equivalent (up to a difference of measure zero) to a countable union of closed sets, and a direct generalization of what we have just proved is that every bounded element of the -algebra “generated” from closed sets can be approximated by closed sets themselves. More precisely,

Let be a measure space with . Suppose is an algebra. Then for every , , where is the intersection of all -algebra containing , there exists such that .
Fix and let . Since contains , it suffices to show that is itself a -algebra. It is easy to see that is closed under complement since is. For countable union, for every , let , . By definition, for every , there is some such that , where will be chosen later. By upward monotone convergence, there exists some such that . Write and , and note that is in . Then

of , and our choice of , respectively. Similarly,

Thus, 3 and setting finishes the proof.

## Second Principle

(Lusin’s Theorem) Let be a finite, measurable function. For every , there exists such that and , the restriction of to , is continuous.

As an example, consider the indicator function where is the set of rationals. When restricted to the domain of , the function becomes identically zero. However, the function remains discontinuous at the points in . Thus, the continuity asserted in Lusin’s Theorem applies only to the restriction of the original function.

Before proving Lusin’s Theorem, we first prove that the continuous functions are dense in absolutely integrable functions.

Let be a measurable function. Suppose . Then for every , there exists a continuous function such that .
We proceed in stages, where in each stage is restricted to an elementary, but more general class of functions than the previous stage. Note that in all cases, the hypothesis that is measurable and always applies.

Case 1: , where is a cube in (as defined in the First Principle).
When , is an interval, and has two points of discontinuity at the endpoints of this interval. A continuous function can be defined so that it agrees with everywhere, except when near each endpoint, is a nearly vertical line dropping from to . The case for larger can be similarly constructed.

Case 2: , where is a finite collection of cubes.
By Case 1, each has a continuous function such that . is continuous, and by triangle inequality, .

Case 3: , where is a measurable set.
From the First Principle, can be approximated by a finite union of disjoint cubes, and the result follows by Case 2 and applying triangle inequality.

Case 4: is simple, i.e., , where is a finite collection of measurable sets.
Follows from a similar argument as in Case 2.

Case 5: .
By definition, . Since , there exists some simple with . Result follows from Case 4 and triangle inequality.

Case 6: General case.
Write , where and . Then Case 5 applies to and , and the general case follows from Case 5 and triangle inequality.

(Lusin’s Theorem) We proceed in stages by proving the statement for progressively more general classes of functions. In all casees, the hypothesis that is measurable and finite always applies.

Case 1: .
Fix . By the previous proposition, for every positive integer , (to be specified), there is a continuous function such that . Define

By Markov’s Inequality, . Then , which is at most if we specify . Let . Then by construction, converges to uniformly inside . The restriction of to remains continuous, and since continuity is perserved under uniform limit, is continuous as well.

Case 2: is a bounded function.
Consider the “vertical” truncation of : . Since is bounded, is bounded and . By Case 1, there exists some such that , with continuous when restricted to . Let , then , thus every vertical truncation is continuous when restricted to . Since continuity is a local property, for every , must agree with some on a neighborhood of , so is continuous on as well.

Case 3: General case.
Consider the “horizontal” truncation of : . Since is bounded, by Case 2, there is some such that , with continuous when restricted to . Similarly as in Case 2, we define , with , and every truncation is continuous when restricted to . Since is finite, for every , must agree for some on a neighborhood of and is continuous on as well.

One may extend Lusin’s Theorem to an abstract measure space , where is Radon so that its measure is also compatibile with its topology so that continuity can be defined appropriately.

## Third Principle

(Egorov’s Theorem) , with . Let be a sequence of measurable functions with converging to pointwise as . Then for every , there exists a measurable subset with , where converging to uniformly within .
Egorov’s Theorem also implies Lusin’s Theorem, the Second Principle. If is measurable, by an alternate definition of measurability, it is also the pointwise limit of simple functions. These simple functions are also approximated by continuous functions. By Egorov’s Theorem, these continuous functions uniformly converge to except on a small subset . Since continuity is preserved under uniform convergence, is continuous on a domain without .
By definition, converges to uniformly on iff for every , for every positive integer , there is some positive integer with . Let

We see that converges to uniformly on , where will be chosen later. First note that is measurable: the limit of measurable functions is measurable, so and thus is meaurable, implying that , the pre-image of the open interval under , is measurable. Since is a countable intersection of , is also measurable. Second, note that is an increasing sequence, and its complement is a decreasing sequence. Since converges to , as . Since , by the downward monotone convergence of measure, as . Thus, there exists some such that .

Then

where the lines follow by the definition of , sub-additivity of measure, construction of , and geometric series, respectively.

It is easy to extend the above setting directly to an abstract one, with the proof following verbatim as before, except replacing the Lebesgue measure by an arbitrary measure :

(Abstract Egorov’s Theorem) Let be a measure space with . Let be a sequence of measurable functions, with converging to pointwise as . Then for every , there exists a measurable subset with , where converges to uniformly within .
When the measure space is a probability space, the finiteness of measure is trivially true. Since random variables are measurable by definition, Egorov’s Theorem states that a sequence of converging random variables is then almost uniformly convergent, except on a subset with small probability.

Lastly, we can lift the restriction that the domain of has finite measure, but uniform convergence must still be local.

(Egorov’s Theorem II) Let be a sequence of measurable functions with converging to pointwise as . Then for every , there exists a measurable subset with , where converges to locally uniform within , i.e., for every bounded subset , converges to uniformly on .
We will simply describe how to modify the preceding proof. For every positive integer , let be the ball of radius of centered at the origin. Define . Then following the same argument applied to , there exists some such that . Then letting , has measure at most . By definition,

so any bounded must be inside for some , so , i.e., converges to uniformly on .

In both variations of Egorov’s Theorem, the boundedness condition is necessary. Otherwise, when , consider , which converges to the zero function pointwise, but can never converge uniformly to zero. One can see that the mass of this function “escapes” to horizontal infinity. This is exemplified in the proof above, where convergence is not uniform on : a sequence of points with can all reside in but remain outside of .

# Dirichlet’s Theorem for arithmetic progressions with difference 4

From antiquity, Euclid’s Theorem asserts that the number of primes is infinite. Since all primes except are odd, a re-phrasement of Euclid’s theorem is that the set of odd integers contains an infinite number of primes. A natural generalization, proved by Dirichlet, is that every arithmetic progression of the form contains an infinite number of primes, provided that and are relatively prime.

(Dirichlet’s Theorem) If , then the arithmetic progression contains infinitely many primes, where denotes the greatest common divisor of and .

The proof is one of the first application of Fourier analysis on finite abelian groups. Here in this post, we prove Dirichlet’s theorem when , i.e., both the arithmetic progressions and contain an infinite number of primes. The restriction to highlights the main structure of Dirichlet’s proof without needing as much background from number theory.

Before jumping directly into the proof, let us first discuss some number-theoretic background and the high-level strategy. First recall Euclid’s argument. For the sake of contradiction, there are exactly primes of the . Then the number is larger than every and cannot be a prime of the form . On the other hand, from the Fundamental Theorem of Arithmetic, is the product of primes, and one of them must be congruent to since itself is. So some must divide both and and , implying that divides , a contradiction. One can easily verify that this argument can be adapted to by taking . However, the argument breaks down when applied to the arithmetic progression . The reason is that the number is no longer guaranteed to have a prime divisor of the form .

Instead, Euler’s analytic proof of Euclid’s Theorem provides the proper framework to extend the infinitude of primes to arithmetic progressions, where the zeta function can be written as the product of geometric series of primes:

(Euler-Dirichlet Product Formula) For every ,

Furthermore, if is multiplicative, i.e., , then

(A note on notation: always denotes a prime, and and range over all primes.) The identity can be viewed as an analytic version of the Fundamental Theorem of Arithmetic: every positive integer is the product of some prime powers, and the expression is a geometric series. Since diverges, The Product Formula also implies that the number of primes is infinite. With additional calculation, Euler proved the stronger form of Euclid’s Theorem:

Now to prove Dirichlet’s Theorem, we will show that the sum as , where is the indicator function on for being congruent to . By Fourier analysis, can be decomposed into two sums. Roughly, the first corresponds to the zeroth Fourier coefficient of and evaluates to , which diverges as , and the second sum corresponds to the non-zero Fourier coefficients and is always bounded. In our writeup, the advantage of restricting to is that the estimate of the second sum becomes significantly simpler, without further tools from number theory.

(Proof of Dirichlet’s Theorem restricted to .) Let be the multiplicative group of integers modulo , and be the indicator function such that if and otherwise. Then by Fourier expansion,
for every ,

where ranges over all characters of the dual group of . Since is a finite abelian group, it is is also isomorphic to its dual, and with , we can conclude that the only characters of are: the trivial character that is identically , and the character where if
and if . Thus, we can simplify and rewrite as

(For sanity check, one can easily verify via direct computation, without Fourier analysis, that the identities and hold.) For the rest of this proof, we will rely on the the fact that the characters and are real-valued.

To prove the theorem, we have to sum over all integers instead of just the multiplicative subgroup of . To this end, for every character , we define its Dirichlet character to be the extension to all of as follows: if and otherwise. Let be the indicator function of being congruent to . Then it is easy to see that

where are the Dirichlet characters of , respectively. Since we can express the indicator function in terms of Dirichlet characters, we have

It suffices to prove that as . In particular, we will show that

• as , which coincides with Euler’s argument since for all , and
• .

To estimate these sums, we prove the following:

Let be a Dirichlet character for . Then , where .
(of Proposition) Since is multiplicative, from the Euler-Dirichlet Product Formula,

Since is real-valued, taking log of both sides, we have

where the second line follows from the estimate of the power series when , and the third from the fact that converges.

Now we estimate the two sums using the above proposition. For the trivial Dirichlet character , we have

which diverges as since diverges as .

For the non-trivial character , is simply the alternating series , which converges to a positive number. Thus,

completing the proof.

Most steps in the preceding proof can be easily extended to an arbitrary . The Euler-Dirichlet Product Formula works for a multiplicative function taking values in . The Fourier expansion of works as before. The Proposition still holds, but extra care has to be taken since the -function is now complex-valued. The sum diverges, but for a non-trivial Dirichlet character , the fact that the sum is bounded is significantly more involved. See for instance Apostol or Stein-Shakarchi for further details.

We finish by observing that the proof above has a quantitative form.

(Quantitative version of Dirichlet’s Theorem) For every ,

In general, for an arbitrary , the expression is replaced by , with , where is the Euler totient function.
Proof proceeds the same as before, where we showed that

with and . Previously, we simply noted that diverges as . To finish the proof, it suffices to note that

# Exponential sum and the equidistribution theorem

Consider the sequence , where gives the fractional part of a real number. The equidistribution theorem states that is irrational iff for any sub-interval of the unit interval, for sufficiently large , roughly of the numbers fall inside . More precisely,

(Equidistributed sequence) A sequence with is equidistributed mod 1 if for every ,

(Equidistribution theorem) The sequence is equidistributed mod 1 iff is irrational.

Let us try to understand why the sequence behaves differently depending on whether is rational or not. If for some integers and , then roughly of the first multiples of are integers, i.e., . In fact, it is not difficult to see that for , fraction of the sequence equals . So equidistribution does not occur when is rational.

Now for , consider the exponential function , which has period . As discussed above, roughly of the sequence is , so the exponential sum contains an infinite number of ones. For example if , the exponential sum evaluates to , which is Grandi’s series and diverges. For an arbitrary , the exponential sum is a repeating sum of all -th roots of unity, and one can use the same technique showing that Grandi’s series diverges to establish that this exponential sum diverges too. However, the case when is irrational differs: every nonzero integer multiple of is an non-integer, and thus for any . Writing , the exponential sum converges to the geometric series , since .

In fact, the above intuition can be summarized into the following criterion due to Weyl:

(Weyl’s criterion) A sequence is equidistributed mod 1 iff for all integers ,

From the above discussion, Weyl’s criterion immediately implies the equidistribution theorem.

(of equidistribution theorem) Suppose is rational, i.e., for some integers and . Without loss of generality, we assume . Then for all integer , by Euclid’s algorithm, is in . So the sequence is not equidistributed, e.g., no multiples of fall inside .

Now suppose is irrational. Since , we have

which tends to as .

Before proving Weyl’s criterion, it is instructive to state the notion of equidistribution analytically. For , let iff . Note that is a periodic function on all of .

(Weyl’s criterion restated) Let be a sequence in . The following two statements are equivalent:
1) For ,

2) For all integers ,

Written in this form, Weyl’s criterion is asserting that if the sum of every interval function at a sequence converges to its integral, then every exponential sum converges to its integral as well, and vice versa. The reason is that both the space of interval functions and the space of exponential functions can approximate one another. More precisely, an exponential function is clearly periodic and continuous (and thus uniformly continuous), and every uniformly continuous function can be approximated by a finite sum of interval functions. For the other direction, a periodic, interval function can be approximated by a periodic, continuous function, which by FejÃ©r’s Theorem can also be approximated by a finite sum of exponential functions. Now we have all the machinery to write down a proof.

(of Weyl’s criterion) For the forward direction (1) => (2), fix and . Since the exponential function continuous on the closed interval , it is also uniformly continuous, i.e., there exists some such that for every , . Let be a step function where if . By construction, is a finite sum of interval functions with .

By linearity, we have

By taking sufficiently large and repeatedly applying triangle inequality, we have

implying that converges to as .

Now we consider the reverse direction (2) => (1). Fix and let . Define

Note that is continuous, periodic, and dominates . By FejÃ©r’s Theorem, there exists such that . By linearity, we have

By taking sufficiently large and repeatedly applying triangle inequality, we have

implying that

Since dominates , we have

One can similarly define a periodic, continuous function that approximates from below, showing that is bounded below by , which together with the proceeding argument will show that the limit of must exist and converge to .

# Summability, Tauberian theorems, and Fourier series

Consider a periodic function . Its Fourier series always exists formally, but questions of whether its Fourier series converges to itself can be rather subtle. In general, may be different from its Fourier series: a Fourier coefficient is the evaluation of an integral, so can be changed pointwise without affecting the value of any Fourier coefficient. It may be natural to believe that convergence holds when is continuous. However, an example constructed by du Bois-Reymond showed that continuity is not sufficient. The most general result in this area is Carleson’s theorem, showing that -functions have convergent Fourier series almost everywhere.

Here we will prove that the Fourier series of converges to in the sense of CesÃ ro (or Abel), and we will highlight through a Tauberian-type theorem that convergence holds when is “smooth”. In particular, the main theorem we will show is that for a periodic, continuous function, its Fourier series converges pointwise if its Fourier coefficients are decaying at a linear rate.

If and and is continuous at , then as .
The sufficient condition in the above theorem can be improved to , but we won’t prove the stronger statement here.

What types of functions are characterized by decaying Fourier coefficients?
A simple calculation with integration by parts shows that if is differentiable, then . Since by the Riemann-Lesbesgue lemma, we have the following:

If is differentiable, then its Fourier series converges pointwise to .

In general, convergence also holds for other types of smoothness conditions.

## Summability

We first take a detour (without the Fourier analysis setting) to investigate the different notions of summability for a sequence. The standard and familiar notion of summability captures the intuitive notion that as one adds more numbers from a sequence, the sum gets closer to its limit. More precisely,

A sequence is summable to if its sequence of partial sums where converges to .

Under this definition, the partial sums of Grandi’s series oscillate between and , and thus the series diverges. However, one could argue that this series “hovers” around since the partial sums oscillate between and . In fact, the average partial sums of the sequence converge to . This motivates the following alternate definition of summability:

A sequence is CesÃ ro-summable to if its sequence of CesÃ ro means converges to , where and is the -th partial sum .

It is instructive to rewrite the CesÃ ro mean as

We can see that the CesÃ ro mean is a weighted average of the ‘s, where the later terms contribute with a discount linear factor. With this insight, it is intuitive to conclude if a sequence is summable, then it is also CesÃ ro-summable: a summable sequence must have vanishing “tail”, implying that its CesÃ ro means form a Cauchy sequence and thus converge.

We can consider another definition of summability where the discount factor is exponential:

A sequence is Abel summable to if for every , converges and .

Intuitively, Abel summability ought to capture a larger class of sequences. In fact, one can summarize this entire section in the following:

If a sequence is summable to , then it is CesÃ ro-summable to . If a sequence is CesÃ ro-summable to , then it is also Abel-summable to .
Suppose first that is summable to . For every , there exists such that for every , . Let and . Then for every , we have

and when is sufficiently large, ,
implying that as .

Now suppose that converges to . Define . Then we can write

Since , using a similar calculation as above, we can write

Since converges (and is thus bounded), converges for every and so does .

Now it remains to show that . Let , then there exists such that for each , . We can split into two sums:

Since one can exchange limit with finite sums, is . So

A similar shows that , and hence is Abel summable to .

## A Tauberian-type theorem

In the previous section, we showed that the class of summable sequences is a subset of CesÃ ro-summable sequeences, which in turn is a subset of Abel-summable sequences. It is not difficult to see that these containments are strict. However, by imposing certain conditions, these containments can also be reversed, and statements of this type are called “Tauberian-type theorems”. Here we prove a simple version where the magnitude of the sequence decays linearly.

(Tauberian) Suppose the sequence satisfies .
(a) If is CesÃ ro-summable to , then is also summable to .
(b) If is Abel-summable to , then is also summable to .
(a) Fix . Let be the CesÃ ro mean and partial sum of , respectively. By assumption, when is sufficiently large, and by triangle inequality, is at most , so it suffices to prove that .

Recall that in the previous section, we proved that

Then we have

By assumption, there is some such that for every , , implying . Then when is sufficiently large, , proving that as desired.

(b) Let . Define . By assumption, when is sufficiently large, , and by triangle inequality, is at most , so it suffices to prove that . By triangle inequality again, we have

By assumption, there is some such that for every , . Again we can break the the above sum into two, and for the later terms, we have

For the initial terms, we have

where the last inequality is due to Bernoulli’s inequality, and is bounded above by when is sufficiently large. Together we have as desired.

## Fourier series

We now come back to the Fourier setting. First recall that

For a periodic function , we define its -th partial Fourier sum to be , with , and .

We now introduce Dirichlet and FejÃ©r kernels, which when convolved with a function , we obtain the partial sum and CesÃ ro mean of , letting us invoke Tauberian Theorem.

is the -th Dirichlet kernel, and is the -th FejÃ©r kernel.
(Tauberian theorem restated) Let be a periodic function with . Then for any , if for some as , then as .
For any nonnegative integer , let . Note that by assumption . By the Convolution Theorem, the -th partial sum of is simply

and similarly, the -th CesÃ ro mean of is

where the second line follows from the linearity of convolution. Thus, by Tauberian theorem, if converges, then converges to the same value as well.

To prove the main theorem, it now suffices to show that approaches . We make one last definition:

Let be a periodic function. We say that is a family of good kernels if the following three conditions all hold:
(a) for each , ,
(b) for each , , and
(c) for any , as .

The idea is that a family of good kernels essentially approximate the Dirac delta function, which is a single point with infinite mass at and vanishes everywhere else.

The FejÃ©r kernels is a family of good kernels.

We will skip the proof of this fact as it is a straightforward calculation once one establishes the trignometric identity . (However, the Dirichlet kernels cannot be a family of good kernels, otherwise every Fourier series converges to its function, which is not true.) Intuitively, since is a weighted average of with highest weights around (by the definition of a good family of kernels), we can expect that this value is close to , as long as the does not change its value too much around . Now we formalize and prove this intuition, which will finish the proof of our main theorem.

Suppose is a family of good kernels. Let be a periodic, integrable function that is continuous at . Then as .
We first write

where the first through third lines follow from the definition of convolution, Condition (a) of a good family of kernels, and triangle inequality.

The idea is that when integrating over , is small if is bounded away from , and is small if is close to . Formally, let . Since is continuous at , there is some such that

for some by Condition (b) of a good family of kernels. Since can be arbitrary, the above integral is .

Now for the other values of , note that since is integrable, the function is bounded by some . Then

which tends to as , finishing the proof.

In the previous section, we showed that the Abel mean can play a similar role to CesÃ ro. Similarly, one can define the Poisson kernel and show that it is a good family of kernels as to prove the main theorem through instead.

# The Basel problem via Fourier series

The Basel problem asks to compute the summation of the reciprocal of the natural numbers squared, and it is known that

While there are numerous known proofs (our presentation resembles Proof 9 most closely), we give a self-contained one that motivates the usage of Fourier analysis for periodic functions.

Recall that a function is -periodic if for every , . From Fourier analysis, every such function can be expressed as a series of cosines and sines. More precisely,

If is continuous and -periodic, then

where , and is the -th Fourier coefficient equal to .

We say that is the Fourier series of . When we define the inner product of two functions to be , then it is easily seen that the “characters” form an orthonormal system, and the -th Fourier coefficient can be viewed as the projection of along the -th character. The Fourier theorem asserts that can be approximated in -norm by its Fourier series. In fact, by applying the Weierstrass M-test, we can make the following statement with a stronger convergence guarantee:

If is continuous and -periodic and is convergent, then its Fourier series converges uniformly to .

Furthermore, the Fourier transform itself encodes many of the properties of the original function . In particular, we note that the symmetry of is preserved in its Fourier transform.

If is even, then for every , .
If is odd, then for every , .

Now we have the machinery to compute .

(Of Basel) Define to be . We compute the Fourier coefficient of . First note that

For , we have

Using integration by parts, we have for every ,

Then

Thus,

From Euler’s formula, the Fourier series of can be written as

Since is even, by Proposition, . From our calculation, the Fourier series of is explicitly

Note that is convergent from the Cauchy condensation test. Thus, by the Convergence Theorem, we conclude that

where the convergence is uniform (and in particular, pointwise). Setting , we see that

Lastly, observe that

finishing the proof.

# Auction algorithm for the assignment problem

The maximum bipartite matching is a well-known problem in graph theory, operations research, and economics. Also known by the name assignment problem, it models a marketplace with buyers and items, where every buyer has a valuation for each item, and we want to match (assign) each buyer to an item, with no item being shared. For social utility, an assignment that maximizes the total valuation is ideal.

In graph theory, the Hungarian algorithm by Kuhn produces a matching in polynomial time maximizing the total weight of the edges. Independently, Bertsekas from operations research and Demange, Gale, and Sotomayor from the economics perspective both use an underlying auction to solve the same problem. The auction provides additional intuition for this problem not transparent when using only graph-theoretic techniques. Here we describe a simple auction algorithm, largely following the presentation from this blog post.

To formulate this problem, we consider a bipartite graph , where represents buyers and represents items, with each edge having an nonnegative weight representing the value Buyer places on Item .

A matching from to is a function such that for all , or .

The assignment problem is simply to find a matching function such that its valuation is maximized. (Since it is possible that some buyers may not be assigned an item, we write for notational convenience.)

Below is the pseudocode of the auction algorithm. Intuitively, the algorithm is simulating a multi-item auction, where we put a price tag initialized to zero on each item. The queue represents the list of unmatched buyers, which is initialized to . In each iteration, a buyer is greedily matched with his most valued item minus the price tag. However, each time an item is matched, it becomes slightly more expensive, becoming less valuable to other buyers in future rounds.

AUCTION(epsilon):
Queue Q <- B
for j in I:
p[j] <- 0

BidirectionalMap M
while !Q.isEmpty():
i <- Q.pop()
j <- Find j in I maximizing v[i][j] - p[j]

if v[i][j]-p[j] >= 0:
if M.ContainsValue(j):
Q.push(M.KeyOf(j))
M(i) <- j
p[j] <- p[j] + epsilon

Output M, p

Consider the case when , where a group of buyers is being matched for a single item. Clearly whoever values the item the most will win the auction, but at what price? From the highlighted line in the above pseudocode, it is readily seen that a buyer drops out when the price is above his value. Thus, the final sale price is at most the second highest valuation among all buyers (plus ) . Hence, the above algorithm can be seen as a generalization of a second-price auction for multiple items.

Complexity. Before analyzing the running time, we first make the observation that the algorithm must terminate in finite steps. The key insight is that a buyer will not overpay for an item. In particular, writing , we have

AUCTION() terminates within iterations.

To see this, fix an item . Note that before each increment to , the inequality must hold. So the final price must satisfy . The number of iterations in the loop is at most the number of times a price is incremented, which is .

A trivial implementation that finds the item with maximum value takes linear time, leading to an implementation with a running time of . A faster algorithm can be achieved by maintaining priority queues of size , one for each buyer, as follows: Each time the price of Item is incremented, priority queues are updated, where is the number of buyers who are connected to Item in the bipartite graph. Then the total number of priority queue updates is

By the handshaking lemma, , where is the number of edges in the bipartite graph. Thus, a priority queue-based implementation takes time at most .

Now we analyze the valuation produced from the matching . The proof is short and self-contained but utilizes -complementary slackness, a concept related to primal-dual method in optimization.

Let be the matching produced by AUCTION() and be any matching from to . Then

Since we can choose to be arbitrarily small, the theorem implies that output matching is arbitrarily close to optimal. In particular, if all the values are binary, setting implies that the algorithm terminates with a maximal matching, and its time complexity is cubic on dense graphs, on par with the Hungarian algorithm.

We say that Buyer is -happy under if he is matched with an item that is -close to optimal, i.e., for all , For notational convenience, we will write , so a buyer being completely out-priced (being matched with an “empty” item) is also -happy.

The key insight is that during each iteration, the algorithm preserves the loop invariant that all buyers in are -happy. To see this, note that the invariant holds vacuously true initially. During each iteration, whenever a buyer is removed from the queue, he is always matched with an item whose price (after the update) is -close to being optimal. Then the previous holder of the item is added back to the queue. Since all buyers in are -happy when the algorithm terminates, we can observe that for any matching ,

Re-arranging, it is easy to see that

Thus, it suffices to show that . If Item is in the range of but not , then the algorithm must have never incremented its price, so . Thus,

which is nonnegative.

The theorem also implies that in any marketplace, there is a set of market-clearing prices, i.e., each buyer has at most one preferred item. If all the valuation are integers, then a variant of the above algorithm from the DGS paper produces a price vector that is pointwise minimal among all market-clearing prices.

# Data analysis workflow

## Motivation

In data analysis, a REPL (read-evaluate-print-loop) is great for asking questions quickly about a dataset. As opposed to writing code using a compiler, an interactive environment lets us hone in on the right questions, which is of great importance for exploratory work.

A typical REPL session — e.g., using R, Pig, Hive, Python — involves loading the dataset and performing a combination of filtering, projection, and transformation. Finding the appropriate combination may require many iterations, such as tweaking the various parameters used in filtering. The process of repeating almost the same commands can be quite tedious, especially dealing with wraparound lines.

Some potential workflows are:
1) Write script in a text editor. Execute it on the command line.
During development, lines are typically appended to an existing script. So each script execution has a significant overlap with previous executions. This can be a bottleneck when loading the input or a particular transformation takes time to process. Executing a script also makes it harder to try out various transformation on the fly.

2) Write script in a text editor. Then copy and paste commands as needed into a REPL.
While this allows many iteration, the physical act of copy-and-paste becomes the most dominant part of script writing, overshadowing the thought process. Furthermore, copy-and-paste from one window to another is somewhat challenging in a ssh session when working remotely.

3) Write script in a text editor. Execute the current line of the cursor in a REPL in a separate window.
This workflow allows the flexibility of experimental work. Certain IDEs, such as RStudio, already has this functionality. However, if one is looking for a uniform experience across various languages, a simple shell experience can be achieved with the vim+tmux+slime combination, described next.

## vim + tmux + slime

The basic idea is to split a shell into two panes divided by a horizontal line, where vim is in the top pane and a REPL session at the bottom. A keyboard shortcut then sends the current line under the cursor in vim to the REPL. (Selecting a block of lines to be evaluated is also an option.)

1) tmux
tmux has many features. Here we just focus on our particular use case. Once installed, create a new session and split the current window into two panes:

tmux new -s session-name tmux split-window

2) vim-slime
Originally an Emacs plugin, vim-slime is the tool that sends a block of lines in vim directly to another tmux pane. Once installed, adding these lines to .vimrc enables this powerful trick:

let mapleader="\" map t :SlimuxREPLSendLine vmap t :SlimuxREPLSendSelection

In this example, in vim’s normal mode, the keystroke “space” followed by “t” sends either the current line or the highlighted block of lines, if it exists, to another pane. (For the first usage, there will be a prompt that asks which pane should receive the signal from vim.)

Lastly, the vim-tmux-navigator plugin allows seamless navigation among vim split windows and tmux panes.

Here is an animated screenshot that sends three lines in vim to be evaluated in R:

# SVD and low-rank approximation

The singular value decomposition (SVD) factorizes a matrix where are unitary and is diagonal with nonnegative entries. Unlike the eigenvalue decomposition, every (real or complex) matrix is guaranteed to have a SVD. Geometrically, the SVD implies that every linear transformation is equivalent to a rotation, a scaling, then another rotation.

In data analysis, the SVD can be computed to perform principal component analysis (PCA), where an ellipsoid is used to “fit” a data matrix. In other words, once the SVD is computed, a partial SVD, can be used to approximate the matrix, where and are the left and right singular vectors, and are the singular values in decreasing order. Equivalently, a partial SVD is obtained by replacing the smaller singular values with zero in the factorization. Intuitively, with the length of each ellipsoid’s component equal to its corresponding singular value, keeping only the components with non-trivial length makes the ellipsoid a good fit to the data. Formally, the Eckart-Young-Mirsky Theorem states that a partial SVD provides the best approximation to among all low-rank matrices.

Let and be any matrices, with having rank at most . Then
,
.

The theorem has a short proof for either norm, but here we describe a slightly longer proof using spectral method. Before proceeding, since we will work with singular values of different matrices, we will write to denote the -th singular value of a matrix. We first state the following lemma, which provides an estimate on how much a low-rank perturbation to a matrix can affect its singular values.

Let and be any matrices, with having rank at most .

The theorem is then an easy application of the above lemma.

(Of theorem) Recall that the norm of a matrix is equal to its largest singular value. So

which by the lemma (setting ) is at most .

For Frobenius norm, recall that the square of the Frobenius norm of a matrix is equal to the sum of the squares of its singular values. Applying the lemma above, we have

finishing the proof.

The lemma is almost a re-statement of one of Weyl’s inequalities:

To see this, let , , and , and note that is zero. Instead of invoking this inequality directly, we will prove the lemma from first principle.

(Of lemma) We first prove the case when , i.e., .
Let be the vector space spanned by the top right singular vectors , and be the null space of . By dimension argument, there must exist a non-zero vector in . Then bounding from above, we have

Bounding from below and using the facts that is orthogonal to when , Pythagorean Theorem, decreasing magnitude of singular values, and lies in the orthonormal set , respectively, we obtain

Combining both sides yields .

Now we prove the general case. Using the case, we know that for any matrix with rank at most ,

Writing , we can write Since (expressing as the inner product and applying Cauchy-Schwarz, where and are the top left and right singular vectors of , respectively) , we have that

Since the above inequality holds for arbitrary with rank at most , we can choose and . Then we can conclude that

completing the proof since is zero.