A subsequence converging to an analytic curve

This is a question that confronted me while I was trying to find a proof of a different result. Consider a sequence $x_n \in \mathbb{R}^m$ with $x_n \to 0$. Under what circumstances does a subsequence converge to an analytic curve $\gamma:[0,\varepsilon) \to \mathbb{R}^m$ with $\gamma(0)=0$? Let me make this notion precise: the sequence must converge according to all derivatives, that is, faster than any power of $r = \|x\|$. It should be noted that the eventual subsequence we extract need not lie on the curve, because of the existence of nonanalytic functions which converge more quickly than any polynomial. By the compactness of $S^{m-1}$ we can pass to a subsequence such that $s_1^n = \|x_n\|$ is converging to some point $s_1 \in S^{m-1}$. So we begin to construct a curve by starting with \[ \gamma(t) = tv_1, \] where $v_1=s_1$. Next, let $s^2_n$ be the intersection of $\gamma(t) = v_1t +v_2^nt^2$ with $S^{n-1}$, where the vector $v_2^n$ is chosen such that $\gamma(t)$ contains $x_n$. Passing to a subsequence, we have $s^2_n \to s_2$. We then have the curve \[ \gamma(t) = v_1t +v_2t^2, \] where $v_2$ is chosen so that the curve intersects $S^{m-1}$ at $s_2$. We assume for the moment that such a $v_2$ exists, and examine this assumption shortly. Note that the distance from $x_n$ to the curve is bounded by $ct_n^2$, where $\gamma(t_n)$ is the point of the curve closest to $x_n$, and since $s^2_n \to s_2$, $c$ can be made as small as we like by truncating the sequence. Iterating this process, we arrive at a curve \[ \gamma(t) = v_1t +v_2t^2 + \ldots + v_kt^k, \] and a subsequence $x_n$ such that $d(x_n,\gamma(t_n)) \leq ct_n^k \leq cr_n^k$, where $r_n =||x_n||$. Now we return to the question of whether the vector $v_2$ (and $v_3,\ldots,v_k$) actually exists. It can happen that as $s^2_n \to s_2$, $v_2^n$ becomes unbounded and consequently $v_2$ doesn't exist. This means that the sequence is converging to $v_1$ slower than $t^2$. This corresponds to the case where the curve must be written as a Puiseux series, rather than a Taylor series. In this case, we multiply the Taylor series by $t$, i.e. we consider \[ \gamma(t) = v_1t^2 +v_2t^3 + \ldots + v_kt^{k+1}, \] and again try to construct $v_2$. It could happen that $v_2 = 0$, in which case we attempt to construct $v_3$, continuing to multiply by $t$ whenever a vector fails to exist. Eventually we will obtain the first two non-zero terms of our curve \[ \gamma(t) = v_1t^{1+l} + v_jt^{j+l} \] for some $j \geq 2$. Otherwise, all subsequences of the sequence $x_n$ must be asymptoting to $v_1$ slower than any rational power $\rho$ of $r$, $\rho > 1$, $\rho \to 1$. From here, we can construct all remaining terms using our original process, i.e. all remaining vectors $v_i$ will exist. Thus, after multiplying by $t$ enough times, we will eventually be able to construct a curve \[ \gamma(t) = v_1t^{1+l} +v_2t^{2+l} + \ldots + v_kt^{k}, \] which satisfies our requirements. However, it's unfortunately possible for $x_n$ to be asymptoting to $v_1$ slower than any rational power or $r$. In cases where the more information is known about the sequence $x_n$, it may be possible to pass to looking for a 2 dimensional manifold the sequence is converging to. If the pathological case is encountered again, pass to looking for a three dimensional manifold, and so on until the dimension of the space is reached.

The two envelopes problem

This post concerns the two envelopes problem.

To summarise, suppose we know that one envelope contains some money, and another envelope contains twice that amount of money. However, we do not know which is which. We choose one of the envelopes, which contains an unknown amount $x$. There is a 50% chance that this is the larger envelope, and a 50% chance it is the smaller. Thus it would seem that the expected value for the other envelope should be $\frac{1}{2}(2x+\frac{1}{2}x)>x$, so that the other envelope is always the larger one. But since this argument would apply equally well to each envelope, it is obviously incorrect.

The problem is a little tricky, but the error with the argument is clear once you spot it.

The mistake is that one cannot talk about expectation value in the absence of a prescribed probability distribution. Suppose someone puts some money in an envelope. What is the expected value for the amount of money in the envelope? It's clearly a nonsense question. Assuming every positive amount has equal probability, then the expected value would seem to be $\infty / 2$. Similarly, suppose someone puts some money in one envelope, and twice that amount in another envelope. What is the expected value of the amount of money in either envelope? Again, no reasonable answer can be given. Therefore, having supposed that the first envelope contains x, the probability distribution for the second envelope is simply unknown. The only thing we can say about it is that values other than x/2 and 2x are not possible.

