Riemann-, Generalized-Riemann-, and Darboux-Stieltjes integrals

(The following is somewhat rough and may have typos.)

Let us begin by setting the notations and recalling what happens without the Stieltjes part.

Defn (Partition)
Let be a closed interval. A partition is a finite collection of closed subintervals such that

1. is finite;
2. covers , i.e. ;
3. is pairwise almost disjoint, i.e. for distinct elements of , their intersection contains at most one point.

We write for the set of all partitions of .

Defn (Refinement)
Fix a closed interval, and two partitions. We say that refines or that if for every there exists such that .

Defn (Selection)
Given a closed interval and a partition, a selection is a mapping that satisfies .

Defn (Size)
Given a closed interval and a partition, the size of is defined as , where is the length of the closed interval .

Remark In the above we have defined two different preorders on the set of all partitions. One is induced by the size: we say that if . The other is given by the refinement . Note that neither are partial orders. (But that the preorder given by refinement can be made into a partial order if we disallow zero-length degenerate closed intervals.) Note also that if we must have .

Now we can define the notions of integrability.

Defn (Integrability)
Let be a closed, bounded interval and be a bounded function. We say that is integrable with integral in the sense of

• Riemann if for every there exists such that for every and every selection we have
  

• Generalised-Riemann if for every there exists such that for every and every selection we have
  

• Darboux if
  

From the definition it is clear that “Riemann integrable” implies “Generalised-Riemann integrable”. Furthermore, we have clearly that for a fixed

and that if we have

so “Darboux integrable” also implies “Generalised-Riemann integrable”. A little bit more work shows that “Generalised-Riemann integrable” also implies “Darboux integrable” (if the suprema and infima are obtained on the intervals , this would follow immediately; using the boundedness of the intervals we can find such that the Riemann sum approximates the upper or lower Darboux sums arbitrarily well.

The interesting part is the following
Theorem
Darboux integrable functions are Riemann integrable. Thus all three notions are equivalent.

Proof. Let be partitions. Let , and let be the number of non-degenerate subintervals in . We have the following estimate

The estimate follows by noting that “most” of the will be proper subsets of , and there can be at most of the that straddles between two different non-degenerate sub-intervals of . To prove the theorem it suffices to choose first a such that the upper and lower Darboux sums well-approximates the integral. Then we can conclude for all with sufficiently small the Riemann sum is almost controlled by the -Darboux sums. Q.E.D.

Now that we have recalled the case of the usual integrability. Let us consider the case of the Stieltjes integrals: instead of integrating against , we integrate against , where is roughly speaking a “cumulative distribution function”: we assume that is a bounded monotonically increasing function.

The definition of the integrals are largely the same, except that at every step we replace the width of the interval by the diameter of , i.e. . The arguments above immediately also imply that

• “Riemann-Stieltjes integrable” implies “Generalised-Riemann-Stieltjes integrable”
• “Darboux-Stieltjes integrable” implies “Generalised-Riemann-Stieltjes integrable”
• “Generalised-Riemann-Stieltjes integrable” implies “Darboux-Stientjes integrable”

However, Darboux-Stieltjes integrable functions need not be Riemann-Stieltjes integrable. The possibility of failure can be seen in the proof of the theorem above, where we used the fact that is allow to be made arbitrarily small. The same estimate, in the case of the Stieltjes version of the integrals, has replaced by , which for arbitrary partitions need to shrink to zero. To have a concrete illustration, we give the following:

Example
Let . Let if and otherwise. Let if and otherwise. Let be the partition . We have that

while

so we have that in particular the pair is Darboux-Stieltjes integrable with integral 0. However, let be any odd integer, consider the partition of into equal portions. Depending on the choice of the selection , we see that the sum can take the values

which shows that the Riemann-Stieltjes condition can never be satisfied.

The example above where both and are discontinuous at the same point is essentially sharp. A easy modification of the previous theorem shows that
Prop
If at least one of is continuous, then Darboux-Stieltjes integrability is equivalent to Riemann-Stieltjes integrability.

Remark The nonexistence of Riemann-Stieltjes integral when and has shared discontinuity points is similar in spirit to the idea in distribution theory where whether the product of two distributions is well-defined (as a distribution) depends on their wave-front sets.

An optimization problem: variation

Examining the theorem proven in the previous post, we are led naturally to ask whether there are higher order generalizations.

Question: Let with . What can we say about the minimizer of where ranges over degree polynomials?

It is pretty easy to see that we expect to intersect at the maximum number of points, which is . We label those points and call and . Then the cost function can be written as

Since we know that values of at the points we can write down the interpolation polynomial explicitly using Sylvester’s formula:

The partial derivatives are now

It remains to compute for . We observe that when

and also

So

Now, we observe that

so after some computation we arrive at

which we can further simplify to

Now, since and cross transversely at , the difference of their derivatives is non-zero. (This harks back to our assumption that .) So we are down, as in the case where , to equations entirely independent of .

More precisely, we see that the stationarity condition becomes the choice of such that the integrals

for each . Since form a basis for the polynomials of degree at most , we have that the function

is orthogonal to every polynomial of degree at most . So in particular the are solutions to the following system of equations

From symmetry considerations we have that . This also kills about half of the equations. For the low we have

1. 
2. 
3. 
4. 
5. 

Products and expectation values

Let us start with an instructive example (modified from one I learned from Steven Landsburg). Let us play a game:

I show you three identical looking boxes. In the first box there are 3 red marbles and 1 blue one. In the second box there are 2 red marbles and 1 blue one. In the last box there is 1 red marble and 4 blue ones. You choose one at random. What is …

• The expected number of red marbles you will find?
• The expected number of blue marbles you will find?
• The expected number of marbles, irregardless of colour, you will find?
• The expected percentage of red marbles you will find?
• The expected percentage of blue marbles you will find?

Answer below the cut…

Continuity of the infimum

Just realised (two seeks ago, but only gotten around to finish this blog posting now) that an argument used to prove a proposition in a project I am working on is wrong. After reducing the problem to its core I found that it is something quite elementary. So today’s post would be of a different flavour from the ones of recent past.

Question Let be topological spaces. Let be a bounded, continuous function. Is the function continuous?

Intuitively, one may be tempted to say “yes”. Indeed, there are plenty of examples where the answer is in the positive. The simplest one is when we can replace the infimum with the minimum:

Example Let the space be a finite set with the discrete topology. Then is continuous.
Proof left as exercise.

But in fact, the answer to the question is “No”. Here’s a counterexample:

Example Let with the standard topology. Define

which is clearly continuous. But the infimum function is roughly the Heaviside function: if , and if .

So what is it about the first example that makes the argument work? What is the different between the minimum and the infimum? A naive guess maybe that in the finite case, we are taking a minimum, and therefore the infimum is attained. This guess is not unreasonable: there are a lot of arguments in analysis where when the infimum can be assumed to be attained, the problem becomes a lot easier (when we are then allowed to deal with a minimizer instead of a minimizing sequence). But sadly that is not (entirely) the case here: for every , we can certainly find a such that . So attaining the infimum point-wise is not enough.

What we need, here, is compactness. In fact, we have the following

Theorem If are topological spaces and is compact. Then for any continuous , the function is well-defined and continuous.

Proof usually proceeds in three parts. That follows from the fact that for any fixed , is a continuous function defined on a compact space, and hence is bounded (in fact the infimum is attained). Then using that the sets and form a subbase for the topology of , it suffices to check that and are open.

Let be the canonical projection , which we recall is continuous and open. It is easy to see that . So continuity of implies that this set is open. (Note that this part does not depend on compactness of . In fact, a minor modification of this proof shows that for any family of upper semicontinuous functions , the pointwise infimum is also upper semicontinuous, a fact that is very useful in convex analysis. And indeed, the counterexample function given above is upper semicontinuous.)

It is in this last part, showing that is open, that compactness is crucially used. Observe that . In other words an open set. This in particular implies that there exists a “box” neighborhood contained in . Now using compactness of , a finite subset of all these boxes cover . And in particular we have

and hence is open. Q.E.D.

One question we may ask is how sharp is the requirement that is compact. As with most things in topology, counterexamples abound.

Example Let be any uncountably infinite set equipped with the co-countable topology. That is, the collection of open subsets are precisely the empty set and all subsets whose complement is countable. The two interesting properties of this topology are (a) is not compact and (b) is hyperconnected. (a) is easy to see: let be some countably infinite subset of . For each let . This forms an open cover with not finite sub-cover. Hyperconnected spaces are, roughly speaking, spaces in which all open nonempty sets are “large”, in the sense that they mutually overlap a lot. In particular, a continuous map from a hyperconnected space to a Hausdorff space must be constant. In our case we can see this directly: suppose is a continuous map. Fix . Let be open neighborhoods of . Since is continuous, is open and non-empty (by the co-countable assumption). Therefore for any pairs of neighborhoods. Since is Hausdorff, this forces to be the constant map. This implies that for any topological space , a continuous function is constant along , and hence for any , we have is continuous.

One can try to introduce various regularity/separation assumptions on the spaces to see at what level compactness becomes a crucial requirement. As an analyst, however, I really only care about topological manifolds. In which case the second counterexample up top can be readily used. We can slightly weaken the assumptions and still prove the following partial converse in essentially the same way.

Theorem Let be Tychonoff, connected, and first countable, such that contains a non-trivial open subset whose closure is not the entire space; and let be paracompact, Lindelof. Then if is noncompact, there exists a continuous function such that is not continuous.

Remark Connected (nontrivial) topological manifolds automatically satisfy the conditions on and except for non-compactness. The conditions given are not necessary for the theorem to hold; but they more or less capture the topological properties used in the construction of the second counterexample above.

Remark If is such that every open set’s closure is the entire space, we must have that it is hyperconnected (let be a closed set. Suppose is another closed set such that . Then and vice versa, but is open, so . Hence cannot be written as the union of two proper closed subsets). And if it is Tychonoff, then is either the empty-set or the one-point set.

Lemma For a paracompact Lindelof space that is noncompact, there exists a countably infinite open cover and a sequence of points such that if .

Proof: By noncompactness, there exists an open cover that is infinite. By Lindelof, this open cover can be assumed to be countable, which we enumerate by and assume WLOG that . Define and inductively by: and choose .

Proof of theorem: We first construct a sequence of continuous functions on . Let be a non-empty open set such that its closure-complement is a non-empty open set ( exists by assumption). By connectedness , so we can pick in the intersection. Let be a sequence of points converging to , which exists by first countability. Using Tychonoff, we can get a sequence of continuous functions on such that and .

On , choose an open cover and points per the previous Lemma. By paracompactness we have a partition of unity subordinate to , and by the conclusion of the Lemma we have that . Now we define the function

which is continuous, and such that . But by construction , which combined with the fact that shows the desired result. q.e.d.

Shock singularities in Burgers’ equation

It is generally well known that partial differential equations that model fluid motion can exhibit “shock waves”. In fact, the subject I will write about today is generally presented as the canonical example for such behaviour in a first course in partial differential equations (while also introducing the method of characteristics). The focus here, however, will not be so much on the formation of shocks, but on the profile of the shock boundary. This discussion tends to be omitted from introductory texts.

Solving Burgers’ equation
First we recall the inviscid Burgers’ equation, a fundamental partial differential equation in the study of fluids. The equation is written

Equation 1. Inviscid Burgers’ equation

where is the “local fluid velocity” at time and at spatial coordinate . The solution of the equation is closely related to its derivation: notice that we can re-write the equation as

The question we consider is the initial value problem for the PDE: given some initial velocity configuration , we want to find a solution to Burgers’ equation such that .

The traditional way of obtaining a solution is via the method of characteristics. We first observe (1) the alternate form of the equation above means that if is a curve tangent to the vector field , we must have be a constant valued function of the parameter . (2) Plugging this back in implies that along such a curve , the vector field is constant. (3) A curve whose tangent vector is constant is a straight line. So we have that a solution of the Burgers’ equation must verify

And we call the family of curves given by the characteristic curves of the solution.

To extract more qualitative information about Burgers’ equation, let us take another spatial derivative of the equation, and call the function . Then we have

So letting be a characteristic curve, and write , we have that along the characteristic curve

So in particular, we see that if , must blow up in time .

So what does this mean? We’ve seen that along characteristic lines, the value of stays constant. But we’ve also seen that along those lines, the value of its spatial derivative can blow up if the initial slope is negative. Perhaps the best thing to do is to illustrate it with two pictures. In the pictures the thick, red curve is the initial velocity distribution , shown with the black line representing the -axis: so when the curve is above the axis, initially the local fluid velocity is positive, and the fluid is moving to the right. The blue curves are the characteristic lines. In the first image to the right, we see that the initial velocity distribution is such that the velocity is increasing to the right. And so is always positive. We see that in this situation the flow is divergent, the flow lines getting further and further apart, corresponding to the solution where gets smaller and smaller along a flow line. For the second image here on our left, the situation is different. The initial velocity distribution starts out increasing, then hits a maximum, dips down to a minimum, and finally increases again. In the regions where the velocity distribution is increasing, we see the same “spreading out” behaviour as before, with the flow lines getting further and further apart (especially in the upper left region). But for flowlines originating in the region where the velocity distribution is decreasing, those characteristic curves gets bunched together as time goes on, eventually intersecting! This intersection is what is known as a shock. From the picture, it becomes clear what the blow-up of means: Suppose the initial velocity distribution is such that for two points . Since the flow line originating from is moving faster, it will eventually catch up to the the flow line originating from . When the two flow lines intersect, we have a problem: if we follow the flow line from , the function must take the value at the point; but if we follow the flow line from , the function must take the value at the point. So we cannot consistently assign a value to the function at the points of intersection for flow-lines in a way that satisfies Burgers’ equation.

Another way of thinking about this difficulty is in terms of particle dynamics. Imagine the line being a highway, and points on it being cars. The dynamics of the traffic flow described by Burgers’ equation is one in which each driver starts at one speed (which can be in reverse), and maintains that speed completely without regard for the cars in front of or behind it. If we start out with a distribution where the leading cars always drive faster than the trailing ones, then the cars will spread further apart as time goes on. But if we start out with a distribution where a car in front is driving slower than a car behind, the second car will eventually catch up and crash into the one in front. And this is the formation of the shock wave.

(Now technically, in this view, once the two cars crash their flow-lines should end, and so cars that are in front of the collision and moving forward should not be affected by the collision at all. But if we imagine that instead of real cars, we are driving bumper cars, so after a collision, the car in front maintains speed at the velocity of the car that hit it, while the car in back drives at the velocity of the car it hit [so the they swap speeds in an elastic collision], then we have something like the picture plotted above.)

Shock boundary
Having established that shocks can form, we move on to the main discussion of this post: the geometry of the set of shock singularities. We will consider the purely local effects of the shocks; by which we mean that we will ignore the chain reactions as described in the parenthetical remark above. Therefore we will assume that at the formation of the shock, the flow-lines terminate and the particles they represent disappear. In other words, we will consider only shocks coming from nearest neighbor collisions. In this scenario, the time of existence of a characteristic line is precisely governed by the equation on we derived before: that is given , the characteristic line emanating from will run into the shock precisely at the time . (It will continue indefinitely in the future if the derivative is positive.)

The most well-known image of a shock formation is the image on the right, where we see the classic fan/wedge type shock. (Due to the simplicity in sketching thie diagram by hand, this is probably how most people are introduced to this type of diagrams, either on a homework set or in class.) What we see here is an illustration of the fact that

If for , we have , and , then the shock boundary is degenerate: it consists of a single focal point.

To see this analytically: observe that because the blow-up time depends on the first derivative of the initial velocity distribution, for such a set-up the blow-up time is constant for the various points. Then we see that the spatial coordinate of the blow-up will be . But since is linear in , we have

is constant. And therefore the shock boundary is degenerate.

Next we consider the case where vanishes at some point , but . The two pictures to the right of this paragraph illustrates the typical shock boundary behaviour. On the far right we have the slightly aphysical situation: notice that for a particle coming in from the left, before it hits its shock boundary, it first crosses the shock boundary formed by the particles coming in from the right. This is the situation where the third derivative is positive, and the cusp point which corresponds to the shock boundary for opens to the future. The nearer picture is the situation where the third derivative is negative, with the cusp point opening downwards. Notice that since we are in a neighborhood of a point where the second derivative vanishes, the initial velocity distributions both look almost straight, and it is hard to distinguish from this image the sign of the third derivative. The picture on the far right is based on an arctan type initial distribution, whereas the nearer picture is based on an type initial distribution. Let us again analyse the situation more deeply. Near the point , we shall assume that for some constant. And we will assume, using Galilean transformations, that . Then letting , we have

Thus as a function of , the blow-up times of flow lines are given by

Solving for their blow-up profile then gives (after quite a bit of algebraic manipulation)

which can be easily seen to be a cusp: at . And it is clear that the side the cusp opens is dependent on the sign of the third derivative, .

The last bit of computation we will do is for the case . In this case we can take

as an approximation. Then the blowup times will be

which leads to the blowup profile being [Thanks to Huy for the correction.]

and a direct computation will then lead to the conclusion that in this generic scenario, the shock boundary will be everywhere tangent to the flow-line that ends there.

Conway’s Base 13 Function

(N.b. Credit where credit’s due: I learned about this function from an answer of Robin Chapman’s on MathOverflow, and its measurability from Noah Stein.)

Conway’s base 13-function is a strange beast. It was originally crafted by John Conway as a counterexample to the converse of the intermediate value theorem, and has the property that on any open interval its image contains the entire real line. In addition, its support set also serves as an illustration of a dense, uncountable set of numbers whose Lebesgue measure is 0.

Digital computing and catastrophic failures

I just read a wonderful article on Discover magazine. The article centers around Kwabena Boahen (and other members of the school of Carver Mead) in creating electronic circuitry modeled more after the human brain. The main claim is that these types of neurocircuits have the potential in significantly lowering the power consumption for computing. If the claim were correct, though, it will imply there are certain nontrivial relationship between the voltage applied to a transistor and the noise experienced.

The idea, I think, if I understood correctly just from the lay explanation, is a trade-off between error rates versus power. Let us consider the completely simplified and idealized model given by the following. A signal is sent in at voltage . The line introduces thermal noise in the form of a Gaussian distribution. So the signal that comes out at the other end has a distribution , where the Gaussian family is defined as

Definition 1 (Noisy signal)

(Note: our definition is not the standard definition, in particular our Gaussian is centered at ! This definition makes calculations later simpler, as we shall see.)