6 June 2013

Lévy's forgery theorem

I asked my students in the exam of my graduate probability class to prove Lévy's forgery theorem which, in folk terms, states that if you run a Brownian motion long enough then it will write your signature (provided your signature is performed continuously). The one-dimensional version of this can be stated in mathematical terms as follows.

Let B be a Brownian motion and let f be a continuous function (your "signature"). Assume B(0) = f(0) = 0. Then, no matter how small ε > 0 is we will for sure be able to find a time interval of length 1 such that B will differ from f on that time interval by at most ε.

To prove this, all we have to prove is that there is a positive probability that the above will happen on the time interval 0 ≤ t ≤ 1, and then appeal to ergodicity (a theorem in probability): if you toss a coin sufficiently many times, you will for sure bring a head, provided that the probability of a single head is positive (assuming that coin tosses are independent).

The idea for proving the above is as follows. Split the interval 0 ≤ t ≤ 1 into n subintervals I1, ... , In of length 1/n each and pick n so large that the maximum change of f within any interval of length 1/n is at most ε. (This can be done because f is uniformly continuous.)

Then observe that on each interval  Ik, the maximum deviation of B from its value at the beginning of the interval is smaller than ε with positive probability. This requires understanding that the maximum of a Brownian motion has density which leaves no gaps.

Also, observe that the difference of B and f at the beginning of the interval Ik can also be made smaller than ε with positive probability because when we observe a Brownian motion on equally spaced times, such as 0, 1/n, 2/n,..., then we are observing a random walk with normal increments.

Putting these things together we obtain a proof.

Intuitively, the proof was based on the following observation: The maximum difference of B(t) from f(t) will be small if 
(i) the maximum deviation of B(t) from its value at the beginning of the interval Ik containing t is small,
(ii) the difference between B and f at the beginning of this interval is small, and
(iii) f does not change much on this interval.

You might say, well, yes, this result is correct, but I might have to wait really long time to see my signature. And you'd be right. The analogy is this: if the probability of heads is 10-10 then you will have to wait on the average  1010 billion seconds (more than 300 years) to see a single head, if you toss one coin per second.

We spoke of  "an interval of length 1'' above. Why? Is there any reason? No, absolutely none. By scaling, we can prove the same thing for any length. But this means that you don't have to wait too long, provided you don't mind if your signature is written in tiny letters. That is, the following holds:

When you wake up in the morning, pick a particle and make it move like a Brownian motion. Arrange things so that the particle's motion is monitored by a computer which keeps track of all places it visits. Go make a cup of coffee and come back and look at the computer files. The trajectory of the particle is stored in there. Zoom in, and zoom, and zoom, and zoom, and move around, and you will see your name. In fact, you will see the whole Bible, both in Greek and in Hebrew.

Is that amazing or what? You may say, "I don't believe this". This is a false statement. It's not a matter of belief. It's a matter of proof. Assuming that the hypotheses hold, the conclusion is true. The catch is, of course, that the hypotheses are mathematical ones and whether they are met in reality is a different matter. Of course, there is no such thing as "complete independence'' in real life, and there is no such thing as ``particle with infinitesimal size'' in real life. (Also, there is no such thing as a straight line...) However, a physicist can assure us that, with high precision, the assumptions are not unrealistic, meaning that, yes, even in real life the above claims are true. When it comes to seeing your signature some time far in the future, yes, you will see it, but it will take long time. When it comes to seeing your signature before you have finished your cup of coffee, all you'll see is black space because when you zoom and zoom and zoom, after a while you'll hit the limit imposed by the particle's size.

There is no problem with mathematics. There is no problem with physics. However, there is a problem with the word "belief". Simply, the word does not exist.


What measure theory is about

It's about counting, but when things get too large.
Put otherwise, it's about addition of positive numbers, but when these numbers are far too many.

The principle of dynamic programming

max_{x,y} [f(x) + g(x,y)] = max_x [f(x) + max_y g(x,y)]

The bottom line

Nuestras horas son minutos cuando esperamos saber y siglos cuando sabemos lo que se puede aprender.
(Our hours are minutes when we wait to learn and centuries when we know what is to be learnt.) --António Machado

Αγεωμέτρητος μηδείς εισίτω.
(Those who do not know geometry may not enter.) --Plato

Sapere Aude! Habe Muth, dich deines eigenen Verstandes zu bedienen!
(Dare to know! Have courage to use your own reason!) --Kant