Random walks

Fifteen hundred walkers without a map set out from Republic Square. At every crossing each of them turns into a random street: all options are equally likely, and the past is not remembered. The cloud spreads over the real streets of central Almaty. Look at how: not in a straight line, not as a wave like Dijkstra’s algorithm, but slowly and ever more slowly. In 10 turns the walkers get on average 270 metres from the square, in 100 a kilometre, in 1000 2.9 kilometres. To get ten times further takes a hundred times as many steps.

On the chart below the distance grows along the dashed line, a line proportional to √t. This is the law of diffusion: it is how a drop of ink spreads in water and how heat spreads. At the end the cloud runs into the edge of the map, and the growth slows even more. And the counter “have been back home” almost immediately rises to 87% and then creeps along: in the plane a walker returns home with probability 1, but the wait can be arbitrarily long. The proof, Pólya’s theorem, is worked through in “Mathematics, the Queen of the Sciences”.

The idea

A random walk on a graph is a sequence of vertices in which each next one is a random neighbour of the current one. A walk has no memory, so equations can be written about it: what happens next depends only on where it is now. These equations give exact answers to three questions (how far, how long, and where first), and walks themselves become algorithms: a cheap step, and nothing to store but the current vertex.

Where a walk spends its time on a long stroll is covered elsewhere: the share of time at a vertex is proportional to its degree (the proof is in “Mathematics, the Queen of the Sciences”), and if random jumps are allowed you get PageRank. Here the questions are different.

A street between two ends

Let us start with the simplest graph, a segment. A street of N blocks, with crossings numbered 0, 1, …, N. A walker stands at crossing k and each time, with probability ½, goes one block right or left, until reaching one of the ends. With what probability does the walk end at the right end, and how many steps will it take?

From the middle of the street to one of the ends takes N²/4 steps, although in a straight line it is N/2 blocks. This is the square root in the law of diffusion: to wander a distance N takes on the order of N² steps, and in t steps a walk gets about √t away. On the streets of Almaty in the listing below the ratio “distance / √t” stays around 100 metres from 30 to 300 steps: 98, 108, 106.

We will also need a variant with a wall: let the street be a dead end at crossing 0, so that from there the walker always comes back to crossing 1. Then the mean time from k to the right end is N² − k². The check is the same: this formula satisfies the equation E_k = 1 + ½E_k−1 + ½E_k+1 inside the segment, the condition at the wall E₀ = 1 + E₁, and the condition E_N = 0, and there are no other solutions: the condition at the wall fixes the first difference D₁ = −1, and after that the differences decrease by 2.

Who gets there first: harmonic functions

The same question “where first” can be asked on any graph. A walker sets out from Republic Square. Which will they reach first: the Green Bazaar or the Botanical Garden? Denote by h(v) the probability of reaching the bazaar first when starting from crossing v.

Functions with the property “at every point, the mean over the neighbours” are called harmonic. They have a physical meaning: if every street is replaced by an identical resistor, 1 volt is applied to the bazaar and the Botanical Garden is earthed, the voltage at each crossing equals h; by Kirchhoff’s law the current into a node equals the current out of it, and that is the same equation. A whole book is devoted to the link between walks and electrical networks: “Random Walks and Electric Networks” by Peter Doyle and Laurie Snell (1984).

The scene finds the harmonic function on 7909 crossings by solving a system of linear equations: h at the bazaar is 1, at the rival 0, and at every other crossing degree × h minus the sum over neighbours is 0. The matrix is symmetric and positive definite, and the conjugate gradient method suits it well: each iteration is one pass over the streets. For Republic Square it comes out at 0.7174: in almost three cases out of four the walker reaches the bazaar first. In a straight line the bazaar is 2.9 kilometres away and the garden 3.3, but what decides is not the distance but how the streets are laid out around each goal. The scene’s walkers check this directly, but slowly: on average each needs more than twenty thousand steps, and the error of an estimate from N walkers decreases only as 1/√N.

Three thousand walkers give 0.7243 instead of 0.7174. To get one more correct digit takes a hundred times as many. That is why, when the graph fits in memory, “who gets there first” probabilities and mean times to a goal are computed from equations rather than by simulation; walks are indispensable where the graph is huge or known only “from inside”, through the neighbours of the current vertex, like the web for a search crawler.

An algorithm: 2-SAT by random flips

