Remix clone Hacker News

A random walk on a graph is a stochastic process that starts at a vertex and, at each step, moves to a randomly chosen neighboring vertex. Formally:

Given a graph, a random walk is a sequence of vertices [v1, v2, ..., vk] such that each v{i+1} is selected uniformly at random from the neighbors of vi.

In weighted graphs, the next vertex is chosen with probability proportional to edge weights.

▲

seanhunter 3 days ago | parent [-]

I’m pretty sure it’s not a requirement that the distribution is uniform and also not path-dependent as per the example I gave - a random walk where you’re not allowed to visit a node more than once.

▲

JohnKemeny 3 days ago | parent [-]

Here's a reference for the definition I'm using:

https://www.cs.yale.edu/homes/spielman/561/lect10-18.pdf

It's from lecture notes (pdf) from a course in Spectral Graph Theory by Professor Daniel Spielman at Yale.

▲

seanhunter 3 days ago | parent [-]

Those notes look interesting thanks. I’ve really never heard of someone saying you have to have uniform probability for a random walk on a graph. In fact the context where I’m most familiar with them (lattice/grid pricers) it’s always specified something like “the probability of branch a is p and b is 1-p” (ie explicitly not uniform) and they aren’t a weighted graph in the normal sense.

▲

srean 3 days ago | parent [-]

It doesn't have to be uniform or memory less.

However, in general when people mention random walks without further qualifications they are usually talking about the uniform and memoryless case.

That vanilla case can be generalized extensively, on kinds of state spaces, kinds of index sets, kinds of dependence and so on.

	▲	seanhunter 3 days ago \| parent [-]
		That makes sense. THanks.