Journey into Randomness

Consider the standard plane lattice and suppose that each point represents a city. Each city is connected to its neighbors only and each edge carries a weight that represents the time it takes to go from city to city . 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 . In other words, each edge of the lattice carries a random variable . The random variables are and distributed according to . It takes

to travel on the optimal route between city and city . 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 hours, say. On the next picture, each red dot represents a city that can be reached in less than hours when the travel time between any two neighboring city is exponentially distributed with mean hour.

One may also wonder how the optimal routes look like. On the next picture I have plotted 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.