A walk on a segment with a wall unexpectedly solves a real algorithmic problem. In 2-SAT we are given Boolean variables and conditions of the form “a or b”, where a and b are variables or their negations; we must find values for which all conditions hold. An example: map labels with two possible places each. “The village label is on the right” is a variable, and for each pair of labels that might collide there is a condition “not both in these positions”. The exact algorithm for 2-SAT looks for the strongly connected components of the implication graph. And in 1991 Christos Papadimitriou proposed a very simple one:

1. start with random values;
2. while there is an unsatisfied condition, take any of them and flip one of its two variables, with a coin deciding which.

The bound is reached almost exactly on the chain “x₀ is true; x_i implies x_i+1”: the only solution is all variables true, there is always exactly one unsatisfied condition, at the “front”, and the front wanders along the chain. In the listing below 20 runs on a chain of 80 variables make 5355 flips on average, with n² = 6400. On real data, the labels of 675 villages and towns from GeoNames, where a letter takes 97 metres, the algorithm needs from 11 to 28 flips, although n² there is 455,625: there are only 44 conditions, and almost all variables are free.

For 3-SAT the same walk is no longer polynomial: the chance of a step towards the solution is only a third. But in 1999 Uwe Schöning showed that short walks of length 3n with restarts from random points find a solution of 3-SAT in (4/3)ⁿ times a polynomial in n on average, noticeably faster than trying all 2ⁿ options.

Code

A walk on a graph is a few lines: lists of neighbours and a random index into a list. The first listing lets 300 walkers out from Republic Square and prints the root-mean-square distance and the share that have been back home.

The second is Papadimitriou’s algorithm. To make each step cost O(1) rather than a pass over all conditions, the unsatisfied conditions are kept in a list with an index “who lies where”: a condition is removed in O(1), with the last one taking its place. After a variable is flipped, only its own conditions are re-examined.

What it costs

A walk covers a whole connected graph of n vertices and m edges in at most 2m(n − 1) steps on average; this was proved in 1979 by Romas Aleliunas, Richard Karp, Richard Lipton, László Lovász and Charles Rackoff. Hence their surprising corollary: to check whether two vertices of an undirected graph are connected, memory for the current vertex number and a step counter is enough, O(log n) bits, if randomness is allowed. Without randomness Omer Reingold obtained the same result only in 2005.

Where it works

• Ranking and recommendations. PageRank is the share of time a wandering reader spends on a page; personalised PageRank and “who to follow” are built from short walks starting from one user.
• Sampling from complex distributions. The Metropolis method is a walk over states arranged so that it spends time in each in proportion to the desired probability; simulated annealing and almost all of computational statistical physics rest on it.
• Satisfiability. The walks of Papadimitriou and Schöning, and in practice their descendants like WalkSAT, which flip not a random variable of a condition but, with some probability, the most profitable one.
• Huge graphs visible only from inside. Search crawlers and social network researchers estimate a graph’s size and properties with walks, because the whole graph cannot be downloaded.
• Physics and chemistry. Diffusion of molecules, heat conduction, Brownian motion are all walks, and the √t law from the first scene is the same one Albert Einstein derived in 1905 for Brownian particles.

History

The phrase “random walk” itself appeared in 1905: in a letter to the journal Nature, Karl Pearson asked how far a person would end up after making n steps of length l, turning in a random direction each time. The answer for large n (Rayleigh immediately pointed out having solved this problem earlier for sound vibrations) is the √n law. In the same year Einstein described Brownian motion. The problem of the two ends of a segment is much older: Pascal and Fermat discussed it in letters in 1656, and a year later Christiaan Huygens included it as the last of five problems in his treatise on reckoning in games of chance; that is how it got its historical name, “gambler’s ruin”. In 1921 George Pólya proved that on a line and in the plane a walk returns home for certain, but in space it does not.

The walk became an algorithm at the end of the 1970s: Aleliunas, Karp, Lipton, Lovász and Rackoff (1979) checked graph connectivity in logarithmic memory, Papadimitriou (1991) solved 2-SAT, and in 1998 Sergey Brin and Larry Page described a search engine that ranked the web by a reader’s walk along links.

Problems

In the first problem a walker wanders the tree of this site’s folders and files, and you need to compute how many steps on average it takes from one file to another; for a tree there is an exact formula. The second is the same segment as in the article, only steps right and left are not equally likely, and the segment is up to a billion long; the trap there is not in the formula but in the arithmetic.