I was in Paris in the last few days.

Paris has a good metro system. One of its big hubs is Chatelet, which is the intersection of about ten metro lines.

Apparently, one has to walk from one line to the other. In order to help the commuters, signs have been put out to indicate the direction to each metro, and the amount of time one needs to reach them. For instance:

2 —->
4 minutes

means that if one follows the given direction, one will reach metro 2 in approximately 4 minutes.

One night, I wanted to use Metro 1 from Chatelet, and tried to follow these arrows (of course you have to change directions many times). The sequence of number of minutes read like this:

4,4,6,8,3,4,4.

In other words, walking towards the target could increase the amount of time to reach it! This should be a discovery of the magnitude of a Nobel prize and  even Sheldon, the genius of Big Bang theory, would agree. (OK, being a fair scientist, I suspect that the designers of the 5 year plans in the Central Committee of the former Soviet union have achieved this feat several times in the past, without publication of course. They should deserve at least partial credit for their hard works.)

But how drunkards come into the picture?

The next scientific development was initiated by  a long-time resident of Paris and serious researcher at Ecole Normale, Dr. Phan Duong Hieu, who tried to explain the issue from the designers’ point of view (the ones who designed the signs, not the 5 years plans). Dr. Hieu argued that most commuters around Chatelet (at nights at least) are drunk. Thus, they walk randomly and reach their destination sooner or later. As they do not read the signs anyway, one may as well post a random sequence of numbers.

Hmm, I have to confess, this theory, supported by the impressive  statistics of drunkards in Paris  and the laziness of french designers, has gained solid ground and could put my breakthrough discovery in jeopardy.

Here is where the math deepens. Dr. Hieu apparently referred to Polya’s random walk theorem, which asserted  that the random walks in two dimensions is recurrent, meaning one would reach any given point with probability 1. However, he forgot the fine details that Polya works only for walks on the grid.

The precise content of Polya’s famous drunkard walk theorem is as follows. A drunkard, starting at the origin, walks on the grid $Z^d$, each time choosing a direction totally at random. Then the  probability
he reaches a fixed point X after n steps is roughly  $n^{-d/2}$, for all sufficiently large n. For $d =2$, the series $n^{-1}$ diverges, so he will reach every point on the grid with probability one.

Technically, let $B =\{e_1, \dots, e_d\}$ be the set of basic vectors in $Z^d$ and $\xi_1, \dots, \xi_n$ be iid Bernoulli random variables (taking values $\pm 1$ with probability half), and let $S_n = f_1 \xi_1 + \dots + f_n \xi_n$, where $f_i$ are chosen randomly uniformly from $B$; $S_n$ apparently represents the position of our drunkard after $n$ steps. Polya showed that for any fixed point $X$ and $n$ sufficiently large, the probability that $S_n = X$ is  $\Theta (n^{-d/2} ) .$

But gentlemen, there is no grid in Chatelet !! Without  basic vectors to follow, what happens with the poor drunkards of Paris (or anywhere else)?

Intense scientific research in the last few years indicates that lives of drunkards outside the grids are not rosy, very bad in fact.

To make a mathematical model, let us assume that a drunkard has the same step length (say 1 yard), but the directions of the steps are different. Let $f_1, \dots, f_n$ be different unit vectors in $d$ dimension, and consider $S_n = f_1 \xi_1 + \dots + f_n \xi_n$. As before, $S_n$ is the positive of after $n$ steps. We found that for fixed $X$ and $d$ at least 3, the probability that $S_n =X$ is at most   n^{-d/2 – d/(d-2) } .

This bound is sharp, as it can be realized by some sets of vectors. However, dimension 2 is fatal. In this case

$P(S_n=x) < n^{-100 }. (*)$

As a matter of fact, one can replace 100 by any constant. This means that  for a drunkard,  the walk in two dimension is worse than in any other.  Unfortunately, 2 dimension is where they live and walk.

(*) is not entirely trivial. We have a proof in this paper, which is short but uses some deep facts. I promise enough alcohol to get one drunk (in any country) for  a simple, self contained,  proof.

Now, where is that Nobel prize ?

From → Khác

6 phản hồi

GS đi Paris có vài ngày thôi thì chắc chỉ kịp thăm métro thôi ạ ? Em hy vọng là Dr Phan Duong Hieu có dẫn GS đi xem ballet ở Opéra de Paris ! 🙂

• Dr Hieu chi dan di tham quan bia thoi :=))