While it is true that the other envelope must be either x/2 or 2x, it is not true that each of these must be equally likely. In fact, if the person preparing the envelopes only ever chooses from one of two values, the possible values for the envelopes span only a factor of two, so x/2 and 2x cannot both be possible. Furthermore, the probability distribution for the amount contained in the first envelope and the probability distribution for whether it is the larger or the smaller of the envelopes, are not independent random variables. Although it is correct to say that $x$ has a 50% chance of being the smaller value, and a 50% chance of being the larger value, $x$ may be a different value in each case!

In summary, one must begin with the (not independent) probability distributions for the two envelopes, before being able to talk about expectation values.

When does a smooth function fail to be analytic?

It's well known that not all smooth functions $f(x)$ are analytic, i.e. can be locally represented by a power series \[ f(x) = f(0) + f'(0)x + \frac{1}{2!}f''(x)x^2 + \frac{1}{3!}f^{(3)}(x)x^3 + \ldots \] The counterexample typically given is the function \[ f(x) = \left\{ \begin{array}{lr} 0 & : x \leq 0 \\ e^{-1/x} & : x > 0 \end{array} \right. \] However, I thought it would be worthwhile to make explicit why the failure occurs.

Suppose we are interested in the interval $[0,\varepsilon]$. An $n$th-order polynomial is a function whose $n$th derivative is constant. So it stands to reason that as long as a function's $n$th derivative doesn't change "too much" over this interval, the function should be well approximated by the first $n$ terms of its Taylor series.

Let's write \[ f^{n}(x) = f^{n}(0) + E_{n}(x), \] where $E_{n}(x)$ is the error function representing how much $f^{(n)}$ differs from constant. Then we can integrate to get \[ f^{(n-1)}(x) = f^{(n-1)}(0) + f^{(n)}(0)x + \int_0^x{E_n(t)dt}, \] where the error in the $(n-1)$th derivative is \[ \left| E_{n-1}(x) \right| = \left| \int_0^x{E(t)dt} \right| \leq \sup_{t \in [0,\varepsilon]}{\left| E_n(t) \right|}x. \] Iterating this process, we eventually find that the original function differs from it's $n$th-order Taylor series by \[ \left| E_0(x) \right| \leq \frac{1}{n!} \sup_{t \in [0,\varepsilon]}{\left| E_n(t) \right|}x^n. \] For the function to be analytic, this expression needs to converge to zero as $n \to \infty$. Due to the $n!$ denominator, this can only fail if $E_n$, and hence the $n$th derivative, is growing extremely quickly as n increases. In this sense, non-analytic functions are pathological.

We can observe this pathological behaviour for our counterexample by plotting a few of the derivatives. While the 3rd derivative (left) shoots up to the value of 30 within .15 of the origin, the 10th derivative (right) is already order $10^{14}$ approximately $.04$ from the origin!

Random walks on surfaces

Here I describe a procedure for computing random walks on surfaces (that is, manifolds of dimension two). The procedure can be easily generalised to higher dimensions, but surfaces are more commonly encountered in practice.

Let $\vec x(u,v) = (x(u,v),y(u,v),z(u,v))$ represent a parameterised surface, and $(u_0,v_0)$ the coordinates of the initial position of a diffusing particle. We illustrate with the example of a torus of major radius $R$ and minor raidus $r$, which can be parameterised by \[ \vec x = [\cos{u}(R+r\cos{v}),\sin{u}(R+r\cos{v}),r\sin{v}]. \] Of course, we cannot simply perform a random walk in the coordinate space $(u,v)$. Not only would this depend on the choice of parameterisation, but in general there exists no parameterisation for which a random walk in the coordinate space coincides with a random walk on the actual surface.

Instead, in order to perform a random walk on a surface, we need to find a pair of vectors $e_1(u,v), e_2(u,v)$ in the coordinate space which represent orthonormal directions on the surface. To do this, we begin by computing the Riemannian metric, which is defined by the following matrix: \[{g_{ij}} = \left[ {\begin{array}{*{20}{c}} {{g_{11}}}&{{g_{12}}}\\ {{g_{21}}}&{{g_{22}}} \end{array}} \right] = \left[ {\begin{array}{*{20}{c}} {\frac{{\partial \vec x}}{{\partial u}} \cdot \frac{{\partial \vec x}}{{\partial u}}}&{\frac{{\partial \vec x}}{{\partial u}} \cdot \frac{{\partial \vec x}}{{\partial v}}}\\ {\frac{{\partial \vec x}}{{\partial v}} \cdot \frac{{\partial \vec x}}{{\partial u}}}&{\frac{{\partial \vec x}}{{\partial v}} \cdot \frac{{\partial \vec x}}{{\partial v}}} \end{array}} \right] = \left[ {\begin{array}{*{20}{c}} {{{(R + r\cos{v})}^2}}&0\\ 0&{{r^2}} \end{array}} \right].\] Using the Gramm-Schmidt process, we can take our vectors to be \begin{align*} e_1 & = \frac{1}{\sqrt{g_{11}}}(1,0),\\ e_2 & = \frac{1}{\sqrt{g}\sqrt{g_{11}}}(-g_{21},g_{11}), \end{align*} where $g$ is the determinant of the above matrix. In the specific case of the torus, this works out to be \begin{align*} e_1 & = ((R+r\cos{v})^{-1},0), \\ e_2 & = (0,r^{-1}). \end{align*} Now, all we have to do to choose at random a vector $e_0$ from the four vectors ${\pm e_1, \pm e_2}$, and the new coordinates of the particle will be given by \[ (u_1,v_1) = (u_0,v_0) + \delta e_0, \] where $\delta$ is a small number representing the step size.

A simple and intuitive proof of the central limit theorem

Statisticians are often tasked with estimating the average of a quantity based on only a "sample" of the true population. For example, if we want to determine the height of the average person, it would be impractical to measure the height of everybody on earth. Instead, we measure the height of a finite sample of people, chosen at random, and compute the average of this sample. The law of large numbers tells us that as the sample size increases, the sample average approaches the population average. But just how large does our sample need to be to achieve a desired accuracy in our estimate?

This is where the central limit theorem comes in. It is an invaluable tool used daily by practicing statisticians to tell us how close to the real average our sample average is likely to be. We assume that we have a random sample $\{X_1,...,X_n\}$ of independent, identically distributed random variables, whose distribution $X$ has average $\mu$ and variance $\sigma^2$. For convenience, we will normalise $X$ so that $\mu = 0$. From this sample we may compute the sample average \[ S_n = \frac{X_1+...+X_n}{n}. \] If we were to repeat this procedure with a different sample of $n$ individuals, we would get a slightly different value for $S_n$. Thus, $S_n$ can be viewed as a random variable which satisfies a certain distribution.

Roughly speaking, the central limit theorem says that, as $n$ gets larger, $S_n$ approaches a normal distribution with average $\mu = 0$ and variance $\frac{\sigma^2}{n}$. Using this fact and the $68–95–99.7$ rule for normal distributions, we can then determine the probability that our sample average lies within a certain number of standard deviations of the true value.

A search for an explanation of the central limit theorem will typically yield abstract proofs that rely on the Fourier transform. However, the purpose of this post is to show that the central limit theorem is in fact quite simple and intuitive, and can be derived in an elementary way. The key insight is to remember that a normal distribution represents the probability for a particle to be found a given distance from the origin while it undergoes a diffusion or random walk. It follows that to demonstrate the central limit theorem, all we have to do is figure out what our scenario has to do with a random walk! As luck would have it, we can conceive of the sample average as an $n$-step random walk \[ S_n = \frac{X_1}{n}+...+\frac{X_n}{n}. \] By assumption, $E(X) = 0$, so that the drift is indeed random. As we increase $n$, the number of steps increases while the step size goes to zero, so that $S_n$ will clearly approach a normal distribution. And that's really all there is to it!

We still need to show though that the variance of this distribution is $\frac{\sigma^2}{n}$. We write $S_{n} = S_{n-1} + Z_n$, where $Z_n$ represents the random drift between steps $n-1$ and $n$. Then \begin{align*} E(S_n^2) & = E(S_{n-1}^2 +2S_{n-1}Z_n + Z_n^2) \\ & = E(S_{n-1}^2) + 2E(S_{n-1})E(Z_n) + E(Z_n^2) \\ & = E(S_{n-1}^2) + E(Z_n^2), \end{align*} since $S_{n-1}$ and $Z_n$ are independent variables and $E(Z_n)=0$. So each time we increase $n$ by one, we add the quantity $E(Z_n^2)$ to $E(S_n^2)$. This means that \[ E(S_n^2) = nE(Z_n^2). \] But $E(Z_n^2) = E(\frac{1}{n^2}X^2) = \frac{\sigma^2}{n^2}$. It follows that $E(S_n^2) = \frac{\sigma^2}{n}$.