Skip to content

Drunkards’ Mathematics (Toán Say)

Tháng Mười 24, 2014

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
  1. thilan permalink

    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 :=))

      • thilan permalink

        Em đọc báo thấy nói GS vẫn còn đang ở Pháp ạ? Nếu GS có thời gian, muốn đi bộ thăm thú Paris, hay muốn xem Opéra hoặc Ballet, mà phu nhân của GS lại không ngại, thì em rất hân hạnh được dẫn GS đi ạ !🙂

  2. thilan permalink

    Hehe, comment không bị kiểm duyệt thật là dễ chịu, lâu lắm em không có cảm giác này, từ thời bác Đông A còn viết blog🙂 Hy vọng là GS không đổi tính, em xin bình bầu blog của GS là cái blog dễ thương nhất trong các blog toán học, dù người đọc có hiểu hay không hiểu !😀

  3. Is it it true that the drunkard will always return, with probability equal to one, to his house if the house has finite size?

    • damtson: If his house is centered at the origin and has positive area, then yes. If it is somewhere else, then it depends on the vectors f_i. For instance if all f_i are very close to the unit vector e_1, then the drunkard will never get anywhere close to the point (0,10), say.

Gửi phản hồi

Mời bạn điền thông tin vào ô dưới đây hoặc kích vào một biểu tượng để đăng nhập:

WordPress.com Logo

Bạn đang bình luận bằng tài khoản WordPress.com Log Out / Thay đổi )

Twitter picture

Bạn đang bình luận bằng tài khoản Twitter Log Out / Thay đổi )

Facebook photo

Bạn đang bình luận bằng tài khoản Facebook Log Out / Thay đổi )

Google+ photo

Bạn đang bình luận bằng tài khoản Google+ Log Out / Thay đổi )

Connecting to %s

%d bloggers like this: