Travelling between cities …

December 19, 2011 at 12:29 am (probability, Uncategorized)
Tags: cox durrett, first passage, optimal route, percolation, simulation, traveling salesman

Consider the standard plane lattice ${\mathbb{Z}^2}$ and suppose that each point ${(x,y) \in \mathbb{Z}^2}$ represents a city. Each city is connected to its ${4}$ neighbors only and each edge ${(AB)}$ carries a weight that represents the time it takes to go from city ${A}$ to city ${B}$ . A natural question is the following:

Given two (non-neighboring) cities on the map, how long does take to travel between them?

To make the problem more tractable, mathematicians usually assume that the time it takes to travel between neighboring cities are independent from each other and identically distributed according to a distribution ${\mu(dt)}$ . In other words, each edge of the lattice ${\mathbb{Z}^2}$ carries a random variable ${T_{e}}$ . The random variables ${\big\{ T_e \big\}_e}$ are ${i.i.d}$ and distributed according to ${\mu(dt)}$ . It takes

$\displaystyle \begin{array}{rcl} \tau(A,B)\;=\; \inf \; \Big\{ \; \sum_{\text{path}}T_{e} \;: \text{paths between A and B} \; \Big\} \end{array}$

to travel on the optimal route between city ${A}$ and city ${B}$ . The optimal route is usually called a geodesic. If one starts from the origin, one may wonder what are the cities that can be reached in less that ${30}$ hours, say. On the next picture, each red dot represents a city that can be reached in less than ${30}$ hours when the travel time between any two neighboring city is exponentially distributed with mean ${1}$ hour.

One may also wonder how the optimal routes look like. On the next picture I have plotted ${4.10^4}$ cities (the origin is the blue dotted city) and highlighted the optimal routes between the origin and each one of the cities on the border of the map.

Is it very different from the highway system around a typical city?

For those who want to play with this model, you can modify the quick and dirty Python code that can be found here. The study of these models is an active area of research.

Like this:

Be the first to like this post.

4 Comments

Angelo said,

December 19, 2011 at 7:05 am

Dear Alekk,

if the times (T or X?) between two neighboring vertices are i.i.d. the minimizing paths between any A and B (sometimes there can be more than one minimizing path) should be totally independent of the chosen distribution. I guess that the traffic issue becomes more interesting if you allow for a) “fast” and “slow” tracks (exp distributions with small or large average) or b) by playing with the tail of the distribution (exponential vs gamma with the same average) and c) by allowing traffic jams to occur.

Best regards,

Angelo

Reply
Alekk said,

December 19, 2011 at 9:50 am

thanks, typo fixed. Nevertheless I don’t see why the geodesics should be independent from the chosen distribution ?!

Reply
- Angelo said,
  
  December 19, 2011 at 11:14 am
  
  Hi Alekk,
  
  I have re-read your post now. You probably assign to each edge a time T_\epsilon which is then quenced and you perform your walk on a disordered lattice. In this case, the time associated to each edge was drawn from a probability distribution but it is no more a random variable during the process (it is quenched).
  
  I had interpreted your process in a different way. Namely, that every time the walker crosses an edge it takes him a random time drawn from a certain distribution. In fact, only if the walker is able to sample “all” paths it will know, at the end, which one satisfies the optimization condition. But I find it a bit unrealistic, in a traffic context, that the time to cross an edge is quenced.
  
  Best, A.
  
  Reply
Alekk said,

December 19, 2011 at 1:25 pm

Hi Angelo,

yes, sorry for being unclear: I was talking of a quenched randomness. That makes the situation easier for talking of geodesics and distances.

Regards,
Alex.

Reply

Journey into Randomness