You are driving a car with maximal acceleration (and deceleration) A on a road that’s been blocked off in both directions (or, if you prefer, on the landing strip of an aircraft carrier). Let L be the length of the road available to you.
What is the maximal speed you can reach?
Besides A and L, the answer also depends on your mood: do you want to live, or are you willing to go out in a blaze of glory? In the latter case the answer is obvious: position the car at one end of the interval, and put the pedal to the metal. The car will cover the distance L within the time , reaching the speed at the end. In the former scenario one has to switch to the brake pedal midway through the distance, so the maximal speed will be attained at half the length, .
Rephrased in mathematical terms: if is a twice differentiable function and for , then if is defined on a half-infinite interval, and if the domain of is the entire line. To connect the notation, just put and in the previous paragraph… and I guess some proof other than “this is obvious” is called for, but it’s not hard to find one: this is problem 5.15 in Rudin’s Principles of Mathematical Analysis.
Perhaps more interesting is to study the problem in higher dimensions: one could be driving in a parking lot of some shape, etc. Let’s normalize the maximal acceleration as 1, keeping in mind it’s a vector. Given a set E, let S(E) be the square of maximal speed attainable by a unit-acceleration vehicle which stays in E indefinitely. Also let U(E) be the square of maximal speed one can attain while crashing out of bounds after the record is set. Squaring makes these quantities scale linearly with the size of the set. Both are monotone with respect to set inclusion. And we know what they are for an interval of length L: namely, and , so that gives some lower bounds for sets that contain a line interval.
When E is a circle of radius 1, the best we can do is to drive along it with constant speed 1; then the centripetal acceleration is also 1. Any higher speed will exceed the allowable acceleration in the normal direction, never mind the tangential one. So, for a circle both S and U are equal to its radius.
On the other hand, if E is a disk of radius R, then driving along its diameter is better: it gives and .
If E is a convex set of diameter D, is it true that and ?
Is it true that in general?
How to express S and U for a smooth closed curve in terms of its curvature? They are not necessarily equal (like they are for a circle): consider thin ellipses converging to a line segment, for which S and U approach the corresponding values for that segment.
The answer to Question 1 is yes. Consider the orthogonal projection of E, and of a trajectory it contains, onto some line L. This does not increase the diameter or the acceleration; thus, the one-dimensional result implies that the projection of velocity vector onto L does not exceed (or for the crashing-out version). Since L was arbitrary, it follows that and . These upper bounds hold for general sets, not only convex ones. But when E is convex, we get matching lower bounds by considering the longest segment contained in E.
When does a map admit a lower “anti-continuity” bound like for some function and for all ? The answer is easy: must be injective and its inverse must be uniformly continuous. End of story.
But recalling what happened with diameters of connected sets last time, let’s focus on the inequality for connected subsets . If such exists, the map f has the LOB property, for “lower oscillation bound” (oscillation being the diameter of image). The LOB property does not require to be injective. On the real line, satisfies it with : since it simply folds the line, the worst that can happen to the diameter of an interval is to be halved. Similarly, admits a lower oscillation bound . This one decays faster than linear at 0, indicating some amount of squeezing going on. One may check that every polynomial has the LOB property as well.
On the other hand, the exponential function does not have the LOB property, since tends to as . No surprise there; we know from the relation of continuity and uniform continuity that things like that happen on a non-compact domain.
Also, a function that is constant on some nontrivial connected set will obviously fail LOB. In topology, a mapping is called light if the preimage of every point is totally disconnected, which is exactly the same as not being constant on any nontrivial connected set. So, lightness is necessary for LOB, but not sufficient as shows.
Theorem 1: Every continuous light map with compact domain admits a lower oscillation bound.
Proof. Suppose not. Then there exists and a sequence of connected subsets such that and . We can assume compact, otherwise replace it with its closure which we can because .
The space of nonempty compact subsets of is called the hyperspace of ; when equipped with the Hausdorff metric, it becomes a compact metric space itself. Pass to a convergent subsequence, still denoted . Its limit has diameter at least , because diameter is a continuous function on the hyperspace. Finally, using the uniform continuity of we get , contradicting the lightness of .
Here is another example to demonstrate the importance of compactness (not just boundedness) and continuity: on the domain define . This is a homeomorphism, the inverse being . Yet it fails LOB because the image of line segment has diameter , which can be arbitrarily close to 0. So, the lack of compactness hurts. Extending to the closed square in a discontinuous way, say by letting it be the identity map on the boundary, we see that continuity is also needed, although it’s slightly non-intuitive that one needs continuity (essentially an upper oscillation bound) to estimate oscillation from below.
All that said, on a bounded interval of real line we need neither compactness nor continuity.
Theorem 2: If is a bounded interval, then every light map admits a lower oscillation bound.
Proof. Following the proof of Theorem 1, consider a sequence of intervals such that and . There is no loss of generality in considering open intervals, since it can only make the diameter of the image smaller. Also WLOG, suppose and ; this uses the boundedness of . Consider a nontrivial closed interval . For all sufficiently large we have , which implies . Thus is constant on , a contradiction.
The property that distinguishes real line here is that nontrivial connected sets have nonempty interior. The same works on the circle and various tree-like spaces, but fails for spaces that don’t look one-dimensional.
The definition of uniform continuity (if it’s done right) can be phrased as: is uniformly continuous if there exists a function , with , such that for every set . Indeed, when is a two-point set this is the same as , the modulus of continuity. Allowing general sets does not change anything, since the diameter is determined by two-point subsets.
Does it make a difference if we ask for only for connected sets ? For functions defined on the real line, or on an interval of the line, there is no difference: we can just consider the intervals and obtain
However, the situation does change for maps defined on a non-convex domain. Consider the principal branch of square root, , defined on the slit plane .
This function is continuous on but not uniformly continuous, since as . Yet, it satisfies for connected subsets , where one can take . I won’t do the estimates; let’s just note that although the points are close to each other, any connected subset of containing both of them has diameter greater than 1.
In a way, this is still uniform continuity, just with respect to a different metric. Given a metric space , one can define inner diameter metric on by letting be the infimum of diameters of connected sets that contain both and . This is indeed a metric if the space is reasonable enough (i.e., any two points are contained in some bounded connected set). On a convex subset of , the inner diameter metric coincides with the Euclidean metric .
One might think that the equality should imply that the domain is convex, but this is not so. Indeed, consider the union of three quadrants on a plane, say . Any two points of can be connected by going up from whichever is lower, and then moving horizontally. The diameter of a right triangle is equal to its hypotenuse, which is the Euclidean distance between the points we started with.
Inner diameter metric comes up (often implicitly) in complex analysis. By the Riemann mapping theorem, every simply connected domain , other than itself, admits a conformal map onto the unit disk . This map need not be uniformly continuous in the Euclidean metric (the slit plane is one example), but it is uniformly continuous with respect to the inner diameter metric on .
Furthermore, by normalizing the situation in a natural way (say, and ), one can obtain a uniform modulus of continuity for all conformal maps onto the unit disk, whatever the domain is. This uniform modulus of continuity can be taken of the form for some universal constant . Informally speaking, this means that a slit domain is the worst that can happen to the continuity of a conformal map. This fact isn’t often mentioned in complex analysis books. A proof can be found in the book Conformally Invariant Processes in the Plane by Gregory Lawler, Proposition 3.85. A more elementary proof, with a rougher estimate for the modulus of continuity, is on page 15 of lecture notes by Mario Bonk.
Green functions of the Laplacian are bounded in one dimensional domains, a reflection of the fact that square integrability of the derivative implies boundedness in one dimension but not in two or more. So, it’s possible to say something about the envelope obtained by taking the supremum over source location y.
In order to satisfy the distributional equation , Green functions have a corner at y, where the derivative jumps down by 1. Combining this property with the boundary conditions identifies the function. Let’s use the interval (0,1) as the domain.
The Dirichlet boundary condition leads to the formula :
The upper envelope is the parabola . This fact becomes more evident if we use more functions.
Mixed Dirichlet-Neumann conditions yield an even simpler formula . The envelope is boring in this case:
The pure Neumann condition requires an adjustment to the definition of Green function, since it is incompatible with . Instead, let’s ask for where the constant c is the reciprocal of the length of the interval. This ensures that the integral of the second derivative is zero. Also, it is more convenient to use the interval (-1,1) here. The Neumann Green function for this interval is , up to an additive constant.
So the envelope is also determined up to a constant. On the picture above it is .
Finally, let’s consider the periodic condition , . As with the Neumann condition, the definition is adjusted to allow the second derivative integral be zero. Using the interval (-1, 1) we get using the notation and for brevity. Note that the first term, , is the Dirichlet Green function for this interval. The additional quadratic term brings the integral of the second derivative to zero, which ensures the periodic condition for the first derivative. And the upper envelope is, up to a constant…
a constant. Not exciting but makes perfect sense, considering that we are dealing with the Green function of a circle, where moving the source amounts to shifting the function.
In a comment to Recursive randomness of integers Rahul pointed out a continuous version of the same problem: pick uniformly in , then uniformly in , then uniformly in , etc. What is the distribution of the sum ?
The continuous version turns out to be easier to analyse. To begin with, it’s equivalent to picking uniformly distributed, independent and letting . Then the sum is
which can be written as
So, is a stationary point of the random process where is uniformly distributed in . Simply put, and have the same distribution. This yields the value of in a much simpler way than in the previous post:
We also get an equation for the cumulative distribution function . Indeed,
The latter probability is . Conclusion: . Differentiate to get an equation for the probability density function , namely . It’s convenient to change the variable of integration to , which leads to
Looks pretty simple, doesn’t it? Since the density is zero for negative arguments, it is constant on . This constant, which I’ll denote , is , or simply . I couldn’t get an analytic formula for . My attempt was where are the moments of . The moments can be computed recursively using , which yields
The first few moments, starting with , are 1, 1, 3/2, 17/6, 19/3, 81/5, 8351/80… Unfortunately the series diverges, so this approach seems doomed. Numerically which is not far from the Euler-Mascheroni constant, hence the choice of notation.
On the interval (1,2) we have , hence
The DDE gets harder to integrate after that… on the interval the solution already involves the dilogarithm (Spence’s function):
To generate a sample from distribution S, I begin with a bunch of zeros and repeat “add 1, multiply by U[0,1]” many times. That’s it.
import numpy as np
import matplotlib.pyplot as plt
trials = 10000000
terms = 10000
x = np.zeros(shape=(trials,))
for _ in range(terms):
np.multiply(x+1, np.random.uniform(size=(trials,)), out=x)
_ = plt.hist(x, bins=1000, normed=True)
I still want to know the exact value of … after all, it’s also the probability that the sum of our random decreasing sequence is less than 1.
The constant I called “” is in fact where is indeed Euler’s constant… This is what I learned from the Inverse Symbolic Calculator after solving the DDE (with initial value 1) numerically, and calculating the integral of the solution. From there, it did not take long to find that
The p.d.f. of S is the Dickman function, normalized to have integral 1. Wikipedia plots it on log scale, but Wolfram Mathworld has a plot identical to the above. Neither one mention the sum of random decreasing sequence.
Oh well. At least I practiced solving delay differential equations in Python. There is no built-in method in SciPy for that, and although there are some modules for DDE out there, I decided to roll my own. The logic is straightforward: solve the ODE on an interval of length 1, then build an interpolating spline out of the numeric solution and use it as the right hand side in the ODE, repeat. I used Romberg’s method for integrating the solution; the integration is done separately on each interval [k, k+1] because of the lack of smoothness at the integers.
import numpy as np
from scipy.integrate import odeint, romb
from scipy.interpolate import interp1d
numpoints = 2**12 + 1
solution = [lambda x: 1]
integrals = 
for k in range(1, 15):
y0 = solution[k-1](k)
t = np.linspace(k, k+1, numpoints)
rhs = lambda y, x: -solution[k-1](np.clip(x-1, k-1, k))/x
y = odeint(rhs, y0, t, atol=1e-15, rtol=1e-13).squeeze()
solution.append(interp1d(t, y, kind='cubic', assume_sorted=True))
total_integral = sum(integrals)
As a byproduct, the program found the probabilities of the random sum being in each integer interval:
Entering a string such as “random number 0 to 7” into Google search brings up a neat random number generator. For now, it supports only uniform probability distributions over integers. That’s still enough to play a little game.
Pick a positive number, such as 7. Then pick a number at random between 0 and 7 (integers, with equal probability); for example, 5. Then pick a number between 0 and 5, perhaps 2… repeat indefinitely. When we reach 0, the game becomes really boring, so that is a good place to stop. Ignoring the initial non-random number, we got a random non-increasing sequence such as 5, 2, 1, 1, 0. The sum of this one is 9… how are these sums distributed?
Let’s call the initial number A and the sum S. The simplest case is A=1, when S is the number of returns to 1 until the process hits 0. Since each return to 1 has probability 1/2, we get the following geometric distribution
When starting with A=2, things are already more complicated: for one thing, the probability mass function is no longer decreasing, with P[S=2] being greater than P[S=1]. The histogram shows the counts obtained after 2,000,000 trials with A=2.
The probability mass function is still not too hard to compute: let’s say b is the number of times the process arrives at 2, then the sum is 2b + the result with A=1. So we end up convolving two geometric distributions, one of which is supported on even integers: hence the bias toward even sums.
For large k, the ratio P[S=k+2]/P[s=k] is asymptotic to (4/3)/4 = 1/3, which means that the tail of the distribution is approximately geometric with the ratio of .
I did not feel like computing exact distribution for larger A, resorting to simulations. Here is A=10 (ignore the little bump at the end, an artifact of truncation):
There are three distinct features: P[S=0] is much higher than the rest; the distribution is flat (with a bias toward even, which is diminishing) until about S=n, and after that it looks geometric. Let’s see what we can say for a general starting value A.
Perhaps surprisingly, the expected value E[S] is exactly A. To see this, consider that we are dealing with a Markov chain with states 0,1,…,A. The transition probabilities from n to any number 0,…,n are 1/(n+1). Ignoring the terminal state 0, which does not contribute to the sum, we get the following kind of transition matrix (the case A=4 shown):
The initial state is a vector such as . So is the state after j steps. The expected value contributed by the j-th step is where is the weight vector. So, the expected value of the sum is
It turns out that the matrix has a simple form, strongly resembling M itself.
Left multiplication by v extracts the bottom row of this matrix, and we are left with a dot product of the form . Neat.
What else can we say? The median is less than A, which is no surprise given the long tail on the right. Also, P[S=0] = 1/(A+1) since the only way to have zero sum is to hit 0 at once. A more interesting question is: what is the limit of the distribution of T = S/A as A tends to infinity? Here is the histogram of 2,000,000 trials with A=50.
It looks like the distribution of T tends to a limit, which has constant density until 1 (so, until A before rescaling) and decays exponentially after that. Writing the supposed probability density function as for , for , and using the fact that the expected value of T is 1, we arrive at and . This is a pretty good approximation in some aspects: the median of this distribution is , suggesting that the median of S is around which is in reasonable agreement with experiment. But the histogram for A=1000 still has a significant deviation from the exponential curve, indicating that the supposedly geometric part of T isn’t really geometric:
One can express S as a sum of several independent geometric random variables, but the number of summands grows quadratically in A, and I didn’t get any useful asymptotics from this. What is the true limiting distribution of S/A, if it’s not the red curve above?